NumberDB$^\beta$ Advanced search Tags Tables Help Login
Growth constants of the classes of trees
edit · history · discussion · files · short url · combinatorics generating function
Numbers
class 
$\gamma$
unlabelled rooted trees:
2.9557652856519949747148175241231945883754923046636
comment: Otter's constant for unlabelled rooted trees [2].
unlabelled free trees:
2.9557652856519949747148175241231945883754923046636
comment: The same growth constant as for unlabelled rooted trees; the counts have the $n^{-5/2}$ subexponential factor [2].
unlabelled planted trees:
2.9557652856519949747148175241231945883754923046636
comment: An unlabelled planted tree is a rooted tree with one extra root vertex, counted as a node; this one-node shift does not change the growth constant.
unlabelled rooted identity trees:
2.5175403526320038907953545984634472773359812668031
comment: Rooted identity trees have trivial automorphism group [4].
unlabelled free identity trees:
2.5175403526320038907953545984634472773359812668031
comment: Free identity trees are asymmetric unlabelled trees [5].
unlabelled planted series-reduced trees:
2.1894619856608505638870275771145449673317087442385
comment: Series-reduced planted trees have no non-root vertex of degree $2$ [7].
unlabelled rooted series-reduced trees:
2.1894619856608505638870275771145449673317087442385
comment: Series-reduced rooted trees have no vertex of degree $2$ [8].
unlabelled free series-reduced trees:
2.1894619856608505638870275771145449673317087442385
comment: Series-reduced free trees have no vertex of degree $2$ [9].
unlabelled rooted trees with outdegree at most 2:
2.4832535361726368585622885181782212891886973408144
comment: Children are unordered and every vertex has outdegree at most $2$ [10].
unlabelled rooted trees with outdegree at most 3:
2.8154600331761507465266167782426995425365065396907
comment: Children are unordered and every vertex has outdegree at most $3$ [12].
unlabelled rooted plane trees:
4
comment: The value is exact: unlabelled rooted plane trees with $n$ nodes are counted by $C_{n-1}$ [14].
unlabelled rooted plane trees with outdegree at most 2:
3
comment: The value is exact: unlabelled rooted plane trees with outdegree at most $2$ are counted by Motzkin numbers shifted by one node [15].
labelled rooted trees:
2.7182818284590452353602874713526624977572470937000
comment: Exactly $e$, by Cayley's formula $n^{n-1}$ [16].
labelled free trees:
2.7182818284590452353602874713526624977572470937000
comment: Exactly $e$, by Cayley's formula $n^{n-2}$ [16].
Definition
For a class of trees, let $T(x)$ be the ordinary generating function counting its unlabelled members by number of nodes, or the exponential generating function counting its labelled members by number of nodes. This table gives the growth constant $\gamma=1/\rho$, where $\rho$ is the radius of convergence of $T(x)$.
Parameters
class
—   tree class (one of the listed tree classes)
Formulas
(1)
If $T(x)$ is the ordinary or exponential generating function specified in the definition and has radius of convergence $\rho$, then $\gamma=1/\rho$. For unlabelled classes this is $\lim_{n\to\infty}t_n^{1/n}$, where $t_n$ is the number of $n$-node members; for labelled classes it is $\lim_{n\to\infty}(t_n/n!)^{1/n}$ with the same convention for $t_n$.
(2)
The ordinary generating function $R(x)$ for unlabelled rooted trees satisfies $R(x)=x\exp\left(\sum_{k\geq1}R(x^k)/k\right)$ [2].
(3)
The labelled rooted and free tree counts are $n^{n-1}$ and $n^{n-2}$, so Stirling's formula gives $\lim_{n\to\infty}(n^{n-1}/n!)^{1/n} =\lim_{n\to\infty}(n^{n-2}/n!)^{1/n}=e$.
(4)
Unlabelled rooted plane trees have $t_n=C_{n-1}$ and $\gamma=4$. The subclass with outdegree at most $2$ has $t_n=M_{n-1}$, where $M_n$ is the $n$th Motzkin number, and $\gamma=3$.
Comments
(5)
The unlabelled rooted, free, and planted classes use Otter's tree constant [2]. Their counts satisfy $t_n\sim c\,\gamma^n n^{-3/2}$ for rooted and planted trees and $t_n\sim c\,\gamma^n n^{-5/2}$ for free trees, with the same $\gamma$ [1].
(6)
An identity tree has trivial automorphism group. The unlabelled rooted identity class is counted by OEIS A004111 [4], and the unlabelled free identity class is counted by OEIS A000220 [5]. They share the growth constant [3].
(7)
For the unlabelled rooted and free classes, series-reduced means that no vertex has degree $2$. The unlabelled planted class is formed by adding a planted root, counted as a node, to a rooted tree with no vertex of outdegree $1$; equivalently, no non-root vertex of the planted tree has degree $2$. The three classes have the same growth constant [6].
(8)
The bounded-outdegree classes are unlabelled rooted trees whose children are unordered. The class with outdegree at most $2$ uses the weakly binary tree constant [10]. The class with outdegree at most $3$ uses the rooted ternary tree constant [12].
(9)
Unlabelled rooted plane trees are rooted ordered trees. They are counted by Catalan numbers shifted by one node [14]; the subclass with outdegree at most $2$ is counted by Motzkin numbers shifted by one node [15].
(10)
For labelled trees, Cayley's formulas $n^{n-1}$ and $n^{n-2}$ for rooted and free labelled trees give the value $e$ in both classes [16].
(11)
Full binary and full $d$-ary tree classes are not included here, because the common conventions for them count leaves or internal nodes rather than all nodes.
Programs
(P1)
Sage
# Otter's constant belongs to the unlabelled rooted, free, and planted classes.
# A quick check uses the recurrence for A000081 and removes the leading
# n^(-3/2) ratio correction.
from sage.arith.misc import divisors
from sage.rings.rational_field import QQ
N = 200
a = [0] * (N + 1)
a[1] = 1
for n in range(2, N + 1):
    total = 0
    for k in range(1, n):
        sigma = sum(d * a[d] for d in divisors(k))
        total += sigma * a[n - k]
    a[n] = total // (n - 1)
