Описание подхода получения результата и восполнение пробела

[kthxbye]

Около года назад я опубликовал результат по числу ГП ладьи на доске $n\times3$ где просил о помощи с вычислением значений по формуле на PARI. Теперь мне бы хотелось описать цепочку рассуждений, благодаря которой я пришел к результату, попросить помощи в корректировании описания хода рассуждений и восполнении пробела, который возник ввиду того, что я долгое время не возвращался к этой проблеме.

Все что будет ниже до определенного момента - это последовательные рассуждения.

Начнем с элементарного случая $n\times1$. 1-ую клетку выбираем $n$ способами, 2-ую клетку выбираем $n-1$ способами, перемножаем способы. Продолжая далее будем иметь $n!$ ГП ладьи на доске $n\times1$.

Ладья $n\times2$. Вводим заранее размещаемые элементы - змейки и лестницы, занимающие по 2 клетки или один полный столбец. Разместим 1 лестницу в любом столбце, начинаем движение с любой из нижних клеток, заканчиваем на любой из нижних ($(n-1)!$ ГП), далее проходим через лестницу и начинаем так же на любой, заканчиваем на любой ($(n-1)!$ ГП). Перемножая будем иметь $(n-1)!^2$ ГП.

Размещаем змейку. Аналогично начинаем вверху, проходим через змейку, заканчиваем внизу. Если поменять строки клеток местами, это будет не змейка, а лестница, т.е. эти 2 случая симметричны и достаточно исследовать, например, лестницу, что мы уже практически сделали выше, а затем удвоить результат. Лестницу мы можем разместить в любой из столбцов $n$ способами, итого $n\cdot(n-1)!^2$ ГП.

1 лестница и 1 змейка. Здесь мы можем разбить посещение нижних клеток на 2 этапа. На 1-ом этапе мы можем посетить от $0$ до $n-2$ клеток, которые мы выбираем из $n-2$ клеток:

$\sum\limits_{k=0}^{n-2} \binom{n-2}{k}$

Затем мы их посещаем начиная с любой и заканчивая на любой, т.е.

$\sum\limits_{k=0}^{n-2} \binom{n-2}{k}k!$

Когда мы проходим через лестницу, мы обходим все верхние клетки до посещения змейки, т.е.

$\sum\limits_{k=0}^{n-2} \binom{n-2}{k}k!(n-2)!$

и проходя через змейку посещаем все оставшиеся нижние клетки

$\sum\limits_{k=0}^{n-2} \binom{n-2}{k}k!(n-2)!(n-k-2)!$

По итогам имеем

$\sum\limits_{k=0}^{n-2} (n-2)!^2 = (n-2)!^2 \sum\limits_{k=0}^{n-2} 1 = (n-2)!^2\cdot(n-1)$

Змейку и лестницу мы размещаем $n(n-1)$ способами или $\binom{n}{2}2!$ способами, итого

$\binom{n}{2}2!(n-2)!^2\cdot(n-1)$ ГП.

2 лестницы и 1 змейка. Случай 2 змейки и 1 лестница симметричен, если поменяем строки местами. Т.е. достаточно аналогично рассмотреть какой-нибудь один из случаев. Здесь посещение верхних клеток также разбивается на 2 этапа.

$\sum\limits_{k=0}^{n-3} \binom{n-3}{k}k!\sum\limits_{p=0}^{n-3} \binom{n-3}{p}p!(n-k-3)!(n-p-3)!$

$\sum\limits_{k=0}^{n-3} (n-3)!\sum\limits_{p=0}^{n-3} (n-3)! = (n-3)!^2 \sum\limits_{k=0}^{n-3} 1 \sum\limits_{p=0}^{n-3} 1 = (n-3)!^2\cdot(n-2)^2$

итого $\binom{n}{3}3!(n-3)!^2\cdot(n-2)^2$ ГП.



Далее 2 змейки и 2 лестницы, тут уже 3 этапа внизу:

