Editing Tree (graph theory) (section)

==Enumeration==

=== Labeled trees ===
[[Cayley's formula]] states that there are {{math|''n''{{sup|''n''−2}}}} trees on {{mvar|n}} labeled vertices. A classic proof uses [[Prüfer sequence]]s, which naturally show a stronger result: the number of trees with vertices {{math|1, 2, …, ''n''}} of degrees {{math|''d''{{sub|1}}, ''d''{{sub|2}}, …, ''d{{sub|n}}''}} respectively, is the [[Multinomial theorem|multinomial coefficient]]
: <math>{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.</math>

A more general problem is to count [[spanning tree]]s in an [[undirected graph]], which is addressed by the [[matrix tree theorem]]. (Cayley's formula is the special case of spanning trees in a [[complete graph]].) The similar problem of counting all the subtrees regardless of size is [[Sharp-P-complete|#P-complete]] in the general case ({{harvtxt|Jerrum|1994}}).

===Unlabeled trees===
Counting the number of unlabeled free trees is a harder problem. No closed formula for the number {{math|''t''(''n'')}} of trees with {{mvar|n}} vertices [[up to]] [[graph isomorphism]] is known. The first few values of {{math|''t''(''n'')}} are
: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … {{OEIS|A000055}}.
{{harvtxt|Otter|1948}} proved the asymptotic estimate
: <math>t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,</math>
with {{math|''C'' ≈ 0.534949606...}} and {{math|''α'' ≈ 2.95576528565...}} {{OEIS|A051491}}. Here, the {{math|~}} symbol means that 
:<math>\lim_{n \to \infty} \frac{t(n)}{C \alpha^n n^{-5/2} } = 1.</math>
This is a consequence of his asymptotic estimate for the number {{math|''r''(''n'')}} of unlabeled rooted trees with {{mvar|n}} vertices:
: <math>r(n) \sim D\alpha^n n^{-3/2} \quad\text{as } n\to\infty,</math>
with {{math|D ≈ 0.43992401257...}} and the same {{mvar|α}} as above (cf. {{harvtxt|Knuth|1997}}, chap. 2.3.4.4 and {{harvtxt|Flajolet|Sedgewick|2009}}, chap. VII.5, p.&nbsp;475).

The first few values of {{math|''r''(''n'')}} are<ref>See {{harvtxt|Li|1996}}.</ref>
: 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … {{OEIS|A000081}}.