|
|
A019318
|
|
Number of inequivalent ways of choosing n squares from an n X n board, considering rotations and reflections to be the same.
|
|
6
|
|
|
1, 2, 16, 252, 6814, 244344, 10746377, 553319048, 32611596056, 2163792255680, 159593799888052, 12952412056879996, 1147044793316531040, 110066314584030859544, 11375695977099383509351, 1259843950257390597789296, 148842380543159458506703546, 18685311541775061906510072648, 2483858381692984848273972297368, 348545122958862200122401771463328
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|