A141243 Number of ways to place non-attacking knights on the n X n board.

1, 2, 16, 94, 1365, 55213, 3368146, 394631712, 101693175442, 50929053498909, 48988729226134301, 96325314726538906164, 375615195988659173454092, 2933480442104347575000834468, 45480806737377995771543610802659, 1422902021111889804120495149240353936

Offset

0,2

Comments

The maximum number of non-attacking knights is given by A030978.

Also the number of vertex covers and independent vertex sets in the n X n knight graph.

Links

Table of n, a(n) for n=0..15.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-72, 283-285.

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Knight Graph

Eric Weisstein's World of Mathematics, Vertex Cover

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]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True &, n*3]]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

Crossrefs

Cf. A182407, A182408, A201540.

Row sums of A244081.

Sequence in context: A220882 A295903 A362767 * A163229 A038749 A002699

Adjacent sequences: A141240 A141241 A141242 * A141244 A141245 A141246

Keyword

hard,nonn,nice

Author

Max Alekseyev, Jun 17 2008

Extensions

a(8)-a(13) from R. H. Hardin, Aug 25 2008

a(0) from Alois P. Heinz, Jun 19 2014

a(14) from Hiroaki Yamanouchi, Aug 28 2014

a(15) from Hiroaki Yamanouchi, Aug 29 2014

Status

approved