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.

%I A244081 #39 Feb 16 2025 08:33:22
%S A244081 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 A244081 1360,4436,9386,13384,12996,8526,3679,994,158,15,1,1,36,550,4752,
%U A244081 26133,97580,257318,491140,688946,716804,556274,323476,141969,47684,12488,2560,393,40,2
%N 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.
%C A244081 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 A244081 Alois P. Heinz, <a href="/A244081/b244081.txt">Rows n = 0..12, flattened</a>
%H A244081 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>
%H A244081 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>
%H A244081 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightsProblem.html">Knights Problem</a>
%e A244081 T(4,8) = 6:
%e A244081   ._______. ._______. ._______. ._______. ._______. ._______.
%e A244081   |_|o|_|o| |o|_|o|_| |o|o|o|o| |o|_|_|o| |o|_|o|o| |o|o|_|o|
%e A244081   |o|_|o|_| |_|o|_|o| |_|_|_|_| |o|_|_|o| |_|_|_|o| |o|_|_|_|
%e A244081   |_|o|_|o| |o|_|o|_| |_|_|_|_| |o|_|_|o| |o|_|_|_| |_|_|_|o|
%e A244081   |o|_|o|_| |_|o|_|o| |o|o|o|o| |o|_|_|o| |o|o|_|o| |o|_|o|o| .
%e A244081 .
%e A244081 Triangle T(n,k) begins:
%e A244081   1;
%e A244081   1,  1;
%e A244081   1,  4,   6,    4,    1;
%e A244081   1,  9,  28,   36,   18,    2;
%e A244081   1, 16,  96,  276,  412,  340,   170,    48,    6;
%e A244081   1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1;
%e A244081   ...
%e A244081 As independence polynomials:
%e A244081   1
%e A244081   1 + x
%e A244081   1 + 4*x + 6*x^2 + 4*x^3 + x^4
%e A244081   1 + 9*x + 28*x^2 + 36*x^3 + 18*x^4 + 2*x^5
%e A244081   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 A244081   ...
%p A244081 b:= proc(n, l) option remember; local d, f, g, k;
%p A244081       d:= nops(l)/3; f:=false;
%p A244081       if n=0 then 1
%p A244081     elif l[1..d]=[f$d] then b(n-1, [l[d+1..3*d][], true$d])
%p A244081     else for k while not l[k] do od; g:= subsop(k=f, l);
%p A244081          if k>1 then g:=subsop(2*d-1+k=f, g) fi;
%p A244081          if k<d then g:=subsop(2*d+1+k=f, g) fi;
%p A244081          if k>2 then g:=subsop(  d-2+k=f, g) fi;
%p A244081          if k<d-1 then g:=subsop(d+2+k=f, g) fi;
%p A244081          expand(b(n, subsop(k=f, l)) +b(n, g)*x)
%p A244081       fi
%p A244081     end:
%p A244081 T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, [true$(n*3)])):
%p A244081 seq(T(n), n=0..7);
%t A244081 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 A244081      If [k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
%t A244081      If [k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
%t A244081      If [k > 2, g = ReplacePart[ g, d - 2 + k -> f]];
%t A244081      If [k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
%t A244081      Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
%t A244081 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][
%t A244081   b[n, Array[True&, n*3]]];
%t A244081 Table[T[n], {n, 0, 7}] // Flatten (* _Jean-François Alcover_, Mar 28 2016, after _Alois P. Heinz_ *)
%t A244081 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 A244081 Columns k=0-6 give: A000012, A000290, A172132, A172134, A172135, A172136, A178499.
%Y A244081 T(n,n) gives A201540.
%Y A244081 Row sums give A141243.
%Y A244081 Cf. A030978.
%K A244081 nonn,tabf
%O A244081 0,5
%A A244081 _Alois P. Heinz_, Jun 19 2014