A064280 Number of nonequivalent solutions to the order n checkerboard problem up to reflection and rotation: place n pieces on an n X n board so there is exactly one piece in each row, column and main diagonal.

1, 0, 0, 1, 4, 12, 86, 696, 6150, 61760, 673256, 8137200, 105074420, 1479237312, 22077680616, 354753059584, 6007578698408, 108500041654272, 2055204828592832, 41215470268919040, 863378484993573840, 19036646809582054400, 436944006380312366240

Offset

1,5

Comments

For even n>=4: A007016(n) = 8*A064280(n).

For even n, the diagonals do not intersect and there can be no symmetrical solutions. For odd n, a symmetrical solution will have a rook on the central square and the remaining n-1 rooks must be placed so as to avoid the main diagonals. See A292080 for information on counting non-attacking rook configurations with no rook on either main diagonal. - Andrew Howroyd, Sep 12 2017

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Geoffrey Chase, Checkerboard Problem Solved, Creative Computing 6(1), Jan 1980, 122.

Bahairiv Joshi, Unique Solutions to the Checkerboard Problem, Creative Computing 6(10), Oct 1980, 124-125.

Abijah Reed, Comments on Checkerboard Problem Solved, Creative Computing 6(5), May 1980, 94.

Formula

a(2n) = A007016(2n) / 8, a(2n+1) = (A007016(2n+1) + 2^n * A000166(n) + 2*A037224(2*n) + 2*A053871(n)) / 8 for n > 0. - Andrew Howroyd, Sep 12 2017

Example

The 4 X 4 solution is unique, up to equivalence, with pieces at (1,1), (2,3), (3,4) and (4,2).

Mathematica

sf = Subfactorial;
x[n_] := x[n] = Integrate[If[EvenQ[n], (x^2 - 4*x + 2)^(n/2), (x - 1)*(x^2 - 4*x + 2)^((n - 1)/2)]/E^x, {x, 0, Infinity}];
F[n_ /; EvenQ[n]] := With[{m = n/2}, m*(x[2*m] - (2*m - 3)*x[2*m - 1])];
F[n_ /; OddQ[n]] := With[{m = (n - 1)/2}, (2*m + 1)*x[2*m] + 3*m*x[2*m - 1] - 2*m*(m - 1)*x[2*m - 2]];
d[n_] := (-1)^n HypergeometricPFQ[{1/2, -n}, {}, 2];
R[n_] := If[OddQ[n], 0, If[n == 0, 1, (n - 1)!*2/(n/2 - 1)!]];
a[1] = 1; a[n_] := With[{m = Quotient[n, 2]}, (F[n] + If[EvenQ[n], 0, 2^m * sf[m] + 2*R[m] + 2*d[m] + 2*Boole[m == 0]])/8];
Array[a, 30] (* Jean-François Alcover, Sep 15 2019 *)

Prog

(PARI) \\ here sf is A000166, F is A007016, D is A053871, R(n) is A037224(2n).
sf(n) = {n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}
F(n) = {my(v = vector(n)); for(n=4, length(v), v[n] = (n-1)*v[n-1] + 2*if(n%2==1, (n-1)*v[n-2], (n-2)*if(n==4, 1, v[n-4]))); if(n<4, [1, 0, 0][n], if(n%2==0, n*(v[n] - (n-3)*v[n-1]), 2*n*v[n-1] + 3*(n-1)*v[n-2] - (n-1)*(n-3)*v[n-3])/2)}
D(n) = {sum(k=0, n, (-1)^(n-k) * binomial(n, k) * (2*k)!/(2^k*k!))}
R(n) = {if(n%2==1, 0, if(n==0, 1, (n-1)!*2/(n/2-1)!))}
a(n) = {(F(n) + if(n%2==0, 0, my(m=n\2); 2^m * sf(m) + 2*R(m) + 2*D(m) + 2*(m==0)))/8} \\ Andrew Howroyd, Sep 12 2017

Crossrefs

A007016 gives the number of solutions including symmetrical ones.

Cf. A000166, A007016, A037224, A053871, A292080.

Sequence in context: A081214 A331087 A194004 * A203379 A209031 A096424

Adjacent sequences: A064277 A064278 A064279 * A064281 A064282 A064283

Keyword

nonn

Author

Jud McCranie, Sep 24 2001

Extensions

a(11)-a(12) from Lars Blomberg, Jan 13 2013

Name clarified and terms a(13) and beyond from Andrew Howroyd, Sep 12 2017

Status

approved