float(a[N] / a[N - 1] / (1 - QQ(3) / (2 * N)))
References
[1]
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)
Links
Similar tables
Connective constants of lattices —   the same limit $\lim c_n^{1/n}$, taken over self-avoiding walks of a lattice rather than over a class of trees
Entropy constants of lattice models —   growth constants for lattice models, normalised per site of a finite region rather than per object of the class
Independence polynomials of trees —   polynomials attached to finite trees rather than asymptotic counts of classes of trees
Euler's constant e —   the labelled rooted and labelled free classes both have growth constant exactly $e$
Data properties
Entries are of type: real number
How well the digits are known: heuristic (agreement-checked)
How they were obtained:

The tree-species asymptotic constants used here are tabulated by Harary, Robinson and Schwenk [1]. The two integer entries are exact, and the labelled entries are the exact constant $e$ stored as a real. The other decimal entries are transcribed from the OEIS constant pages cited in the comments.

more

They were independently checked against the defining sequences or radii: A000081 for Otter's constant, A004111 and A000220 for the identity-tree constant, A001678, A001679 and A000014 for the series-reduced constant, A001190 [11] for the weakly binary constant, and A000598 with A261340 [13] for the rooted ternary constant. These checks support the displayed digits but are not interval proofs of every transcribed decimal.

Table is complete: no (it holds the standard rooted, free, planted, identity, series-reduced, bounded-outdegree, rooted plane, rooted plane trees with outdegree at most $2$, and labelled rooted and free tree classes named in the comments, but not every named class of trees or every degree bound)


API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.