Изменения
→Вычисление производящей функции чисел Каталана
==Вычисление производящей функции чисел Каталана==
Будем искать производящую функцию в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^n</tex>
Как известно, рекуррентное соотношение для чисел Каталана имеет вид
<tex>C_0 = 1</tex>
<tex>C_n = \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},</tex> если <tex>n > 0</tex>
В рекуррентном соотношении домножаем <tex>C_n</tex> на <tex>z^n</tex>, получая
<tex>z^0 C_0 = z^0</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>
Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex>, получаем:
<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}</tex>
==Смотри также==
