cp's OEIS Frontend

A133687 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.

%I A133687 #11 Apr 03 2020 18:29:22
%S A133687 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 A133687 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 A133687 1165,121790,601055,121790,1165,12,1,1,1,1,14,7454,5582612,156473848,156473848,5582612,7454,14,1,1
%N A133687 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 A133687 T(n,k) = T(n,n-k). When 0 and 1 are switched, the number of equivalence classes remain the same.
%C A133687 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 A133687 Andrew Howroyd, <a href="/A133687/b133687.txt">Table of n, a(n) for n = 0..189</a>
%F A133687 Sum_{k=1..n} T(n, k) = A000519(n).
%e A133687 Triangle begins:
%e A133687   1;
%e A133687   1, 1;
%e A133687   1, 1, 1;
%e A133687   1, 1, 1,   1;
%e A133687   1, 1, 2,   1,    1;
%e A133687   1, 1, 2,   2,    1,    1;
%e A133687   1, 1, 4,   7,    4,    1,   1;
%e A133687   1, 1, 4,  16,   16,    4,   1, 1;
%e A133687   1, 1, 7,  51,  194,   51,   7, 1, 1;
%e A133687   1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1;
%e A133687   ...
%Y A133687 Columns k=0..5 are A000012, A000012, A002865, A000512, A000513, A000516.
%Y A133687 Row sums are A333681.
%Y A133687 T(2n,n) gives A333740.
%Y A133687 Cf. A000519, A008300 (labeled case), A008327 (bipartite graphs), A333159 (symmetric case).
%K A133687 nonn,tabl
%O A133687 0,13
%A A133687 Joost Vermeij (joost_vermeij(AT)live.nl), Jan 04 2008
%E A133687 Missing a(72) inserted by _Andrew Howroyd_, Apr 01 2020