Изменения
→Вычисление производящей функции чисел Каталана
Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex>, получаем:
<tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n z^n = C^0 C_0 z^0 + \sum\limits_{n = 01}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} =C_0 + \sum\limits_{n = 01}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} = 1 + \sum\limits_{n = 01}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}</tex> (так как <tex>C_0 = 1</tex> по определению чисел Каталана). Получили, что <tex> G(z) = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}~~~~~ \textbf{(1)}</tex>
Распишем произведение <tex>G(z) \cdot G(z)</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]].
<tex>G(z) \cdot G(z) = (\sum\limits_{n = 0}^{\infty} C_n z^n) \cdot (\sum\limits_{n = 0}^{\infty} C_n z^n) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k}</tex>
В последнем выражении выполним сдвиг индексации, положив <tex>n' = n + 1</tex>. Тогда имеем: <tex>n = n' - 1, n = 0 \Rightarrow n' = 1</tex>. Кроме того, <tex>z^n = z^{n' - 1}</tex>. <tex>n - k</tex> преобразуется в <tex>n' - 1 - k</tex> (так как <tex>n' - 1 = n</tex>). Тогда, преобразуя предыдущее выражение, получаем:
Преобразуя, получаем квадратное уравнение на <tex>G(z)</tex>
<tex>z \cdot G^2(z) - G(z) + 1 = 0</tex>
Из этого квадратного уравнения находим два варианта <tex>G(z)</tex>
