Число путей

[Grom Hellscream]

Интересно, насколько стара такая задача.

Посчитать количество путей, соединяющих две противоположные вершины k-мерного параллелепипеда $n_1\times\ldots\times n_k $ и идущих по линиям сетки.

[arseniiv]

Путей, каждая координата вершин которых неубывает? Должна быть стара. Для квадрата даёт числа Каталана.

Если простых путей, то хитрее. Если любых путей, то для $k\ne0\ne n_1\times\ldots\times n_k$ их бесконечно много.

[Grom Hellscream]

arseniiv в сообщении #1344939 писал(а):

Путей, каждая координата вершин которых неубывает? Должна быть стара. Для квадрата даёт числа Каталана.

Если простых путей, то хитрее. Если любых путей, то для $k\ne0\ne n_1\times\ldots\times n_k$ их бесконечно много.

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

(Оффтоп)

Интересно, хорошо изучены ли многомерные разбиения?

[EtCetera]

Grom Hellscream в сообщении #1344937 писал(а):

Посчитать количество путей, соединяющих две противоположные вершины k-мерного параллелепипеда $n_1\times\ldots\times n_k $ и идущих по линиям сетки.

Даже для квадрата нет явной формулы: A007764.

[arseniiv]

Grom Hellscream в сообщении #1344985 писал(а):

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

Если мы можем ходить по одному и тому же отрезку взад и вперёд, можно накрутить много. Потому я предложил вариант «простые пути» — это как раз те, где рёбра не повторяются. Судя по всему, их вы изначально и имели в виду.

С монотонными путями выходит довольно просто, это мультиномиальные коэффициенты $\binom{n_1+\ldots+n_k}{n_1,\ldots,n_k}$. Просто раскидываете $k$ видов стрелочек в ряд, каждого вида стрелочек по $n_i$ штук.

Так что с учётом монотонности:

arseniiv в сообщении #1344939 писал(а):

Для квадрата даёт числа Каталана.

Меня сегодня тянет говорить ерунду, в другой теме начал выдумывать рекуррентные соотношения на пустом месте. Не Каталана, а $\binom{2n}n$, а первые можно получить, добавив ограничение не вылезать за диагональ.

[hund]

Не могу понять пример в http://oeis.org/A007764:

Цитата:

Suppose we start at (1,1) and end at (n,n). Let U, D, L, R denote steps that are up, down, left, right.

a(2) = 2: UR or RU.

a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.

Для $n=1$ - отрезок и $n=2$ - квадрат всё понятно.
А по $a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU$ ничего не понимаю.
Это куб. Как можно 2 раза подряд пойти вверх? - UU
Где самые явные пути URL, RUR и т.д.?
Наконец, за 4 хода вообще нельзя добраться в противолежащий угол.

[EtCetera]

hund в сообщении #1345048 писал(а):

Это куб.

Квадрат $3\times 3$.

[hund]

EtCetera
В квадрате $3x3$ за 4 хода нельзя добраться до противоположного угла. - минимум 6 ходов: UUURRR, RRRUUU, URURUR, RRUURU и т.д.

[grizzly]

hund в сообщении #1345084 писал(а):

В квадрате $3x3$ за 4 хода нельзя добраться до противоположного угла.

Вы взяли сразу рассматривать сложный пример. Посмотрите сначала пример $a(2)$ в этой же последовательности. Тогда Вы поймёте, что там называют решёткой $2\times 2$, и дальше будет уже проще.