A141243 -id:A141243 - cp's OEIS frontend

A244081 Number T(n,k) of ways to place k nonattacking knights on an n X n board; triangle T(n,k), n>=0, 0<=k<=A030978(n), read by rows.

1, 1, 1, 1, 4, 6, 4, 1, 1, 9, 28, 36, 18, 2, 1, 16, 96, 276, 412, 340, 170, 48, 6, 1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1, 1, 36, 550, 4752, 26133, 97580, 257318, 491140, 688946, 716804, 556274, 323476, 141969, 47684, 12488, 2560, 393, 40, 2

Offset: 0

Alois P. Heinz, Jun 19 2014

In other words, the n-th row gives the coefficients of the independence polynomial of the n X n knight graph. - Eric W. Weisstein, May 05 2017

			T(4,8) = 6:
  ._______. ._______. ._______. ._______. ._______. ._______.
  |_|o|_|o| |o|_|o|_| |o|o|o|o| |o|_|_|o| |o|_|o|o| |o|o|_|o|
  |o|_|o|_| |_|o|_|o| |_|_|_|_| |o|_|_|o| |_|_|_|o| |o|_|_|_|
  |_|o|_|o| |o|_|o|_| |_|_|_|_| |o|_|_|o| |o|_|_|_| |_|_|_|o|
  |o|_|o|_| |_|o|_|o| |o|o|o|o| |o|_|_|o| |o|o|_|o| |o|_|o|o| .
.
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  4,   6,    4,    1;
  1,  9,  28,   36,   18,    2;
  1, 16,  96,  276,  412,  340,   170,    48,    6;
  1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1;
  ...
As independence polynomials:
  1
  1 + x
  1 + 4*x + 6*x^2 + 4*x^3 + x^4
  1 + 9*x + 28*x^2 + 36*x^3 + 18*x^4 + 2*x^5
  1 + 16*x + 96*x^2 + 276*x^3 + 412*x^4 + 340*x^5 + 170*x^6 + 48*x^7 + 6*x^8
  ...

Alois P. Heinz, Rows n = 0..12, flattened
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Knights Problem

Columns k=0-6 give: A000012, A000290, A172132, A172134, A172135, A172136, A178499.
T(n,n) gives A201540.
Row sums give A141243.
Cf. A030978.

b:= proc(n, l) option remember; local d, f, g, k;
      d:= nops(l)/3; f:=false;
      if n=0 then 1
    elif l[1..d]=[f$d] then b(n-1, [l[d+1..3*d][], true$d])
    else for k while not l[k] do od; g:= subsop(k=f, l);
         if k>1 then g:=subsop(2*d-1+k=f, g) fi;
         if k2 then g:=subsop(  d-2+k=f, g) fi;
         if k(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, [true$(n*3)])):
