A172518 -id:A172518 - cp's OEIS frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

1, 1, 1, 2, 5, 4, 7, 6, 7, 9, 11, 10, 13, 13, 13, 14, 17, 16, 19, 18, 19, 21, 23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47, 46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, 61, 61, 61, 62, 65, 64, 67, 66

Offset: 1

Konrad Schlude, Jul 24 2003

Independence number of the queens' graph on toroidal n X n board. - Andrey Zabolotskiy, Dec 11 2016

			Four non-attacking queens can be placed on a 6 X 6 toroidal board:
......
..Q...
....Q.
.Q....
...Q..
......
But five queens cannot. Hence a(6) = 4.

G. Polya: Über die 'Doppelt-Periodischen' Loesungen des n-Damen-Problems, in: W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner, Leipzig, 1918, 364-374. Reprinted in: G. Polya: Collected Works, Vol. V, 237-247.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001
Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of Logic to Combinatorial Sequences and Their Recurrence Relations
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
P. Monsky, Problem E3162, Amer. Math. Monthly 96 (1989), 258-259.
Konrad Schlude and Ernst Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Computer Science Department ETH Zurich, 2003.

Cf. A051906, A007705, A279402, A279404, A279405, A172517, A172518, A172519, A173775, A178722.

(* Explicit formula, based on an article by Monsky: *)
Table[n-1/6*(2*Cos[Pi*n/2]-3*Cos[Pi*n/3]+5*Cos[2*Pi*n/3]-Cos[Pi*n/6]-Cos[5*Pi*n/6]+3*Cos[Pi*n]+7),{n,1,100}] (* Vaclav Kotesovec, Dec 13 2010 *)

a(n)=n-1/6*(2*cos(Pi*n/2)-3*cos(Pi*n/3)+5*cos(2*Pi*n/3)-cos(Pi*n/6)-cos(5*Pi*n/6)+3*cos(Pi*n)+7);
vector(60,n,round(a(n))) \\ Joerg Arndt, Dec 13 2010

