Подкрепление опытных результатов логикой

[kthxbye]

Еще один из моих результатов, разрешаю свободное использование без указания авторства (однако был бы признателен за ссылки на статьи, в которых эти материалы потенциально могут быть использованы; приятно было бы взглянуть на результат, хорошо оформленный и внятно описанный). Какое-то время интересовался проблемой ГП для ладьи $n\times1$, где клетки располагались не в шахматном порядке, а в соответствии с бинарной записью числа (черные клетки соответствуют единицам, белые - нулям). С белых клеток можно перемещаться только налево, с черных - только направо. Рассматриваются два варианта, где подсчитываются ГП, оканчивающиеся только на белых клетках (A329369) и на любых (A329718). Все результаты являются опытными и базируются на подсчетах из темы Перестановки в pari/gp (или где-нибудь еще).

Чтобы как-то увязать их с логикой я в свое время наткнулся на последовательность A152884, которая рассматривают совсем иную проблему и размещена в откровенно неудобном порядке. С целью исправить это я разместил A329369, которая помимо данных о ладье раскрывает вышеупомянутую последовательность на языке двоичных последовательностей. В основу легла замечательная статья авторов R. Ehrenborg and E. Steingrimsson которая называется The excedance set of a permutation и размещена вот тут. Ниже представлены преобразования на основе перевода некоторых формул и тождеств из статьи на язык двоичных последовательностей.

Перевод Теоремы 6.3.

$a(n) = \sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)}\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$

где

$b(2n) = b(n), b(2n+1) = b(n) + 1$
$T(0,0) = 1, T(2n+1,0) = 1, T(2n,0) = T(n,0) + 1, T(2^{m}n)=T(n,0)+m$
$T(2n+1,k) = T(n,k-1), T(2n,k) = T(n,k)$

Начнем с преобразования $a(2n+1)$. Запишем в том же виде и применим $b(2n+1)=b(n)+1, T(2n+1,0)=1, T(2n+1,k)=T(n,k-1)$, получим:

$a(2n+1) = \sum\limits_{j=0}^{2^{b(n)+1}-1}(-1)^{b(n)-b(j)+1}(1+b(j))\prod\limits_{k=1}^{b(n)+1}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k-1)}$

далее сдвинем произведение на $1$:

$a(2n+1) = \sum\limits_{j=0}^{2^{b(n)+1}-1}(-1)^{b(n)-b(j)+1}(1+b(j))\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^{k+1}}\right\rfloor))^{T(n,k)}$

после чего будем суммировать раздельно по $2j$ и $2j+1$ через

$\sum\limits_{j=0}^{n}j=\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2j+\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2j+1$

а именно:

$\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}(1+b(j))\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$+\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)}(1+b(j))\prod\limits_{k=0}^{b(n)}(2+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$

по итогам будем иметь:

$(-1+1)\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)}(1+b(j))\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$+\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)}\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}=a(n)$

отсюда $a(2n+1)=a(n)$. Далее переходим к $a(2n)$. В элементарном виде получить не удается, прибегаем изначально к $a(2^{m}n)$, где заранее преобразовываем $1+b(j)=b(2j+1)$ и применяем $b(2^{m}n)=b(n), T(2^{m}n)=T(n,0)+m, T(2^{m}n,k)=[k>0]T(n,k)$:

$a(2^{m}n)=\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)}(b(2j+1))^m\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$

На основе этого находим применяя операции, аналогичные тем, что мы использовали в $a(2n+1)$:

$a(2^{m}(2n+1))=\sum\limits_{j=0}^{2^{b(n)+1}-1}(-1)^{b(n)-b(j)+1}(b(2j+1))^{m+1}\prod\limits_{k=1}^{b(n)+1}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k-1)}$
$=\sum\limits_{j=0}^{2^{b(n)+1}-1}(-1)^{b(n)-b(j)+1}(b(2j+1))^{m+1}\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^{k+1}}\right\rfloor))^{T(n,k)}$
$=\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}(b(2j+1))^{m+1}\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$+\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}(1+b(2j+1))^{m+1}\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$

