1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Файл:Каталан2.PNG|right]]
Такой путь обязательно пересекает прямую <tex dpi = 120> y = x </tex>. Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> и пусть <tex dpi = 120> A </tex> — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(-1, 0)</tex> до точки <tex dpi = 120>A</tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex>. Следовательно, неправильных путей из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex> столько же, сколько путей из точки <tex dpi = 120>(-1, 0)</tex> в
точку <tex dpi = 120>(n, n-1)</tex>. Такой путь длины <tex dpi = 120>2n</tex> содержит <tex dpi = 120>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \dbinom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно
<tex> C_n = \dbinom {2n} {n} - \dbinom {2n} {n-1} = \dfrac{2n!}{n!n!} - \dfrac{2n!}{(n-1)!(n+1)!} = \dfrac{2n!}{n!} (\dfrac{1}{n!} - \dfrac{1}{(n-1)! (n+1)}) = \dfrac{2n!}{n!n!(n+1)} = \dfrac{1}{n+1} \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> является производящей функцией чисел Каталана.
==Смотри также==
