login
Triangle with number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to k (0<=k<=n), where equivalence is defined by row and column permutations.
16

%I #11 Apr 03 2020 18:29:22

%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,4,7,4,1,1,1,1,4,16,16,

%T 4,1,1,1,1,7,51,194,51,7,1,1,1,1,8,224,3529,3529,224,8,1,1,1,1,12,

%U 1165,121790,601055,121790,1165,12,1,1,1,1,14,7454,5582612,156473848,156473848,5582612,7454,14,1,1

%N Triangle with number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to k (0<=k<=n), where equivalence is defined by row and column permutations.

%C T(n,k) = T(n,n-k). When 0 and 1 are switched, the number of equivalence classes remain the same.

%C Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A008300. Burnside's lemma can be used to extend this method to the unlabeled case. This seems to require looping over partitions for both rows and columns. The number of partitions squared increases rapidly with n. For example, A000041(20)^2 = 393129. - _Andrew Howroyd_, Apr 03 2020

%H Andrew Howroyd, <a href="/A133687/b133687.txt">Table of n, a(n) for n = 0..189</a>

%F Sum_{k=1..n} T(n, k) = A000519(n).

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 1, 1;

%e 1, 1, 1, 1;

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

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

%e 1, 1, 4, 7, 4, 1, 1;

%e 1, 1, 4, 16, 16, 4, 1, 1;

%e 1, 1, 7, 51, 194, 51, 7, 1, 1;

%e 1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1;

%e ...

%Y Columns k=0..5 are A000012, A000012, A002865, A000512, A000513, A000516.

%Y Row sums are A333681.

%Y T(2n,n) gives A333740.

%Y Cf. A000519, A008300 (labeled case), A008327 (bipartite graphs), A333159 (symmetric case).

%K nonn,tabl

%O 0,13

%A Joost Vermeij (joost_vermeij(AT)live.nl), Jan 04 2008

%E Missing a(72) inserted by _Andrew Howroyd_, Apr 01 2020