\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

Section8.5Counting Trees

Our aim is to derive the generating series for the number of trees on \(n\) vertices (or, more precisely, the number of isomorphism classes of tress on \(n\) vertices). We use \(R(x)\) to denote the generating series for rooted trees on \(n\) vertices. We can check that

\[R(x) = x+x^2+2x^2+\ldots\]
The problem is to get further. We do not have an explicit formula for \(R(x)\), just an equation:
\[R(x) = x\exp\left(\sum_{k\ge1}\frac{1}{k}R(x^k)\right).\]
We use the technology from the previous sections to solve this.

We see that \(R(x)\) is a fixed point of a map of the form

\[R = \Phi(R)\]
and we can use this to compute \(R\).

We set up our ring of power series:

If R is a power series \(\sum r_n x^n\), then R.V(i) denotes the series \(\sum r_n x^{ni}\). For example,

So our mapping on series is easy.

You should prove that this procedure produces a sequence of series that converges to the generating series for rooted trees. You will probably find this procedure converges somewhat more quickly than your convergence proof implies.

Next we apply the Newton-Raphson procedure. Here's the code, without explanation :-(

Note that rr = Qx([0,1,1]) is an up-market version of rr = x+x^2. The line rr = Qx(rr.list()) is a hack to force Sage to work with the required degree of precision. Your exercise is to show that the output of this procedure is correct.

If \(T(x)\) is the generating series for trees, then

\[T(x) = R(x) -\frac12(R(x)^2-R(x^2))\]
Hence we can easily get the number of trees from \(R(x)\).