Foreword (for English-speaking readers)

After the formula for 6 queens problem on n×n chessboard had been obtained, Vaclav Kotesovec gave a hypothesis of recurrence for 7,8, … queens problem and for 6,7, … queens problem on a toroidal chessboard. It was suggested that the recurrence for 6 queens problem on an n×n toroidal chessboard has the order 142. This recurrence is right, but we found another recurrence with smaller order (124). We will explain the difference below (in Russian). These results were obtained thanks to O(n5) program written by Andrey Khalyavin. He calculated necessary values up to n=81.

————————————————————

Конкурс завершён досрочно, поскольку Андрей Халявин предоставил необходимое количество чисел (и даже больше – 81 шт.), которых оказалось достаточно для проверки гипотезы. Здесь я объясню, что из этого всего получилось. Забегая вперед, сообщу, что гипотеза о виде рекуррентного соотношения хоть и была правильной, но соотношение имело не минимальный порядок. Минимальный порядок будет 124, а не 142. Так же я объясню, как из 142 получить 78 для этой задачи, благодаря чему и удалось решить её так быстро. Для понимания объяснений читатель должен быть немного знаком с производящими функциями.

Обозначим Q6t(n) – число способов расставить 6 не бьющих друг друга ферзей на тороидальной доске размером n×n.

Можно строго показать (но мы не будем этого делать), что Q6t(n) является квазиполиномом (грубо говоря, это полиномом, в котором также присутствует целая часть от деления на некоторые константы). Такое доказательство может быть основано на составлении системы линейных ограничений (а расстановка ферзей может быть записана именно линейными ограничениями). Число целых точек внутри множества, порождаемого линейными ограничениями, будет описываться именно квазиполиномом (это считается известным). Из этого следует, что корни производящей функции (которая обязательно будет рациональной), порождающей последовательность (Q6t(n)), будут по модулю равны 1. Если бы они не были равны 1, то последовательность (Q6t(n)) была бы экспоненциальной.

Таким образом, знаменатель производящей функции представляет собой произведение разнообразных делителей полиномов вида (1-zP). То есть, например, для нашей задачи было сделано предположение, что знаменатель имеет вид

(z^4-z^3+z^2-z+1)^3*(z^6+z^5+z^4+z^3+z^2+z+1)^3*(z^4+1)^3*(z^2-z+1)^5*(z^4+z^3+z^2+z+1)^5*(z^2+1)^7*(z^2+z+1)^7*(z+1)^11*(z-1)^13*(z^6+z^3+1)^3

Это предположение было сделано в книге Vaclav Kotesovec про расстановки шахматных фигур (скачать можно с сайта автора).

Каждый из множителей здесь является делителем полинома (1-zP) (если подобрать нужное P), например, (1-z5) / (z4+z3+z2+z+1)=1-z. Степень знаменателя показывает порядок рекуррентного соотношения. Здесь она равна 142, но так как числитель неизвестен, заранее трудно было угадать, что множитель (z6+z3+1)3 окажется лишним. Он сокращается с аналогичным множителем в числителе. Числитель полностью зависит от начальных данных, а они не были известны. Итак, знаменатель имеет степень 142-18=124.

Далее, обозначим через Q6tF(n) ответ к нашей задаче, когда первый ферзь занимает клетку A1. Тогда Q6t(n) = Q6tF(n)⋅n2/6;

Из теории производящий функций известно, что если у нас есть последовательность (an), которая генерируется функцией G(z), то последовательность (n⋅an) генерируется функцией z⋅DG(z) (то есть производящую функцию нужно продифференцировать и домножить на z). Применение оператора zD дважды даст (n2⋅an). Таким образом, если ответ для Q6tF(n) известен, то двойное дифференцирование даст ответ для Q6t(n). А двойное дифференцирование на 2 увеличивает степень каждого множителя в знаменателе производящей функции. То есть знаменатель не дифференцированной функции (для Q6tF(n)) должен иметь вид:

(z^4-z^3+z^2-z+1)*(z^6+z^5+z^4+z^3+z^2+z+1)*(z^4+1)*(z^2-z+1)^3*(z^4+z^3+z^2+z+1)^3*(z^2+1)^5*(z^2+z+1)^5*(z+1)^9*(z-1)^11*(z^6+z^3+1)

