A333740 -id:A333740 - 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.

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, 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, 1165, 121790, 601055, 121790, 1165, 12, 1, 1, 1, 1, 14, 7454, 5582612, 156473848, 156473848, 5582612, 7454, 14, 1, 1

Offset: 0

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

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

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

			Triangle begins:
  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,    4,   1, 1;
  1, 1, 7,  51,  194,   51,   7, 1, 1;
  1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..189

Columns k=0..5 are A000012, A000012, A002865, A000512, A000513, A000516.
Row sums are A333681.
T(2n,n) gives A333740.
Cf. A000519, A008300 (labeled case), A008327 (bipartite graphs), A333159 (symmetric case).

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

Missing a(72) inserted by Andrew Howroyd, Apr 01 2020

A377007 Array read by antidiagonals: T(n,k) is the number of inequivalent 2n X 2k binary matrices with all row sums k and column sums n up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 4, 7, 4, 1, 1, 1, 1, 5, 19, 19, 5, 1, 1, 1, 1, 7, 46, 194, 46, 7, 1, 1, 1, 1, 8, 132, 3144, 3144, 132, 8, 1, 1, 1, 1, 10, 345, 65548, 601055, 65548, 345, 10, 1, 1, 1, 1, 12, 951, 1272696, 128665248, 128665248, 1272696, 951, 12, 1, 1

Offset: 0

Andrew Howroyd, Oct 12 2024

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

			Array begins:
============================================================================
n\k | 0 1 2   3       4           5               6                    7 ...
----+-----------------------------------------------------------------------
  0 | 1 1 1   1       1           1               1                    1 ...
  1 | 1 1 1   1       1           1               1                    1 ...
  2 | 1 1 2   3       4           5               7                    8 ...
  3 | 1 1 3   7      19          46             132                  345 ...
  4 | 1 1 4  19     194        3144           65548              1272696 ...
  5 | 1 1 5  46    3144      601055       128665248          24124134235 ...
  6 | 1 1 7 132   65548   128665248    294494683312      607662931576945 ...
  7 | 1 1 8 345 1272696 24124134235 607662931576945 14584161564179926207 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..119 (first 15 antidiagonals)

Main diagonal is A333740.
Columns k=0..6 are A000012, A000012, A001399, A377003, A377004, A377005, A377006.
Cf. A133687, A376935.

T(n,k) = T(k,n).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A377007 Array read by antidiagonals: T(n,k) is the number of inequivalent 2n X 2k binary matrices with all row sums k and column sums n up to permutations of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A377007 Array read by antidiagonals: T(n,k) is the number of inequivalent 2*n X 2*k binary matrices with all row sums k and column sums n up to permutations of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A377007 Array read by antidiagonals: T(n,k) is the number of inequivalent 2n X 2k binary matrices with all row sums k and column sums n up to permutations of rows and columns.