2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Подкрепление опытных результатов логикой
Сообщение13.10.2020, 09:23 
Аватара пользователя


22/11/13
270
Еще один из моих результатов, разрешаю свободное использование без указания авторства (однако был бы признателен за ссылки на статьи, в которых эти материалы потенциально могут быть использованы; приятно было бы взглянуть на результат, хорошо оформленный и внятно описанный). Какое-то время интересовался проблемой ГП для ладьи $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 были получены либо опытным путем, либо за год я уже забыл каким именно образом они получались. :roll:

 Профиль  
                  
 
 Re: Подкрепление опытных результатов логикой
Сообщение14.10.2020, 09:26 
Аватара пользователя


22/11/13
270
Откопал программку, которую писал на основе поддержки в теме Перестановки в 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 учитываем решения, оканчивающиеся только на нулях (белые клетки, единицы - черные).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group