A116532 -id:A116532 - cp's OEIS frontend

A116539 Number of zero-one matrices with n ones and no zero rows or columns and with distinct rows, up to permutation of rows.

1, 1, 2, 7, 28, 134, 729, 4408, 29256, 210710, 1633107, 13528646, 119117240, 1109528752, 10889570768, 112226155225, 1210829041710, 13640416024410, 160069458445202, 1952602490538038, 24712910192430620, 323964329622503527, 4391974577299578248, 61488854148194151940

Offset: 0

Vladeta Jovovic, Mar 27 2006

nonn

Also the number of labeled hypergraphs spanning an initial interval of positive integers with edge-sizes summing to n. - Gus Wiseman, Dec 18 2018

			From _Gus Wiseman_, Dec 18 2018: (Start)
The a(3) = 7 edge-sets:
    {{1,2,3}}
   {{1},{1,2}}
   {{2},{1,2}}
   {{1},{2,3}}
   {{2},{1,3}}
   {{3},{1,2}}
  {{1},{2},{3}}
Inequivalent representatives of the a(4) = 28 0-1 matrices:
  [1111]
.
  [100][1000][010][0100][001][0010][0001][110][110][1100][101][1010][1001]
  [111][0111][111][1011][111][1101][1110][101][011][0011][011][0101][0110]
.
  [10][100][100][1000][100][100][1000][1000][010][010][0100][0100][0010]
  [01][010][010][0100][001][001][0010][0001][001][001][0010][0001][0001]
  [11][101][011][0011][110][011][0101][0110][110][101][1001][1010][1100]
.
  [1000]
  [0100]
  [0010]
  [0001]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..300
P. J. Cameron, T. Prellberg and D. Stark, Asymptotics for incidence matrix classes , arXiv:math/0510155 [math.CO], 2005-2006.
M. Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Cf. A049311, A058891, A101370, A255906, A283877, A306021, A319190.
Row sums of A326914 and of A326962.

