login
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.
3
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
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.
Sequence in context: A081214 A331087 A194004 * A203379 A209031 A096424
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