Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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? –  Hans Stricker Apr 16 '10 at 16:59
1  
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. –  Joel David Hamkins Apr 16 '10 at 17:06
1  
I edited it to use a clearer representation of the data. –  Joel David Hamkins Apr 16 '10 at 17:13
2  
To maybe save others some confusion: The top row is n=2, and the leftmost column is k=2. –  Reid Barton Apr 16 '10 at 18:19
    
Thanks, Reid, surely that clears things up a lot. –  Joel David Hamkins Apr 17 '10 at 0:04
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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