most recent 30 from http://mathoverflow.net 2013-05-22T09:50:46Z http://mathoverflow.net/feeds/question/21589 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21589/number-of-trees-with-n-nodes-and-m-leaves Hans Stricker 2010-04-16T16:45:24Z 2010-04-21T09:44:05Z

<p>Even searching for " <a href="http://www.research.att.com/~njas/sequences/?q=%2522number+of+trees%2522+leaves&amp;sort=0&amp;fmt=0&amp;language=english&amp;go=Search" rel="nofollow">'number of trees' leaves</a> " didn't reveal what I am looking for: an approach for calculating the (approximate) number of trees with exactly n nodes and m leaves. Any hints from MO?</p>

http://mathoverflow.net/questions/21589/number-of-trees-with-n-nodes-and-m-leaves/21590#21590 Joel David Hamkins 2010-04-16T16:50:35Z 2010-04-16T17:12:41Z

<p>I think this is what you want:</p> <p><a href="http://www.research.att.com/~njas/sequences/A055290" rel="nofollow">OEIS: the triangle of trees with n nodes and k leaves</a></p> <p>(You should draw the sequence as a triangle to get the 2-dimensional information.) </p> <pre> 1 1 0 1 1 0 1 1 1 0 1 2 2 1 0 1 3 4 2 1 0 1 4 8 6 3 1 0 1 5 14 14 9 3 1 0 1 7 23 32 26 12 4 1 0 1 8 36 64 66 39 16 4 1 0 1 10 54 123 158 119 60 20 5 1 0 1 12 78 219 350 325 202 83 25 5 1 0 </pre> <p>Edit: I edited to use a different representation of the data. I assume that the n-th row, k-th entry means the number of trees with n nodes and k leaves. See <a href="http://www.research.att.com/~njas/sequences/table?a=55290&amp;fmt=312" rel="nofollow">these other displays</a></p>

http://mathoverflow.net/questions/21589/number-of-trees-with-n-nodes-and-m-leaves/22035#22035 Douglas S. Stones 2010-04-21T09:44:05Z 2010-04-21T09:44:05Z

<p>The answer to this (very natural) question depends on your notion of "tree" (e.g. free, rooted) and the equivalence relation you employ (e.g. labelled, unlabelled). I haven't gone into the nitty-gritty details of all these results, but here's what I've found so far. There's likely published results I haven't found yet, but hopefully this helps to get you started.</p> <p>We can compute $T_{m,n}$, the number of non-isomorphic free trees with $m$ leaves and $n$ vertices, for small $m$ and large $m$. For example, (a) $T_{3,n}$ is the number of partitions of $n-1$ into $3$ positive integer parts (<a href="http://www.research.att.com/~njas/sequences/A001399" rel="nofollow">Sloane's A001399</a>), (b) $T_{n-2,n}=\lfloor (n-2)/2 \rfloor$ and (c) $T_{n-3,n}=\sum_{j=0}^{n-5} \lfloor (n-3-j)/2 \rfloor$. The first result can be observed by deleting the vertex of degree 3 and the last two can be observed by colouring each non-leaf vertex by the number of adjacent leaves, then deleting the leaves.</p> <p>Yu (8) seems to have given an algorithm for generating rooted trees with $m$ leaves. Wang (6) and Liu (3,4) considered the number of "structurally different" trees with $m$ leaves (according to MathSciNet). Bergeron, Labelle and Leroux (1) consider the expected number of leaves in trees that admit a certain automorphism. Lam (2) discusses embeddings of trees with $m$ leaves and discusses trees with $(d+1)d^{r+1}$ leaves for integers d and r.</p> <p>Wilf (7. p. 163) gave a generating function for $\sum_k T_{k,n}^{\text{lab}}$ where $T_{k,n}^{\text{lab}}$ is the number of labelled free trees with $m$ leaves and $n$ vertices. He also gives a formula for the average number of leaves in a labelled tree with $n$ vertices.</p> <p>There is also this: K. Yamanaka, Y. Otachi, S.-I. Nakano <a href="http://www.springerlink.com/content/u617un0m241wk4h8/" rel="nofollow">Efficient Enumeration of Ordered Trees with k Leaves</a>, which I haven't looked at yet.</p> <p>(1) F. Bergeron, G. Labelle, and P. Leroux, Computation of the expected number of leaves in a tree having a given automorphism, and related topics, Discrete Appl. Math., 34 (1991), pp. 49-66.</p> <p>(2) P. C. B. Lam, On number of leaves and bandwidth of trees, Acta Math. Appl. Sinica (English Ser.), 14 (1998), pp. 193-196.</p> <p>(3) B. L. Liu, The enumeration of directed trees with a given number of leaves and the enumeration of free trees, Kexue Tongbao, 32 (1987), pp. 244-247. In Chinese.</p> <p>(4) B. L. Liu, Enumeration of oriented trees and free trees with a given number of leaves, Kexue Tongbao (English Ed.), 33 (1988), pp. 1577-1581.</p> <p>(5) Q. Q. Nong, The degree sequence and number of leaves in a tree, J. Yunnan Univ. Nat. Sci., 24 (2002), pp. 167-171. In Chinese.</p> <p>(6) Z. Y. Wang, An enumeration problem on ordered trees, J. Math. (Wuhan), 6 (1986), pp. 201-208.</p> <p>(7) H. C. Wilf, Generatingfunctionology, Academic Press, 1990.</p> <p>(8) Q. L. Yu, An algorithm for lexicographically generating ordered rooted trees with constraints on the number of leaves, Chinese J. Oper. Res., 6 (1987), pp. 71-72</p>