$\sum\limits_{k=0}^{n-4} \binom{n-4}{k}k!\sum\limits_{p=0}^{n-4} \binom{n-4}{p}p!\sum\limits_{k_{1}=0}^{n-k-4} \binom{n-k-4}{k_{1}}(n-p-4)!(n-k-k_{1}-4)!$
$(n-4)!^2 \sum\limits_{k=0}^{n-4} \sum\limits_{k_{1}=0}^{n-k-4} 1 \sum\limits_{p=0}^{n-4} 1 = (n-4)!^2 \sum\limits_{k=0}^{n-4} \sum\limits_{k_{1}=0}^{k}1 \sum\limits_{p=0}^{n-4} 1 = (n-4)!^2 \sum\limits_{k=0}^{n-4} \binom{k+1}{1} \sum\limits_{p=0}^{n-4} 1 = (n-4)!^2\cdot\binom{n-2}{2}(n-3)$

итого

$\binom{n}{4}4!(n-4)!^2\cdot\binom{n-2}{2}(n-3)$ ГП.

Далее

$\binom{n}{5}5!(n-5)!^2\cdot\binom{n-3}{2}^2$

затем

$\binom{n}{6}6!(n-6)!^2\cdot\binom{n-3}{3}\binom{n-4}{2}$

еще далее

$\binom{n}{7}7!(n-7)!^2\cdot\binom{n-4}{3}^2$

В общем виде угадывается формула для нечетного набора змеек и лестниц

$\binom{n}{2q+1}(2q+1)!(n-(2q+1))!^2\cdot\binom{n-(2q+1)+q}{q}^2$

для четных аналогично

$\binom{n}{2q}(2q)!(n-2q)!^2\cdot\binom{n-2q+q}{q}\binom{n-2q+q-1}{q-1}$

Если ввести функцию $R(n,k)$, такую, что

$R(n,k)=\binom{n+k}{k}$, то

$\binom{n}{2q+1}(2q+1)!(n-(2q+1))!^2\cdotR(n-(2q+1),q)^2$

$\binom{n}{2q}(2q)!(n-2q)!^2\cdotR(n-2q,q)R(n-2q,q-1)$

В общем виде

$\binom{n}{k}k!(n-k)!^2\cdotR(n-k,\left\lfloor \frac{k}{2}\right\rfloor)R(n-k,\left\lfloor \frac{k-1}{2}\right\rfloor)$

Все это помещаем под сумму и удваиваем ввиду симметрий (1 л и 1 з; 1л, 1з; 1 з и 2 л, 2 з и 1 л; 2 л, 2 з; и т.л.):

$2\sum\limits_{k=1}^{n}\binom{n}{k}k!(n-k)!^2\cdotR(n-k,\left\lfloor \frac{k}{2}\right\rfloor)R(n-k,\left\lfloor \frac{k-1}{2}\right\rfloor)$

Поиск в OEIS приводит нас к A096121 где описание последовательности соответствует полученному результату. К последовательности мною когда-то добавлялась формула, в которой мы приходим к еще одной последовательности, что интересно рекуррентной, если выносим из выражения $2\cdot n!$.

Для наглядного иллюстрирования разбиения на этаы мы могли бы обозначать:

1 лестница - $ab$ - переход с нижней строки ($a$) на верхнюю ($b$).

1 лестница - $ab$ $\equiv$ 1 змейка $ba$
1 лестница 1 змейка - $aba$ $\equiv$ 1 змейка 1 лестница $bab$

и т.д. Получаются строки из элементов $a,b$ типа

ab, aba, abab, ababa
ba, bab, baba, babab

нижние тождественны из-за симметрии верхним.

Ладья $n\times3$. Тут уже более расширенная симметрия

$abc \equiv acb \equiv bac \equiv bca \equiv cab \equiv cba$

Исходной строкой будет ab. Мы будем генерировать также недопустимые здесь случаи ab, aba, abab и т.д. для удобства. Все случаи для $n\times3$ мы будем учитывать через:

aba
abc

abab
abac
abca
abcb

ababa
ababc
abaca
abacb
abcab
abcac
abcba
acbcb

Все строки симметричны относительно ab, т.е.