G.f.: (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/(x^13 - x^12 - x + 1) = (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/((x - 1)^2*(x + 1)*(x^2 + 1)*(x^2 - x + 1)*(x^2 + x + 1)*(x^4 - x^2 + 1)). - Joerg Arndt, Dec 13 2010
From Andrey Zabolotskiy, Dec 11 2016: (Start)
a(n) = n if n = 1, 5, 7, 11 (mod 12);
a(n) = n-1 if n = 2, 10 (mod 12);
a(n) = n-2 otherwise.
(End)

A172519 Number of ways to place 4 nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 50, 288, 2450, 16384, 62208, 233600, 638880, 1755072, 3901534, 8772176, 17051850, 33507328, 59175640, 105557904, 173570244, 287904000, 447885774, 702042000, 1044894554, 1565385984, 2247132500, 3244194304, 4519015596

Offset: 1

Vaclav Kotesovec, Feb 05 2010

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (-1, 3, 6, 3, -9, -20, -11, 15, 40, 31, -15, -53, -50, 0, 50, 53, 15, -31, -40, -15, 11, 20, 9, -3, -6, -3, 1, 1).

Cf. A007705, A061994, A172517, A172518, A173775, A178722.

LinearRecurrence[{-1, 3, 6, 3, -9, -20, -11, 15, 40, 31, -15, -53, -50, 0, 50, 53, 15, -31, -40, -15, 11, 20, 9, -3, -6, -3, 1, 1},{0, 0, 0, 0, 0, 50, 288, 2450, 16384, 62208, 233600, 638880, 1755072, 3901534, 8772176, 17051850, 33507328, 59175640, 105557904, 173570244, 287904000, 447885774, 702042000, 1044894554, 1565385984, 2247132500, 3244194304, 4519015596},40] (* Harvey P. Dale, Apr 30 2018 *)

a(n) = (n^8/24 - n^7 + 245n^6/24 - 113n^5/2 + 2843n^4/16 - 593n^3/2 + 4757n^2/24) + (n^6/8 - 5n^5/2 + 305n^4/16 - 129n^3/2 + 629n^2/8)*(-1)^n + 8n^2*cos(2*Pi*n/3)/3 + 9n^2*cos(Pi*n/2)/2.
Recurrence: a(n) = -a(n-1) + 3a(n-2) + 6a(n-3) + 3a(n-4) - 9a(n-5) - 20a(n-6) - 11a(n-7) + 15a(n-8) + 40a(n-9) + 31a(n-10) - 15a(n-11) - 53a(n-12) - 50a(n-13) + 50a(n-15) + 53a(n-16) + 15a(n-17) - 31a(n-18) - 40a(n-19) - 15a(n-20) + 11a(n-21) + 20a(n-22) + 9a(n-23) - 3a(n-24) - 6a(n-25) - 3a(n-26) + a(n-27) + a(n-28), n >= 29. - Vaclav Kotesovec, Feb 09 2010
G.f.: -2*x^5*(287*x^22 + 5191*x^21 + 25616*x^20 + 105043*x^19 + 280800*x^18 + 651461*x^17 + 1186795*x^16 + 1925172*x^15 + 2611064*x^14 + 3190574*x^13 + 3337574*x^12 + 3161250*x^11 + 2574658*x^10 + 1891298*x^9 + 1175308*x^8 + 649556*x^7 + 291897*x^6 + 115771*x^5 + 34682*x^4 + 8835*x^3 + 1294*x^2 + 169*x + 25) / ((x - 1)^9*(x + 1)^7*(x^2 + 1)^3*(x^2 + x + 1)^3). - Colin Barker, Sep 21 2014

A172530 Number of ways to place 3 nonattacking knights on an n X n toroidal board.

Original entry on oeis.org

0, 0, 6, 208, 600, 3252, 10584, 27584, 61992, 125300, 233772, 409584, 682084, 1089172, 1678800, 2510592, 3657584, 5208084, 7267652, 9961200, 13435212, 17860084, 23432584, 30378432, 38955000, 49454132, 62205084

Offset: 1

Vaclav Kotesovec, Feb 06 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes

Cf. A172529, A172134, A172518.

CoefficientList[Series[- 2 x^2 (50 x^9 - 398 x^8 + 1425 x^7 - 2989 x^6 + 3971 x^5 - 3325 x^4 + 1605 x^3 - 365 x^2 + 83 x + 3) / (x - 1)^7, {x, 0, 40}], x] (* Vincenzo Librandi, May 29 2013 *)

a(n) = n^2*(n^4 - 27*n^2 + 218)/6, n>=6.

G.f.: -2*x^3 * (50*x^9 -398*x^8 +1425*x^7 -2989*x^6 +3971*x^5 -3325*x^4 +1605*x^3 -365*x^2 +83*x +3) / (x-1)^7. - Vaclav Kotesovec, Mar 25 2010

More terms from Vincenzo Librandi, May 29 2013

A173775 Number of ways to place 5 nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 10, 0, 882, 13312, 85536, 561440, 2276736, 9471744, 27991470, 85725696, 209107890, 525062144, 1116665944, 2437807104, 4691672964, 9234168960, 16462896030, 29919532544, 50215537658, 85687824384, 136944081500

Offset: 1

Vaclav Kotesovec, Feb 24 2010

Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes.

Cf. A172517, A172518, A172519, A007705, A108792, A061991.

a(n) = (1/120)*n^10 - (1/3)*n^9 + (143/24)*n^8 - (373/6*n^7) + (99377/240)*n^6 - (3603/2)*n^5 + (119627/24)*n^4 - (23833/3)*n^3 + (16342/3)*n^2 + ((1/24)*n^8 - (3/2)*n^7 + (1111/48)*n^6 - (391/2)*n^5 + (7595/8)*n^4 - 2487*n^3 + (8032/3)*n^2)*(-1)^n + ((9/2)*n^4 - 78*n^3 + 374*n^2)*cos(Pi*n/2) + ((8/3)*n^4 - (128/3)*n^3 + (656/3)*n^2)*cos(2*Pi*n/3) + (80/3)*n^2*cos(Pi*n/3) + (16/5)*n^2*cos(2*Pi*n/5) + (16/5)*n^2*cos(Pi*n/5)*(-1)^n.

Recurrence: a(n) = -3a(n-1) - 5a(n-2) - 5a(n-3) + 2a(n-4) + 17a(n-5) + 37a(n-6) + 49a(n-7) + 35a(n-8) - 16a(n-9) - 101a(n-10) - 185a(n-11) - 215a(n-12) - 139a(n-13) + 56a(n-14) + 321a(n-15) + 544a(n-16) + 588a(n-17) + 368a(n-18) - 99a(n-19) - 656a(n-20) - 1069a(n-21) - 1111a(n-22) - 689a(n-23) + 84a(n-24) + 929a(n-25) + 1488a(n-26) + 1506a(n-27) + 939a(n-28) - 939a(n-30) - 1506a(n-31) - 1488a(n-32) - 929a(n-33) - 84a(n-34) + 689a(n-35) + 1111a(n-36) + 1069a(n-37) + 656a(n-38) + 99a(n-39)-368a(n-40) - 588a(n-41) - 544a(n-42) - 321a(n-43) - 56a(n-44) + 139a(n-45) + 215a(n-46) + 185a(n-47) + 101a(n-48) + 16a(n-49) - 35a(n-50) - 49a(n-51) - 37a(n-52) - 17a(n-53) - 2a(n-54) + 5a(n-55) + 5a(n-56) + 3a(n-57) + a(n-58).

A190398 Number of ways to place 3 nonattacking grasshoppers on a toroidal chessboard of size n x n.

Original entry on oeis.org

0, 4, 72, 496, 2100, 6708, 17640, 40384, 83376, 158900, 284108, 482160, 783484, 1227156, 1862400, 2750208, 3965080, 5596884, 7752836, 10559600, 14165508, 18742900, 24490584, 31636416, 40440000, 51195508, 64234620, 79929584

Offset: 1

Vaclav Kotesovec, May 10 2011

The Grasshopper moves on the same lines as a queen, but must jump over a hurdle to land on the square immediately beyond.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens, kings, bishops and knights (in English and Czech)

Cf.: A190395, A172518.

CoefficientList[Series[- 4 x (3 x^8 - 17 x^7 + 37 x^6 - 35 x^5 + 11 x^4 + 19 x^2 + 11 x + 1) / (x - 1)^7, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 02 2013 *)

a(n) = 1/6*n^2*(n^4 -3*n^2 -24*n +74), n>3.

G.f.: -4*x^2*(3*x^8 -17*x^7 +37*x^6 -35*x^5 +11*x^4 +19*x^2 +11*x +1)/(x-1)^7.

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

Original entry on oeis.org

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

Vaclav Kotesovec, Jun 07 2010

nonn

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

Artem M. Karavaev, Zealint blog (in Russian)
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013
Vaclav Kotesovec, G.f.

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

(* 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

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

A178973 Number of ways to place 3 nonattacking amazons (superqueens) on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 588, 3328, 9720, 27600, 59048, 124992, 226460, 408464, 666900, 1086464, 1650768, 2505168, 3610000, 5198400, 7191828, 9945232, 13320220, 17835264, 23265000, 30341584, 38718648, 49401408, 61880780, 77504400, 95550308, 117788672, 143225280, 174144464, 209210400, 251325504, 298732228, 355068048, 418062060, 492217600

Offset: 1

Vaclav Kotesovec, Jan 02 2011

An amazon (superqueen) moves like a queen and a knight.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013

Cf. A172201, A172518, A178972.

CoefficientList[Series[- 4 x^6 (36 x^11 - 47 x^10 - 178 x^9 + 228 x^8 + 354 x^7 - 419 x^6 - 356 x^5 + 297 x^4 + 182 x^3 + 178 x^2 + 538 x + 147) / ((x - 1)^7 (x + 1)^5), {x, 0, 50}], x] (* Vincenzo Librandi, May 31 2013 *)

a(n) = 1/3*n^2*(n^4/2 -6*n^3 +61*n^2/4 +42*n -285/2 +(3*n^2/4 -6*n +21/2)*(-1)^n), n>=7.

G.f.: -4*x^7 * (36*x^11 -47*x^10 -178*x^9 +228*x^8 +354*x^7 -419*x^6 -356*x^5 +297*x^4 +182*x^3 +178*x^2 +538*x +147)/((x-1)^7*(x+1)^5).

A178720 Degree of denominator of GF for number of ways to place k nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

3, 8, 12, 28, 58, 142, 350, 906, 2320, 6056, 15778, 41024, 107132, 280184, 732998, 1918354, 5019810, 13141378, 34398686, 90045424, 235729374, 617126438, 1615633560, 4229774958, 11073514332, 28990794770, 75898640094, 198704554772

Offset: 1

Vaclav Kotesovec, Jun 07 2010

nonn

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

A172517, A172518, A172519, A173775, A000010, A000045, A178717.

Table[If[k > 1, 4*k + Sum[ Sum[(2*j + 1)*EulerPhi[i], {i, 2*Fibonacci[k - j - 1] + 1, 2*Fibonacci[k - j]}], {j, 1, k - 2}], 3], {k, 1, 20}]

Explicit formula (Vaclav Kotesovec, Jun 05 2010), for k>2 : t(k) = 4*k+Sum[Sum[(2*j+1)*EulerPhi[i],{i,2*Fibonacci[k-j-1]+1,2*Fibonacci[k-j]}],{j,1,k-2}], Asymptotic formula: t(k) ~ 12/(5*Pi^2)*((1+Sqrt[5])/2)^(2*k+1) or t(k) ~ 6*(1+Sqrt[5])/Pi^2*Fibonacci[k]^2

cp's OEIS Frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A172519 Number of ways to place 4 nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A172530 Number of ways to place 3 nonattacking knights on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A173775 Number of ways to place 5 nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Formula

A190398 Number of ways to place 3 nonattacking grasshoppers on a toroidal chessboard of size n x n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A178973 Number of ways to place 3 nonattacking amazons (superqueens) on an n X n toroidal board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A178720 Degree of denominator of GF for number of ways to place k nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula