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

Author

Jud McCranie, Sep 24 2001

Keywords

• nonn

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

Examples

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

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.

Crossrefs

A007016 gives the number of solutions including symmetrical ones.

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

Programs

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 *)

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

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

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