$ab \equiv ac \equiv ba \equiv bc \equiv ca \equiv cb$

где за каждой парой элементов следуют некоторые другие. Кроме побочных, необходимых для корректной генерации все строки содержат как минимум по 1 элементу каждого типа (из a,b,c).

abac 321
abca 222
abcb 132

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

Все вышеуказанные случаи реализуемы через

$(n-3)!(n-2)!(n-1)!R(n-3,2)R(n-2,1)R(n-1,0)$
$+(n-2)!(n-2)!(n-2)!R(n-2,1)^3$
$+(n-1)!(n-3)!(n-2)!R(n-1,0)R(n-3,2)R(n-2,1)$

По опыту $n\times2$ при разбиении на 2 этапа у нас $R(n,1)$, при разбиении на 3 этапа у нас $R(n,2)$, соответственно без разбиения на этапы $R(n,0)$. Индекс $k$ в $R(n,k)$ отражает число разбиений, которые в случае $n\times3$ вырастают из строкиз элементов a,b,c.

Откуда нам взять тройки чисел (3,2,1), (2,2,2), (1,3,2)? Мы можем задавать строки из элементов a,b,c функцией. Еще удобнее ввести функцию для последнего элемента строки, т.к. каждая новая строка генерирует две последующих и т.д.

Если обозначить a - 0, b - 1, c - 2, то нам нужна функция, которая превращает

• $0$ в $1,2$
• $1$ в $0,2$
• $2$ в $0,1$

Такая функция существует, это

$h(n,k)=[n=1]\cdot[k=0]+[n>1]\cdot[0\leqslant k<2^{n-1}]\cdot\left(1+k \operatorname{mod} 2 + \left\lfloor\frac{k \operatorname{mod} 2 - h(n-1,\left\lfloor\frac{k}{2}\right\rfloor)}{2}\right\rfloor\right)$

Строки тогда представляются как цепочки элементов на дереве

0
|
1
| \
0 2
| \ | \
1 2 0 1
|\ |\ |\ |\
0 2 0 1 1 2 0 2
|\ |\ |\ |\ |\ |\ |\ |\
1201120202011201

каждый новый срез свзяан с предыдущим, а именно:
1) за исключением 1-го элемента 1-ая половина каждого нового среза полностью повторяет предыдущий;
2) вторая половина - либо зеркальное отражение первой с заменой 0 -> 2, 1 без изменений, 2 -> 0, либо копия первой половины за исключением крайних значений, что отражено мною сегодня в https://oeis.org/draft/A091297 (схожая последовательность где 0 -> 2, 2 -> 0).

Последние 2 факта позволяют нам задавать $h(n,k)$ через одномерный массив, а именно $h(n,k) = a(k)$.

Вычислять число занятых клеток на той или иной строке из которых вытекает число разбиений на этапы мы будем специальной функцией

$f(i,n,k)=[0\leqslant i<2]\cdot[n=1]\cdot[k=0]+[0\leqslant i<3]\cdot[n>1]\cdot[0\leqslant k<2^{n-1}]\cdot\left(f(i,n-1,\left\lfloor\frac{k}{2}\right\rfloor)+[i=h(n,k)]\right)$

Отсюда мы получаем заготовку

$\sum\limits_{k=1}^{2^{j-1}-1}\prod\limits_{i=0}^{2}A!R(A,f(i,j,k)-1)\right)$

где

$A=n-2f(i,j,k)+[i=0]+[i=h(j,k)]$

От числа $j$ зависит число размещаемых змеек и лестниц. По промежуточным итогам имеем:

$\sum\limits_{j=2}^{n}\binom{n}{j}j!\sum\limits_{k=1}^{2^{j-1}-1}\prod\limits_{i=0}^{2}A!R(A,f(i,j,k)-1)\right)$

где \binom{n}{j}j! служит для учета вариантов размещения змеек и лестниц постолбцово. Необходимо также учесть вставку промежуточных элементов, о которой упоминалась ранее и которую мы реализуем через (дополнительно домножая на $6$ ввиду симметрии и добавляя постолбцовые пробеги)

