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

Author

Alois P. Heinz, Jun 19 2014

Keywords

• nonn
• tabf

Comments

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

Examples

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

Links

• 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

Crossrefs

Columns k=0-6 give: A000012, A000290, A172132, A172134, A172135, A172136, A178499.

T(n,n) gives A201540.

Row sums give A141243.

Cf. A030978.

Programs

Maple

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

Mathematica

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