login
A141243
Number of ways to place non-attacking knights on the n X n board.
10
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
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
Row sums of A244081.
Sequence in context: A220882 A295903 A362767 * A163229 A038749 A002699
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