A000516 -id:A000516 - 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

A229161 Number of n X n binary matrices with exactly 2 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Original entry on oeis.org

0, 1, 1, 2, 5, 13, 42, 155, 636, 2889, 14321, 76834, 443157

Offset: 1

N. J. A. Sloane, Sep 15 2013

A column of A227061.
From Brendan McKay, Sep 16 2013: (Start)
If all row and column permutations are allowed, one gets A002865 for k=2, A000512 for k=3, A000513 for k=4, A000516 for k=5, etc., where k = number of 1's in each row and column. See also A133687.
A229161 is strictly different from A002865, which gives the number of equivalence classes of n X n binary matrices with exactly 2 1's in each row and column, up to permutations of rows and columns.
For example, take two non-equivalent n X n matrices A,B which are in sorted form (i.e. the rows are in increasing order and so are the columns). Now form a 2n X 2n matrix by placing A and B in the off-diagonal blocks and zeros in the two diagonal blocks.  This matrix is in sorted form.  Interchanging A and B gives a different matrix that is also in sorted form, and yet it is easily produced from the first matrix by permuting rows and columns.  That is, one equivalence class can contain two different sorted matrices.  I expect that on average the number of sorted matrices per equivalence class is exponentially large.
(End)

K. Yordzhev, On an Algorithm for Isomorphism-Free Generations of Combinatorial Objects, International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Web Site: www.ijettcs.org, Volume 2, Issue 6, November - December 2013, ISSN 2278-6856

K. Yordzhev, Fibonacci sequence related to a combinatorial problem on binary matrices, arXiv preprint arXiv:1305.6790, 2013
K. Yordzhev, Semi-canonical binary matrices, arXiv preprint arXiv:1506.04642, 2015

Cf. A229162, A229163, A229164, A181344, A181345, A002865, A000512, A000513, A000516, A133687.

Better definition and values of a(12)-a(13) from R. H. Hardin, Sep 17 2013

A229164 Number of n X n binary matrices with exactly 5 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 8, 1112, 287311

Offset: 1

N. J. A. Sloane, Sep 15 2013

K. Yordzhev, On an Algorithm for Isomorphism-Free Generations of Combinatorial Objects, International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Web Site: www.ijettcs.org, Volume 2, Issue 6, November - December 2013, ISSN 2278-6856

K. Yordzhev, Fibonacci sequence related to a combinatorial problem on binary matrices, arXiv preprint arXiv:1305.6790, 2013
K. Yordzhev, Semi-canonical binary matrices, arXiv preprint arXiv:1506.04642, 2015

Cf. A229161-A229163, A000516.

A column of A227061.

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

A229161 Number of n X n binary matrices with exactly 2 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A229164 Number of n X n binary matrices with exactly 5 ones in each row and column, and with rows and columns in lexicographically nondecreasing order.

Views

Author

Keywords

References

Links

Crossrefs