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?
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 nittygritty 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 nonisomorphic 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 $n1$ into $3$ positive integer parts (Sloane's A001399), (b) $T_{n2,n}=\lfloor (n2)/2 \rfloor$ and (c) $T_{n3,n}=\sum_{j=0}^{n5} \lfloor (n3j)/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 nonleaf 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. 4966. (2) P. C. B. Lam, On number of leaves and bandwidth of trees, Acta Math. Appl. Sinica (English Ser.), 14 (1998), pp. 193196. (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. 244247. 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. 15771581. (5) Q. Q. Nong, The degree sequence and number of leaves in a tree, J. Yunnan Univ. Nat. Sci., 24 (2002), pp. 167171. In Chinese. (6) Z. Y. Wang, An enumeration problem on ordered trees, J. Math. (Wuhan), 6 (1986), pp. 201208. (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. 7172 


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 2dimensional 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 nth row, kth entry means the number of trees with n nodes and k leaves. See these other displays 

