Комбинторика. Кол-во путей из (0,0) в (n,n) с ограничениями

[C0rWin]

Как подсчитать кол-во путей из точки $(0,0)$ в точку $(n,n)$ которые не проходят ни через одну точку вида $(k,k-1)$.

[Руст]

Определите вначале, что означает "путь". По видимому, речь идёт о последовательности целочисленных координат на плоскости. Остаётся выяснить, как связаны соседние точки. Они могут отличаться на (a,b), где a, b =0,+-1 или (направленные) (a,b)=(0,1) или (1,0) возможно ещё (1,1). В зависимости от этого, существенно отличается количество путей.

[C0rWin]

Извиняюсь, на самом деле забыл уточнить, возможное передвижение только на ($i+1$, $j$) или ($i$, $j+1$).

[Руст]

Количество путей просчитывается (имеется формула через биномиальный коэффициент). Я это проделывал, кажется в этом форуме. Попробуйте найти в старых постах.

[RIP]

По-моему, это числа Каталана в чистом виде. Вместо шага $(i,j+1)$ ставим левую скобку, вместо $(i+1,j)$ правую скобку. Задача сводится к подсчету "правильных" комбинаций из $n$ пар скобок, а это и есть числа Каталана. Можно посчитать через производящие функции.

[C0rWin]

Это чем-то напоминает числа Каталана, но решение тековым не является, так как я не обязан начинать свой путь с открывающей скобки и тем более не обяза сохранять орфографию правильного скобочного выражения. Для чисел Каталана характерна задача подобного вида, только вопрос заключается в том, что бы посчитать кол-во путей так, что бы не опускаться ниже главной диагонали. Тут задача заключается в том, чтобы посчитать кол-во путей в которых не выполняется два шага подряд влево, а это не много другое. Ответ мне изветен, мне не совсем понятно как он получается. Если кто-то сможет объяснить, я буду очень признателен. Ответ $C(2n,n)$-$C(2n,n-2).

[Руст]

Ваш ответ не верен (уже при n=1, ваш ответ дает 2 вместе 1). Rip прав, это числа Каталана $\frac{1}{n+1}C_{2n}^n$. Я раньше подсчитывал число путей от (0,0) до (n,k), при условии, что путь не опускается (или не поднимается) ниже (выше) диагонали. Возможно это было на форуме НГУ. Для диагональных точек получались числа Каталана.

[C0rWin]

Я извиняюсь, я изначально в условии допустил ошибку. Я имел ввиду, что нельзя проходить через точки вида: $C(k,k-2)$. В том контексте, что я изначально изложил это действительно числа Каталана, сорри.

[Руст]

Для этого случая как раз пригодились бы выведенные формулы. Но я их уже не помню, поэтому можно считать суммируя количество путей всегда не ниже главной диагонали (число Каталана+ число путей до (k,k), потом (k+1,k) и не ниже соседней с главной диагональю до (m+1,m), потом (m+1,m+1) и не ниже главной диагонали, т.е. сумма:

$$Ca(n)+\sum_{0\le k\le m\le n-1}Ca(k)Ca(m-k)Ca(n-1-m)$$

Только остаётся привести эту сумму в удобоваримую форму. Подправив путь в точках k и m последняя сумма приведётся к Ca(n-1)t(n), где t(n) число пар 0<=k<=m<=n-1, т.е. ответ должен быть $Ca(n)+\frac{n(n+1)}{2}Ca(n-1)=\frac{1}{n+1}C_{2n}^n+\frac{n+1}{2}C_{2n-2}^{n-1}.$

[maxal]

C0rWin писал(а):

Я извиняюсь, я изначально в условии допустил ошибку. Я имел ввиду, что нельзя проходить через точки вида: $C(k,k-2)$. В том контексте, что я изначально изложил это действительно числа Каталана, сорри.

Ответом будет также число Каталана, только следующее по счету: $C_{n+1}.$
Соответствие между правильными скобочными структурами с $n+1$ парами скобок и путями при этом такое: берем скобочную структуру и выкидиваем из нее первую (открывающую) скобку и последнюю (закрывающую) скобку, оставшееся трактуем как и раньше: "(" - шаг вверх, ")" - шаг вправо.

Кстати, несложно проверить, что $C_{n+1}={2n\choose n} - {2n\choose n-2}.$

[romanz]

Такие задачи решаются сложно. Общее решение можно найти в Математических заметках. — 2002.
— Т.72, Вып.6 — С.834–852.

[bot]

Здесь сложностей нет в силу простоты ограничения. Рассмотрим наоборот число путей, имеющих с прямой $y=x-1$ хотя бы одну общую точку. Часть пути от точки $(0;0)$ до первой точки $(k;k-1)$ на этом пути отразим симметрично относительно прямой $y=x-1$. В итоге получим путь из точки $(1;-1)$ в точку $(n;n)$. Наоборот, всякий такой путь обязательно пересечёт прямую $y=x-1$. Отсюда и получится число Каталана $\frac{1}{n+1}}{2n\choose n}={2n\choose n} - {2n\choose n-1}$

-- Пт апр 16, 2010 10:36:00 --

(Оффтоп)

Не заметил изменения задачи.

Если требуется не пересекать прямую $y=x-k$, то аналогично получаем ${2n\choose n} - {2n\choose n-k}$

[romanz]

Я имею ввиду общую задачу на диаграммах Ферре или косых диаграммах

[bot]

(я это понял)

Сходил по ссылке и добавил - в силу простоты ограничения.

[iig]

Руст в сообщении #38804 писал(а):

Определите вначале, что означает "путь". По видимому, речь идёт о последовательности целочисленных координат на плоскости. Остаётся выяснить, как связаны соседние точки. Они могут отличаться на (a,b), где a, b =0,+-1 или (направленные) (a,b)=(0,1) или (1,0) возможно ещё (1,1). В зависимости от этого, существенно отличается количество путей.

Совершенно согласен, понятие "путь" применимо к графам, в исходнике, похоже подразумевается плоскость с целыми координатами. В таком случае число путей бесконечно и надо ввести ограничения. чтобы не заблудиться, так что вопрос некорректен.
Кроме того, зачем узнавать число путей - обычно требуется найти какой-то один или несколько удовлетворяющих, например, максимальности узлов и минимуму бензина.