x, y, z

Количество траекторий

# 20 Сен 2015 16:51:13
Роман83
Пусть $k \ge 2, m, n -$ заданные натуральные числа, причем $k>|m-n|$. Кузнечик хочет с начала координат точки $(0;0)$ добраться точки $(m;n)$, двигаясь прыжками, каждый из которых либо на $1$ вверх или же на $1$ вправо. Найти количество траекторий кузнечика, которые не имеют общих точек с прямыми $y=x+k$ и $y=x-k$.
# 20 Сен 2015 19:01:58
Evgeniy

Обозначим $0$ - прыжок вправо, $1$ - прыжок вверх. Тогда задача сводится к нахождению количества последовательностей из $m$ нулей и $n$ единиц таких, что на любой префиксной подпоследовательности кол-во нулей меньше кол-ва единиц + $k$ и наоборот.

Несложно было бы просто для прямоугольника, без ограничений с прямыми. Если не ошибаюсь, кол-во последовательностей из $m$ нулей и $n$ единиц равно $$\frac{(m+n)!}{m!n!}$$.
# 20 Сен 2015 19:41:27
Роман83
Да, для прямоугольника - все просто. Тут же - все намного сложней. Может быть тут используются числа Каталана.
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

* Сколько символов на картинке?
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.