A178722 Number of ways to place 6 nonattacking queens on an n X n toroidal board.

0, 0, 0, 0, 0, 0, 196, 3072, 42768, 550000, 3573856, 25009344, 102800672, 454967744, 1441238400, 4811118592, 12616778208, 34692705648, 79514466480, 189770459200, 392908083876, 842040318416, 1610365515264, 3172863442176, 5692888800000

Offset

1,7

Comments

Previous recurrence (order 142) was right, but Artem M. Karavaev and his team found (Jun 19 2011) another recurrence with smaller order (124).

Links

Table of n, a(n) for n=1..25.

Artem M. Karavaev, Zealint blog (in Russian)

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013

Vaclav Kotesovec, G.f.

Formula

Explicit formula (Artem M. Karavaev, after values computed by Andrey Khalyavin, Jun 19 2011):

n^2/6*(n^10/120-5*n^9/8+125*n^8/6-3275*n^7/8+316073*n^6/60-371219*n^5/8+282695*n^4-4676911*n^3/4+15512322*n^2/5-4626944*n+2452536

+(n^8/4-14*n^7+1411*n^6/4-5227*n^5+199399*n^4/4-313302*n^3+2530255*n^2/2-2984844*n+3117968)*Floor[n/2]

+(24*n^4-864*n^3+12852*n^2-95112*n+309128)*Floor[n/3]+(12*n^4-432*n^3+6180*n^2-42384*n+117584)*Floor[(n+1)/3]

+(27*n^4-1044*n^3+16044*n^2-118296*n+350388)*Floor[n/4]+(27*n^4-1044*n^3+16044*n^2-118296*n+360348)*Floor[(n+1)/4]

+(96*n^2-1920*n+22248)*Floor[n/5]+(48*n^2-960*n+10224)*Floor[(n+1)/5]+(48*n^2-960*n+12024)*Floor[(n+2)/5]+(48*n^2-960*n+10224)*Floor[(n+3)/5]

+(492*n^2-10344*n+73960)*Floor[(n+1)/6]

+1968*Floor[n/7]+984*Floor[(n+1)/7]+984*Floor[(n+2)/7]+984*Floor[(n+3)/7]+984*Floor[(n+4)/7]+984*Floor[(n+5)/7]

+9960*Floor[n/8]+9960*Floor[(n+3)/8]

+1800*Floor[(n+1)/10]-1800*Floor[(n+2)/10]+1800*Floor[(n+3)/10]).

Alternative formula (Vaclav Kotesovec, after values computed by Andrey Khalyavin, Jun 20 2011):

a(n) = 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])).

Recurrence: a(n) = a(n-124) + 5a(n-123) + 19a(n-122) + 53a(n-121) + 126a(n-120) + 256a(n-119) + 460a(n-118) + 731a(n-117) + 1024a(n-116) + 1234a(n-115) + 1180a(n-114) + 631a(n-113) - 677a(n-112) - 2917a(n-111) - 6108a(n-110) - 9923a(n-109) - 13657a(n-108) - 16137a(n-107) - 15876a(n-106) - 11304a(n-105) - 1172a(n-104) + 14879a(n-103) + 35916a(n-102) + 59190a(n-101) + 80301a(n-100) + 93334a(n-99) + 92030a(n-98) + 70850a(n-97) + 26815a(n-96) - 39130a(n-95) - 120942a(n-94) - 207185a(n-93) - 282105a(n-92) - 327419a(n-91) - 326009a(n-90) - 265142a(n-89) - 140929a(n-88) + 39571a(n-87) + 256518a(n-86) + 479114a(n-85) + 668872a(n-84) + 785798a(n-83) + 795775a(n-82) + 677688a(n-81) + 430187a(n-80) + 74064a(n-79) - 347112a(n-78) - 773130a(n-77) - 1134433a(n-76) - 1364780a(n-75) - 1412189a(n-74) - 1250448a(n-73) - 885628a(n-72) - 357906a(n-71) + 262286a(n-70) + 885029a(n-69) + 1413752a(n-68) + 1762777a(n-67) + 1870496a(n-66) + 1712484a(n-65) + 1305033a(n-64) + 705009a(n-63) - 705009a(n-61) - 1305033a(n-60) - 1712484a(n-59) - 1870496a(n-58) - 1762777a(n-57) - 1413752a(n-56) - 885029a(n-55) - 262286a(n-54) + 357906a(n-53) + 885628a(n-52) + 1250448a(n-51) + 1412189a(n-50) + 1364780a(n-49) + 1134433a(n-48) + 773130a(n-47) + 347112a(n-46) - 74064a(n-45) - 430187a(n-44) - 677688a(n-43) - 795775a(n-42) - 785798a(n-41) - 668872a(n-40) - 479114a(n-39) - 256518a(n-38) - 39571a(n-37) + 140929a(n-36) + 265142a(n-35) + 326009a(n-34) + 327419a(n-33) + 282105a(n-32) + 207185a(n-31) + 120942a(n-30) + 39130a(n-29) - 26815a(n-28) - 70850a(n-27) - 92030a(n-26) - 93334a(n-25) - 80301a(n-24) - 59190a(n-23) - 35916a(n-22) - 14879a(n-21) + 1172a(n-20) + 11304a(n-19) + 15876a(n-18) + 16137a(n-17) + 13657a(n-16) + 9923a(n-15) + 6108a(n-14) + 2917a(n-13) + 677a(n-12) - 631a(n-11) - 1180a(n-10) - 1234a(n-9) - 1024a(n-8) - 731a(n-7) - 460a(n-6) - 256a(n-5) - 126a(n-4) - 53a(n-3) - 19a(n-2) - 5a(n-1).

Mathematica

(* General formulas (denominator and recurrence) for k nonattacking queens on an n X n toroidal board: *) inversef[j_]:=(m=2; While[j>2*Fibonacci[m-1], m=m+1]; m); denomt[k_, par_]:=(x-1)^(2k+1)*Product[Cyclotomic[j, x]^(2*(k-inversef[j]+1)+par), {j, 2, 2*Fibonacci[k-1]}]; Table[denomt[k, 1], {k, 1, 7}]//TraditionalForm Table[Sum[Coefficient[Expand[denomt[k, 1]], x, i]*Subscript[a, n-i], {i, 0, Exponent[denomt[k, 1], x]}], {k, 1, 7}]//TraditionalForm

Crossrefs

Cf. A172517, A172518, A172519, A173775, A178720.

Sequence in context: A251308 A251301 A277792 * A061622 A128990 A061619

Adjacent sequences: A178719 A178720 A178721 * A178723 A178724 A178725

Keyword

nonn

Author

Vaclav Kotesovec, Jun 07 2010

Status

approved