OFFSET
1,2
COMMENTS
Number of n X n binary matrices with n ones under action of dihedral group of the square D_4.
LINKS
Mathieu Gouttenoire, Table of n, a(n) for n = 1..300
Mario Velucchi, Different Dispositions in the ChessBoard.
Mario Velucchi, Different Dispositions in the ChessBoard.
FORMULA
See Velucchi link or the PARI program. Note that the polynomial whose coefficient of a^k is divided by 8 differs based upon whether the term's index is even or odd.
Let A(n) = C(n^2, n); B(n) = C((n^2-(n mod 2))/2, n/2); C(n) = C((n^2-(n mod 2))/4, n/4); D(n) = Sum(p = 0 to [n/2], C((n^2-n)/2, p)*C(n, n-2p)). Then a(n) = (A(n) + 3B(n) + 2C(n) + 2D(n))/8 if n == 0 (mod 4), (A(n) + B(n) + 2C(n) + 4D(n))/8 if n == 1 (mod 4), (A(n) + 3B(n) + 2D(n))/8 if n == 2 (mod 4), (A(n) + B(n) + 4D(n))/8 if n == 3 (mod 4). - David W. Wilson, May 29 2003
EXAMPLE
For n=3 the 16 solutions are
111 110 110 110 110 110 110 101 101 101 100 100 100 010 010 010
000 100 010 001 000 000 000 010 000 000 011 010 001 110 101 010
000 000 000 000 100 010 001 000 100 010 000 001 010 000 000 010
MATHEMATICA
p[a_, b_, n_] := If[EvenQ[n], (a+b)^(n^2) + 2*(a+b)^n*(a^2 + b^2)^((n^2 - n)/2) + 3*(a^2 + b^2)^(n^2/2) + 2*(a^4 + b^4)^(n^2/4), (a+b)^(n^2) + 2*(a+b)*(a^4 + b^4)^((n^2-1)/4) + (a+b)*(a^2 + b^2)^((n^2-1)/2) + 4*(a+b)^n*(a^2 + b^2)^((n^2-n)/2)]; Table[Coefficient[p[a, 1, k], a, k]/8, {k, 1, 20}] (* Jean-François Alcover, Nov 12 2013, translated from Pari *)
PROG
(PARI) {p(a, b, N) = if(N%2==0, (a+b)^(N^2) + 2*(a+b)^N*(a^2+b^2)^((N^2-N)/2) + 3*(a^2+b^2)^(N^2/2) + 2*(a^4+b^4)^(N^2/4), (a+b)^(N^2) + 2*(a+b)*(a^4+b^4)^((N^2-1)/4) + (a+b)*(a^2+b^2)^((N^2-1)/2) + 4*(a+b)^N*(a^2+b^2)^((N^2-N)/2))} for(k=1, 20, print1(polcoeff(p(a, 1, k), k)/8, ", "))
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Mario Velucchi (mathchess(AT)velucchi.it)
EXTENSIONS
More terms from Rick L. Shepherd and David W. Wilson, May 28 2003
STATUS
approved