login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 02:15 EDT 2020. Contains 336287 sequences. (Running on oeis4.)