в последнем выражении мы раскрываем $b(2j+1)=b(j)+1$ что ввиду раздельной суммы преобразуем в $b(2j+1)+1$. Далее мы совмещаем два выражения, выражаем разность через бином и меняем порядок суммирования:

$\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}((1+b(2j+1))^{m+1}-b(2j+1)^{m+1})\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$=\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}\sum\limits_{i=0}^{m}\binom{m+1}{i}(b(2j+1)^i)\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$=\sum\limits_{i=0}^{m}\binom{m+1}{i}\sum\limits_{j=0}^{2^{b(n)}-1}(-1)^{b(n)-b(j)+1}(b(2j+1)^i)\prod\limits_{k=0}^{b(n)}(1+b(\left\lfloor\frac{j}{2^k}\right\rfloor))^{T(n,k)}$
$\sum\limits_{i=0}^{m}\binom{m+1}{i}a(2^{i}n)$

По промежуточным итогам имеем:

$a(2n+1)=a(n), a(2^{m}(2n+1))=[m>0]\sum\limits_{i=0}^{m}\binom{m+1}{i}a(2^{i}n)$

Перевод утверждения 2.1

$[vbaw]=[vabw]+[vbw]+[vaw]$

Переведем это утверждение на язык двоичных последовательностей так: пусть

$B=b_{m},b_{m-1},\cdots,b_{q+3},b_{q+2}, A=b_{q-1},b_{q-2},\cdots,b_{1},b_{0}$

т.е. $A,B$ - это элементы двоичной записи некоторого числа, тогда

$a((B,1,0,A)_{2})=a((B,0,1,A)_{2})+a((B,1,A)_{2})+a((B,0,A)_{2})$

Пусть $A$ - это крайняя справа последовательность нулей в двоичной записи $n$, т.е. $A = \underbrace{0\cdots0}_{q}$, где $q$ - максимальная степень двойки, на которую $n$ делится без остатка. Тогда

$a((B,1,A)_{2})=2^{q}(2k+1)=n$
$a((B,0,A)_{2})=2^{q}(2k+1)-2^q=2^{q+1}k=n-2^q$
$a((B,0,1,A)_{2})=2(2^{q+1}k)+2^q=2^{q}(4k+1)=2n-2^{q+1}+2^q=2n-2^q$
$a((B,1,0,A)_{2})=2(2^{q+1}k)+2^{q+1}=2^{q+1}(2k+1)=2n-2^{q+1}+2^{q+1}=2n$

откуда

$a(2^{q+1}(2k+1))=a(2^{q}(2k+1))+a(2^{q}(4k+1))+a(2^{q+1}k)$

или

$a(2n) = a(n) + a(n - 2^f(n)) + a(2n - 2^f(n))$

где $f(n)=q$ это A007814$(n)$.

Если произвести замену $q+1=m$, получим

$a(2^{m}(2k+1))=a(2^{m-1}(2k+1))+a(2^{m-1}(4k+1))+a(2^{m}k)$

что можно доказать используя

$a(2^{m}(2n+1))=[m>0]\sum\limits_{i=0}^{m}\binom{m+1}{i}a(2^{i}n)$

пусть

$a(2^{m-1}(2k+1))+a(2^{m-1}(4k+1))+a(2^{m}k)$
$=\sum\limits_{i=0}^{m-1}\binom{m}{i}a(2^{i}n)+\sum\limits_{i=0}^{m-1}\binom{m}{i}a(2^{i+1}n)+a(2^{m}n)$

тогла

$a(n)+\sum\limits_{i=0}^{m-1}[\binom{m}{i}+\binom{m}{i-1}]a(2^{i}n)+(m+1)a(2^{m}n)$
$=\sum\limits_{i=0}^{m}\binom{m+1}{i}a(2^{i}n)=a(2^{m}(2n+1))$

Остальные формулы к A329369 были получены либо опытным путем, либо за год я уже забыл каким именно образом они получались.

[kthxbye]

Откопал программку, которую писал на основе поддержки в теме Перестановки в pari/gp (или где-нибудь еще). Сейчас уже практически ничего не помню, но что именно выводит программа распознал. А выводит она решения для конечных точек на специфических досках $n\times1$ заданной длины, базирующихся на двоичной записи $m$, о которых я писал выше. В конце добавил сумму всех решений по конечным точкам - это подпоследовательности A329369.

