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

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

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 19, 44, 314, 7526, 846993, 324127860, 403254094632, 1555631972009430, 19731915624463099553, 791773335030637885025288, 107432353216118868234728540268, 47049030539260648478475949282317452, 71364337698829887974206671525372672234855

Offset: 0

Andrew Howroyd, Apr 01 2020

nonn

			The a(2) = 3 matrices are:
  [0 0]  [0 1]  [1 1]
  [0 0]  [1 0]  [1 1]

Row sums of A133687.

Cf. A000519, A067209, A333160.

a(n) = A000519(n) + 1.

A111802 n^2-n-1 for n>3; a(1)=1; a(2)=2; a(3)=3.

Original entry on oeis.org

1, 2, 3, 11, 19, 29, 41, 55, 71, 89, 109, 131, 155, 181, 209, 239, 271, 305, 341, 379, 419, 461, 505, 551, 599, 649, 701, 755, 811, 869, 929, 991, 1055, 1121, 1189, 1259, 1331, 1405, 1481, 1559, 1639, 1721, 1805, 1891, 1979, 2069, 2161, 2255, 2351, 2449, 2549

Offset: 1

Rick L. Shepherd, Aug 17 2005

Inspired by attempt to determine what incorrectly-named A000519 may really be. Conjecture: Sequence is number of different main-diagonal sums among Latin squares of order n. Confirmed for first five terms. Guaranteed to be an upper bound as the diagonal sum can only be in the range from n to n^2 inclusive and it is impossible for the sum to be n+1 or n^2-1. There is probably an easy proof that all other sums in this interval can be realized as the only restriction seems to be that it is not permissible for exactly n-1 numbers on a diagonal to be identical.

			a(3) = 3, the number of different diagonal sums of all order 3 Latin squares. Their diagonal sums can only be 3, 6 and 9.

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A028387.

Table[If[n<4,n,n^2-n-1],{n,60}] (* or *) LinearRecurrence[{3,-3,1},{1,2,3,11,19,29},60] (* Harvey P. Dale, Sep 04 2018 *)

a(n)=if(n>3,n^2-n-1,n) \\ Charles R Greathouse IV, Dec 20 2011

a(n) = n^2-n-1 = A028387(n-2) for n>3; a(n) = n for 1<=n<=3.

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

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

Views

Author

Keywords

Examples

Crossrefs

Formula

A111802 n^2-n-1 for n>3; a(1)=1; a(2)=2; a(3)=3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula