A182408 -id:A182408 - cp's OEIS frontend

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

Max Alekseyev, Jun 17 2008

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.

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

Cf. A182407, A182408, A201540.

Row sums of 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];
     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 *)

A141243(n=4, s=n^2-1, bad=0)={ while(s && bittest(bad, s), s--);
   if(s < n, 2^(s+1-hammingweight(bad % (2<A141243(n, s-1, bad), x = s%n);
      x > 1 && bad = bitor(bad, 2^(s-n-2)); x < n-2 && bad = bitor(bad, 2^(s-n+2));
      if( s >= 2*n, x && bad = bitor(bad, 2^(s-2*n-1));
              x < n-1 && bad = bitor(bad, 2^(s-2*n+1))
   ); cnt + A141243(n, s-1, bad))} \\ M. F. Hasler, Mar 18 2025

def A141243(n=4, start=(1,1), forbidden=()):
    if start[0] >= n: return 2**sum((n,y+1) not in forbidden for y in range(n))
    nxt = (start[0],start[1]+1) if start[1]A141243(n, nxt, forbidden)
    if start in forbidden: return cnt
    forbidden = {s for s in forbidden if s >= nxt}
    if start[1]2: forbidden |= {(start[0]+1,start[1]-2)}
    if start[0]1: forbidden |= {(start[0]+2,start[1]-1)}
    return cnt+A141243(n, nxt, forbidden) # M. F. Hasler, Mar 17 2025

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

A182407 Number of ways to place k non-attacking knights on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 9, 34, 982, 11284, 1048768, 48027971, 23807996588, 3430123782371, 8141109957322587, 4098570575535958632, 46676507893324203092812, 77374614378004006943995980, 4352639823147918661142120756677

Offset: 1

Vaclav Kotesovec, May 09 2012

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.307

Cf. A141243, A182408, A172964.

a(14) from Vaclav Kotesovec, May 17 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions