login
Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.
9

%I #27 Oct 05 2016 14:07:36

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

%T 2860,3238,2860,2016,1092,464,140,32,4,1,1,7,78,578,3182,13302,44330,

%U 120230,270525,510875,817388,1114548,1300316,1300316,1114548,817388

%N Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.

%C Row sums give A047937.

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

%C The formula is obtained from PĆ³lya's counting theorem. See, e.g., the Harary-Palmer reference.

%C The cycle index for a square grid of n X n squares G(n), n >= 1, under the cyclic group C_4 is

%C (s[1]^(n^2)+s[2]^(n^2/2)+2*s[4]^(n^2/4))/4 if n is even,

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

%C The figure counting series is c(x) = 1+x for coloring, say black and white (in the matrix case binary entries).

%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. (End)

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

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

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

%e [1],[1,1],[1,1,2,1,1],[1,3,10,22,34,34,22,10,3,1],...;

%e There are 10 inequivalent 3 X 3 binary matrices with 2 ones, up to rotational symmetry:

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

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

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

%e -------

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

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

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

%e - reformatted. _Wolfdieter Lang_, Oct 01 2016

%e See a remark above: use o for 0 and + for 1.

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

%Y Cf. A054252, columns k=0..4: A000012, A004652, A212714, A011863, A275799.

%K nonn,tabf,easy

%O 0,6

%A _Vladeta Jovovic_, May 18 2000