Изменения

Чтобы блуждание закончилось в координает координате $x$, нужно, чтобы количество движений на +1 было на $x$ больше (на $-x$ меньше) количества движений на -1. Ясно, что это невозможно, если координата $x$ имеет не ту же четность, что и $n$, так как в результате любого блуждания из $n$ шагов координата, в которой мы оказываемся в конце, всегда имеет такую же четность, что и $n$. В случае однаковой четности искомое количество равно количеству битовых векторов длины $n$, в которых ровно <tex>\frac{n + x}{2}</tex> единиц. Понятно, что все такие битовые вектора можно получить следующим способом: выберем <tex>\frac{n + x}{2}</tex> позиций в векторе длины $2n$, на этих позициях расположим значение 1, а на остальных {{---}} значение 0. Из построения ясно, что количество таких способов по определению равно числу сочетаний <tex>\binom{n}{\frac{n + x}{2}}</tex>.}} {{Теорема | id=3|statement=Пусть $w_i$ {{---}} количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула: <tex>w_n = 2 \sum\limits_{i = 0}^{n - 1}{w_i C_{n-i-1}}</tex>, где $C_i$ {{---}} число Каталана. |proof=Доказательство очень похоже на вывод количества путей Дика длины $2n$.  Рассмотрим позицию последнего пересечения путем блуждания нулевой координаты, не равную $2n$. Пусть эта координата равна $2x$, тогда после этого есть два варианта развития: перемещение либо на +1, либо на -1. В обоих случаях путь в следующий раз пересечёт нулевую координату только на $2n$-ое пермещение, поэтому при перемещении из координаты $2x$ далее лежит путь Дика длины $2n - 2x - 2$, не заходящий либо левее координаты 1 (в случае перемещений +1), либо не заходящий правее кординаты -1 (в случае перемещения -1). Количество путей Дика длины $2n - 2x - 2$ равно $C_{n-x-1}$. Так как в каждом пути существует последняя позиция пересечения нулевой координаты, не равная $2n$, то можно рекурсивно посчитать все блуждания следующим образом: <tex>w_n = \sum\limits_{x = 0}^{n - 1}{w_x \cdot 2 C_{n-x-1}} = 2 \sum\limits_{i = 0}^{n - 1}{w_i C_{n-i-1}}</tex>}} {{Теорема | id=4|statement=Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна: <tex>W(t) = \dfrac{1}{\sqrt{1 - 4t}}</tex> |proof=Доказательство через производные можно посмотреть [[Производящая_функция#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87.D0.B8_.D0.BD.D0.B0_.D0.BD.D0.B0.D1.85.D0.BE.D0.B6.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BF.D1.80.D0.BE.D0.B8.D0.B7.D0.B2.D0.BE.D0.B4.D1.8F.D1.89.D0.B5.D0.B9_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|здесь]]. Далее будет приведено доказательство, использующее реккурентное соотношение из предыдущей теоремы. Реккурентному соотношению из предыдущей теоремы соответствует равенство соответствующих формальных рядов: $W(t) = 1 + 2 t W(t) C(t)$, где $C(t)$ {{---}} производящая функция для чисел Каталана.  Таким образом, можно выразить $W(t)$: <tex>W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}</tex>