A244081 -id:A244081 - cp's OEIS frontend

A172132 Number of ways to place 2 nonattacking knights on an n X n board.

0, 6, 28, 96, 252, 550, 1056, 1848, 3016, 4662, 6900, 9856, 13668, 18486, 24472, 31800, 40656, 51238, 63756, 78432, 95500, 115206, 137808, 163576, 192792, 225750, 262756, 304128, 350196, 401302, 457800, 520056, 588448, 663366

Offset: 1

Vaclav Kotesovec, Jan 26 2010

E. Bonsdorff, K. Fabel, O. Riihimaa, Schach und Zahl, 1966, p. 51-63

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
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A036464, A172123.

Column k=2 of A244081.

I:=[0, 6, 28, 96, 252]; [n le 5 select I[n] else 5*Self(n-1)-10*Self(n-2)+10*Self(n-3)-5*Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Apr 30 2013

[(n-1)*(n+4)*(n^2-3*n+4)/2: n in [1..40]]; // Vincenzo Librandi, Apr 30 2013

Table[(n-1)(n+4)(n^2 -3n +4)/2, {n, 40}] (* Vincenzo Librandi, Apr 30 2013 *)

[(n-1)*(n+4)*(n^2-3*n+4)/2 for n in (1..40)] # G. C. Greubel, Apr 18 2022

a(n) = (n - 1)*(n + 4)*(n^2 - 3*n + 4)/2.
G.f.: 2*(12*x^4-39*x^3+37*x^2-20*x+4)/(x-1)^5. - Vaclav Kotesovec, Mar 25 2010
a(n) = 5*a(n-1)-10*a(n-2)+10*a(n-3)-5*a(n-4)+a(n-5). - Vincenzo Librandi, Apr 30 2013
E.g.f.: (1/2)*(16 + (-16 + 16*x - 2*x^2 + 6*x^3 + x^4)*exp(x)). - G. C. Greubel, Apr 18 2022

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

Original entry on oeis.org

0, 4, 36, 276, 1360, 4752, 13340, 32084, 68796, 135040, 247152, 427380, 705144, 1118416, 1715220, 2555252, 3711620, 5272704, 7344136, 10050900, 13539552, 17980560, 23570764, 30535956, 39133580, 49655552, 62431200, 77830324

Offset: 1

Vaclav Kotesovec, Jan 26 2010

E. Bonsdorff, K. Fabel, O. Riihimaa, Schach und Zahl, 1966, p. 51-63

Vincenzo Librandi, 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 (7,-21,35,-35,21,-7,1).

Cf. A047659, A172124, A172132.

Column k=3 of A244081.

[n le 3 select (n*(n-1))^2 else (n-2)*(n+5)*(n^4 -3*n^3 -8*n^2 +66*n -108)/6: n in [1..50]]; // G. C. Greubel, Apr 18 2022

CoefficientList[Series[4x(3x^8 -20x^7 +43x^6 -38x^5 +23x^4 -11x^3 -27x^2 -2x -1)/ (x-1)^7, {x, 0, 40}], x] (* Vincenzo Librandi, May 02 2013 *)

def A172134(n):
    if (n<4): return (n*(n-1))^2
    else: return (n-2)*(n+5)*(n^4 -3*n^3 -8*n^2 +66*n -108)/6
[A172134(n) for n in (1..50)] # G. C. Greubel, Apr 18 2022

Explicit formula (Karl Fabel, 1966): a(n) = (n - 2)*(n + 5)*(n^4 - 3*n^3 - 8*n^2 + 66*n - 108)/6, for n >= 4.
G.f.: 4*x^2*(3*x^8-20*x^7+43*x^6-38*x^5+23*x^4-11*x^3-27*x^2-2*x-1)/(x-1)^7. - Vaclav Kotesovec, Mar 25 2010
From G. C. Greubel, Apr 18 2022: (Start)
a(n) = 7*a(n-1) -21*a(n-2) +35*a(n-3) -35*a(n-4) +21*a(n-5) -7*a(n-6) +a(n-7), for n >= 11.
E.g.f.: (1/6)*(-1080 - 312*x + 12*x^2 +13*x^3 + (1080 - 768*x + 228*x^2 + 38*x^4 + 15*x^5 + x^6)*exp(x)). (End)

A030978 Maximal number of non-attacking knights on an n X n board.

Original entry on oeis.org

0, 1, 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98, 113, 128, 145, 162, 181, 200, 221, 242, 265, 288, 313, 338, 365, 392, 421, 450, 481, 512, 545, 578, 613, 648, 685, 722, 761, 800, 841, 882, 925, 968, 1013, 1058, 1105, 1152, 1201, 1250, 1301, 1352, 1405

Offset: 0

Eric W. Weisstein

In other words, independence number of the n X n knight graph. - Eric W. Weisstein, May 05 2017

H. E. Dudeney, The Knight-Guards, #319 in Amusements in Mathematics; New York: Dover, p. 95, 1970.
J. S. Madachy, Madachy's Mathematical Recreations, New York, Dover, pp. 38-39 1979.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Knights Problem
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Agrees with A000982 for n>1.

Cf. A244081.

CoefficientList[Series[x (2 x^5 - 4 x^4 + 3 x^2 - 2 x - 1)/((x - 1)^3 (x + 1)), {x, 0, 60}], x] (* Vincenzo Librandi, Oct 19 2013 *)
Join[{0, 1, 4}, Table[If[EvenQ[n], n^2/2, (n^2 + 1)/2], {n, 3, 60}]] (* Harvey P. Dale, Nov 28 2014 *)
Join[{0, 1, 4}, LinearRecurrence[{2, 0, -2, 1}, {5, 8, 13, 18}, 60]] (* Harvey P. Dale, Nov 28 2014 *)
Table[If[n == 2, 4, (1 - (-1)^n + 2 n^2)/4], {n, 20}] (* Eric W. Weisstein, May 05 2017 *)
Table[Length[FindIndependentVertexSet[KnightTourGraph[n, n]][[1]]], {n, 20}] (* Eric W. Weisstein, Jun 27 2017 *)

a(n) = 4 if n = 2, n^2/2 if n even > 2, (n^2+1)/2 if n odd > 1.
a(n) = 4 if n = 2, (1 + (-1)^(1 + n) + 2 n^2)/4 otherwise.
G.f.: x*(2*x^5-4*x^4+3*x^2-2*x-1) / ((x-1)^3*(x+1)). [Colin Barker, Jan 09 2013]

More terms from Erich Friedman

Definition clarified by Vaclav Kotesovec, Sep 16 2014

A141243 Number of ways to place non-attacking knights on the n X n board.

Original entry on oeis.org

1, 2, 16, 94, 1365, 55213, 3368146, 394631712, 101693175442, 50929053498909, 48988729226134301, 96325314726538906164, 375615195988659173454092, 2933480442104347575000834468, 45480806737377995771543610802659, 1422902021111889804120495149240353936

Offset: 0

Max Alekseyev, Jun 17 2008

The maximum number of non-attacking knights is given by A030978.

Also the number of vertex covers and independent vertex sets in the n X n knight graph.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-72, 283-285.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A182407, A182408, A201540.

Row sums of A244081.

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f &, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True &, d]]], True, For[k = 1, ! l[[k]], k++]; g = ReplacePart[l, k -> f];
     If[k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If[k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If[k > 2, g = ReplacePart[g, d - 2 + k -> f]];
     If[k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True &, n*3]]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

A141243(n=4, s=n^2-1, bad=0)={ while(s && bittest(bad, s), s--);
   if(s < n, 2^(s+1-hammingweight(bad % (2<A141243(n, s-1, bad), x = s%n);
      x > 1 && bad = bitor(bad, 2^(s-n-2)); x < n-2 && bad = bitor(bad, 2^(s-n+2));
      if( s >= 2*n, x && bad = bitor(bad, 2^(s-2*n-1));
              x < n-1 && bad = bitor(bad, 2^(s-2*n+1))
   ); cnt + A141243(n, s-1, bad))} \\ M. F. Hasler, Mar 18 2025

def A141243(n=4, start=(1,1), forbidden=()):
    if start[0] >= n: return 2**sum((n,y+1) not in forbidden for y in range(n))
    nxt = (start[0],start[1]+1) if start[1]A141243(n, nxt, forbidden)
    if start in forbidden: return cnt
    forbidden = {s for s in forbidden if s >= nxt}
    if start[1]2: forbidden |= {(start[0]+1,start[1]-2)}
    if start[0]1: forbidden |= {(start[0]+2,start[1]-1)}
    return cnt+A141243(n, nxt, forbidden) # M. F. Hasler, Mar 17 2025

a(8)-a(13) from R. H. Hardin, Aug 25 2008
a(0) from Alois P. Heinz, Jun 19 2014
a(14) from Hiroaki Yamanouchi, Aug 28 2014
a(15) from Hiroaki Yamanouchi, Aug 29 2014

A172135 Number of ways to place 4 nonattacking knights on an n X n board.

Original entry on oeis.org

0, 1, 18, 412, 4436, 26133, 111066, 376560, 1080942, 2732909, 6253408, 13204356, 26100160, 48819677, 87137934, 149398608, 247349946, 397168485, 620696612, 946921684, 1413726108, 2069939461, 2977725410, 4215337872

Offset: 1

Vaclav Kotesovec, Jan 26 2010

E. Bonsdorff, K. Fabel, O. Riihimaa, Schach und Zahl, 1966, p. 51-63

Vincenzo Librandi, 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 (9,-36,84,-126,126,-84,36,-9,1).

Cf. A061994, A172127, A172132, A172134.

Column k=4 of A244081.

[0,1,18,412,4436] cat [(n^8 -54*n^6 +144*n^5 +1019*n^4 -5232*n^3 -2022*n^2 +51120*n -77184)/24: n in [6..50]]; // G. C. Greubel, Apr 19 2022

CoefficientList[Series[x*(1 +9*x +286*x^2 +1292*x^3 -345*x^4 +3099*x^5 -5142*x^6 +3606*x^7 -1162*x^8 -390*x^9 +690*x^10 -312*x^11 +48*x^12)/(1-x)^9, {x, 0, 40}], x] (* Vincenzo Librandi, May 26 2013 *)

[0,1,18,412,4436] + [(n^8 -54*n^6 +144*n^5 +1019*n^4 -5232*n^3 -2022*n^2 +51120*n -77184)/24 for n in (6..50)] # G. C. Greubel, Apr 19 2022

a(n) = (n^8 - 54*n^6 + 144*n^5 + 1019*n^4 - 5232*n^3 - 2022*n^2 + 51120*n - 77184)/24, n >= 6. (Karl Fabel, 1966)
G.f.: x^2 * ( 1 + 9*x + 286*x^2 + 1292*x^3 - 345*x^4 +3099*x^5 - 5142*x^6 + 3606*x^7 - 1162*x^8 - 390*x^9 + 690*x^10 - 312*x^11 + 48*x^12) / (1-x)^9. - Vaclav Kotesovec, Mar 25 2010
E.g.f.: x^2/2! + 18*x^3/3! + 412*x^4/4! + 4436*x^5/5! + (1/120)*(385920 + 161040*x + 17940*x^2 - 1200*x^3 - 2660*x^4 - 4484*x^5 + (-385920 + 224880*x - 49860*x^2 + 2940*x^3 + 3250*x^4 + 1920*x^5 + 1060*x^6 + 140*x^7 + 5*x^8)*exp(x)). - G. C. Greubel, Apr 19 2022

A172136 Number of ways to place 5 nonattacking knights on an n X n board.

Original entry on oeis.org

0, 0, 2, 340, 9386, 97580, 649476, 3184708, 12472084, 41199404, 119171110, 309957412, 739123094, 1639655452, 3422020324, 6778432292, 12833460256, 23356032940, 41051290730, 69954580804

Offset: 1

Vaclav Kotesovec, Jan 26 2010

For any fixed value of k>1, a(n) = n^(2*k) /k! - 9*n^(2*k - 2) /2/(k - 2)! + 12*n^(2*k - 3) /(k - 2)! + ...

Vincenzo Librandi, 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 (11,-55,165,-330,462,-462,330,-165,55,-11,1).

Cf. A108792, A172129, A172132, A172134, A172135.

Column k=5 of A244081.

CoefficientList[Series[2x^2(74 x^15 -518x^14 +1110x^13 +1046x^12 -11332x^11 + 29950x^10 -42430x^9 +32476x^8 -11684x^7 -1000x^6 +15021x^5 -18443x^4 -6352x^3 - 2878x^2 -159x -1)/(x-1)^11, {x,0,40}], x] (* Vincenzo Librandi, May 02 2013 *)

[0,0,2,340,9386,97580,649476] + [(n^10 -90*n^8 +240*n^7 +3235*n^6 - 16320*n^5 -40530*n^4 +396480*n^3 -231656*n^2 -3359520*n +6509280)/120 for n in (8..50)] # G. C. Greubel, Apr 19 2022

Explicit formula: a(n) = (n^10 - 90*n^8 + 240*n^7 + 3235*n^6 - 16320*n^5 - 40530*n^4 + 396480*n^3 - 231656*n^2 - 3359520*n + 6509280)/120, n >= 8.

G.f.: 2*x^3 * (74*x^15 -518*x^14 +1110*x^13 +1046*x^12 -11332*x^11 +29950*x^10 -42430*x^9 +32476*x^8 -11684*x^7 -1000*x^6 +15021*x^5 -18443*x^4 -6352*x^3 -2878*x^2 -159*x -1) / (x-1)^11. [Vaclav Kotesovec, Mar 25 2010]

A201540 Number of ways to place n nonattacking knights on an n X n board.

Original entry on oeis.org

1, 6, 36, 412, 9386, 257318, 8891854, 379978716, 19206532478, 1120204619108, 74113608972922, 5483225594409823, 448414229054798028, 40154319792412218900, 3906519894750904583838

Offset: 1

Vaclav Kotesovec, Dec 02 2011

a(n) = A244081(n,n). - Alois P. Heinz, Jun 19 2014

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

Cf. A172132, A172134, A172135, A172136, A178499, A244081.

Cf. A244284, A201511, A201861, A201513, A141243.

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True&, d]]], True, For[k = 1, ! l[[k]], k++]; g = ReplacePart[l, k -> f];
     If[k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If[k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If[k > 2, g = ReplacePart[g, d - 2 + k -> f]];
     If[k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True&, n*3]]];
