31
правка
Изменения
Нет описания правки
Теорема | id=2
|statement=
Число различных блужданий длины $n$, заканчивающихся в целой координате $x$ (<tex>|x| \leq \lfloor \frac{n}{2} \rfloor</tex>), равно <tex>\binomdbinom{n}{\frac{n + x}{2}}</tex>, если $n$ и $x$ имеют одинаковую четность, и 0 иначе.
|proof=
Чтобы блуждание закончилось в координате $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>\binomdbinom{n}{\frac{n + x}{2}}</tex>.
}}
== Производящие функции ==
{{
<tex>W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}</tex>
}}
{{
Теорема | id=5
|statement=
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
<tex>W_n(t) = \dfrac{(1 - \sqrt{1 - 4t^2})^{n+1}}{2^{n+1}t^{n+2}} = t^n C^{n+1}(t^2)</tex>
|proof=Потом.
}}
{{
Теорема | id=6
|statement=
Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:
<tex>W(u, v) = \dfrac{C(v^2)}{1 - u v C(v^2)}</tex>
|proof=Потом.
}}
