A002724 -id:A002724 - cp's OEIS frontend

A002728 Number of n X (n+2) binary matrices.

1, 4, 22, 190, 3250, 136758, 17256831, 7216495370, 10271202313659, 49856692830176512, 826297617412284162618, 46948445432190686211183650, 9200267975562856184153936960940, 6261904454889790650636380541051266410, 14910331834338546882501064075429145637985605

Offset: 0

N. J. A. Sloane

nonn

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..23 from Alois P. Heinz)
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]
B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.

Cf. A002623, A002727, A006148, A002724, A002725.

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

b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
a:= n-> add(add(2^add(add(igcd(i, j)* coeff(s, x, i)*
      coeff(t, x, j), j=1..degree(t)), i=1..degree(s))/
      mul(i^coeff(s, x, i)*coeff(s, x, i)!, i=1..degree(s))/
      mul(i^coeff(t, x, i)*coeff(t, x, i)!, i=1..degree(t)),
      t=b(n+2$2)), s=b(n$2)):
seq(a(n), n=0..12);  # Alois P. Heinz, Aug 01 2014

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Table[Function[{p}, p + j*x^i]@ b[n-i*j, i-1] , {j, 0, n/i}]]] // Flatten; a[n_] := 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+2, n+2]}], {s, b[n, n]}]; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Nov 28 2014, after Alois P. Heinz *)

