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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054252 Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones under action of dihedral group of the square D_4. 25
1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 8, 16, 23, 23, 16, 8, 3, 1, 1, 3, 21, 77, 252, 567, 1051, 1465, 1674, 1465, 1051, 567, 252, 77, 21, 3, 1, 1, 6, 49, 319, 1666, 6814, 22475, 60645, 136080, 256585, 410170, 559014, 652048, 652048, 559014, 410170, 256585, 136080 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

From Geoffrey Critzer, Feb 19 2013: (Start)

Cycle indices for n=2,3,4,5 respectively are:

(1/8)(s[1]^4 + 2*s[1]^2*s[2] + 3*s[2]^2 + 2*s[4]).

(1/8)(s[1]^9 + 4*s[1]^3*s[2]^3 + s[1]s[2]^4 + 2*s[1]*s[4]^2).

(1/8)(s[1]^16 + 2*s[1]^4*s[2]^6 + 2*s[4]^4 + 3*s[2]^8).

(1/8)(s[1]^25 + 4*s[1]^5*s[2]^10 + 2*s[1]*s[4]^6 + s[1]*s[2]^12).

(End)

Also the number of equivalence classes of ways of placing k 1 X 1 tiles in an n X n square under all symmetry operations of the square. - Christopher Hunt Gribble, Feb 17 2014

From Wolfdieter Lang, Oct 03 2016: (Start)

The cycle index G(n) for a square n X n grid with squares coming in two colors with k squares of one color is for the D_4 group (with 8 elements R(90)^j, S R(90)^j, j=0..3)

  (s[1]^(n^2) + s[2]^(n^2/2) +2*s[4]^(n^2/4))/8 + (s[2]^(n^2/2) + s[1]^n*s[2]^((n^2-n)/2))/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))/8) + s[1]^n*s[2]^(n*(n-1)/2)/2 if n is odd.

See the above comment by Geoffrey Critzer for n=2..5.

The figure counting series is c(x) = 1 + x for coloring, say black and white.

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.  This follows from Pólya's counting theorem.  See the Harary-Palmer reference, p. 42, eq. (2.4.6), and eq. (2.2.11) with n=4 on p. 37 for the cycle index of D_4.

(End)

REFERENCES

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

LINKS

Heinrich Ludwig, Rows n = 0..16, flattened

Index entries for sequences related to groups

EXAMPLE

T(3,2) = 8 because there are 8 nonisomorphic 3 X 3 binary matrices with two ones under action of D_4:

  [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] [0 1 0] [1 0 0]

---------------------------------

  [0 0 0] [0 0 0] [0 0 0] [0 0 1]

  [0 1 0] [0 1 0] [1 0 1] [0 0 0]

  [0 0 1] [0 1 0] [0 0 0] [1 0 0]

Triangle T(n,k) begins:

1;

1, 1;

1, 1, 2,  1,  1;

1, 3, 8, 16, 23, 23, 16, 8, 3, 1;

MATHEMATICA

(* As a triangle *) Prepend[Prepend[Table[CoefficientList[CycleIndexPolynomial[

GraphData[{"Grid", {n, n}}, "AutomorphismGroup"], Table[Subscript[s, i], {i, 1, 4}]] /. Table[Subscript[s, i] -> 1 + x^i, {i, 1, 4}], x], {n, 2, 10}], {1, 1}], {1}] // Grid (* Geoffrey Critzer, Aug 09 2016 *)

PROG

(Sage)

def T(n, k):

    if n == 0 or k == 0 or k == n*n:

        return 1

    grid = graphs.Grid2dGraph(n, n)

    m = grid.automorphism_group().cycle_index().expand(2, 'b, w')

    b, w = m.variables()

    return m.coefficient({b: k, w: n*n-k})

[T(n, k) for n in range(6) for k in range(n*n + 1)] # Freddy Barrera, Nov 23 2018

CROSSREFS

Cf. A014409, A019318, A054247 (row sums), A054772.

Sequence in context: A343555 A251660 A279453 * A240472 A007442 A054772

Adjacent sequences:  A054249 A054250 A054251 * A054253 A054254 A054255

KEYWORD

easy,nonn,tabf

AUTHOR

Vladeta Jovovic, May 04 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 December 1 11:29 EST 2021. Contains 349429 sequences. (Running on oeis4.)