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,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 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

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: A366836 A007442 A362483 * A294616 A085384 A067856

Adjacent sequences: A054769 A054770 A054771 * A054773 A054774 A054775

Keyword

nonn,tabf,easy

Author

Vladeta Jovovic, May 18 2000

Status

approved