

A054772


Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.


8



1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 10, 22, 34, 34, 22, 10, 3, 1, 1, 4, 32, 140, 464, 1092, 2016, 2860, 3238, 2860, 2016, 1092, 464, 140, 32, 4, 1, 1, 7, 78, 578, 3182, 13302, 44330, 120230, 270525, 510875, 817388, 1114548, 1300316, 1300316, 1114548, 817388
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Row sums give A047937.
From Wolfdieter Lang, Oct 01 2016: (Start)
The formula is obtained from PĆ³lya's counting theorem. See, e.g., the HararyPalmer reference.
The cycle index for a square grid of n X n squares G(n), n >= 1, under the cyclic group C_4 is
(s[1]^(n^2)+s[2]^(n^2/2)+2*s[4]^(n^2/4))/4 if n is even,
s[1]*(s[1]^(n^21) + s[2]^((n^21)/2) + 2*s[4]^((n^21)/4))/4 if n is odd. (Numerate the squares from 1 .. n^2 and compute for the C_4 rotations the cycle structure of the permutation from the symmetric group S(n^2)).
The figure counting series is c(x) = 1+x for coloring, say black and white (in the matrix case binary entries).
Therefore the counting series is C(n,x) = G(n) with substitution s[2^j] = c(x^(2*j)) = 1 + x^(2^j) for j=0,1,2. Row n gives the coefficients of C(n,x) in rising (or falling) order. (End)
A pedantic note: One should not use 0,1 matrices for this T(n,k) model because 1 (also ) is not C_4 invariant. Square grids with coloring of the squares, say black and white, or central entries o and + are better suited.  Wolfdieter Lang, Oct 02 2016


REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 42, (2.4.6).


LINKS

Table of n, a(n) for n=0..50.


FORMULA

See the comment above: T(n,k) = [x^k]C(n,x), with the counting series C(n,x) obtained from the cycle index for the n X n grid under C_4 rotations G(n;s[1],s[2],s[4]) with s[2^j] = 1 + x^(2^j) for j=0,1,2.  Wolfdieter Lang, Oct 01 2016


EXAMPLE

[1],[1,1],[1,1,2,1,1],[1,3,10,22,34,34,22,10,3,1],...;
There are 10 inequivalent 3 X 3 binary matrices with 2 ones, up to rotational symmetry:
[0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0]
[0 0 0] [0 0 0] [0 0 0] [0 0 1] [0 0 1]
[0 1 1] [1 0 1] [1 1 0] [0 1 0] [1 0 0]

[0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1]
[0 1 0] [0 1 0] [1 0 0] [1 0 1] [0 0 0]
[0 0 1] [0 1 0] [0 0 1] [0 0 0] [1 0 0].
 reformatted. Wolfdieter Lang, Oct 01 2016
See a remark above: use o for 0 and + for 1.
n=3: Cycle index G(3) = s[1]*(s[1]^8 + s[2]^4 + 2*s[4]^2)/4. C(3,x) = (1+x)*((1+x)^8 + (1+x^2)^4 + 2*(1+x^4)^2)/4 = 1 + 3*x + 10*x^2 + 22*x^3 + 34*x^4 + 34*x^5 + 22*x^6 + 10*x^7 + 3*x^8 + x^9.  Wolfdieter Lang, Oct 01 2016


CROSSREFS

Cf. A054252, columns k=0..4: A000012, A004652, A212714, A011863, A275799.
Sequence in context: A054252 A240472 A007442 * A294616 A085384 A067856
Adjacent sequences: A054769 A054770 A054771 * A054773 A054774 A054775


KEYWORD

nonn,tabf,easy


AUTHOR

Vladeta Jovovic, May 18 2000


STATUS

approved



