Example 3.10 (The Catalan Generating Function as a Rational Diagonal)

Expressing the Catalan generating function as the main diagonal of a rational function.
Requirements: None

# The Catalan generating function satisfies C(0) = 1 and is a root of
var('y,z')
P1 = z*y^2-y+1
P1

y^2*z - y + 1

# The function K(z) = C(z) - 1 satisfies
P2 = P1(y+1,z)
P2.collect(y)

y^2*z + y*(2*z - 1) + z

# Proposition 3.8 of the textbook applies to K, since
diff(P2,y)(0,0)

-1

# Thus, we can express K(z) as a rational diagonal
R1 = (y^2*(diff(P2,y)/P2).subs(z=z*y)).factor()
show(LatexExpr("K(x) = \\Delta"),R1)

$$\newcommand{\Bold}[1]{\mathbf{#1}}K(x) = \Delta \frac{{\left(2 \, y^{2} z + 2 \, y z - 1\right)} y}{y^{2} z + 2 \, y z + z - 1}$$

# Since, C(z) = 1 + K(z), we have the Catalan GF as a rational diagonal
R2 = (R1+1).factor()
show(LatexExpr("C(x) = \\Delta"),R2)

$$\newcommand{\Bold}[1]{\mathbf{#1}}C(x) = \Delta \frac{{\left(2 \, y^{2} z + y z + z - 1\right)} {\left(y + 1\right)}}{y^{2} z + 2 \, y z + z - 1}$$

# Check that the initial diagonal terms of R2 match the initial Catalan numbers
ser = QQ[y,z](taylor(R2,(y,0),(z,0),20))
print([ser[k,k] for k in range(10)]) # Diagonal sequence of R2

GF = (1-sqrt(1-4*z))/2/z
print([k for (k,j) in GF.series(z,10).coefficients()]) # Series coefficients of Catalan GF

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]