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

A000512 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 3, where equivalence is defined by row and column permutations.

Original entry on oeis.org

0, 0, 1, 1, 2, 7, 16, 51, 224, 1165, 7454, 56349, 481309, 4548786, 46829325, 519812910, 6177695783, 78190425826, 1049510787100, 14886252250208, 222442888670708, 3492326723315796, 57468395960854710, 989052970923320185, 17767732298980160822, 332572885090541084172, 6475438355244504235759, 130954580036269713385884

Offset: 1

Eric Rogoyski

Also, isomorphism classes of bicolored cubic bipartite graphs, where isomorphism cannot exchange the colors.

			n=4: every matrix with 3 1's in each row and column can be transformed by permutation of rows (or columns) into {1110,1101,1011,0111}, therefore a(4)=1. - _Michael Steyer_, Feb 20 2003

A. Burgess, P. Danziger, E. Mendelsohn, B. Stevens, Orthogonally Resolvable Cycle Decompositions, 2013; http://www.math.ryerson.ca/~andrea.burgess/OCD-submit.pdf
Goulden and Jackson, Combin. Enum., Wiley, 1983 p. 284.

Index entries for sequences related to Latin squares and rectangles

Column k=3 of A133687.
Cf. A000186, A000513, A000840, A001501, A008325, A232215.
A079815 may be an erroneous version of this, or it may have a slightly different (as yet unknown) definition. - N. J. A. Sloane, Sep 04 2010.

Definition corrected by Brendan McKay, May 28 2006
a(1)-a(12) checked by Brendan McKay, Aug 27 2010
Terms a(15) and beyond from 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

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

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 161, 7776, 626649

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-A229164, A000513.

A column of A227061.

A000516 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 5, where equivalence is defined by row and column permutations. Isomorphism classes of bicolored 5-regular bipartite graphs, where isomorphism cannot exchange the colors.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 4, 51, 3529, 601055, 156473848, 54062069505, 23869437984682, 13186966476208771, 8971034249976338907, 7414924597575224629299, 7360058177440420943520750, 8683626883245180573511018830, 12066478410398147578519948851818, 19585444567548740264243478805318202

Offset: 1

Eric Rogoyski

nonn

Index entries for sequences related to Latin squares and rectangles

Column k=5 of A133687.

Cf. A000512, A000513.

Definition corrected by Brendan McKay, May 28 2006

Offset corrected and terms a(12) and beyond from Andrew Howroyd, Apr 01 2020

A000843 Number of quartic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 12, 66, 433, 3442, 30404, 294951, 3093770, 34846185, 419020738, 5355289843, 72466668921, 1034818990771, 15548633703424, 245182764121059, 4047990858838185, 69826392559499108, 1256005988628521464, 23517396850332614602, 457623646061902648705

Offset: 1

Brendan McKay and Eric Rogoyski

nonn

Column k=4 of A333159.

Cf. A000513, A000840.

a(11)-a(25) from Andrew Howroyd, Mar 10 2020

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

A000512 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 3, where equivalence is defined by row and column permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

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

Views

Author

Keywords

References

Links

Crossrefs

A000516 Number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to 5, where equivalence is defined by row and column permutations. Isomorphism classes of bicolored 5-regular bipartite graphs, where isomorphism cannot exchange the colors.

Views

Author

Keywords

Links

Crossrefs

Extensions

A000843 Number of quartic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Views

Author

Keywords

Crossrefs

Extensions