A052269 -id:A052269 - cp's OEIS frontend

A002724 Number of inequivalent n X n binary matrices, where equivalence means permutations of rows or columns.

1, 2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, 21467043671008, 105735224248507784, 1764356230257807614296, 100455994644460412263071692, 19674097197480928600253198363072, 13363679231028322645152300040033513414, 31735555932041230032311939400670284689732948

Offset: 0

N. J. A. Sloane

A diagonal of the array A(m,n) described in A028657. - N. J. A. Sloane, Sep 01 2013

Also, number of bipartite graphs with both partite sets of size n, one of which is marked. For connected bipartite graphs, see A363846. - Max Alekseyev, Jun 24 2023

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..26 from Alois P. Heinz)
Manuel Kauers and Jakob Moosbauer, Good pivots for small sparse matrices, arXiv:2006.01623 [cs.SC], 2020.
A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
Mathematics Stack Exchange, How many n-by-m binary matrices are there up to row and column permutations
B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
Marko Riedel, Maple code with two different algorithms
M. Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
Index entries for sequences related to binary matrices
Index to number of inequivalent matrices modulo permutation of rows and columns

Cf. A002623, A002727, A006148, A002728, A002725, A052269, A052271, A052272, A091059, A363845, A363846, A000595.
Cf. A028657 (this sequence is the diagonal). - N. J. A. Sloane, Sep 01 2013
Column k=2 of A246106.

Maple
```
# See Marko Riedel link.
```

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Union[Flatten[Table[ Function[{p}, p + j*x^i] /@ b[n - i*j, i - 1], {j, 0, n/i}]]]]];
g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n - k]];
Table[A[n, n], {n, 0, 15}] (* Jean-François Alcover, Aug 10 2018, after Alois P. Heinz *)

a(n) = A(n,n) \\ A defined in A028657. - Andrew Howroyd, Mar 01 2023

a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...)) where fixA[...] = 2^Sum_{i, j>=1} (gcd(i, j)*s_i*t_j). - Christian G. Bower, Dec 18 2003

a(n) = A028657(2*n, n). - Max Alekseyev, Jun 24 2023

More terms from Vladeta Jovovic, Feb 04 2000

a(15) from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008

A246106 Number A(n,k) of inequivalent n X n matrices with entries from [k], where equivalence means permutations of rows or columns; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 7, 1, 0, 1, 4, 27, 36, 1, 0, 1, 5, 76, 738, 317, 1, 0, 1, 6, 175, 8240, 90492, 5624, 1, 0, 1, 7, 351, 57675, 7880456, 64796982, 251610, 1, 0, 1, 8, 637, 289716, 270656150, 79846389608, 302752867740, 33642660, 1, 0

Offset: 0

Alois P. Heinz, Aug 13 2014

			Square array A(n,k) begins:
  1, 1,    1,        1,           1,              1, ...
  0, 1,    2,        3,           4,              5, ...
  0, 1,    7,       27,          76,            175, ...
  0, 1,   36,      738,        8240,          57675, ...
  0, 1,  317,    90492,     7880456,      270656150, ...
  0, 1, 5624, 64796982, 79846389608, 20834113243925, ...

Columns k = 0-10 give: A000007, A000012, A002724, A052269, A052271, A052272, A246112, A246113, A246114, A246115, A246116.
Rows n = 0-10 give: A000012, A001477, A039623, A058001, A058002, A058003, A058004, A246108, A246109, A246110, A246111.
Main diagonal gives A246107.
A028657, A242106, A353585 are related tables.
Cf. A242095, A256069.

b:= proc(n, i) option remember; `if`(n=0, [[]],
      `if`(i<1, [], [b(n, i-1)[], seq(map(p->[p[], [i, j]],
       b(n-i*j, i-1))[], j=1..n/i)]))
    end:
A:= proc(n, k) option remember; add(add(k^add(add(i[2]*j[2]*
      igcd(i[1], j[1]), j=t), i=s) /mul(i[1]^i[2]*i[2]!, i=s)
      /mul(i[1]^i[2]*i[2]!, i=t), t=b(n$2)), s=b(n$2))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

A246106(n,k)=A353585(k,n,n) \\ M. F. Hasler, May 01 2022

A(n,k) = Sum_{i=0..k} C(k,i) * A256069(n,i).

A(n,k) = Sum_{p,q in P(n)} k^Sum_{i in p, j in q} gcd(i, j) / (N(p)*N(q)) where N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p. - M. F. Hasler, Apr 30 2022 [corrected by Anders Kaseorg, Oct 04 2024]

A052271 Number of n X n matrices over GF(4) under row and column permutations.

Original entry on oeis.org

1, 4, 76, 8240, 7880456, 79846389608, 9178323524804624, 12508419942924578958856, 209493560585995285291677153144, 44407122853769773657258254744483639216, 122042291850117110186411151373496788803833567344, 4435666701292795500500326090033525002278314431436080593856

Offset: 0

Vladeta Jovovic, Feb 05 2000

nonn

Cf. A002724, A052269, A052272, A091061.

Column k=4 of A246106.

a(n) = sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2,...]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...)) where fixA[...] = 4^sum_{i, j>=1} (gcd(i,j)*s_i*t_j). - Christian G. Bower, Dec 18 2003

More terms from Alois P. Heinz, Jul 31 2014

A052272 Number of n X n matrices over GF(5) under row and column permutations.

Original entry on oeis.org

1, 5, 175, 57675, 270656150, 20834113243925, 28125393244553141210, 699686291478538604891895515, 333504381764054807093590006199733915, 3140944762272022074073055438393255181867210010, 599071101908675118606355537962231556550216893297767505350

Offset: 0

Vladeta Jovovic, Feb 05 2000

