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:

QQx.<x> = QQ[[]]; QQx

Power Series Ring in x over Rational Field

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,

R = 5 + 4*x -3*x^3
R.V(4)

5 + 4*x^4 - 3*x^12

So our mapping on series is easy.

Phi = lambda R, n: x*(sum([R.V(i)/i for i in [1..n]]).exp(n+1))
def iter2( init, acc, times):
    val = Phi( init, acc)
    for i in [1..times]:
        acc += 1
        val = Phi( val, acc)
    return val

iter2( x+x^2,2,7)

x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 48*x^7 + 
115*x^8 + 286*x^9 + 719*x^10 + O(x^11)

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 then your convergence proof implies.

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

def nrtrees(n):
    Qx.<x> =QQ[[]]
    rr = Qx([0,1,1])
    lim = 2
    for j in [1..n]:
        ss = x*(sum([rr.V(i)/i for i in [1..2*lim]]).exp(2*lim+1))
        lim = 2*lim+1
        rr = rr +(ss-rr)/(1-ss)
        rr = Qx(rr.list())
    return rr

nrtrees(2)

x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 
48*x^7 + 115*x^8 + 286*x^9 + 719*x^10 + 1842*x^11

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)$.

rr = nrtrees(3)
rr - (1/2)*(rr^2-rr.V(2)).O(14)

x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 
11*x^7 + 23*x^8 + 47*x^9 + 106*x^10 + 
235*x^11 + 551*x^12 + 1301*x^13 + O(x^14)