login
A178722
Number of ways to place 6 nonattacking queens on an n X n toroidal board.
3
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
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
KEYWORD
nonn
AUTHOR
Vaclav Kotesovec, Jun 07 2010
STATUS
approved