Кол.-во откр. туров ладьей, заверш.-ся на k-ой справа клетке

[kthxbye]

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

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

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

$$T_1(n,k) = a_1(g(n) + 2^{k-2}(1 - L(n,k-2)))$$

для $1 < k \leqslant \left\lfloor\log_2{n}\right\rfloor + 1$ с

$$T_1(n,1) = T_1(n, \left\lfloor\log_2{n}\right\rfloor + 2) = a_1(g(n))$$

где

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

$$b_1(n)=b_1(\left\lfloor\frac{n}{2}\right\rfloor)+n\bmod 2, b_1(0)=0$$

$$g(n)=n-2^{\left\lfloor\log_2{n}\right\rfloor}$$

$$L(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor \bmod 2$$

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

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

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

$$T_2(n,k) = a_2(g(n) - 2^{k-2}L(n,k-2)) + a_2(g(n) + 2^{k-2}(1 - L(n,k-2)))$$

для $1 < k \leqslant \left\lfloor\log_2{n}\right\rfloor + 1$ с

$$T_2(n,1) = T_2(n, \left\lfloor\log_2{n}\right\rfloor + 2) = a_2(g(n))$$

где

$$a_2(2n+1) = a_2(n), a_2(2n) = a_2(n) + a_2(n - 2^{b_2(n)}) + a_2(2n - 2^{b_2(n)}), a_2(0)=1$$

$$b_2(2n+1) = 0, b_2(2n) = b_2(n) + 1, b_2(1) = 0$$

$$g(n)=n-2^{\left\lfloor\log_2{n}\right\rfloor}$$

$$L(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor \bmod 2$$

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

Существует также альтернативное представление для $a_1(n)$:

$$a_1(2n+1) = a_1(n) + a_1(2n), a_1(2n) = a_1(n) + a_1(2n - 2^{b_2(n)}), a_1(0)=1$$

См. также A284005 (это $a_1(n)$), A329369 (это $a_2(n)$), A329718.

Существует ли способ доказать выражения для $T_1(n)$ и $T_2(n)$?