login
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.
9
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,5
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
LINKS
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Knights Problem
EXAMPLE
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
...
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 k<d then g:=subsop(2*d+1+k=f, g) fi;
if k>2 then g:=subsop( d-2+k=f, g) fi;
if k<d-1 then g:=subsop(d+2+k=f, g) fi;
expand(b(n, subsop(k=f, l)) +b(n, g)*x)
fi
end:
T:= n->(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 *)
CROSSREFS
Columns k=0-6 give: A000012, A000290, A172132, A172134, A172135, A172136, A178499.
T(n,n) gives A201540.
Row sums give A141243.
Cf. A030978.
Sequence in context: A365947 A230207 A277949 * A279445 A217285 A212635
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jun 19 2014
STATUS
approved