Example 3.11 (Counting Leaves in Rooted Plane Trees)

We compute a rational function encoding theleaves in rooted plane trees.
Requirements: None

# The bivariate generating function T(u,z) counting rooted binary trees by leaves (u) and number of vertices (z) and its algebraic equation
var('u,y,z')
T = 1/2*(u - 1)*z - 1/2*sqrt((u^2 - 2*u + 1)*z^2 - 2*(u + 1)*z + 1) + 1/2
P = y^2 + (z-u*z-1)*y + z*u
print("The GF {} satisfies P(u,z,T) = 0 where P = {}".format(T,P))

The GF 1/2*(u - 1)*z - 1/2*sqrt((u^2 - 2*u + 1)*z^2 - 2*(u + 1)*z + 1) + 1/2 satisfies P(u,z,T) = 0 where P = -(u*z - z + 1)*y + y^2 + u*z

# The initial terms of T
T.series(z,5).truncate().expand()

u^3*z^4 + 3*u^2*z^4 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z

# Note T(0,0) = 0. Proposition 3.9 of the textbook applies since
diff(P,y)(0,0,0)

-1

# Thus, T(u,z) as a series extraction
R = (y^2*(diff(P,y)/P).subs(z=z*y)).factor()
show(LatexExpr("[u^kz^n]T(z,u) = [u^kz^ny^n]"),R)

$$\newcommand{\Bold}[1]{\mathbf{#1}}[u^kz^n]T(z,u) = [u^kz^ny^n] \frac{{\left(u y z - y z - 2 \, y + 1\right)} y}{u y z - u z - y z - y + 1}$$

# Verify that the rational function series terms where z and y have the same power give T(u,z)
ser = QQ[u,y,z](taylor(R,(u,0),(y,0),(z,0),20))
print(add([ser[k,n,n]*u^k*z^n for k in range(6) for n in range(6)])) # Rational function coefficients
print(T.series(z,6).truncate().expand()) # Bivariate generating function T

u^4*z^5 + 6*u^3*z^5 + u^3*z^4 + 6*u^2*z^5 + 3*u^2*z^4 + u*z^5 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z
u^4*z^5 + 6*u^3*z^5 + u^3*z^4 + 6*u^2*z^5 + 3*u^2*z^4 + u*z^5 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z