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 W. Weisstein, Rows n = 0..14, flattened (first 12 rows from Alois P. Heinz)
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
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jun 19 2014
STATUS
approved