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

A005745 Number of n-covers of an unlabeled 3-set.

Original entry on oeis.org

1, 6, 23, 65, 156, 336, 664, 1229, 2159, 3629, 5877, 9221, 14070, 20951, 30530, 43634, 61283, 84725, 115461, 155294, 206368, 271210, 352784, 454550, 580509, 735280, 924163, 1153207, 1429292, 1760218, 2154776, 2622859, 3175555, 3825247

Offset: 1

N. J. A. Sloane, Simon Plouffe

Number of n X 3 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
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 = 1..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.
First differences give A055609.
Cf. A002623, A002727.
Cf. A005744, A005746, A005747, A005748, A005771.

Vec(G(3, x) - G(2, x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

a(n) = A002727(n) - A002623(n).

G.f.: -x*(x^8-x^7-x^6-2*x^5+2*x^4+x^3-3*x^2-2*x-1)/((x^3-1)^2*(x^2-1)^2*(x-1)^4).

More terms from Vladeta Jovovic, May 26 2000

A005746 Number of n-covers of an unlabeled 4-set.

Original entry on oeis.org

1, 9, 51, 230, 863, 2864, 8609, 23883, 61883, 151214, 350929, 778113, 1656265, 3398229, 6743791, 12983181, 24311044, 44377016, 79124476, 138048542, 236050912, 396137492, 653285736, 1059923072, 1693592112, 2667563553, 4145373780, 6360553548, 9643151582

Offset: 1

N. J. A. Sloane, Simon Plouffe

Number of n X 4 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

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

Colin Barker, Table of n, a(n) for n = 1..1000
R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.
First differences give A055082.
Cf. A002727, A006148.
Cf. A005744, A005745, A005747, A005748, A005771.

Rest@ CoefficientList[Series[x (1 + 3 x + 9 x^2 + 26 x^3 + 35 x^4 + 92 x^5 + 127 x^6 + 201 x^7 + 242 x^8 + 253 x^9 + 248 x^10 + 205 x^11 + 123 x^12 + 86 x^13 + 31 x^14 + 24 x^15 + 19 x^16 + 5 x^17 + 3 x^18 -
2 x^19 - 4 x^20 + 2 x^21 - 4 x^22 + 3 x^23 - x^25 + 2 x^26 - x^27)/((1 - x)^16 (1 + x)^6 (1 + x^2)^3 (1 + x + x^2)^4), {x, 0, 29}], x] (* Michael De Vlieger, Aug 23 2016 *)

Vec(x*(1 +3*x +9*x^2 +26*x^3 +35*x^4 +92*x^5 +127*x^6 +201*x^7 +242*x^8 +253*x^9 +248*x^10 +205*x^11 +123*x^12 +86*x^13 +31*x^14 +24*x^15 +19*x^16 +5*x^17 +3*x^18 -2*x^19 -4*x^20 +2*x^21 -4*x^22 +3*x^23 -x^25 +2*x^26 -x^27) / ((1 -x)^16*(1 +x)^6*(1 +x^2)^3*(1 +x +x^2)^4) + O(x^40)) \\ Colin Barker, Aug 23 2016

Vec(G(4, x) - G(3, x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

a(n) = A006148(n) - A002727(n).

G.f.: x*(1 +3*x +9*x^2 +26*x^3 +35*x^4 +92*x^5 +127*x^6 +201*x^7 +242*x^8 +253*x^9 +248*x^10 +205*x^11 +123*x^12 +86*x^13 +31*x^14 +24*x^15 +19*x^16 +5*x^17 +3*x^18 -2*x^19 -4*x^20 +2*x^21 -4*x^22 +3*x^23 -x^25 +2*x^26 -x^27) / ((1 -x)^16*(1 +x)^6*(1 +x^2)^3*(1 +x +x^2)^4). - Corrected by Colin Barker, Aug 23 2016

More terms and g.f. from Vladeta Jovovic, May 26 2000

a(19) onwards corrected by Sean A. Irvine, Aug 22 2016

A005747 Number of n-covers of an unlabeled 6-set.

Original entry on oeis.org

1, 16, 196, 2197, 22952, 223034, 2004975, 16642937, 127654604, 907349654, 6000728764, 37093282121, 215296646264, 1178514299094, 6108871834312, 30098215339608, 141433252447082, 635816643771438, 2742163498527536, 11374522802412498, 45482770393453638

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

Number of n X 6 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
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 = 1..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.

First differences give A055084.

Vec((G(6, x) - G(5, x)) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Corrected and extended by Vladeta Jovovic, Jun 13 2000

Terms a(20) and beyond from Andrew Howroyd, Feb 28 2023

A005771 Number of n-covers of an unlabeled 5-set.

Original entry on oeis.org

1, 12, 103, 736, 4571, 25326, 127415, 588687, 2518997, 10053739, 37656707, 133084998, 445949359, 1422934989, 4340110439, 12697803333, 35744330644, 97081519369, 255032046536, 649459943602, 1606518048420, 3867119228081, 9073566868140, 20783186834063

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

Number of n X 5 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
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 = 1..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.
First differences give A055083.
Cf. A006148, A052264.

Vec(G(5, x) - G(4, x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

a(n) = A052264(n) - A006148(n). - Andrew Howroyd, Feb 28 2023

More terms from Vladeta Jovovic, Jun 13 2000

Terms a(21) and beyond from Andrew Howroyd, Feb 28 2023

A055084 Number of 6 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 15, 180, 2001, 20755, 200082, 1781941, 14637962, 111011667, 779695050, 5093379110, 31092553357, 178203364143, 963217652830, 4930357535218, 23989343505296, 111335037107474, 494383391324356, 2106346854756098

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column k=6 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(6, x) - G(5, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 8, 42, 179, 633, 2001, 5745, 15274, 38000, 89331, 199715, 427184, 878152, 1741964, 3345562, 6239390, 11327863, 20065972, 34747460, 58924066, 98002370, 160086580, 257148244, 406637336, 633669040, 973971441, 1477810227, 2215179768, 3282598034, 4811946882

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning, B 5 (1978), 31-43.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy]

Column k=4 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(4, x) - G(3, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A055083 Number of 5 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 11, 91, 633, 3835, 20755, 102089, 461272, 1930310, 7534742, 27602968, 95428291, 312864361, 976985630, 2917175450, 8357692894, 23046527311, 61337188725, 157950527167, 394427897066, 957058104818, 2260601179661, 5206447640059, 11709619965923, 25752660738209

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Column k=5 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(5, x) - G(4, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

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

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

A005745 Number of n-covers of an unlabeled 3-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A005746 Number of n-covers of an unlabeled 4-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A005747 Number of n-covers of an unlabeled 6-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A005771 Number of n-covers of an unlabeled 5-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A055084 Number of 6 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions