Открытые туры предвзятой ладьи (проверка доказательств)

[kthxbye]

У нас есть простая структура - предвзятая ладья двух типов. Здесь и далее открытый тур тождественен Гамильтонову пути.

Предвзятая ладья первого рода совершает открытые туры на специфической доске $f(n)\times 1$ , где $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$, а ячейки окрашены в белый или черный цвет в соответствии с двоичным представлением $2n$. Ячейка окрашивается в белый цвет, если двоичная цифра равна $0$, и ячейка окрашивается в черный цвет, если двоичная цифра равна $1$. Предвзятая ладья на белой клетке движется только влево и в противном случае движется в любом направлении.

Предвзятая ладья второго рода совершает открытые туры на специфической доске $f(n)\times 1$ , где $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$, а ячейки окрашены в белый или черный цвет в соответствии с двоичным представлением $2n$. Ячейка окрашивается в белый цвет, если двоичная цифра равна $0$, и ячейка окрашивается в черный цвет, если двоичная цифра равна $1$. Предвзятая ладья на белой клетке движется только влево и в противном случае движется только вправо.

Пусть $a_1(n)$ (A284005) - число открытых туров предвзятой ладьей первого рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на любой клетке. Тогда имеет место быть рекурсия

$$a_1(n)=(1+\operatorname{wt}(n))a_1(\left\lfloor\frac{n}{2}\right\rfloor), a_1(0)=1$$

где $\operatorname{wt}(n)$ (A000120) - число единиц в двоичной записи $n$.

Как это можно доказать? Начнем с доски, заполненной лишь черными клетками, коих у нас будет $k$ штук.

$$\underbrace{1\cdots1}_{k}$$

Исходную клетку мы выбираем $k$ способами. По условию предвзятая ладья на черной клетке движется в любом направлении, соответственно следующую мы выбираем $k-1$, третью - $k-2$ способами и т.д. По итогам имеем $k!$ открытых туров.

Добавим белую клетку где-нибудь посредине между черными:

$$\underbrace{1\cdots1}_{k_2}0\underbrace{1\cdots1}_{k_1}$$

Представим, что ее как и ранее нет, тогда мы вновь начинаем с $k!$ открытых туров. Теперь зададимся вопросом: сколькими способами мы можем вставить белую клетку в последовательность посещения черных? Пусть $1_1$ это черные клетки справа от белой, а $1_2$ - черные клетки слева. Разберем на примере:

$$1_11_21_21_11_11_2$$

Очевидно, что перед $1_1$ белая клетка стоять не может, поскольку предвзятая ладья на белой клетке движется только влево. Отметим возможные и невозможные положения через $+$ и $-$:

$$-1_1+1_2+1_2-1_1-1_1+1_2+$$

Как мы видим на примере, белая клетка может стоять перед любой из $1_2$ плюс в конце. Домножая на $k!$ имеем $k!(k_2+1)$ открытых туров.

Добавим еще одну белую клетку справа от предыдущей и аналогично разберем на примере:

$$-1_1+1_2+0-1_2-1_1-1_1+1_2+$$

Ввиду того, что клетка расположена справа, перейти на нее с предыдущей белой мы не можем, что и отражено $-$ после $0$. Зная, что исходная белая клетка может стоять лишь перед $1_2$, мы все также имеем $k_2+1$ способов. Домножая, имеем $k!(k_2+1)^2$ открытых туров. Аналогично для

$$\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j}\underbrace{1\cdots1}_{k_1}$$

имеем $k!(k_2+1)^j$ открытых туров. Далее добавляем белые клетки справа:

$$\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$

Разберем на примере:

$$+1_1+0_2-1_2+0_2-1_2+1_1+1_1+1_2+$$

Здесь мы уже можем перемещаться как на $1_2$, так и на $1_1$. После $0_2$ белая клетка $0_1$ стоять не может, итого имеем $(k_1+k_2+1)$ способов. По аналогии в итоге будем иметь $k!(k_2+1)^{j_2}(k_1+k_2+1)^{j_1}$.

Разбирая аналогичные примеры для

$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$

имеем

$$k!(k_m+1)^{j_m}(k_{m-1}+k_m+1)^{j_{m-1}}\cdots(k_2+\cdots+k_m+1)^{j_2}(k_1+k_2+\cdots+k_m+1)^{j_1}$$

где $k=k_1+k_2+\cdots+k_m$. Компактно выражение выше можно записать через

$$a_1(n)=\left(\sum\limits_{i=1}^{m}k_i\right)!\prod\limits_{p=1}^{m}\left(1+\sum\limits_{q=p}^{m}k_q\right)^{j_p}$$

Вот код на pari для проверки:

default(parisizemax,10^9)
n=5
T(n,k)=if(n>0,if(k==0,valuation(n,2)+1,T(n\2,k-n%2)),0)
A003188(n)=bitxor(n, n>>1)
R(n,k)=T(A003188(n),k)
v=vector(2^n-1,i,vector(hammingweight(A003188(i)),j,R(i,j-1)))
for(i=1,2^n-1,print(v[i])) \\ просмотр массива ранов нулей и единиц в n
A069010(n)=(1 + (hammingweight(bitxor(n, n>>1)))) >> 1
a(n)=if(n==0,1,(sum(i=1,A069010(n),v[2*n][2*i]))!*prod(p=1,A069010(n),(1+sum(q=p,A069010(n),v[2*n][2*q]))^v[2*n][2*p-1]))
for(i=0,2^(n-1)-1,print(a(i)))

Имея теперь выражение для $a_1(n)$, докажем рекурсию. Здесь надо вернуться к началу и еще раз подчеркнуть, что

Цитата:

Пусть $a_1(n)$ (A284005) - число открытых туров предвзятой ладьей первого рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на любой клетке.

Т.е. в конце у нас всегда будет как минимум один $0$.

Начнем с $a(2n)$. Добавляя $0$ к последовательности нулей длиной $j_1$ имеем

$$a_1(2n)=\left(\sum\limits_{i=1}^{m}k_i\right)!\prod\limits_{p=1}^{m}\left(1+\sum\limits_{q=p}^{m}k_q\right)^{j_p+[p=1]}=\left(1+\sum\limits_{q=1}^{m}k_q\right)a_1(n)=(1+\operatorname{wt}(n))a_1(n)$$

Теперь разберем $a_1(2n+1)$. Возможны два случая:

$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}1\underbrace{0}_{j_1}$$

и

$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1-1}\underbrace{1}_{k_0}\underbrace{0}_{j_0}$$

В первом у нас

$$a_1(2n+1)=(\sum\limits_{i=1}^{m}k_i+[i=1])!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q+[q=1])^{j_{p}}=(2+\sum\limits_{q=1}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=2}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}$$

$$a_1(2n+1)=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a_1(n)$$

А во втором

$$a_1(2n+1)=(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=0}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_{p}-[p=1]}=(1+\sum\limits_{q=0}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p-[p=1]}$$

$$a_1(2n+1)=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a_1(n)$$

По совокупным итогам имеем

$$a_1(2n)=(1+\operatorname{wt}(n))a_1(n)=(1+\operatorname{wt}(2n))a_1(n)$$

$$a_1(2n+1)=(2+\operatorname{wt}(n))a_1(n)=(1+\operatorname{wt}(2n+1))a_1(n)$$

Что и требовалось доказать.

И еще одна маленькая деталь.

Пусть $a_2(n)$ (A329369) - число открытых туров предвзятой ладьей второго рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на белой клетке. Тогда имеет место быть трансформация

$$a_1(n) = \sum\limits_{k=0}^{n}(\binom{n}{k}\bmod 2)a_2(k)$$

Как это можно доказать? Рассмотрим на примере небольшой доски, скажем $1100$. Заменим последовательно $k$ единиц $k$ нулями:

• $1100$ - без изменений ($0$ единиц заменено $0$ нулями)
• $0100$ - $1$ единица заменена $1$ нулем
• $1000$ - другой вариант предыдущего
• $0000$ - $2$ единицы заменено $2$ нулями

Результирующие значения $0,2,4,6$ (ввиду того, что, опять-таки, мы работаем с двоичным представлением $2n$) это и есть суммируемые $a_2(k)$, такие, что $\binom{n}{k}\bmod 2=1$. В каждом из случаев мы суммировали пути, оканчивающиеся лишь на белых клетках, но т.к. черные были заменены на белые, мы по итогам имеем все возможные пути, оканчивающиеся на всех клетках.

Что и требовалось доказать.

Насколько строгими можно назвать доказательства? Требуют ли они уточнений? Могут ли они быть улучшены (например каким-нибудь образом упрощены)?