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

*Requirements: None*

In [1]:

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

Out[1]:

y^2*z - y + 1

In [2]:

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

Out[2]:

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

In [3]:

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

Out[3]:

-1

In [4]:

```
# 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)
```

In [5]:

```
# 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)
```

In [6]:

```
# 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]

In [0]:

```
```