most recent 30 from http://mathoverflow.net 2013-05-26T00:58:47Z http://mathoverflow.net/feeds/question/16403 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16403/count-of-full-binary-trees-with-fixed-number-of-leaves Mouk 2010-02-25T15:23:20Z 2010-02-25T15:39:38Z

<p>How many ways is there to build an arithmetic expression with fixed number of terms and fixed order? Let’s assume we have only one distinct operation that is neither commutative nor associative. The problem can be reduced to the question of how many different, full, binary trees could be constructed with a fixed number of leaves.</p> <p>Suppose we have a list of n elements which have to become leaves in a full, binary tree. The root could be chosen between each two sequential numbers. Thus, there is (n-1) different ways to choose the root. If the root is located after the i-th number, we can still construct the left child as a binary tree with i leaves and the right one with (n – i) leaves.</p> <p>The formula for the number of different ways to construct a full, binary tree is</p> <p><code>$ \Phi(n) = \sum^{n-1}_{i=1}\Phi(i).\Phi(n-i)$</code></p> <p>The first value for n=1 ist set to:</p> <p><code>$ \Phi(1) = 1 $</code></p> <p>Is there a closed formula for this function? Is it - maybe - a popular problem in the Graph Theory with known solutions?</p>

http://mathoverflow.net/questions/16403/count-of-full-binary-trees-with-fixed-number-of-leaves/16405#16405 Dan Petersen 2010-02-25T15:33:56Z 2010-02-25T15:33:56Z

<p>There is a general algorithm that solves this kind of problem.</p> <ol> <li>Calculate the first terms of your sequence by hand.</li> <li>Plug them into Sloane's and see if it is a known sequence.</li> </ol> <p><a href="http://www.research.att.com/~njas/sequences/?q=1%2C1%2C2%2C5%2C14&amp;sort=0&amp;fmt=0&amp;language=english&amp;go=Search" rel="nofollow">http://www.research.att.com/~njas/sequences/?q=1%2C1%2C2%2C5%2C14&amp;sort=0&amp;fmt=0&amp;language=english&amp;go=Search</a></p> <p>Here you see that your numbers are called Catalan numbers; they are extremely well-studied.</p>

http://mathoverflow.net/questions/16403/count-of-full-binary-trees-with-fixed-number-of-leaves/16407#16407 Marty 2010-02-25T15:39:38Z 2010-02-25T15:39:38Z

<p>This is a very well-known enumeration problem. The number of full binary rooted trees with $n+1$ leaves is just the $n$-th Catalan number $$C_n = \frac{(2n)!}{(n+1)!n!}.$$ </p> <p>You can read more by looking at Wikipedia's entry on Catalan numbers, for example. </p>