Количество путей без возвращений

[alleut]

Дан квадрат $2 \times 2$:

$$ \xymatrix{{A \ar@{-}[rr] \ar@{-}[dd] }&{\bullet\ar@{-}[dd]}&{\bullet\ar@{-}[dd]} \\ {\bullet \ar@{-}[rr]}&{\bullet}&{\bullet} \\ {\bullet \ar@{-}[rr]}&{\bullet}&{B}}$$

В нем 6 путей без возвращений из точки $A$ в точку $B$. На рисунке внизу 3 путя + 3 симметричных относительно диагонали $AB$.

$$\xymatrix{ {A \ar@{=>}[r] \ar@{-}[dd] }&{\bullet\ar@{-}[dd] \ar@{=>}[r]}&{\bullet \ar@{=>}[d]} \\ {\bullet \ar@{-}[rr]}&{\bullet}&{\bullet \ar@{=>}[d]} \\ {\bullet \ar@{-}[rr]}&{\bullet}&{B} } \xymatrix{ {A \ar@{=>}[r] \ar@{-}[dd] }&{\bullet\ar@{=>}[d] \ar@{-}[r] }&{\bullet \ar@{-}[d] } \\ {\bullet \ar@{-}[r]}&{\bullet\ar@{=>}[r]\ar@{-}[d]}&{\bullet \ar@{=>}[d]} \\ {\bullet \ar@{-}[rr]}&{\bullet}&{B} } \xymatrix{ {A \ar@{=>}[r] \ar@{-}[dd] }&{\bullet\ar@{=>}[d] \ar@{-}[r] }&{\bullet \ar@{-}[d] } \\ {\bullet \ar@{-}[r]}&{\bullet\ar@{=>}[d]\ar@{-}[r]}&{\bullet \ar@{-}[d]} \\ {\bullet \ar@{-}[r]}&{\bullet\ar@{=>}[r]}&{B} } $$

Задача: найти количество путей без возвращения из $A$ в $B$ для произвольного прямоугольника $n\times m$.

Единственный вариант, который мне приходит в голову - построить матрицу достижимости для графа с $(n+1)\times (m+1)$ вершинами и далее по порядку.
Есть ли какое-нибудь аналитическое решение?

[Cash]

Есть.
Чему равна длина пути из $A$ в $B$? Сколько раз надо шагнуть вправо, а сколько вниз?
И обратно, если мы ... раз шагнем вправо и ... раз шагнем вниз, вне зависимости от порядка шагов, то где мы окажемся?

[alleut]

Для упрощения рассмотрим исходный квадрат.
Длина пути очевидна - 4 (в общем случае$m + n$). 2 шага вниз, 2 шага вправо. Но я вот в упор не вижу связь длины пути с количеством путей.

[ИСН]

А Вы попробуйте нарисовать квадрат (не 2 на 2, а побольше, наверное) и в каждой вершине подписать число путей, коими туда можно прийти из A.

[alleut]

$$C_{q+r-2}^{q-1}=C_{m+n}^n$$

где $q$ и $r$ - число узлов в прямоугольнике по горизонтали и вертикали соотв.

[ИСН]

Я знал, что Вы это увидите.

[alleut]

Спасибо за помощь

[TOTAL]

alleut в сообщении #575255 писал(а):

Задача: найти количество путей без возвращения из $A$ в $B$ для произвольного прямоугольника $n\times m$.

Что такое "путь без возвращений"?