Он имеет степень 78, то есть рекуррентное соотношение для Q6tF(n) имеет порядок 78, благодаря чему нам и потребовалось знать всего 80 первых чисел. Но если убрать лишний множитель (z6+z3+1), то порядок будет 72.

Таким образом, соотношение для Q6tF(n) будет иметь вид (получается путём раскрытия скобок в знаменателе производящей функции)

Q6tF(n) = Q6tF(n-72) + 3*Q6tF(n-71) + 6*Q6tF(n-70) + 8*Q6tF(n-69) + 5*Q6tF(n-68) — 5*Q6tF(n-67) — 24*Q6tF(n-66) — 45*Q6tF(n-65) — 59*Q6tF(n-64) — 52*Q6tF(n-63) — 14*Q6tF(n-62) + 53*Q6tF(n-61) + 135*Q6tF(n-60) + 200*Q6tF(n-59) + 218*Q6tF(n-58) + 160*Q6tF(n-57) + 27*Q6tF(n-56) — 159*Q6tF(n-55) — 346*Q6tF(n-54) — 472*Q6tF(n-53) — 488*Q6tF(n-52) — 364*Q6tF(n-51) — 122*Q6tF(n-50) + 193*Q6tF(n-49) + 497*Q6tF(n-48) + 714*Q6tF(n-47) + 778*Q6tF(n-46) + 664*Q6tF(n-45) + 391*Q6tF(n-44) + 13*Q6tF(n-43) — 382*Q6tF(n-42) — 714*Q6tF(n-41) — 902*Q6tF(n-40) — 912*Q6tF(n-39) — 734*Q6tF(n-38) — 409*Q6tF(n-37) + 409*Q6tF(n-35) + 734*Q6tF(n-34) + 912*Q6tF(n-33) + 902*Q6tF(n-32) + 714*Q6tF(n-31) + 382*Q6tF(n-30) — 13*Q6tF(n-29) — 391*Q6tF(n-28) — 664*Q6tF(n-27) — 778*Q6tF(n-26) — 714*Q6tF(n-25) — 497*Q6tF(n-24) — 193*Q6tF(n-23) + 122*Q6tF(n-22) + 364*Q6tF(n-21) + 488*Q6tF(n-20) + 472*Q6tF(n-19) + 346*Q6tF(n-18) + 159*Q6tF(n-17) — 27*Q6tF(n-16) — 160*Q6tF(n-15) — 218*Q6tF(n-14) — 200*Q6tF(n-13) — 135*Q6tF(n-12) — 53*Q6tF(n-11) + 14*Q6tF(n-10) + 52*Q6tF(n-9) + 59*Q6tF(n-8) + 45*Q6tF(n-7) + 24*Q6tF(n-6) + 5*Q6tF(n-5) — 5*Q6tF(n-4) — 8*Q6tF(n-3) — 6*Q6tF(n-2) — 3*Q6tF(n-1).

Вывод формулы

Производящую функцию, знаменатель которой факторизуется, можно разбить на сумму простых дробей. Так как каждый множитель в знаменателе является делителем полинома (1-zP), мы всегда можем домножить числитель и знаменатель на нужный полином, получив знаменатели всех простых дробей в виде (1-zP)Q (числа P и Q могут быть разными у разных дробей).

Например, если в знаменателе есть множитель (z2+1)5, то он будет соответствовать простой дроби S(z) / (z2+1)5= S(z) ⋅ (1-z2) / (1-z4)5, где S(z) — некоторый многочлен, который нас сейчас не интересует (он получается из числителя исходной производящей функции, когда мы разбиваем на простые дроби). Когда в знаменателе дроби стоит терм (1-zP), то он означает, что последовательность будет иметь вид 1,0,0,…,1,0,0,…,1 (период равен P). А такая последовательность может быть записана в виде разности двух функций [x] (целая часть x). Например, 1,0,1,0,1,0,… можно представить как [n/2]-[(n-1)/2]. Степень Q у полинома в знаменателе показывает, что разницу этих функций [x] нужно умножить на полином степени Q-1.

