Изменения
→Вычисление производящей функции чисел Каталана
<tex dpi = 135> C_n = \frac{4n-2}{n+1} C_{n-1} </tex>.
==Вычисление [[Производящая функция |производящей функции ]] чисел Каталана==
Пусть мы имеем последовательность чисел Каталана <tex>(C_0, C_1, C_2, \ldots)</tex>. Будем искать её производящую функцию в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^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> (так как <tex>C_0 = 1</tex> по определению чисел Каталана). Распишем произведение <tex>G(z) \cdot G(z)</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]]. <tex>G(z) \cdot G(z) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k}</tex>
==Смотри также==
