Chapter 3 Catalan and generating functions
Definition 3.1 Let \[ \mathcal{C}(x)=\sum_{n\geq 0}c_n x^n=1+x+2x^2+5x^3+\dots \] denote the generating function of the Catalan numbers.
We can first deduce the recursive formula of the Catalan numbers \[ \mathcal{C}(x)=1+x\mathcal{C}(x)^2. \]
We use the ordinary generating function for the Catalan numbers, we have \[ \mathcal{C}(x)=\sum_{n\ge 0}c_nx^n=\sum_{n\ge 0}\sum_{k=0}^{n-1}c_kc_{n-1-k}x^n \] Since we know \(C_{0} = 1\) , we have \[ \begin{aligned} \mathcal{C}(x)&=\sum_{n\ge 0}\sum_{k=0}^{n-1}c_kc_{n-1-k}x^n\\ &=1+\sum_{n\ge 1}\sum_{k=0}^{n-1}c_kc_{n-1-k}x^n\\ &=1+x\sum_{n\ge 0}\sum_{k=0}^nc_kc_{n-k}x^n\\ &=1+x\left(\sum_{n\ge 0}c_nx^n\right)^2\\ &=1+x\mathcal{C}(x)^2 \end{aligned} \] Therefore, we got \[ \mathcal{C}(x)=1+x\mathcal{C}(x)^2 \]
Use the recursive formula (\(\star\)) to prove that \(\mathcal{C}(x)\) is a solution of the following equation of degree two:
\[
\mathcal{C}(x)=1+x\mathcal{C}(x)^2.
\]
From the equation \(\mathcal{C}(x)=1+x\mathcal{C}(x)^2\) we have \[ \mathcal{C}(x)=1+x\mathcal{C}(x)^2 \Rightarrow \frac{\mathcal{C}(x)-1}{x}=\mathcal{C}(x)^2 \] Then we try to prove the LHS equal to RHS.
For LHS we have \[ \begin{aligned} \frac{\mathcal{C}(x)-1}{x} &= \frac{\sum_{n\geq 1}c_n x^n}{x}\\ & = {\sum_{n\geq 0}c_{n+1} x^{n}} \end{aligned} \]
For RHS, we apply we got \[ \begin{aligned} \mathcal{C}(x)^{2} &= (\sum_{n\geq 0}c_n x^n) ^{2}\\ &= \mathcal\sum_{n\geq 0}(\sum_{k=0}^{n} c_{k}c_{n-k}) x^{n} \\ &= \mathcal\sum_{n\geq 0} c_{n+1} x^n \quad (\text{By Definition}) \end{aligned} \]
Therefore we have \[ \mathcal{C}(x)^{2} = \mathcal\sum_{n\geq 0} c_{n+1} x^n = \frac{\mathcal{C}(x)-1}{x} \] Then we prove that \(\mathcal{C}(x)\) is a solution for the equation of \[ \mathcal{C}(x)=1+x\mathcal{C}(x)^2 \]
Deduce a formula for \(\mathcal{C}(x)\) and the radius of convergence.
Here we have the computation code in python
x = Symbol('x')
c = Symbol('c')
solution = solve(c - 1 - x * c**2, c)
# display the solution in latex
print("--------- Question 4.2 ----------")
print("The solution of the equation in is ")
display(solution[0]), display(solution[1])
print("The solution of the equation in Latex is ", (latex(solution[0])),
latex(solution[1]))We use sympy to solve the equation \(\mathcal{C}(x)=1+x\mathcal{C}(x)^2\) and we get
\[
\mathcal{C}_{1}(x)= \frac{1 - \sqrt{1 - 4 x}}{2 x} \quad \text{and} \quad \mathcal{C}_{2}(x)= \frac{1 + \sqrt{1 - 4 x}}{2 x}
\]
From the two possibilities, the \(\mathcal{C}_{1}(x)\) must be chosen because only the choice of the first gives
\[
C_0=\lim _{x \rightarrow 0} \mathcal{C}_{1}(x)=1
\]
Therefore we have \(\mathcal{C}(x)=\frac{1 - \sqrt{1 - 4 x}}{2 x}\)
Then we compute the radius of convergence of \(\mathcal{C}(x)\). For the definition of radius of convergence from Wiki page. We use the expression of \(\mathcal{C}(x)\) in power series that \[ \mathcal{C}(x)= \frac{1 - \sqrt{1 - 4 x}}{2 x}= \sum_{n\geq 0}c_n x^n \] Base on [D’Alembert’s test], for radius of convergence \(R\) we compute \(\lim _{n \rightarrow \infty}\left|\frac{c_{n+1}}{c_n}\right|=\rho\) for \(\sum_{n\geq 0}c_n x^n\) \[ \begin{aligned} \rho &= \lim_{n \rightarrow \infty}|\frac{c_{n+1}}{c_n}|\\ &= \lim_{n \rightarrow \infty} \left| \frac{\frac{1}{n+2} \binom{2n+2}{n+2}}{\frac{1}{n+1} \binom{2n}{n}} \right|\\ &= \lim_{n \rightarrow \infty} \left|\frac{4n+4}{n+2} \right|\\ &= \lim_{n \rightarrow \infty} \left|4-\frac{4}{n+2} \right|\\ &= 4 \end{aligned} \] Since \(\rho \neq 0\), then we have the radius of convergence \(R=\frac{1}{\rho}=\frac{1}{4}\)
Compare the efficiency of different approaches.
knitr::include_graphics('static/pic3.png')
knitr::include_graphics('static/pic4.png')
From the two graph we can see that the formula of \(\mathcal{c}_{n}=\frac{1}{n+1}\binom{2n}{n}\) has the highest computation efficiency. However, the non-recursive method has more execution time than the method above, compare with recursive method the complexity is still much better since the execution time is in the level of \(10^{-5}sec\).
We can prove the expression of \[ c_{n}=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!n!} \] with \(\mathcal{C}(x)= \frac{1 - \sqrt{1 - 4 x}}{2 x}= \sum_{n\geq 0}c_n x^n\)
For power series we have \[ \sqrt{1+y}=\sum_{n=0}^{\infty}\left(\begin{array}{c} \frac{1}{2} \\ n \end{array}\right) y^n=\sum_{n=0}^{\infty} \frac{(-1)^{n+1}}{4^n(2 n-1)}\left(\begin{array}{c} 2 n \\ n \end{array}\right) y^n \] We denote that \(y=-4x\) we got \[ \sqrt{1-4 x}=1-\sum_{n=1}^{\infty} \frac{1}{2 n-1}\left(\begin{array}{c} 2 n \\ n \end{array}\right) x^n \] Therefore we got \[ \mathcal{C}(x)= \frac{1 - \sqrt{1 - 4 x}}{2 x} = \sum_{n=1}^{\infty} \frac{1}{2(2 n-1)}\left(\begin{array}{c} 2 n \\ n \end{array}\right) x^{n-1} = \sum_{n\geq 0}c_n x^n \] We can deduce that \[ c_{n}=\frac{1}{2(2n+1)} \binom{2n+2}{n+1}=\frac{1}{n+1} \binom{2n}{n} \]
3.1 Manipulate Generating Functions with SymPy
Definition 3.2 We work out with the example of \[ f(x)=\frac{1}{1-2x}=1+2x+4x^2+8x^3+16x^4+ \dots \] We first introduce variable \(x\) and function \(f\) as follows:
x=var('x')
f=(1/(1-2*x))
print('f = '+str(f))
print('series expansion of f at 0 and of order 10 is: '+str(f.series(x,0,10)))
display(f.series(x,0,10))\[ 1+2 x+4 x^2+8 x^3+16 x^4+32 x^5+64 x^6+128 x^7+256 x^8+512 x^9+O\left(x^{10}\right) \]
One can extract coefficient \(n\) as follows:
- \(f\) has to be truncated at order \(k\) (for some \(k>n\)) with f.series(x,0,k)
- the \(n\)-th coefficient is then extracted by f.coeff(x**n)
f_truncated = f.series(x,0,8)
print('Truncation of f is '+str(f_truncated))
n=6
nthcoefficient=f_truncated.coeff(x**n)
print(str(n)+'th coefficient is: '+str(nthcoefficient))
display(f_truncated)\[ 1+2 x+4 x^2+8 x^3+16 x^4+32 x^5+64 x^6+128 x^7+O\left(x^{8}\right) \]
Use SymPy to write another programm which computes the Catalan numbers using \(\mathcal{C}(x)\), and compare the execution times with the functions of the first part of the Project.
# We compute C(x) with Taylor Expansion
x = var('x')
f = (1 - sqrt(1 - 4 * x)) / (2 * x)
def CatalanTaylorExpansion(n):
return f.series(x, 0, n).coeff(x**(n - 1))
lis = [CatalanTaylorExpansion(i) for i in range(11)]
lis[1] = 1
print("The first ten Catalan numbers with Taylor Expansion are ", lis[1:])
The first ten Catalan numbers with Taylor Expansion are [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]knitr::include_graphics('static/pic5.png')
knitr::include_graphics('static/pic6.png')
From the two graph we can see that the Taylor Expansion method is much faster than the recursive method but much slower than the method non-recursive and Binomial Formula.
3.2 Motzkin Numbers
Definition 3.3 The Motzkin numbers \(m_0,m_1,m_2,\dots\) are similar to Catalan numbers and defined by \(m_0=m_1=1\) and for every \(n\geq 2\) \[ m_n=m_{n-1}+\sum_{k=0}^{n-2}m_km_{n-2-k}. \]
- Find the generating function \(\mathcal{M}(x)=\sum_{n\geq 0}m_nx^n\).
- Compute the radius of convergence of \(\mathcal{C}\) and \(\mathcal{M}\). Compare with numerical experiments: which sequence is growing fastest between \((c_n)\) and \((m_n)\)?
We first try to simplify the motzkin numbers recurrence relation. We have \[ \mathcal{M}(x)=\sum_{n\geq 0}m_nx^n = \sum_{n \geq 0}(m_{n-1}+\sum^{n-2}_{k=0}m_{k}m_{n-2-k})x^{n} \] Since we have \(\mathcal{M}_0 = \mathcal{M}_1 = 1\), therefore we have \[ \begin{aligned} \mathcal{M}(x) &= \sum_{n \geq 0}(m_{n-1}+\sum^{n-2}_{k=0}m_{k}m_{n-2-k})x^{n}\\ &= x \sum_{n \geq 0}m_{n-1} x^{n-1} + \sum_{n \geq 0} \sum^{n-2}_{k=0}m_{k}m_{n-2-k} x^{n}\\ &= x \mathcal{M}(x) + 1 + \sum_{n \geq 2} \sum^{n-2}_{k=0}m_{k}m_{n-2-k} x^{n} \\ &= x \mathcal{M}(x) + 1 + x^{2}\sum_{n \geq 0} \sum^{n}_{k=0}m_{k}m_{n-k}x^{n}\\ &= x \mathcal{M}(x) + 1 + x^{2} (\sum_{n \geq 0} m_{n}x^{n})^{2}\\ &= x \mathcal{M}(x) + 1 + x^{2} \mathcal{M(x)} \end{aligned} \]
Therefore, we know that \(\mathcal{M}(x)=\sum_{n\geq 0}m_nx^n\) is a root for \(x^2 M^2 + (x-1)M + 1 =0\).
x = symbols('x')
M = symbols('M')
SeriesM = solve(x**2 * M**2 + x * M - M + 1, M)
print(SeriesM)
display(SeriesM[0])
display(SeriesM[1])We use sympy to solve the equation we have
\[
\mathcal{M}_{1}(x)= \frac{1 -x - \sqrt{1 - 2 x-3x^2}}{2 x^2} \quad \mathcal{M}_{2}(x)= \frac{1 -x + \sqrt{1 - 2 x-3x^2}}{2 x^2}
\]
Since we know \(\mathcal{M}(0)=1\), therefore the only possible solution is
\[
\mathcal{M}(x)= \frac{1 -x - \sqrt{1 - 2 x-3x^2}}{2 x^2}
\]
# Implementation of the formula of Motzkin Numbers
def MotzkinFormula(n):
x = symbols('x')
m= (1-x-sqrt(1-2*x-3*x**2))/(2*x**2)
m_truncated = m.series(x,0,n+1)
return m_truncated.coeff(x**n)
print("--------- Question 4.1.1.1 ----------")
lis = [MotzkinFormula(i) for i in range(11)]
lis[0] = 1
print("The first ten Motzkin numbers with Taylor Expansion are ", lis[1:])
--------- Question 4.1.1.1 ----------
The first ten Motzkin numbers with Taylor Expansion are [1, 2, 4, 9, 21, 51, 127, 323, 835, 2188]An integral representation of Motzkin numbers is given by \[ m_n=\frac{2}{\pi} \int_0^\pi \sin (x)^2(2 \cos (x)+1)^n d x . \] They have the asymptotic behaviour \[ m_n \sim \frac{1}{2 \sqrt{\pi}}\left(\frac{3}{n}\right)^{3 / 2} 3^n, n \rightarrow \infty \] Therefore, they have the same radius of convergence. We apply the similar method as Catalan number. Base on [D’Alembert’s test], for radius of convergence \(R\) we compute \(\lim _{n \rightarrow \infty}\left|\frac{m_{n+1}}{m_n}\right|=\rho\) for \(\sum_{n\geq 0}m_n x^n\) \[ \begin{aligned} \rho &= \lim_{n \rightarrow \infty}|\frac{m_{n+1}}{m_n}|\\ &= \lim_{n \rightarrow \infty} \left| \frac{(\frac{3}{n+1})^{\frac{3}{2}}3^{n+1}}{(\frac{3}{n})^{\frac{3}{2}}3^{n}} \right|\\ &= \lim_{n \rightarrow \infty} \left| 3(\frac{n}{n+1})^{3/2} \right|\\ &= 3 \end{aligned} \] Since \(\rho \neq 0\), then we have the radius of convergence \(R=\frac{1}{\rho}=\frac{1}{3}\).
Or we can illustrate in this way, from the definition of radius of convergence, we need to find an \(R\) such that when \(\|x\|<R\) the series converges. Then we observe that radius shows when \(1-2R-3R^2 = 0\). Then we got \(R=\frac{1}{3}\) or \(r=-1\). Since when \(x<1\), the function diverges, we can also get \(R=\frac{1}{3}\)
Then we can say the radius of convergence of \(\mathcal{C}\) is smaller than \(\mathcal{M}\). Therefore the sequence of \(c_n\) is growing faster than \(m_n\). We can also show this in the graph.
# plot the Catalan numbers and Motzkin numbers in the same graph
N = [i for i in range(1, 16)]
plt.figure(figsize=(10, 7))
lis_catalan = [CatalanNonRecursive(i) for i in range(1, 16)]
lis_motzkin = [MotzkinFormula(i) for i in range(1, 16)]
plt.plot(N, lis_catalan, 'o-', label='Catalan Numbers')
plt.plot(N, lis_motzkin, 'o-', label='Motzkin Numbers')
plt.legend()
plt.title("Catalan Numbers and Motzkin Numbers")
plt.xlabel("N")
plt.ylabel("Numbers")
plt.show()knitr::include_graphics('static/pic7.png')