a(n) = A(n+2,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+2} (fix A[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 fix A[...] = 2^sum {i, j>=1} (gcd(i, j)*s_i*t_j). - Sean A. Irvine, Jul 31 2014

More terms from Vladeta Jovovic, Feb 04 2000

A053305 Number of 8 X 8 binary matrices with n=0..64 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 3, 6, 16, 34, 90, 211, 558, 1371, 3601, 9209, 24110, 61740, 157559, 390832, 946490, 2206364, 4948194, 10591141, 21606125, 41821936, 76738813, 133157386, 218402867, 338187004, 494330780, 681660841, 886842587, 1088201827

Offset: 0

Vladeta Jovovic, Mar 05 2000

Andrew Howroyd, Table of n, a(n) for n = 0..64

Row 8 of A052371 and A321609.

Cf. A049311, A002724.

\\ See A321609 for M.
vector(65, n, M(8, 8, n-1))

a(n) = A049311(n) for n <= 8.

Sum_{n=0..64} a(n) = 14685630688 = A002724(8).

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

A123234 Number of n X n Latin squares up to row and column permutation (or "RC-equivalence").

Original entry on oeis.org

1, 1, 1, 4, 16, 1868, 2420400, 66915816462

Offset: 1

Dan Eilers, Oct 06 2006

Brendan McKay writes: (Start)
"It would be possible to find the counts for n=9 and n=10 using the method of my paper in JCD [see link below]. For n=10 it is probably a 24-digit number. I'll explain the method I used. See the paper above for terminology.
"Is(L) is the autotopism group. Also define the group RC(L) of all autotopisms for which the symbols component is the identity. For any Latin square L we have:
"The isotopy class containing L contains (n!)^3/|Is(L)| squares.
"The RC-equivalence class containing L contains (n!)^2/|RC(L)| squares.
"If L and L' are isotopic then |RC(L)| = |RC(L')|. Therefore the number of RC-equivalence classes in the isotopy class of L is n!*|RC(L)|/|Is(L)|. I modified an existing program slightly to find |RC(L)|/|Is(L)|. and applied it to one square from each isotopy class. The sum of n!*|RC(L)|/|Is(L)| is the total number of RC-equivalence classes. " (End)

			01234 => 20413 => 01234
13042 => 01234 => 14320
24310 => 32041 => 20413
30421 => 43102 => 32041
42103 => 14320 => 43102
The first square is transformed by permuting columns; the 2nd square is transformed by permuting rows.
Both the first and 3rd square are in reduced form, so are considered equivalent by row/col permutation.

Dan R. Eilers, Phil A. Sallee, The number of Latin squares up to row and column permutation, Poster Session, Harvey Mudd College Mathematics Conference on Enumerative Combinatorics (2006) (for terms 1 to 7)
Brendan D. McKay, private communication (2006) (for term 8)

B. D. McKay, A. Meynert, W. Myrvold, (2007), Small latin squares, quasigroups, and loops, J. Combin. Designs, 15 (2007), 98-119. doi:10.1002/jcd.20105
Index entries for sequences related to Latin squares and rectangles

Cf. A000315, A002724, A058163.

A321609 Array read by antidiagonals: T(n,k) is the number of inequivalent binary n X n matrices with k ones, under row and column permutations.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 3, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 6, 3, 1, 1, 0, 0, 0, 7, 6, 3, 1, 1, 0, 0, 0, 7, 16, 6, 3, 1, 1, 0, 0, 0, 6, 21, 16, 6, 3, 1, 1, 0, 0, 0, 3, 39, 34, 16, 6, 3, 1, 1, 0, 0, 0, 1, 44, 69, 34, 16, 6, 3, 1, 1, 0, 0, 0, 1, 55, 130, 90, 34, 16, 6, 3, 1, 1

Offset: 0

Andrew Howroyd, Nov 14 2018

			Array begins:
==========================================================
n\k| 0  1  2  3  4  5  6   7   8    9   10    11    12
---+------------------------------------------------------
0  | 1  0  0  0  0  0  0   0   0    0    0     0     0 ...
1  | 1  1  0  0  0  0  0   0   0    0    0     0     0 ...
2  | 1  1  3  1  1  0  0   0   0    0    0     0     0 ...
3  | 1  1  3  6  7  7  6   3   1    1    0     0     0 ...
4  | 1  1  3  6 16 21 39  44  55   44   39    21    16 ...
5  | 1  1  3  6 16 34 69 130 234  367  527   669   755 ...
6  | 1  1  3  6 16 34 90 182 425  870 1799  3323  5973 ...
7  | 1  1  3  6 16 34 90 211 515 1229 2960  6893 15753 ...
8  | 1  1  3  6 16 34 90 211 558 1371 3601  9209 24110 ...
9  | 1  1  3  6 16 34 90 211 558 1430 3825 10278 28427 ...
...

Rows n=6..8 are A052370, A053304, A053305.
Main diagonal is A049311.
Row sums are A002724.
Cf. A052371 (as triangle), A057150, A246106, A318795.

permcount[v_List] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
c[p_List, q_List, k_] := SeriesCoefficient[Product[Product[(1 + O[x]^(k + 1) + x^LCM[p[[i]], q[[j]]])^GCD[p[[i]], q[[j]]], {j, 1, Length[q]}], {i, 1, Length[p]}], {x, 0, k}];
M[m_, n_, k_] := Module[{s = 0}, Do[Do[s += permcount[p]*permcount[q]*c[p, q, k], {q, IntegerPartitions[n]}], {p, IntegerPartitions[m]}]; s/(m!*n!)]
Table[M[n - k, n - k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
c(p, q, k)={polcoef(prod(i=1, #p, prod(j=1, #q, (1 + x^lcm(p[i], q[j]) + O(x*x^k))^gcd(p[i], q[j]))), k)}
M(m, n, k)={my(s=0); forpart(p=m, forpart(q=n, s+=permcount(p) * permcount(q) * c(p, q, k))); s/(m!*n!)}
for(n=0, 10, for(k=0, 12, print1(M(n, n, k), ", ")); print); \\ Andrew Howroyd, Nov 14 2018

T(n,k) = T(k,k) for n > k.

T(n,k) = 0 for k > n^2.

A052370 Number of 6 X 6 binary matrices with n=0...36 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 3, 6, 16, 34, 90, 182, 425, 870, 1799, 3323, 5973, 9595, 14570, 19865, 25191, 28706, 30310, 28706, 25191, 19865, 14570, 9595, 5973, 3323, 1799, 870, 425, 182, 90, 34, 16, 6, 3, 1, 1

Offset: 0

Vladeta Jovovic, Mar 08 2000

Sum_{k=0..36}a(n)=A002724(6)

Cf. A049311, A053304, A053305.

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

A241956 Number of inequivalent m X n binary matrices, where equivalence means permutations of rows or columns. Presented in diagonal order, with (m,n)=(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ... .

Original entry on oeis.org

2, 3, 3, 4, 7, 4, 5, 13, 13, 5, 6, 22, 36, 22, 6, 7, 34, 87, 87, 34, 7, 8, 50, 190, 317, 190, 50, 8, 9, 70, 386, 1053, 1053, 386, 70, 9, 10, 95, 734, 3250, 5624, 3250, 734, 95, 10, 11, 125, 1324, 9343, 28576, 28576, 9343, 1324, 125, 11

Offset: 1

Don Knuth, Aug 09 2014

Same as A028657 without first row and column.

			The array begins:
  2  3    4     5      6        7         8           9 ...
  3  7   13    22     34       50        70          95 ...
  4 13   36    87    190      386       734        1324 ...
  5 22   87   317   1053     3250      9343       25207 ...
  6 34  190  1053   5624    28576    136758      613894 ...
  7 50  386  3250  28576   251610   2141733    17256831 ...
  8 70  734  9343 136758  2141733  33642660   508147108 ...
  9 95 1324 25207 613894 17256831 508147108 14685630688 ...
  (cf. A028657).

Alois P. Heinz, Antidiagonals m = 1..45, flattened
Adalbert Kerber, Applied Finite Group Actions, second edition, Springer-Verlag, (1999). See table under Corollary 2.3.1 on page 68.
Various authors, How many n-by-m binary matrices are there up to row and column permutations
Index to number of inequivalent matrices modulo permutation of rows and columns

Cf. A002724.

b:= proc(n, i) b(n, i):= `if`(n=0, [[]], `if`(i<1, [], [seq(map(
      p->`if`(j=0, p, [p[], [i, j]]), b(n-i*j, i-1))[], j=0..n/i)]))
    end:
g:= proc(n, k) option remember; add(add(2^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+k$2)), s=b(n$2))
    end:
A:= (m, n)-> g(min(m, n), abs(m-n)):
seq(seq(A(m, 1+d-m), m=1..d), d=1..12); # Alois P. Heinz, Aug 13 2014

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 - k + 1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 09 2019, after Alois P. Heinz in A028657 *)

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).

A363846 Number of connected bipartite graphs on 2n nodes with a marked bipartite set of size n.

Original entry on oeis.org

1, 1, 2, 13, 150, 3529, 194203, 29350896, 13668966399, 20662731749804, 103588456044907944, 1744955436868541083098, 99859125842603176324368784, 19611138475504485904873456937288, 13340730475029359536419515017040194246, 31706419735128559894860278029259121951682970, 265351742295121848168241791689670791068746978140331

Offset: 0

Max Alekseyev, Jun 24 2023

nonn

Also, number of n X n binary matrices up to permutations of rows and columns, representing the reduced adjacency matrices of connected bipartite graphs (cf. A002724).

Max Alekseyev, Table of n, a(n) for n = 0..50

Diagonal of the rectangular array described in A363845.

Cf. A002724, A028657, A123549.

a(n) = A363845(2n, n).

cp's OEIS Frontend

A002728 Number of n X (n+2) binary matrices.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A053305 Number of 8 X 8 binary matrices with n=0..64 ones up to row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A123234 Number of n X n Latin squares up to row and column permutation (or "RC-equivalence").

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A321609 Array read by antidiagonals: T(n,k) is the number of inequivalent binary n X n matrices with k ones, under row and column permutations.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A052370 Number of 6 X 6 binary matrices with n=0...36 ones up to row and column permutations.

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A241956 Number of inequivalent m X n binary matrices, where equivalence means permutations of rows or columns. Presented in diagonal order, with (m,n)=(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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