Изменения

Перейти к: навигация, поиск

Участник:Unreal.eugene

2 байта добавлено, 21 май
м
Свойства блужданий
|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>\dbinom{n}{\frac{n + x}{2}}</tex>.
}}
30
правок

Навигация