b:= proc(n, i, k) b(n, i, k):=`if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j,
      min(n-i*j, i-1), k)*binomial(binomial(k, i), j), j=0..n/i)))
    end:
a:= n-> add(add(b(n$2, i)*(-1)^(k-i)*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 13 2019

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, Min[n - i*j, i - 1], k]*Binomial[Binomial[k, i], j], {j, 0, n/i}]]];
a[n_] := Sum[Sum[b[n, n, i]*(-1)^(k-i)*Binomial[k, i], {i, 0, k}], {k, 0, n}];
a /@ Range[0, 23] (* Jean-François Alcover, Feb 25 2020, after Alois P. Heinz *)

a(0)=1 prepended and more terms added by Alois P. Heinz, Sep 13 2019

A181230 Square array T(m,n) giving the number of m X n (0,1)-matrices with pairwise distinct rows and pairwise distinct columns.

Original entry on oeis.org

2, 2, 2, 0, 10, 0, 0, 24, 24, 0, 0, 24, 264, 24, 0, 0, 0, 1608, 1608, 0, 0, 0, 0, 6720, 33864, 6720, 0, 0, 0, 0, 20160, 483840, 483840, 20160, 0, 0, 0, 0, 40320, 5644800, 19158720, 5644800, 40320, 0, 0, 0, 0, 40320, 57415680, 595506240, 595506240, 57415680, 40320

Offset: 1

R. H. Hardin, Oct 10 2010

			Table starts
.2..2.....0...........0...............0..................0
.2.10....24..........24...............0..................0
.0.24...264........1608............6720..............20160
.0.24..1608.......33864..........483840............5644800
.0..0..6720......483840........19158720..........595506240
.0..0.20160.....5644800.......595506240........44680224960
.0..0.40320....57415680.....16388749440......2881362718080
.0..0.40320...518676480....418910083200....172145618789760
.0..0.....0..4151347200..10136835072000...9841604944066560
.0..0.....0.29059430400.233811422208000.546156941728204800

R. H. Hardin, Table of n, a(n) for n=1..180
MathOverflow, Number of matrices with no repeated columns or rows

Cf. A088310 (diagonal), A181231, A181232, A181233 (subdiagonals).

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

T(m,n) = Sum_{i=0..n} Sum_{j=0..m} stirling1(n,i) * stirling1(m,j) * 2^(i*j) = n! * Sum_{j=0..m} stirling1(m,j) * binomial(2^j,n) = m! * Sum_{i=0..n} stirling1(n,i) * binomial(2^i,m). - Max Alekseyev, Jun 18 2016

T(m,n) = A059084(m,n) * n!.

A059202 Triangle T(n,m) of numbers of m-block T_0-covers of a labeled n-set, m = 0..2^n - 1.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 0, 0, 3, 29, 35, 21, 7, 1, 0, 0, 0, 140, 1015, 2793, 4935, 6425, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 0, 0, 0, 420, 13965, 126651, 661801, 2533135, 7792200, 20085000, 44307120, 84651840, 141113700, 206251500, 265182300

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Jan 18 2001

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.

Also, T(n,m) is the number of n X m (0,1)-matrices with pairwise distinct nonzero columns and pairwise distinct nonzero rows, up to permutation of columns.

			[1],
[0,1],
[0,0,3,1],
[0,0,3,29,35,21,7,1],
...
There are 35 4-block T_0-covers of a labeled 3-set.

Robert Israel, Table of n, a(n) for n = 0..4094 (rows 0 to 11, flattened).
T_0-covers of a labeled 3-set

Cf. A059201 (row sums), A059203 (column sums), A094000 (main diagonal).
Cf. A059084, A059085, A059086, A059087, A059088, A059089, A181230.
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

with(combinat): for n from 0 to 10 do for m from 0 to 2^n-1 do printf(`%d,`,(1/m!)*sum(stirling1(m+1,i)*product(2^(i-1)-1-j, j=0..n-1), i=1..m+1)) od: od:

T[n_, m_] = Sum[ StirlingS1[n + 1, i + 1]*Binomial[2^i - 1, m], {i, 0, n}]; Table[T[n, m], {n, 0, 5}, {m, 0, 2^n - 1}] (* G. C. Greubel, Dec 28 2016 *)

T(n, m) = (1/m!)*Sum_{1..m + 1} stirling1(m + 1, i)*[2^(i - 1) - 1]_n, where [k]_n := k*(k - 1)*...*(k - n + 1), [k]_0 = 1.
E.g.f: Sum((1+x)^(2^n-1)*log(1+y)^n/n!, n=0..infinity)/(1+y). - Vladeta Jovovic, May 19 2004
Also T(n, m) = Sum_{i=0..n} Stirling1(n+1, i+1)*binomial(2^i-1, m). - Vladeta Jovovic, Jun 04 2004
T(n,m) = A181230(n,m)/m! - n*T(n-1,m) - T(n,m-1) - n*T(n-1,m-1). - Max Alekseyev, Dec 11 2017

More terms from James Sellers, Jan 24 2001

A088310 Number of n X n (0,1)-matrices with all rows distinct and all columns distinct.

Original entry on oeis.org

1, 2, 10, 264, 33864, 19158720, 44680224960, 413586858182400, 14960200449325582080, 2109063823453947981680640, 1162864344149083760773678387200, 2520991223487759548686737154649702400, 21598422878151131130336454273775859841843200, 734233037731110118818452425552296701963294284185600

Offset: 0

N. J. A. Sloane, Nov 07 2003

nonn

			a(2) = 10: 00/01, 00/10, 01/00, 01/10, 01/11, 10/00, 10/01, 10/11, 11/01, 11/10.

G. C. Greubel, Table of n, a(n) for n = 0..57

Cf. A088229, A088309.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

A088310:= func< n | Factorial(n)*(&+[Binomial(2^k,n)*StirlingFirst(n,k): k in [0..n]]) >;
[A088310(n): n in [0..30]]; // G. C. Greubel, Dec 14 2022

Table[n!*Sum[StirlingS1[n, k]*Binomial[2^k,n], {k, 0, n}], {n, 0, 15}] (* Vaclav Kotesovec, Jul 02 2016 *)

@CachedFunction
def A088310(n): return (-1)^n*factorial(n)*sum((-1)^k*binomial(2^k,n)*stirling_number1(n,k) for k in (0..n))
[A088310(n) for n in range(31)] # G. C. Greubel, Dec 14 2022

a(n) = n! * Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003
a(n) = Sum_{i=0..n} Sum_{j=0..n} stirling1(n, i) * stirling1(n, j) * 2^(i*j). - Max Alekseyev, Nov 07 2003
a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2016
a(n) = A181230(n,n).

Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003

a(0)-a(5) from W. Edwin Clark, Nov 07 2003

A094000 Number of n X n (0,1)-matrices with no zero rows or columns and with all rows distinct and all columns distinct, up to permutation of rows.

Original entry on oeis.org

1, 1, 3, 29, 1015, 126651, 53354350, 74698954306, 350688201987402, 5624061753186933530, 314512139441575825493524, 62498777166571927258267336860, 44831219113504221199415663547412096

Offset: 0

Goran Kilibarda and Vladeta Jovovic, May 30 2004

Main diagonal of A059202.

G. Kilibarda and V. Jovovic, "Enumeration of some classes of T_0-hypergraphs", in

G. C. Greubel, Table of n, a(n) for n = 0..59
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

Cf. A048291, A059202, A088309.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

f[n_] := Sum[ StirlingS1[n + 1, k] Binomial[2^(k - 1) - 1, n], {k, 0, n + 1}]; Table[ f[n], {n, 0, 12}] (* Robert G. Wilson v, Jun 01 2004 *)

a(n) = sum(k=0, n+1, stirling(n+1, k, 1)*binomial(2^(k-1)-1, n)); \\ Michel Marcus, Dec 17 2022

a(n) = Sum_{k=0..n+1} Stirling1(n+1, k)*binomial(2^(k-1)-1, n).

a(n) ~ binomial(2^n,n). - Vaclav Kotesovec, Mar 18 2014

More terms from Robert G. Wilson v, Jun 01 2004

A088309 Number of equivalence classes of n X n (0,1)-matrices with all rows distinct and all columns distinct.

Original entry on oeis.org

1, 2, 5, 44, 1411, 159656, 62055868, 82060884560, 371036717493194, 5812014504668066528, 320454239459072905856944, 63156145369562679089674952768, 45090502574837184532027563736271152, 117910805393665959622047902193019284914432, 1139353529410754170844431642119963019965901238144

Offset: 0

N. J. A. Sloane, Nov 07 2003

nonn

Two such matrices are equivalent if they differ just by a permutation of the rows.

			a(2) = 5: 00/01, 00/10, 01/10, 01/11, 10/11.

G. C. Greubel, Table of n, a(n) for n = 0..59
G. Kilibarda and V. Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

Cf. A088229, A088310, A088616.
Main diagonal of A059084.
Binary matrices with distinct rows and columns, various versions: A059202, this sequence, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763.

A088309:= func< n | (&+[Binomial(2^k,n)*StirlingFirst(n,k): k in [0..n]]) >;
[A088309(n): n in [0..30]]; // G. C. Greubel, Dec 15 2022

A088309[n_]:= A088309[n]=Sum[Binomial[2^j,n]*StirlingS1[n,j], {j,0,n}];
Table[A088309[n], {n,0,30}] (* G. C. Greubel, Dec 15 2022 *)

a(n) = sum(k=0, n, stirling(n, k, 1)*binomial(2^k, n)); \\ Michel Marcus, Dec 16 2022

@CachedFunction
def A088309(n): return (-1)^n*sum((-1)^k*binomial(2^k, n)*stirling_number1(n, k) for k in (0..n))
[A088309(n) for n in range(31)] # G. C. Greubel, Dec 15 2022

a(n) = Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003

a(n) = A088310(n) / n!.

Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003

a(0)-a(5) from W. Edwin Clark, Nov 07 2003

A093466 Triangle read by rows: T[n,k] = number of n X n binary matrices with k=0...n^2 ones, distinct up to cyclic shifts of rows and columns; reflection through any vertical or horizontal axis; and reflection through the main diagonal. Also, quasi-n-ominoes on a torus divided into a k X k grid.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 5, 5, 4, 2, 1, 1, 1, 1, 5, 10, 33, 53, 101, 122, 153, 122, 101, 53, 33, 10, 5, 1, 1, 1, 1, 5, 19, 88, 309, 975, 2537, 5637, 10510, 16740, 22734, 26500, 26500, 22734, 16740, 10510, 5637, 2537, 975, 309, 88, 19, 5, 1, 1

Offset: 1

Jon Wild, May 21 2004

			[1,1], [1,1,2,1,1], [1,1,2,4,5,5,4,2,1,1] (the last block giving the numbers of 3 X 3 binary matrices with k=0...9 ones, distinct up to the transformations listed above.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

A259763 Number of symmetric n X n (0,1)-matrices with pairwise distinct rows and columns.

Original entry on oeis.org

1, 2, 6, 44, 716, 24416, 1680224, 229468288, 61820527104, 32848197477760, 34502874046006912, 71850629135663531776, 297429744309497638961920, 2452504520881914016303901696, 40340635076928240671195746599936, 1324981038432182976845483456362661888, 86953044949519288083916385603832568137728

Offset: 0

Max Alekseyev, Jul 04 2015

nonn

G. C. Greubel, Table of n, a(n) for n = 0..80
MathOverflow, Counting matrices of special types, 2015.

Cf. A088310, A006024

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

[(&+[StirlingFirst(n,k)*2^Binomial(k+1,2): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Nov 04 2018

Table[Sum[StirlingS1[n,k]*2^Binomial[k+1,2], {k,0,n}], {n,0,20}] (* G. C. Greubel, Nov 04 2018*)

A259763(n) = sum(k=1,n, stirling(n,k,1) * 2^(k*(k+1)/2) );

a(n) = Sum_{k=0..n} Stirling1(n,k) * 2^(k*(k+1)/2).

a(0)=1 prepended by Alois P. Heinz, Jul 12 2015

A088616 a(n) = number of n X n (0,1) matrices A such that the 2n vectors consisting of the rows and the columns of the matrix A are all distinct.

Original entry on oeis.org

0, 0, 24, 6840, 6568800, 22080988800, 262378244741760

Offset: 1

Yuval Dekel and Vladeta Jovovic, Nov 17 2003

What if you also ask that the two main diagonals are also distinct? - N. J. A. Sloane, Jan 03 2004

Cf. A088310.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

a(6)-a(7) from Bert Dobbelaere, May 05 2025

A089673 a(n) = number of n X n (0,1) matrices A such that the 2n+2 vectors consisting of the rows and the columns of the matrix A, as well as the main diagonal and the main antidiagonal, are all distinct.

Original entry on oeis.org

0, 0, 0, 652, 1658784, 10726929248, 172790068546048

Offset: 1

Vladeta Jovovic, Jan 04 2004

Cf. A088310, A088616, A089674.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

a(6)-a(7) from Bert Dobbelaere, May 05 2025

cp's OEIS Frontend

A116539 Number of zero-one matrices with n ones and no zero rows or columns and with distinct rows, up to permutation of rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A181230 Square array T(m,n) giving the number of m X n (0,1)-matrices with pairwise distinct rows and pairwise distinct columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A059202 Triangle T(n,m) of numbers of m-block T_0-covers of a labeled n-set, m = 0..2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A088310 Number of n X n (0,1)-matrices with all rows distinct and all columns distinct.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A094000 Number of n X n (0,1)-matrices with no zero rows or columns and with all rows distinct and all columns distinct, up to permutation of rows.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A088309 Number of equivalence classes of n X n (0,1)-matrices with all rows distinct and all columns distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A093466 Triangle read by rows: T[n,k] = number of n X n binary matrices with k=0...n^2 ones, distinct up to cyclic shifts of rows and columns; reflection through any vertical or horizontal axis; and reflection through the main diagonal. Also, quasi-n-ominoes on a torus divided into a k X k grid.

Views

Author

Keywords

Examples