The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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. 24

%I

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

%T 1674,1465,1051,567,252,77,21,3,1,1,6,49,319,1666,6814,22475,60645,

%U 136080,256585,410170,559014,652048,652048,559014,410170,256585,136080

%N 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.

%C From _Geoffrey Critzer_, Feb 19 2013: (Start)

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

%C (1/8)(s^4 + 2*s^2*s + 3*s^2 + 2*s).

%C (1/8)(s^9 + 4*s^3*s^3 + ss^4 + 2*s*s^2).

%C (1/8)(s^16 + 2*s^4*s^6 + 2*s^4 + 3*s^8).

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

%C (End)

%C 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

%C From _Wolfdieter Lang_, Oct 03 2016: (Start)

%C 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)

%C (s^(n^2) + s^(n^2/2) +2*s^(n^2/4))/8 + (s^(n^2/2) + s^n*s^((n^2-n)/2))/4 if n is even,

%C s*((s^(n^2-1) + s^((n^2-1)/2) + 2*s^((n^2-1)/4))/8) + s^n*s^(n*(n-1)/2)/2 if n is odd.

%C See the above comment by _Geoffrey Critzer_ for n=2..5.

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

%C 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.

%C (End)

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

%H Heinrich Ludwig, <a href="/A054252/b054252.txt">Rows n = 0..16, flattened</a>

%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>

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

%e [0 0 0] [0 0 0] [0 0 0] [0 0 0]

%e [0 0 0] [0 0 0] [0 0 1] [0 0 1]

%e [0 1 1] [1 0 1] [0 1 0] [1 0 0]

%e ---------------------------------

%e [0 0 0] [0 0 0] [0 0 0] [0 0 1]

%e [0 1 0] [0 1 0] [1 0 1] [0 0 0]

%e [0 0 1] [0 1 0] [0 0 0] [1 0 0]

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 1, 2, 1, 1;

%e 1, 3, 8, 16, 23, 23, 16, 8, 3, 1;

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

%t 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 *)

%o (Sage)

%o def T(n, k):

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

%o return 1

%o grid = graphs.Grid2dGraph(n, n)

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

%o b, w = m.variables()

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

%o [T(n, k) for n in range(6) for k in range(n*n + 1)] # _Freddy Barrera_, Nov 23 2018

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

%K easy,nonn,tabf

%O 0,6

%A _Vladeta Jovovic_, May 04 2000

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.

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