$6(n!+\sum\limits_{j=2}^{n}\binom{n}{j}j!\sum\limits_{k=1}^{2^{j-1}-1}\sum\limits_{p=0}^{2^j-1}\prod\limits_{i=0}^{2}A!R(A,f(i,j,k)-1)\right))$

где мы присваиваем

$A=n-2f(i,j,k)+[i=0]+[i=h(j,k)]-\sum\limits_{q=0}^{j-1}[i=g(j-q,\left\lfloor\frac{k}{2^q}\right\rfloor)]\cdot L(p,q)$
$L(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor \operatorname{mod} 2$
$g(n,k)=[n=1]\cdot[k=0]\cdot2+[n>1]\cdot[0\leqslant k<2^{n-1}]\cdot h(n,k+(-1)^k)$

$g(n,k)$ - функция для вставляемого промежуточного элемента, который отличен от соседствующих, напр ab -> A(C)B ввиду особенности строк из элементов a,b,c (2 элемента одного типа не могут располагаться рядом, существует единственный вариант промежуточного элемента, который должен быть отличен от пары соседствующих).

На этом мои рассуждения подходят к концу. Пробел выражается в выводе формулы для реализации учета промежуточных элементов - за год я совершенно забыл как именно я это реализовывал и почему все в итоге выглядит именно так. Буду признателен за любые комментарии. Кроме того, буду рад, если эти рассуждения послужат основой для, например, чьей-либо статьи (меня там указывать вообще необязательно). Сам результат размещен вот тут - A329319.

[kthxbye]

Без скобок Айверсона (практически) функции задаются аналогично тому, в каком виде они представлены в A329319. Это удобнее для восприятия:

$$h(n,k)=k \operatorname{mod} 2 + \left\lfloor\frac{k \operatorname{mod} 2 + 2 - h(n-1,\left\lfloor\frac{k}{2}\right\rfloor)}{2}\right\rfloor$$

для $0\leqslant k<2^{n-1}$, $n>1$, вместе с тем $h(1,0)=1$. Далее

$$f(i,n,k)=f(i,n-1,\left\lfloor\frac{k}{2}\right\rfloor)+[i=h(n,k)]$$

для $0\leqslant i<3$, $0\leqslant k<2^{n-1}$, $n>1$, вместе с тем $f(i,1,0)=[0\leqslant i<2]$. Далее

$$g(n,k)=h(n,k+(-1)^k)$$

для $0\leqslant k<2^{n-1}$, $n>1$, вместе с тем $g(1,0)=2$.
Пробел с промежуточными элементами восполнился. Через
$\sum\limits_{p=0}^{2^j-1}$
реализуются все бинарные комбинации учета промежуточных элементов, а через
$\sum\limits_{q=0}^{j-1}[i=g(j-q,\left\lfloor\frac{k}{2^q}\right\rfloor)]\cdot L(p,q)$
происходит их изъятие из строк клеток, только и всего.

К слову сказать, аналогичная конструкция будет иметь место для ладьи $n\times4$, только там функции будут задаваться так:

$$h_{4}(n,k)=k \operatorname{mod} 3 + \left\lfloor\frac{k \operatorname{mod} 3 + 3 - h_{4}(n-1,\left\lfloor\frac{k}{3}\right\rfloor)}{3}\right\rfloor$$

для $0\leqslant k<3^{n-2}$, $n>2$, вместе с тем $h_{4}(2,0)=2$. Далее

$$f_{4}(i,n,k)=f_{4}(i,n-1,\left\lfloor\frac{k}{3}\right\rfloor)+[i=h_{4}(n,k)]$$

для $0\leqslant i<4$, $0\leqslant k<3^{n-2}$, $n>2$, вместе с тем $f_{4}(i,2,0)=[0\leqslant i<3]$. Далее

$$g_{4,1}(n,k), g_{4,2}(n,k)$$

это функции в которые инпутятся значения $h_{4}(n,k)$ и $h_{4}(n-1,\left\lfloor\frac{k}{3}\right\rfloor)$, принадлежащие множеству $\left\lbrace0,1,2,3\right\rbrace$ и аутпутятся элементы, отличные от тех, которые были заданы через $h_{4}$. Наименьший инпутится в $g_{4,1}(n,k)$, наибольший - в $g_{4,2}(n,k)$.

Сама функция $h_{4}(n,k)$ нужна чтобы превращать

• $0$ в $1,2,3$
• $1$ в $0,2,3$
• $2$ в $0,1,3$
• $3$ в $0,1,2$

Строки из элементов $a,b,c,d$ генерируются через

abc 0

abca 0
abcb 0
abcd 1

abcab 0
abcac 0
abcad 1
abcba 0
abcbc 0
abcbd 1
abcda 1
abcdb 1
abcdc 1

abcaba 0 abcbab 0 abcdab 1
abcabc 0 abcbac 0 abcdac 1
abcabd 1 abcbad 1 abcdad 1
abcaca 0 abcbca 0 abcdba 1
abcacb 0 abcbcb 0 abcdbc 1
abcacd 1 abcbcd 0 abcdbd 1
abcada 1 abcbda 1 abcdca 1
abcadb 1 abcbdb 1 abcdcb 1
abcadc 1 abcbdc 1 abcdcd 1

т.е. включаются далеко не все элементы. Учет подходящих происходит через две функции

$$t(k)=\sum\limits_{j=0}^{n-3}\left\lfloor\frac{\left\lfloor\frac{k}{3}\right\rfloor \operatorname{mod} 3}{2}\right\rfloor, t_{1}(k)=\operatorname{sgn}(t(k))$$

База для $n\times4$ будет иметь вид

$$\binom{4}{2}\cdot2!\cdot n! + \binom{4}{3}\cdot3!\cdot n!\cdot T_{3}(n,n) + 4!\cdot\sum\limits_{j=3}^{n}\sum\limits_{k=1}^{3^{j-2}-1}\sum\limits_{p=0}^{2^j-1}\sum\limits_{q=0}^{2^j-1}\binom{n}{j}j!t_{1}(k)\prod\limits_{i=0}^{3}A!R(A,f(i,j,k)-1)$$

где

$$A=n-2f_{4}(i,j,k)+[i=0]+[i=h_{4}(j,k)]-\sum\limits_{p_{1}=0}^{j-1}[i=g_{4,1}(j-q,\left\lfloor\frac{k}{3^p_{1}}\right\rfloor)]\cdot L(p,p_{1})-\sum\limits_{q_{1}=0}^{j-1}[i=g_{4,2}(j-q,\left\lfloor\frac{k}{3^q_{1}}\right\rfloor)]\cdot L(q,q_{1})$$

Здесь через

$$\binom{4}{2}\cdot2!\cdot n! + \binom{4}{3}\cdot3!\cdot n!\cdot T_{3}(n,n)$$

учитываются случаи, когда все столбцы заняты змейками и лестницами. Первое произведение отвечает за аналог $n\times2$, где мы добавляем к змейкам лестницам клетки двух оставшихся строк в качестве промежуточных элементов, аналогично второе произведение - для $n\times3$, где

$$T_{3}(n,j)=\sum\limits_{k=1}^{2^{j-1}-1}\sum\limits_{p=0}^{2^j-1}\frac{1}{(n-j)!}\prod\limits_{i=0}^{2}A!R(A,f(i,j,k)-1)$$

И все это только база для $n\times4$. Почему? Потому что до этого разные элементы (змейки и лестницы) мы размещали в разных столбцах, а тут появляется возможность впихнуть сразу пару элементов $1\times2$ в один столбец из 4-х клеток. Здесь нужно изобретать совершенно новые инструменты, поскольку непонятно как выделять такие случаи, как учитывать вставку промежуточных элементов в оставшихся змейках и лестницах, которые не запихиваются в один столбец. Я туда наверное уже не полезу, поскольку навскидку сложновато и смущает уже тот факт, что невозможно корректно задать математически $g_{4,1}(n,k)$ и $g_{4,2}(n,k)$, а дальше вероятно еще что-нибудь такое появится..