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