nonn

Cf. A002724, A052269, A052271, A091062.

Column k=5 of A246106.

a(n) = sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...)) where fixA[...] = 5^sum_{i, j>=1} (gcd(i, j)*s_i*t_j). - Christian G. Bower, Dec 18 2003

A353585 Square array T(n,k): row n lists the number of inequivalent matrices over Z/nZ, modulo permutations of rows and columns, of size r X c, 1 <= r <= c, c >= 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 7, 6, 4, 1, 4, 27, 10, 5, 1, 13, 10, 76, 15, 6, 1, 36, 92, 20, 175, 21, 7, 1, 5, 738, 430, 35, 351, 28, 8, 1, 22, 15, 8240, 1505, 56, 637, 36, 9, 1, 87, 267, 35, 57675, 4291, 84, 1072, 45, 10, 1, 317, 5053, 1996, 70, 289716, 10528, 120, 1701, 55, 11

Offset: 1

M. F. Hasler, Apr 28 2022

The array is read by falling antidiagonals.
Each row lists the number of inequivalent matrices of size 1 X 1, then 2 X 1, 2 X 2, then 3 X 1, 3 X 2, 3 X 3, etc., with coefficients in Z/nZ (or equivalently, in {1, ..., n}). See Examples for more.
Row 1 counts the zero matrices, there is only one of any size. Row 2 counts binary matrices, this is the lower triangular part of A028657, without the trivial row & column 0. (This table might have been extended with a trivial column 0 = A000012 (counting the 1 matrix of size 0) and row 0 = A000007 counting the number of r X c matrices with no entry, as done in A246106.)
The square matrices (size 1 X 1, 2 X 2, 3 X 3, ...) are counted in columns with triangular numbers, k = T(r) = r(r+1)/2 = (1, 3, 6, 10, 15, ...) = A000217.

			The table starts
   n \ k=1,  2,   3,   4,   5,   6, ...: T(n,k)
  ----+--------------------------------------
   1  |  1   1    1    1    1     1 ...
   2  |  2   3    7    4   13    36 ...
   3  |  3   6   27   10   92   738 ...
   4  |  4  10   76   20  430  8240 ...
   5  |  5  15  175   35 1505 57675 ...
  ...
Columns 2, 3 and 4, 5, 6 correspond to matrices of size 1 X 2, 2 X 2 and 1 X 3, 2 X 3, 3 X 3, respectively.
Column 4 says that there are (1, 4, 10, 20, 35, ...) inequivalent matrices of size 1 X 3 with entries in Z/nZ (n = 1, 2, 3, 4, ...); these numbers are given by (n+2 choose 3) = binomial(n+2, 3) = n(n+1)(n+2)/6 = A000292(n).

OEIS Index to number of inequivalent matrices modulo permutation of row and columns.

All of the following related sequences can be expressed in terms of T(n, k, r) := T(n, k(k-1)/2 + r), WLOG r <= k:
A028657(n,k) = A353585(2,n,k): inequivalent m X n binary matrices,
A002723(n) = T(2,n,2): size n X 2, A002724(n) = T(2,n,n): size n X n,
A002727(n) = T(2,n,3): size n X 3, A002725(n) = T(2,n,n+1): size n X (n+1),
A006148(n) = T(2,n,4): size n X 4, A002728(n) = T(2,n,n+2): size n X (n+2),
A052264(n) = T(2,n,5): size n X 5,
A052269(n) = T(3,n,n): number of inequivalent ternary matrices of size n X n,
A052271(n) = T(4,n,n): number of inequivalent matrices over Z/4Z of size n X n,
A052272(n) = T(5,n,n): number of inequivalent matrices over Z/5Z of size n X n,
A246106(n,k) = A353585(k,n,n): number of inequivalent n X n matrices over Z/kZ, and its diagonal A091058 and columns 1, 2, ..., 10: A000012, A091059, A091060, A091061, A091062, A246122, A246123, A246124, A246125, A246126.

A353585(n,k,r)={if(!r,r=sqrtint(8*k)\/2; k-=r*(r-1)\2); my(m(c, p=1, L=0)=for(i=1,#c, if(i==#c || c[i+1]!=c[i], p *= c[i]^(i-L)*(i-L)!; L=i )); p, S=0); forpart(P=k, my(T=0); forpart(Q=r, T += n^sum(i=1,#P, sum(j=1,#Q, gcd(P[i],Q[j]) ))/m(Q)); S += T/m(P)); S}

Let k = c(c-1)/2 + r, 1 <= r <= c, then
T(n, c, r) := T(n, k) = Sum_{p in P(c), q in P(r)} n^S(p, q)/(N(p)*N(q)), where P(r) are the partitions of r, S(p, q) = Sum_{i in p, j in q} gcd(i, j), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p.
(See, e.g., A080577 for a list of partitions of positive integers.)
In particular:
T(n, 1) = n, T(n, 2) = n(n+1)/2 = A000217(n), T(n, 4) = C(n+2, 3) = A000292(n), T(n, 7) = C(n+3, 4) = A000332(n+3), etc.: T(n, k(k+1)/2 + 1) = C(n+k, k+1),
T(n, k(k+1)/2) = A246106(k, n).

cp's OEIS Frontend

A002724 Number of inequivalent n X n binary matrices, where equivalence means permutations of rows or columns.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A246106 Number A(n,k) of inequivalent n X n matrices with entries from [k], where equivalence means permutations of rows or columns; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A052271 Number of n X n matrices over GF(4) under row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A052272 Number of n X n matrices over GF(5) under row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Formula

A353585 Square array T(n,k): row n lists the number of inequivalent matrices over Z/nZ, modulo permutations of rows and columns, of size r X c, 1 <= r <= c, c >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula