login
This site is supported by donations to The OEIS Foundation.

 

Logo


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. 23
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: A196017 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 February 16 21:22 EST 2019. Contains 320199 sequences. (Running on oeis4.)