default(parisizemax,10^9)
\\ увеличиваем объем выделяемой памяти
n=5
\\ задаем длину бинарного массива
n_fac=n!
v_bin=vector(2^(n-2),i,binary(2*(i-1+2^(n-2))));
\\ создаем все четные бинарные массивы длины n
v_perm=vector(n_fac,i,numtoperm(n,i-1));
\\ создаем все перестановки длины n
v_p_inv=vector(n_fac,i,vector(n));
\\ пустой массив для обратных перестановок
v_p_i_1=vector(n_fac,i,vector(n-1));
\\ пустой массив для сравнения их соседних элементов
v_p_last=vector(n_fac,i,vector(n));
\\ пустой массив для выделения в исходных перестановках конечных точек
v_l_sol=vector(2^(n-2),k,vector(n));
for(i=1,n_fac,for(j=1,n,v_p_inv[i][v_perm[i][j]]=v_perm[1][j]));
\\ находим обратные перестановки
for(i=1,n_fac,for(j=1,n-1,v_p_i_1[i][j]=if(v_p_inv[i][j+1]>v_p_inv[i][j],1,0)));
\\ сравниваем их соседние элементы
for(i=1,n_fac,for(j=1,n,v_p_last[i][j]=if(v_perm[i][j]==n,1,0)));
\\ выделяем в исходных перестановках конечные точки
v_1(k)={
my(v_b_inv=vector(n_fac,i,vector(n)),
\\ пустой массив для перестановок k-того бинарного массива
v_b_i_1=vector(n_fac,i,vector(n)),
\\ пустой массив для сравнения их с v_p_i_1
v_cond=vector(n_fac,i,0),
\\ пустой массив для выделения полного соответствия
v_cond_1=vector(n,j,0));
\\ пустой массив для подсчета количества решений для конечных точек
for(i=1,n_fac,for(j=1,n,v_b_inv[i][v_perm[i][j]]=v_bin[k][j]));
\\ переставляем k-тый бинарный массив каждой из n! исходных перестановок
for(i=1,n_fac,for(j=1,n,v_b_i_1[i][j]=if(j==n,if(v_b_inv[i][n]==0,1,0),if(v_b_inv[i][j]==v_p_i_1[i][j],1,0))));
\\ сравниваем элементы получившихся массивов и v_p_i_1
for(i=1,n_fac,v_cond[i]=if(sum(j=1,n,v_b_i_1[i][j])==n,1,0));
\\ выделяем полное соответствие
for(j=1,n,v_cond_1[j]=sum(i=1,n_fac,v_p_last[i][j]*v_cond[i]));
\\ считаем количество решений для j-той конечной точки
return(v_cond_1)}
for(k=1,2^(n-2),v_l_sol[k]=v_1(k));
print(v_l_sol)
a=vector(2^(n-2),i,0);
for(i=1,2^(n-2),a[i]=sum(k=1,n,v_l_sol[i][k]));
print(a)

Вкратце идея состоит в следующем. Берем некоторое $m$, например $m=5=(101)_{2}$. Генерируем массив перестановок длины 4 (длина 2-ной записи $m$ плюс $1$). Пусть перестановка описывает последовательность посещения клеток. Не все перестановки описывают решения. Чтобы найти полезную перестановку необходимо произвести сверку, например:

$101(0)$
$1432$

1) Находим обратную перестановку, как перестановки, так и двоичной записи $m$:

$1234$
$1432$
$1(0)10$

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

$4-1=3, 3-4=-1, 2-3=-1$

подставляем и сравниваем с перестановкой двоичной записи:

$1234$
$1432$
$1(0)10$
$100$

Первые два элемента совпадают, третий - нет, значит перестановка бессмысленна. Если же совпадение полное, то перестановка описывает одно из решений, например

$101(0)$
$2134$

$1234$
$2134$
$011(0)$
$011$

Аналогично для перестановок любой длины $n$. Важно помнить, что к 2-ной записи $m$ всегда добавляем $0$ в конце, т.е. это двоичная запись $2m$. В рамках A329369 учитываем решения, оканчивающиеся только на нулях (белые клетки, единицы - черные).