9
$\begingroup$

Even searching for " 'number of trees' leaves " 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?

$\endgroup$
11
$\begingroup$

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.

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 (Sloane's A001399), (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.

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.

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.

There is also this: K. Yamanaka, Y. Otachi, S.-I. Nakano Efficient Enumeration of Ordered Trees with k Leaves, which I haven't looked at yet.

(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.

(2) P. C. B. Lam, On number of leaves and bandwidth of trees, Acta Math. Appl. Sinica (English Ser.), 14 (1998), pp. 193-196.

(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.

(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.

(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.

(6) Z. Y. Wang, An enumeration problem on ordered trees, J. Math. (Wuhan), 6 (1986), pp. 201-208.

(7) H. C. Wilf, Generatingfunctionology, Academic Press, 1990.

(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

$\endgroup$
8
$\begingroup$

I think this is what you want:

OEIS: the triangle of trees with n nodes and k leaves

(You should draw the sequence as a triangle as below to get the 2-dimensional information.)

                                            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

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 these other displays

$\endgroup$
  • 1
    $\begingroup$ I stumbled over this already, but couldn't make sense of the title: "the TRIANGLE of n nodes and k leaves". And the only reference - Harary's 'Graphical Enumeration' - is almost invisible at books.google.com. Are you sure? $\endgroup$ – Hans-Peter Stricker Apr 16 '10 at 16:59
  • 2
    $\begingroup$ The OEIS is just for (one dimensional) sequences, but this is a two-dimensional function, having two arguments. So they organize it in a triangle. $\endgroup$ – Joel David Hamkins Apr 16 '10 at 17:06
  • 2
    $\begingroup$ I edited it to use a clearer representation of the data. $\endgroup$ – Joel David Hamkins Apr 16 '10 at 17:13
  • 5
    $\begingroup$ To maybe save others some confusion: The top row is n=2, and the leftmost column is k=2. $\endgroup$ – Reid Barton Apr 16 '10 at 18:19
  • $\begingroup$ @Joel: Sorry for not accepting your answer, but I am looking for the "idea" of counting those trees, not for the results only. $\endgroup$ – Hans-Peter Stricker Apr 17 '10 at 2:22
5
$\begingroup$

The number of labelled trees on $n$ vertices with $m$ leaves is $$\binom{n}{m}S(n-2,n-m)(n-m)!$$ where $S(a,b)$ is the Stirling number of the second kind. This can be seen by analysing the multivariate generation which counts trees of any degree sequence given here: https://math.berkeley.edu/~mhaiman/math172-spring10/matrixtree.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.