A052271 -id:A052271 - 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]

A039623 a(n) = n^2*(n^2+3)/4.

Original entry on oeis.org

1, 7, 27, 76, 175, 351, 637, 1072, 1701, 2575, 3751, 5292, 7267, 9751, 12825, 16576, 21097, 26487, 32851, 40300, 48951, 58927, 70357, 83376, 98125, 114751, 133407, 154252, 177451, 203175, 231601, 262912, 297297, 334951, 376075, 420876, 469567

Offset: 1

Christian Meland (christian.meland(AT)pfi.no)

Previous definition was: Consider a figure like this <> (a squashed square, symmetric about both axes); each side is given 1 of n colors; a(n) = number of possibilities, allowing turning over.
Also number of 2 X 2 matrices with entries mod n, up to row and column permutation. Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively. - Vladeta Jovovic, Nov 04 2000
Also, if a 2-set Y and a 3-set Z are disjoint subsets of an n-set X then a(n-5) is the number of 6-subsets of X intersecting both Y and Z. - Milan Janjic, Sep 08 2007

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Jean-Paul Delahaye, Le miraculeux "lemme de Burnside", pp. 145-6 in 'Pour la Science' (French edition of 'Scientific American'), No. 350, December 2006, Paris.
Milan Janjic, Two Enumerative Functions.
Milan Janjic and Boris Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000217, A002724, A005353, A052271, A052272, A058001-A058004.

Row n=2 of A246106.

[n^2*(n^2+3)/4 : n in [1..50]]; // Wesley Ivan Hurt, Dec 26 2016

A039623:=n->n^2*(n^2+3)/4: seq(A039623(n), n=1..50); # Wesley Ivan Hurt, Dec 26 2016

Table[(n^2 (n^2+3))/4,{n,40}] (* or *) LinearRecurrence[{5,-10,10,-5,1},{1,7,27,76,175},40] (* Harvey P. Dale, Oct 01 2011 *)

Vec((-1-2*x-2*x^2-x^3)/(x-1)^5 + O(x^50)) \\ Michel Marcus, Aug 23 2015

a(n) = (1/4)*n^2*(n^2+3); \\ Altug Alkan, Apr 16 2016

From Harvey P. Dale, Oct 01 2011: (Start)
G.f.: (1 + 2*x + 2*x^2 + x^3)/(1 - x)^5.
a(1)=1, a(2)=7, a(3)=27, a(4)=76, a(5)=175; for n>5, a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5). (End)
E.g.f.: x*(4 + 10*x + 6*x^2 + x^3)*exp(x)/4. - Ilya Gutkovskiy, Apr 16 2016
a(n) = t(n-1)*t(n) + t(n-1) + t(n) where t=A000217. - J. M. Bergot, Apr 16 2016
a(n) = A000217(n)^2 - n*A000217(n-1). - Bruno Berselli, Feb 14 2017
a(n) = T(T(n-1)) + T(T(n)) where T(n) = A000217(n). - Charlie Marion, Feb 09 2023
Sum_{n>=1} 1/a(n) = 2*(1 + Pi^2 - sqrt(3)*Pi*coth(sqrt(3)*Pi))/9. - Amiram Eldar, Feb 13 2023
a(n) = binomial(n,2)*binomial(n+1,2) + n^2 = A006011(n) + A000290(n). - Detlef Meya, Nov 23 2023

More terms from Sam Alexander

Simplified the definition. - N. J. A. Sloane, Apr 20 2016

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

A052269 Number of n X n matrices over GF(3) up to row and column permutations.

Original entry on oeis.org

1, 3, 27, 738, 90492, 64796982, 302752867740, 9610448114487414, 2130536585704570302966, 3379836486315342147630795474, 39197947672609240635681299333726499, 3385559039111928075792568062997302563515455, 2212558055097091715366351569353345370930731329332056

Offset: 0

Vladeta Jovovic, Feb 04 2000

nonn

Cf. A002724, A052271, A052272, A091060.

Column k=3 of A246106.

A052269(n)=A353585(3,n,n) \\ M. F. Hasler, Apr 30 2022

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[...] = 3^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