Получим алгоритм вывода формулы в виде квазиполинома: (1) разбить производящую функцию на простые дроби; (2) домножить числитель и знаменатель простых дробей на такие полиномы, чтобы в знаменателе получились функции вида (1-zP)Q; (3) разложить каждую простую дробь в ряд по степеням z, зная, что она представима в виде разности двух функций [z], умноженных на полином степени Q-1; (4) упростить полученное выражение. Все это, кроме шага (4) делается средствами систем компьютерной алгебры типа Maple без особых усилий. Шаг 4 – творческая задача, тут нужно заметить, что некоторые выражения с floor могут быть упрощены достаточно хитрым и не формализуемым способом.

У нас получилась вот такая формула:

Q6t(n) = n^2/6*
(1/120*(n-1)*(n^9-74*n^8+2426*n^7-46699*n^6+585447*n^5
-4981398*n^4+28888722*n^3-110589888*n^2 +255107040*n-273598080)
+1/4*(n^8-56*n^7+1411*n^6-20908*n^5+199507*n^4-1257384*n^3
+5124686*n^2-12412560*n+13866224)
*floor(n/2)
+2*(6*n^4-216*n^3+3213*n^2-23778*n+77282)*(floor(n/3)-floor((n-1)/3))
-3*(9*n^4-348*n^3+5348*n^2-39432*n+118456)*(floor((n+2)/4)-floor((n+1)/4))
+12*(4*n^2-80*n+927)*(floor(n/5)-floor((n-1)/5))
-2*(123*n^2-2586*n+18490)*(floor((n+4)/6)-floor((n+1)/6))
+984*(floor(n/7)-floor((n-1)/7))
+4980*((floor(n/8)-floor((n-1)/8))-(floor((n+4)/8)-floor((n+3)/8)))
+900*((floor(n/10)-floor((n-1)/10))-(floor((n+5)/10)-floor((n+4)/10))))

Лучше, конечно, скачать PDF вариант. Распечатать и повесить в рамочке на стенку.

Vaclav Kotesovec благодарит участников конкурса за предоставленные ему данные и за помощь в уточнении его гипотез. Он также сообщает, что вид знаменателя для 7 ферзей на обычной доске им обоснован достаточно строго, но что будет для 8 ферзей не совсем ясно. Также теперь неясно, что будет на торе для 7 ферзей. Vaclav ещё выслал мне аналогичную формулу, но в тригонометрическом базисе (в формате системы Mathematica):

n^2*(n^10/720-n^9/12+661*n^8/288-153*n^7/4+615887*n^6/1440
-80581*n^5/24+1801697*n^4/96-295355*n^3/4
+9389033*n^2/48-626899*n/2+142789469/630
+(n^8/96-7*n^7/12+1411*n^6/96-5227*n^5/24+199399*n^4/96
-52217*n^3/4+843309*n^2/16-745349*n/6+2315441/18)*(-1)^n
+(9*n^4/4-87*n^3+1337*n^2-9858*n+29614)*Cos[Pi*n/2]
+2*(123*n^2-2586*n+18490)*Cos[Pi*n/3]/9+2*(6*n^4-216*n^3+3213*n^2-23778*n+77282)*Cos[2*Pi*n/3]/9
+415*(Cos[Pi*n/4]+Cos[3*Pi*n/4])
+8/5*Cos[Pi*n/5]*(75*Cos[2*Pi*n/5]+(927-80*n+4*n^2)*Cos[3*Pi*n/5])
+328/7*(Cos[2*Pi*n/7]+Cos[4*Pi*n/7]+Cos[6*Pi*n/7]))

[ Дополнение 22.06.2011 ]: Vaclav также прислал формулу в виде картинки (можно увеличить, нажав на неё):

Формула в тригонометрическом базисе

В какой-то степени её можно назвать более изящной, но считать по ней можно, лишь соблюдая высокую точностью вещественных чисел. Эта формула была частично им упрощена вручную, так как математические пакеты с такими выражениями работают плохо (особенно с cos (…*Pi/7)).

Обсуждение проходит на форуме в этой теме. Обсуждение итогов начинается отсюда.