Изменения
→Вычисление производящей функции чисел Каталана
Как известно, рекуррентное соотношение для чисел Каталана имеет вид
<tex>C_0 = 1</tex>
Домножаем <tex>C_n</tex> на <tex>z^0 C_0 = z^0n</tex>, получая
<tex>z^n C_n = z^n \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},</tex> если <tex>n > 0</tex>
z^n \cdot C_n=\begin{cases}z^0 = 1,&\text{если $n = 0$;}\\z^n \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}\end{cases} </tex> Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>, получаем:
<tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n z^n = C_0 z^0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} =