a[n_] := T[n][[n + 1]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

a(n) ~ n^(2n)/n!*exp(-9/2). - Vaclav Kotesovec, Nov 29 2011

a(11) from Alois P. Heinz, Jun 19 2014
a(12)-a(13) from Vaclav Kotesovec, Jun 21 2014
a(14) from Vaclav Kotesovec, Aug 26 2016
a(15) from Vaclav Kotesovec, May 26 2021

A178499 Number of ways to place 6 nonattacking knights on an n X n board.

Original entry on oeis.org

0, 0, 0, 170, 13384, 257318, 2774728, 20202298, 110018552, 481719518, 1781124856, 5756568738, 16676946372, 44127887910, 108192675468, 248568720338, 539925974784, 1116836380926, 2212958151968, 4220919779218

Offset: 1

Vaclav Kotesovec, May 28 2010

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

Cf. A172132, A172134, A172135, A172136.

Column k=6 of A244081.

CoefficientList[Series[- 2 x^3 (200 x^18 - 1540 x^17 + 2602 x^16 + 15442 x^15 - 98586 x^14 + 256698 x^13 - 336146 x^12 + 70977 x^11 + 587107 x^10 - 1302115 x^9 + 1569905 x^8 - 1100786 x^7 + 367130 x^6 - 212358 x^5 + 247682 x^4 + 212463 x^3 + 48293 x^2 + 5587 x + 85) / (x - 1)^13, {x, 0, 40}], x] (* Vincenzo Librandi, May 31 2013 *)

Explicit formula: a(n) = n^12/720-(3*n^10)/16+n^9/2+(1553*n^8)/144-(163*n^7)/3-(4493*n^6)/16+(4721*n^5)/2+(578777*n^4)/360-(143156*n^3)/3+(124917*n^2)/2+374990*n-899982, n >= 10.

G.f.: -2*x^4 * (200*x^18 -1540*x^17 +2602*x^16 +15442*x^15 -98586*x^14 +256698*x^13 -336146*x^12 +70977*x^11 +587107*x^10 -1302115*x^9 +1569905*x^8 -1100786*x^7 +367130*x^6 -212358*x^5 +247682*x^4 +212463*x^3 +48293*x^2 +5587*x +85) / (x-1)^13.

cp's OEIS Frontend

A172132 Number of ways to place 2 nonattacking knights on an n X n board.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Magma

Mathematica

SageMath

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A030978 Maximal number of non-attacking knights on an n X n board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A141243 Number of ways to place non-attacking knights on the n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A172135 Number of ways to place 4 nonattacking knights on an n X n board.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A172136 Number of ways to place 5 nonattacking knights on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A201540 Number of ways to place n nonattacking knights on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs