Подсчет Гам.-ых путей ладьи на доске nx3

[kthxbye]

По доске $n\times3$ ходит ладья (по стандартным правилам) посещая каждую клетку не более одного раза. Её задача - посетить все клетки. Суммируя различные способы сделать это для каждой из возможных стартовых клеток мы получаем общее число Гамильтоновых путей, которое равно

$$a(n)=6n!\left(1+[n>1]\cdot\sum\limits_{j=2}^{n}\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)\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)$$

$$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)$$

$$g(n,k)=[n=1]\cdot[k=0]\cdot2+[n>1]\cdot[0\leqslant k<2^{n-1}]\cdot h(n,k+(-1)^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)$$

$$L(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor \operatorname{mod} 2, R(n,k)=\binom{n+k}{k}$$

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

Вопрос, собственно, очевиден - что и как можно упростить в плане подсчета, например, на PARI?

[deep blue]

Можно попробовать считать рекуррентно, хотя я не проверял насколько получится (потратил на эту задачу пару секунд). Любое короткое сечение доски имеет одно и то же, определенное число конфигураций кромки. В некоторых из этих конфигураций мы можем рассечь исходный путь на два в других на четыре пути (возможно в конфигурации кромки придется еще учесть сколько концов пути -0,1,2 имеются в левой части сечения). Обозначив $L_1(m),L_2(m),..., L_{10}(m)$ как число путей с типовой конфигурацией кромок (предположим их десять) можно получить линейную систему рекуррентных уравнений. Такие системы легко решаются .

[kthxbye]

deep blue в сообщении #1422322 писал(а):

Можно попробовать считать рекуррентно, хотя я не проверял насколько получится (потратил на эту задачу пару секунд).

Рекурсия для вспомогательных функций, которые я привёл выше или для самой $a(n)$?

В сечения и кромки я так к сожалению и не вник, но на всякий случай отмечу, что число возможных путей одинаково для любой стартовой клетки.

В предыдущем случае $n\times2$

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

где все так же

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

существует нелинейная рекурсия

$$a_2(n)=[n=1]\cdot2+[n=2]\cdot8+[n>2]\cdot n(n-1)(a_2(n-1)+a_2(n-2))$$

Как она выводится, если заранее известно представление в виде суммы - для меня до сих пор загадка. Это как-то связано с функциями Бесселя, а там уравнения с производными, сложно. Все это наводит на мысль, что для $n\times3$ рекурсия ещё хитрее и помимо бинома там могут быть $2^n$.

[Dmitriy40]

kthxbye в сообщении #1422344 писал(а):

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

А это утверждение доказано? Что-то для доски $1\times3$ для центральной стартовой клетки решений вообще нет, а для крайних по одному пути.
Для доски $2\times3$ аналогично, для всех 4-х угловых по 3 пути, для двух центральных лишь по два пути - тоже разное количество.
Думаю не равенство сохранится и для любого другого размера.
Ну или я не понял условие задачи.
UPD. Да, не понял. Вопрос снимаю.

[wrest]

kthxbye в сообщении #1422264 писал(а):

Вопрос, собственно, очевиден - что и как можно упростить в плане подсчета, например, на PARI?

Считаться все будет в лучшем виде, а в чём затруднения?
Давайте начнём, что ли, с этого:

kthxbye в сообщении #1422264 писал(а):

$$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)$$

Например, вот это $[0\leqslant i<2]\cdot[n=1]\cdot[k=0]$ значит, что если все условия в квадратных скобках выполнены, то выражение равно единице, иначе нулю?

[Sender]

Dmitriy40 в сообщении #1422349 писал(а):

Ну или я не понял условие задачи.

Ладья может перепрыгивать через клетки, на которых она уже бывала раньше, т.е. граф, обход которого производится, имеет вид $K_3 \square K_n$, как я понимаю.

[wrest]

А, не. Лучше с этой начать. В ней нету других функций.

kthxbye в сообщении #1422264 писал(а):

$$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)$$

Вопрос тот же, по квадратным скобкам.

Вот функция которая вычисляет $h(n,k)$

MH=Map();
h(n,k)={
my(sum1,sum2,factor1,res);
if(mapisdefined(MH,[n,k],&res),return(res));
if(n==1 && k==0,sum1=1,sum1=0);
if(n>1 && k>=0 && k<2^(n-1), factor1=1, factor1=0);
if(factor1==0, mapput(MH,[n,k],sum1);return(sum1));
sum2=1+k%2+(k%2-h(n-1,k\2))\2;
res=sum1+sum2;
mapput(MH,[n,k],res);
return(res);
}

MH -- это запомненные значения функции, на всякий случай.
Вот несколько их, кстати:

h(1, 0)=1
h(2, 0)=0
h(3, 0)=1
h(4, 0)=0
h(5, 0)=1
h(6, 0)=0
h(7, 1)=2
h(8, 2)=0
h(9, 5)=2
h(10, 10)=0

Это правильно посчиталось?

[kthxbye]

Sender в сообщении #1422357 писал(а):

Dmitriy40 в сообщении #1422349 писал(а):

Ну или я не понял условие задачи.

Ладья может перепрыгивать через клетки, на которых она уже бывала раньше, т.е. граф, обход которого производится, имеет вид $K_3 \square K_n$, как я понимаю.

Абсолютно точно. Ладья просто визуально понятнее.

wrest в сообщении #1422353 писал(а):

Например, вот это $[0\leqslant i<2]\cdot[n=1]\cdot[k=0]$ значит, что если все условия в квадратных скобках выполнены, то выражение равно единице, иначе нулю?

Именно так. Если выражение истинно, скобка возвращает 1, если ложно - 0.

wrest в сообщении #1422358 писал(а):

Это правильно посчиталось?

Да, все верно. Значения $h(n,k)\in\left\lbrace0,1,2\right\rbrace$. Она нужна чтобы превращать

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

wrest в сообщении #1422353 писал(а):

Считаться все будет в лучшем виде, а в чём затруднения?

Возрастающее число слагаемых в суммах по $k$ и по $p$.

[wrest]

kthxbye в сообщении #1422403 писал(а):

Возрастающее число слагаемых в суммах по $k$ и по $p$.

Ну знаете, при численном интегрировании слагаемых тоже немало...

kthxbye в сообщении #1422403 писал(а):

Именно так. Если выражение истинно, скобка возвращает 1, если ложно - 0.

Ok, вот вам $f(i,n,k)$

MF=Map();
f(i,n,k)={
my(sum1,sum2,sum3,factor1,res);
if(mapisdefined(MF,[i,n,k],&res),return(res));
if(i >=0 && i<2 && n==1 && k==0, sum1=1,sum1=0);
if(i >=0 && i<3 && n>1 && k>=0 && k<2^(n-1), factor1=1,factor1=0);
if(factor1==0, mapput(MF,[i,n,k],sum1);return(sum1));
if(i==h(n,k),sum2=1,sum2=0);
sum3=f(i,n-1,k\2);
res=sum1+sum2+sum3;
mapput(MF,[i,n,k],res);
return(res);
}

А, погодите, или вы имели в виду что вы на PARI уже всё написали и оно долго считается?

[kthxbye]

wrest в сообщении #1422421 писал(а):

А, погодите, или вы имели в виду что вы на PARI уже всё написали и оно долго считается?

Вообще, да. Но в ваших способах задания функций я все равно постараюсь разобраться.

Вы не пробовали оценить скорость выдачи $a(n)$?

[wrest]

kthxbye в сообщении #1422435 писал(а):

Вы не пробовали оценить скорость выдачи $a(n)$?

Нет, не пробовал.

[deep blue]

Ладно уговорили распишу немного подробнее, во имя квадратных скобочек Айверсона.
Коробит смотреть на эти вложенные суммы, когда существует примитивный линейный алгоритм подсчета для любой доски вида (const , n).
Определим вспомогательную функцию $L_{1,0,0,0}(m)$ как количество элементарных путей либо пар элементарных путей заполняющих всю доску (3,m), не содержащих ни одной вершины типа Х (Назовем вершиной типа X - начало либо конец Гамильтонова пути уже на доске (3,n) а не (3,m)) на доске (3,m). При этом верхняя правая клеточка доски (3,m) помечена единичкой, что означает путь из неё может и должен быть продолжен, при переходе к доске (3,m+1) в рекуррентном соотношении.
Аналогично определяются все 24 вспомогательные функции
$L_{0,1,0,0}(m)$,$L_{0,1,1,0}(m)$, итд. Где последнее число в записи $0,1,1,0$ кодирует количество вершин типа X на доске (3,m). Их может быть 0,1 или 2.

Далее составляем 24 рекуррентных соотношения для каждой из вспомогательных функций.
$L_{0,0,1,0}(m+1)=L_{1,0,0,0}(m)+L_{1,1,1,0}(m)$
$L_{0,1,0,0}(m+1)=0$
$L_{1,0,0,0}(m+1)=L_{0,0,1,0}(m)+L_{1,1,1,0}(m)$
$L_{1,1,0,0}(m+1)=0$
$L_{1,0,1,0}(m+1)=0$
$L_{0,1,1,0}(m+1)=0$
$L_{1,1,1,0}(m+1)=L_{1,1,1,0}(m)+L_{1,0,0,0}(m)+L_{0,0,1,0}(m)$
$L_{1,0,0,1}(m+1)=L_{0,0,1,1}(m)+L_{1,1,1,1}(m)+L_{0,1,1,0}(m)$
$L_{0,1,0,1}(m+1)=0$
...
$L_{1,0,0,2}(m+1)=L_{0,0,1,2}(m)+L_{1,1,1,2}(m)+L_{0,1,1,1}(m)$
...

Конечный ответ получается по очевидной формуле $a(n)=2L_{1,1,1,1}(n-1)+L_{1,0,1,2}(n-1)$

[kthxbye]

deep blue в сообщении #1422502 писал(а):

Ладно уговорили распишу немного подробнее, во имя квадратных скобочек Айверсона.

Выражаю вам благодарность, но к сожалению и здесь суть опять ускользнула от меня. Ну как, я понял что

deep blue в сообщении #1422502 писал(а):

последнее число в записи $0,1,1,0$ кодирует количество вершин типа X на доске (3,m). Их может быть 0,1 или 2.

ровно как и то, что первые три числа это цифры чисел 0-7 в двоичной системе счисления.

Каким образом вы находите рекуррентные соотношения и откуда там столько нулей - большой вопрос. Вполне возможно, что я слишком глуп, чтобы это понять.

Что касается оптимизации, то удалось упростить часть функций, а именно

$$h(n,k), [i=h(n,k)], g(n,k)$$

до значений последовательностей, которые мы легко генерируем в одномерных массивах. Дало это, правда, всего пару новых значений $a(n)$ (за то же время).

[kthxbye]

На днях добавили A329319. Все желающие могут размещать там (либо напрямую в A269565) примитивные линейные алгоритмы, если таковые существуют и возвращают корректные значения (совпадающие, например, с результатом работы какого-нибудь алгоритма перебора). Буду очень признателен.