Количество путей неубывающее блуждание

[R_e_n]

Рассматриваются неубывающие пути на целочисленной решетке$Z_+^2={(i,j):i,j=0,1,2,…}$, которые выходят из точки $(0;0)$ и приходят в точку $(n;n)$, при этом, однако, оставаясь ниже “диагонали” или касаясь ее (т.е. пути, проходящие через точки множества ${(i,j)∈Z_+^2:0\leqslant j\leqslant i\leqslant n}$. Найти число таких путей.


Подскажите, как решить уже второй день туплю.
Можно ввести обозначение: 0 - двигаемся влево, 1 вправо.
Пути которые приходят в точку c координатами $(n, n)$ содержат $n$ единиц и $n$ нулей.
Тогда количество всех путей проходящих через точку $(n, n)$ можно посчитать по формуле
$N_{nxn}=C_{2n}^{n} \cdot C_{n}^{n}$
Аналогично можно посчитать для любой другой точки.
Дальше я решил действовать следующим образом:
$N_{nxn}=N_<+N_>+N_{\bigcap}$
Где $N_<$ - количество путей которые ниже диагонали
$N_>$ - количество путей которые выше диагонали
$N_{\bigcap}$ - - количество путей которые хоть раз пересекают диагональ

Понятно, что $N_< = N_>$
Дальше хотел поделить $N_{\bigcap}$ на две: которые не пересекли и пошли влево (отразились от диагонали)
и которые пересекли. но тут ничего хорошего не смог. Думается, как то можно по принципу включений и исключений действовать, но никак не получается.

Научился считать количество путей, проходящих через k точек на диагонали, но все равно не знаю как посчитать тех, что отразились, и тех, что пересекли.

[Urnwestek]

Я, может быть, неправильно понял задачу, но разве тут не очевидные числа Каталана?

[R_e_n]

Спасибо, огромное, нагуглил: в качестве примера чисел Каталана как раз эта задача приводится. Сейчас попробую понять почему именно они. А вообще про числа Каталана я не знал

[Urnwestek]

R_e_n
Шаг вправо — открывающая скобка, шаг вверх — закрывающая скобка. А вот комбинаторного доказательства формулы $C_n = \frac{1}{n+1} C_{2n}^n$ я не знаю, но знаю, что оно есть и оно довольно нетривиальное (оттого и не смотрю, надеюсь додуматься сам). Проще всего эту формулу доказать производящими функциями, но это не так красиво.

[hippie]

Любой «плохой» путь проходит через некоторую точку вида $(j,\ j+1).$

Отразите участок пути от точки $(0,\ 0)$ до первой такой точки. Количество «плохих» путей равно количеству «отражённых».

[R_e_n]

hippie в сообщении #772003 писал(а):

Любой «плохой» путь проходит через некоторую точку вида $(j,\ j+1).$

Отразите участок пути от точки $(0,\ 0)$ до первой такой точки. Количество «плохих» путей равно количеству «отражённых».

А что делать с плохими путями, которые два и больше раз пересекают диагональ? Я так и не смог придумать способа их все посчитать.

[hippie]

Не имеет значения, сколько раз «плохой» путь пересекает диагональ! «Отражённый» путь строится по ПЕРВОМУ пересечению. А количество «отражённых» путей легко считается!

[R_e_n]

hippie в сообщении #772027 писал(а):

Не имеет значения, сколько раз «плохой» путь пересекает диагональ! «Отражённый» путь строится по ПЕРВОМУ пересечению. А количество «отражённых» путей легко считается!

А как узнать что путь первый раз пересекает точку $(j,j+1)$? Я правильно начал мыслить?

Количество путей проходящих через точку $(0,1)$ и попадающих в точку $(n,n)$ половина от всех путей попадающих в точку $(n,n)$, т. е. $ \frac{C_{2n}^n}2$
Количество путей проходящих через точку $(1,2)$, но при этом не проходящими через точку $(0,1)$
$ C_{2n-3}^{n-2}$ так как все они начинаются вот так {0,1,1,...}
Количество путей проходящих через точку $(2,3)$, но при этом не проходящими через точки $(0,1)$
и $(1,2)$
$ 2 \cdot C_{2n-5}^{n-3}$ так как могут начинаться вот так {0,0,1,1,1,...} или {0,1,0,1,1,..}

[hippie]

Только что перечитал своё первое сообщение . При копировании (из WORD-документа, в котором я набирал текст, в сообщение) исчезли ключевые слова, а я этого сразу не заметил.

Исправленная версия:

Любой «плохой» путь проходит через некоторую точку вида $(j,\ j+1).$

Отразите участок пути от точки $(0,\ 0)$ до первой такой точки относительно прямой $\bold{(x,\ x+1).}$ Количество «плохих» путей равно количеству «отражённых».