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

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

Offset: 0

Author

Vladeta Jovovic, May 18 2000

Keywords

• nonn
• tabf
• easy

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 Harary-Palmer 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^2-1) + s[2]^((n^2-1)/2) + 2*s[4]^((n^2-1)/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

Examples

			[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
		

References

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

Crossrefs

Cf. A054252, columns k=0..4: A000012, A004652, A212714, A011863, A275799.

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