A related interesting problem is counting binary set hierarchies: the number of perfect binary trees you can build over the same set of n=2^k leaves, where there is no distinction between left and right children.
In other words, starting with n=2^k elements, put them into disjoint sets of 2 elements. Then group these sets into sets of 2 and continue a total k times until you have a single top-level set. The number of ways you can form such a hierarchy is n! / [ (n/2)! 2^(n/ 2) ] . This problem comes up in broadcast encryption algorithms. On Feb 14, 4:52 pm, Don <dondod...@gmail.com> wrote: > For a binary search tree the solution is called the Catalan Numbers. > The formula is (2n)!/(n!(n+1)!) > > The first few terms are: > 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, > 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, > 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, > 4861946401452, 18367353072152, 69533550916004, 263747951750360, > 1002242216651368, 3814986502092304 > > Don > > On Jan 29, 3:58 am, Moheed Moheed Ahmad <mohe...@gmail.com> wrote: > > > > > > > > > I know how to solve it programatically, can anybody pls help me to solve it > > using combinatorics. > > -Moheed -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
