login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244081 Number T(n,k) of ways to place k nonattacking knights on an n X n board; triangle T(n,k), n>=0, k<=0<=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 (list; graph; refs; listen; history; text; internal format)
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

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

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: A155675 A230207 A277949 * A279445 A217285 A212635

Adjacent sequences:  A244078 A244079 A244080 * A244082 A244083 A244084

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Jun 19 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 03:42 EDT 2020. Contains 337316 sequences. (Running on oeis4.)