seq(T(n), n=0..7);

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]]];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 28 2016, after Alois P. Heinz *)
Table[Count[IndependentVertexSetQ[KnightTourGraph[n, n], #] & /@ Subsets[Range[n^2], {k}], True], {n, 4}, {k, 0, If[n == 2, 4, (1 - (-1)^n + 2 n^2)/4]}] // Flatten (* Eric W. Weisstein, May 05 2017 *)

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

A182407 Number of ways to place k non-attacking knights on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 9, 34, 982, 11284, 1048768, 48027971, 23807996588, 3430123782371, 8141109957322587, 4098570575535958632, 46676507893324203092812, 77374614378004006943995980, 4352639823147918661142120756677

Offset: 1

Vaclav Kotesovec, May 09 2012

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

Cf. A141243, A182408, A172964.

a(14) from Vaclav Kotesovec, May 17 2021

A182408 Number of ways to place k non-attacking knights on an n x n toroidal chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 7, 34, 743, 1546, 598078, 6027057, 10163241031, 242407820869

Offset: 1

Vaclav Kotesovec, May 09 2012

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

Cf. A141243, A182407, A067958, A027683, A067960.

A287225 Number of matchings in the n X n knight graph.

Original entry on oeis.org

1, 1, 47, 8617, 4437215, 18283403428, 478131755555352, 65146261730656227552, 51516890628947512147926356, 244151636345172523021724077440553, 6697138334086551576618194527162685383161

Offset: 1

Eric W. Weisstein, May 22 2017

Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Matching

Row sums of A302241.

Cf. A289200, A289202, A141243.

a(7)-a(11) from Andrew Howroyd, Jul 01 2017

A366513 Number of independent vertex sets in the n X n camel graph.

Original entry on oeis.org

2, 16, 512, 5184, 159588, 6041764, 2147569224, 351791334400, 528775298642599, 238297327919927329, 1643642864931094594560

Offset: 1

Eric W. Weisstein, Oct 11 2023

Eric Weisstein's World of Mathematics, Camel Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set

Cf. A141243, A366514, A366517.

A366514 Number of independent vertex sets in the n X n giraffe graph.

Original entry on oeis.org

2, 16, 512, 65536, 1129984, 53104512, 4800173156, 740551922054

Offset: 1

Eric W. Weisstein, Oct 11 2023

Eric Weisstein's World of Mathematics, Giraffe Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set

Cf. A141243, A366513, A366517.

A366517 Number of independent vertex sets in the n X n zebra graph.

Original entry on oeis.org

2, 16, 512, 10000, 207458, 18377967, 7971948455, 4656181368201

Offset: 1

Eric W. Weisstein, Oct 11 2023

Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Zebra Graph

Cf. A141243, A366513, A366514.

A289201 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n knight graph.

Original entry on oeis.org

1, 1, 10, 31, 172, 2253, 50652, 900243, 26990541, 1534414257

Offset: 1

Eric W. Weisstein, Jun 28 2017

Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.
Eric Weisstein's World of Mathematics, Minimal Vertex Cover.

Cf. A141243, A289203, A287071, A289200.

Table[Length[FindIndependentVertexSet[KnightTourGraph[n, n], Infinity, All]], {n, 7}]

from networkx import empty_graph, find_cliques, complement
def A289201(n):
    G = empty_graph((i,j) for i in range(n) for j in range(n))
    G.add_edges_from(((i,j),(i+k,j+l)) for i in range(n) for j in range(n) for (k,l) in ((1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)) if 0<=i+kChai Wah Wu, Jan 11 2024

a(9)-a(10) from Andrew Howroyd, Jul 01 2017

A321251 a(n) is the number of ways to place non-attacking knights on a 3 X n chessboard.

Original entry on oeis.org

1, 8, 36, 94, 278, 1062, 3650, 11856, 39444, 135704, 456980, 1534668, 5166204, 17480600, 58888528, 198548648, 669291696, 2258436248, 7613387344, 25676313144, 86575342536, 291991130840, 984557555352, 3320284572360, 11196209499736, 37757232570616

Offset: 0

Dimitrios Noulas, Nov 01 2018

For n = 3, a(3) = 94 is the same as A141243(3). In both cases these are 3 X 3 chessboards.

Dimitrios Noulas, Table of n, a(n) for n = 0..1000
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 297-301.

Cf. A141243, A189145.

CoefficientList[Series[-(36 x^15 - 72 x^14 - 60 x^13 + 72 x^12 - 120 x^11 + 250 x^10 + 270 x^9 - 256 x^8 - 30 x^7 - 78 x^6 - 98 x^5 + 92 x^4 + 36 x^3 - 8 x^2 - 5 x - 1)/(36 x^16 - 108 x^15 + 48 x^14 + 24 x^13 - 144 x^12 + 376 x^11 - 70 x^10 - 174 x^9 + 108 x^8 - 168 x^7 + 26 x^6 + 78 x^5 - 24 x^4 + 10 x^3 - 4 x^2 - 3 x + 1), {x, 0, 25}], x] (* Michael De Vlieger, Nov 05 2018 *)

G(x)=-(36*x^15 - 72*x^14 - 60*x^13 + 72*x^12 - 120*x^11 + 250*x^10 + 270*x^9 - 256*x^8 - 30*x^7 - 78*x^6 - 98*x^5 + 92*x^4 + 36*x^3 - 8*x^2 - 5*x - 1)/(36*x^16 - 108*x^15 + 48*x^14 + 24*x^13 - 144*x^12 + 376*x^11 - 70*x^10 - 174*x^9 + 108*x^8 - 168*x^7 + 26*x^6 + 78*x^5 - 24*x^4 + 10*x^3 - 4*x^2 - 3*x + 1)
G.series(x,1001)

G.f.: -(36*x^15 - 72*x^14 - 60*x^13 + 72*x^12 - 120*x^11 + 250*x^10 + 270*x^9 - 256*x^8 - 30*x^7 - 78*x^6 - 98*x^5 + 92*x^4 + 36*x^3 - 8*x^2 - 5*x - 1)/(36*x^16 - 108*x^15 + 48*x^14 + 24*x^13 - 144*x^12 + 376*x^11 - 70*x^10 - 174*x^9 + 108*x^8 - 168*x^7 + 26*x^6 + 78*x^5 - 24*x^4 + 10*x^3 - 4*x^2 - 3*x + 1).

cp's OEIS Frontend

A244081 Number T(n,k) of ways to place k nonattacking knights on an n X n board; triangle T(n,k), n>=0, 0<=k<=A030978(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A182407 Number of ways to place k non-attacking knights on an n x n cylindrical chessboard, summed over all k >= 0.

Views

Author

Keywords

Links

Crossrefs

Extensions

A182408 Number of ways to place k non-attacking knights on an n x n toroidal chessboard, summed over all k >= 0.

Views

Author

Keywords

Links

Crossrefs

A287225 Number of matchings in the n X n knight graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A366513 Number of independent vertex sets in the n X n camel graph.

Views

Author

Keywords

Links

Crossrefs

A366514 Number of independent vertex sets in the n X n giraffe graph.

Views

Author

Keywords

Links

Crossrefs

A366517 Number of independent vertex sets in the n X n zebra graph.

Views

Author

Keywords

Links

Crossrefs

A289201 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n knight graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A321251 a(n) is the number of ways to place non-attacking knights on a 3 X n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica