Изменения
→Вычисление производящей функции чисел Каталана
==Вычисление [[Производящая функция |производящей функции]] чисел Каталана==
{{Лемма
|id=lemma1.
|statement=<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \cdot \dbinom{2k}{k} </tex>
|proof=
<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{\dfrac{1}{2} \cdot (\dfrac{1}{2} - 1) \cdot (\dfrac{1}{2} - 2) \cdots (\dfrac{1}{2} - k + 1)}{k!} =
\dfrac{1 \cdot (1 - 2) \cdot (1 - 4) \cdots (1 - 2k + 2)}{2^k \cdot k!} = \dfrac{1 \cdot (-1) \cdot (-3) \cdots (-2k + 3)}{2^k \cdot k!}</tex>
<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 3 \cdot (2k - 3) \cdot (2k - 1)}{2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 2 \cdot 3 \cdots (2k - 3) \cdot (2k - 2) \cdot (2k - 1) \cdot 2k}{2 \cdot 4 \cdots (2k - 2) \cdot 2k \cdot 2^k \cdot k!}</tex>
<tex>= \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{(2 \cdot 1) \cdot (2 \cdot 2) \cdots (2 \cdot (2k - 1)) \cdot (2 \cdot k) \cdot 2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot (1 \cdot 2 \cdots (k - 1) \cdot k) \cdot 2^k\cdot k!} </tex>
<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot k! \cdot 2^k\cdot k!} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 2^k \cdot 2^k} \cdot \dfrac{(2k)!}{k! \cdot k!}= \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \dbinom{2k}{k}</tex>
}}
{{Задача
|definition = Вычислить производящую функцию чисел Каталана
}}
Пусть мы имеем последовательность чисел Каталана <tex>(C_0, C_1, C_2, \ldots)</tex>.
Как известно, рекуррентное соотношение для чисел Каталана имеет вид
<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} =
Домножая это произведение на <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}</tex> Тогда <tex>z \cdot G^2(z) = \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>
Преобразуя, получаем квадратное уравнение на <tex>G(z):</tex>
<tex>z \cdot G^2(z) - G(z) + 1 = 0</tex>
Из этого квадратного уравнения находим два варианта <tex>G(z):</tex>
<tex>G(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}</tex>
Выберем из двух корней тот, который удовлетворяет определению <tex>G(z)</tex> как производящей функции чисел Каталана.
Домножая обе части на <tex>2z</tex>, получаем <tex>G(z) \cdot 2z = 1 \pm \sqrt{1-4z} ~~~~~\textbf{(3)}</tex>
Выберем нужный из двух корней, посчитав значение обеих частей при <tex>z = 0</tex>
Тогда <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex>
Проверим, что <tex>G(z)</tex> действительно является производящей функцией чисел Каталана. Для этого разложим <tex>G(z)</tex> в ряд.
<tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{\sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sqrt{1 - 4z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot (1 - 4z)^{\frac{1}{2}} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dbinom{\frac{1}{2}}{n})</tex>
<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dfrac{(-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^n \cdot 4^n \cdot z^n \cdot (-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^{2n - 1} \cdot 4^n \cdot z^n}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n})</tex>
<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-z^0}{2 \cdot 0 - 1} \cdot \dbinom{2 \cdot 0}{0} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>
<tex>= \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-1}{-1} \cdot 1- \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>
<tex> = \sum\limits_{n = 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n + 2)!}{(n + 1)! \cdot (n + 1)!}</tex>
<tex> = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n)! \cdot (2n + 1) \cdot 2 \cdot (n + 1)}{(n)! \cdot (n)! \cdot (n + 1) \cdot (n + 1)}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(4n + 2)}{n + 1} \cdot \dbinom{2n}{n})</tex>
<tex>= \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (z^n \cdot \dfrac{1}{n + 1} \cdot \dbinom{2n}{n})</tex>
Тогда коэффициент при <tex>z^n</tex> в разложении <tex>G(z)</tex> равен <tex>\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>, что совпадает с аналитической формулой для чисел Каталана. (<tex>C_n = \dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>) Поэтому <tex>G(z) = \sum\limits_{n = 0}^{\infty} z^n \cdot C_n</tex>, поэтому <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex> является производящей функцией чисел Каталана.
==Смотри также==
