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

A000519 Number of equivalence classes of nonzero regular 0-1 matrices of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 18, 43, 313, 7525, 846992, 324127859, 403254094631, 1555631972009429, 19731915624463099552, 791773335030637885025287, 107432353216118868234728540267, 47049030539260648478475949282317451, 71364337698829887974206671525372672234854

Offset: 1

Eric Rogoyski

nonn

Previous name was: Number of different row sums among Latin squares of order n.

A regular 0-1 matrix has all row sums and column sums equal. Equivalence is defined by independently permuting rows and columns (but not by transposing). - Brendan McKay, Nov 18 2015

			For n = 4, representatives of the a(4) = 5 classes are
[1 0 0 0]  [1 1 0 0]  [1 1 0 0]  [1 1 1 0]  [1 1 1 1]
[0 1 0 0]  [1 1 0 0]  [0 1 1 0]  [1 1 0 1]  [1 1 1 1]
[0 0 1 0]  [0 0 1 1]  [0 0 1 1]  [1 0 1 1]  [1 1 1 1]
[0 0 0 1]  [0 0 1 1]  [1 0 0 1]  [0 1 1 1]  [1 1 1 1].
G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 18*x^6 + 43*x^7 + 313*x^8 + 7525*x^9 + ...

Index entries for sequences related to Latin squares and rectangles

One less than the row sums of A133687.

Cf. A333681.

a(n) = A333681(n-1). - Andrew Howroyd, Apr 03 2020

Description changed, after discussion with Andrew Howroyd, by Brendan McKay, Nov 18 2015

Terms a(12) and beyond from Andrew Howroyd, Apr 03 2020

A333732 Number of non-isomorphic n X n binary matrices with equal row and column sums up to permutation of rows and columns and transposition.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 18, 40, 230, 4296, 431206, 162267272, 201636689772, 777816803942188, 9865957936943931980, 395886667549681689592056, 53716176608076643470621240097, 23524515269630339982914646822137232, 35682168849414944013547274452501783251521

Offset: 0

Andrew Howroyd, Apr 03 2020

nonn

Number of simple regular bicolored graphs on 2n unlabeled nodes and allowing the color classes to be interchanged.

First differs from A008324 at n=12. See the note in A004066 by Sean A. Irvine for an explanation of why these two sequences are different.

Cf. A004066, A008324, A333160, A333681.

a(n) = (A333160(n) + A333681(n)) / 2.

a(n) >= A008324(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

A000519 Number of equivalence classes of nonzero regular 0-1 matrices of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A333732 Number of non-isomorphic n X n binary matrices with equal row and column sums up to permutation of rows and columns and transposition.

Views

Author

Keywords

Comments

Crossrefs

Formula