—   tree class (a specified class of trees with a leading asymptotic of the stated form)

—   size statistic

—   labelling convention

Let $R(x)$, $U(x)$ and $H(x)$ count, by nodes, unordered rooted trees, rooted identity trees, and unordered rooted trees with no node of outdegree $1$, respectively. Their ordinary generating functions satisfy $R=x\exp(\sum_{k\ge1}R(x^k)/k)$, $U=x\exp(\sum_{k\ge1}(-1)^{k+1}U(x^k)/k)$ and $H=\frac{x}{1+x}\exp(\sum_{k\ge1}H(x^k)/k)$ [3] [8].

For any of $A=R,U,H$, write $Q_A(x)=\sum_{k\ge2}\epsilon_k A(x^k)/k$, where $\epsilon_k=(-1)^{k+1}$ for $U$ and $\epsilon_k=1$ for $R,H$. The positive singularity $\rho_A$ satisfies $A(\rho_A)=1$. It solves $\log\rho_A+1+Q_A(\rho_A)=0$ for $R,U$, and $\log\rho_H-\log(1+\rho_H)+1+Q_H(\rho_H)=0$ for $H$. If $A(x)=1-b_A\sqrt{1-x/\rho_A}+O(1-x/\rho_A)$, then $b_A^2=2(1+\rho_A Q_A^{\prime}(\rho_A))$ for $R,U$, and $b_H^2=2((1+\rho_H)^{-1}+\rho_H Q_H^{\prime}(\rho_H))$. Put $c_A=b_A/(2\sqrt\pi)$ [1].

The rooted, free and planted amplitudes are $c_R$, $2\pi c_R^3$ and $\rho_R c_R$, respectively. Rooted and free identity trees have amplitudes $c_U$ and $2\pi c_U^3$. The series-reduced planted, rooted and free amplitudes are $\rho_H c_H$, $c_H$ and $2\pi(1+\rho_H)c_H^3$, respectively.

Let $B_d(x)$ count unordered rooted trees with outdegree at most $d$. With $y=B_d(x)$ and $A_j=B_d(x^j)$, set $\Phi_2=1+y+(y^2+A_2)/2$ and $\Phi_3=1+y+(y^2+A_2)/2+(y^3+3yA_2+2A_3)/6$. Then $F_d(x,y)=x\Phi_d-y=0$. At the positive critical point $(\rho_d,\tau_d)$, $F_d=\partial_y F_d=0$, and the amplitude is $\frac{1}{2\sqrt\pi}\sqrt{2\rho_d\,\partial_xF_d/\partial_y^2F_d}$. The partial derivative in $x$ includes the dependence of $B_d(x^j)$ on $x$ [11] [12].

For rooted plane trees, $t_n=C_{n-1}$ and $c=1/(4\sqrt\pi)$, where $C_m=\binom{2m}{m}/(m+1)$ [13]. For rooted plane trees with outdegree at most $2$, $t_n=M_{n-1}$ and $c=\sqrt3/(2\sqrt\pi)$, where $M_m=\sum_{j=0}^{\lfloor m/2\rfloor}\binom{m}{2j}C_j$ [14]. Stirling's formula applied to Cayley's counts gives $c=1/\sqrt{2\pi}$ for both labelled classes [4].

The amplitude multiplies the bare power $n^{-\alpha}$. The corresponding growth constants $\gamma$ are in Growth constants of the classes of trees. The label distinction specifies which trees are counted; every entry gives the leading amplitude of its specified tree class. Each entry states its exponent $\alpha$.

Unlabelled trees are considered up to isomorphism. Children are unordered except in the plane classes, where their order is part of the tree. A free tree is unrooted. A rooted identity tree has no nonidentity automorphism fixing its root; a free identity tree has no nonidentity automorphism [3].

A planted tree is obtained by adjoining one new root of degree $1$ to a rooted tree. Every node, including this planted root, contributes to $n$. Thus adjoining the planted root multiplies an amplitude by $\rho=1/\gamma$.

Series-reduced rooted and free trees have no node of degree $2$. In a series-reduced planted tree, no node other than the planted root has degree $2$; deleting the planted root leaves a rooted tree with no node of outdegree $1$ [8] [9].

Labelled trees use the fixed label set $\{1,\ldots,n\}$. Cayley's counts are $n^{n-1}$ for rooted trees and $n^{n-2}$ for free trees, with the single-node count taken to be $1$ [4].

Sage

import numberdb.sage as numberdb
from sage.rings.real_arb import RealBallField
B = RealBallField(numberdb.bits(100, losing=64))
# Plane, plane with outdegree at most 2, and either labelled class.
(1 / (4 * B.pi().sqrt()), B(3).sqrt() / (2 * B.pi().sqrt()),
 1 / (2 * B.pi()).sqrt())

F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, Journal of the Australian Mathematical Society 20 (1975), 483–503. (doi)

F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species: corrigenda, Journal of the Australian Mathematical Society 41 (1986), 325. (doi)

A. Genitrini, Full asymptotic expansion for Pólya structures, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (2016). (arXiv)

A. Cayley, A theorem on trees, Quarterly Journal of Pure and Applied Mathematics 23 (1889), 376–378.

OEIS A187770: Otter's rooted-tree amplitude

OEIS A086308: Otter's unrooted-tree amplitude

OEIS A004111: rooted identity trees

OEIS A001678: series-reduced planted trees

OEIS A001679: series-reduced rooted trees

OEIS A000014: series-reduced free trees

OEIS A001190: Wedderburn-Etherington numbers

OEIS A000598: rooted ternary trees

OEIS A000108: Catalan numbers

OEIS A001006: Motzkin numbers

Growth constants of the classes of trees —   the growth constants $\gamma$ for these same fourteen tree classes, with the same node-counting conventions

Entries are of type: real number

How well the digits are known: proven

How they were obtained:

All fourteen entries are 100-significant-digit enclosures computed in Arb ball arithmetic. The five implicit generating functions use exact integer coefficients. The bound $0\le a_n\le C_{n-1}\le4^{n-1}$ controls the omitted coefficient tails and the tails of the sums over $k$; explicit bounds and certified opposite signs at each root interval's endpoints are in the attached generator. Errors in the root intervals are propagated into the amplitudes. The working precision has 160 guard bits, and each series tail targets 35 extra decimal places. The calculation was repeated with 30 extra requested digits.

more

The attached checks independently enumerate tree shapes through 10 nodes, compare published amplitude decimals [5] [6] [7] [8] [9] [10], and check convergence of normalized exact counts at 200, 400 and 800 nodes. The identities are also tested on values read back from the draft. The identity constants use the corrected numerical values [2] and agree with the first 17 fractional digits of the rescaled leading coefficients in [3]. The series-reduced values are obtained from the derivative equation (11) in [1] and agree with the OEIS values; the different numerical amplitudes in the original paper's Table 1 are not used.

Table is complete: no (it holds the fourteen tree classes in the companion growth-constant table, including all nodes in the size of a planted tree; it does not cover every tree class or every outdegree bound)