A058001 Number of 3 X 3 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 36, 738, 8240, 57675, 289716, 1144836, 3780288, 10865205, 27969700, 65834406, 143887536, 295467263, 575308020, 1069960200, 1911933696, 3298486761, 5516122788, 8972008810, 14233690800, 22078652211, 33555443636, 50058302988, 73417387200, 106006948125

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Marko R. Riedel, Number of equivalence classes of matrices, Math Stackexchange.
Marko R. Riedel, Computing the cycle index for arbitary k x l matrices using Maple
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Cf. A058002, A058003, A058004, A002724, A052271, A052272.

Row n=3 of A246106.

CoefficientList[Series[x (12x^7+369x^6+2514x^5+4375x^4+2360x^3+423x^2+26x+1)/(x-1)^10,{x,0,30}],x] (* or *) LinearRecurrence[{10,-45,120,-210,252,-210,120,-45,10,-1},{0,1,36,738,8240,57675,289716,1144836,3780288,10865205},30] (* Harvey P. Dale, Nov 23 2024 *)

a(n) = (1/3!^2)*(n^9 + 6*n^6 + 9*n^5 + 8*n^3 + 12*n^2).

G.f.: x*(12*x^7+369*x^6+2514*x^5+4375*x^4+2360*x^3+423*x^2+26*x+1) / (x-1)^10. - Colin Barker, Jul 09 2013

A058004 Number of 6 X 6 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 251610, 302752867740, 9178323524804624, 28125393244553141210, 19909522361922032493690, 5116530046996205504668323, 626072069382507442113224128, 43460016875695276108491159279

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A039623, A058001-A058003, A002724, A052271, A052272.

Row n=6 of A246106.

a(n)=(1/6!^2)*(n^36 + 30*n^30 + 225*n^26 + 170*n^24 + 1350*n^22 + 3225*n^20 + 4075*n^18 + 9900*n^16 + 28500*n^14 + 56048*n^12 + 61020*n^10 + 77616*n^8 + 153840*n^6 + 87840*n^4 + 34560*n^2).

A058003 Number of 5 X 5 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 5624, 64796982, 79846389608, 20834113243925, 1979525296377132, 93242242505023122, 2625154125717590496, 49871029909245781491, 694584034909225304800, 7525039263469551291908, 66252712846754819753160

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A039623, A058001, A058002, A058004, A002724, A052271, A052272.

Row n=5 of A246106.

a(n)=(1/5!^2)*(n^25 + 20*n^20 + 100*n^17 + 70*n^15 + 300*n^14 + 225*n^13 + 400*n^12 + 400*n^11 + 100*n^10 + 1600*n^9 + 2300*n^8 + 1300*n^7 + 1200*n^6 + 1824*n^5 + 480*n^4 + 1680*n^3 + 2400*n^2).

More terms from James Sellers, Nov 08 2000

A058002 Number of 4 X 4 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 317, 90492, 7880456, 270656150, 4947097821, 58002778967, 490172624992, 3223155968811, 17382581357725, 79840867013666, 321169288917192, 1155731257886192, 3782368364610941, 11406226119319725, 32031530635953536, 84493500676300117, 210856844364222717

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A058001, A058003, A058004, A002724, A052271, A052272.

Row n=4 of A246106.

a(n)=(1/4!^2)*(n^16 + 12*n^12 + 36*n^10 + 67*n^8 + 160*n^6 + 204*n^4 + 96*n^2).

G.f.: -x*(x +1)*(x^14 +299*x^13 +84940*x^12 +6299584*x^11 +142482546*x^10 +1214416453*x^9 +4351647617*x^8 +6732281120*x^7 +4351647617*x^6 +1214416453*x^5 +142482546*x^4 +6299584*x^3 +84940*x^2 +299*x +1) / (x -1)^17. - Colin Barker, Jul 09 2013

More terms from Colin Barker, Jul 09 2013

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

A039623 a(n) = n^2*(n^2+3)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

A052269 Number of n X n matrices over GF(3) up to row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A058001 Number of 3 X 3 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A058004 Number of 6 X 6 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A058003 Number of 5 X 5 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords