A244081 - OEIS

%I #39 Feb 16 2025 08:33:22

%S 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,

%T 1360,4436,9386,13384,12996,8526,3679,994,158,15,1,1,36,550,4752,

%U 26133,97580,257318,491140,688946,716804,556274,323476,141969,47684,12488,2560,393,40,2

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

%C 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

%H Alois P. Heinz, <a href="/A244081/b244081.txt">Rows n = 0..12, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightsProblem.html">Knights Problem</a>

%e T(4,8) = 6:

%e   ._______. ._______. ._______. ._______. ._______. ._______.

%e   |_|o|_|o| |o|_|o|_| |o|o|o|o| |o|_|_|o| |o|_|o|o| |o|o|_|o|

%e   |o|_|o|_| |_|o|_|o| |_|_|_|_| |o|_|_|o| |_|_|_|o| |o|_|_|_|

%e   |_|o|_|o| |o|_|o|_| |_|_|_|_| |o|_|_|o| |o|_|_|_| |_|_|_|o|

%e   |o|_|o|_| |_|o|_|o| |o|o|o|o| |o|_|_|o| |o|o|_|o| |o|_|o|o| .

%e .

%e Triangle T(n,k) begins:

%e   1;

%e   1,  1;

%e   1,  4,   6,    4,    1;

%e   1,  9,  28,   36,   18,    2;

%e   1, 16,  96,  276,  412,  340,   170,    48,    6;

%e   1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1;

%e   ...

%e As independence polynomials:

%e   1

%e   1 + x

%e   1 + 4*x + 6*x^2 + 4*x^3 + x^4

%e   1 + 9*x + 28*x^2 + 36*x^3 + 18*x^4 + 2*x^5

%e   1 + 16*x + 96*x^2 + 276*x^3 + 412*x^4 + 340*x^5 + 170*x^6 + 48*x^7 + 6*x^8

%e   ...

%p b:= proc(n, l) option remember; local d, f, g, k;

%p       d:= nops(l)/3; f:=false;

%p       if n=0 then 1

%p     elif l[1..d]=[f$d] then b(n-1, [l[d+1..3*d][], true$d])

%p     else for k while not l[k] do od; g:= subsop(k=f, l);

%p          if k>1 then g:=subsop(2*d-1+k=f, g) fi;

%p          if k<d then g:=subsop(2*d+1+k=f, g) fi;

%p          if k>2 then g:=subsop(  d-2+k=f, g) fi;

%p          if k<d-1 then g:=subsop(d+2+k=f, g) fi;

%p          expand(b(n, subsop(k=f, l)) +b(n, g)*x)

%p       fi

%p     end:

%p T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, [true$(n*3)])):

%p seq(T(n), n=0..7);

%t 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];

%t      If [k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];

%t      If [k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];

%t      If [k > 2, g = ReplacePart[ g, d - 2 + k -> f]];

%t      If [k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];

%t      Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];

%t T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][

%t   b[n, Array[True&, n*3]]];

%t Table[T[n], {n, 0, 7}] // Flatten (* _Jean-François Alcover_, Mar 28 2016, after _Alois P. Heinz_ *)

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

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

%Y T(n,n) gives A201540.

%Y Row sums give A141243.

%Y Cf. A030978.

%K nonn,tabf

%O 0,5

%A _Alois P. Heinz_, Jun 19 2014