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

A060690 a(n) = binomial(2^n + n - 1, n).

Original entry on oeis.org

1, 2, 10, 120, 3876, 376992, 119877472, 131254487936, 509850594887712, 7145544812472168960, 364974894538906616240640, 68409601066028072105113098240, 47312269462735023248040155132636160, 121317088003402776955124829814219234385920

Offset: 0

Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 19 2001

nonn

Also the number of n X n (0,1) matrices modulo rows permutation (by symmetry this is the same as the number of (0,1) matrices modulo columns permutation), i.e., the number of equivalence classes where two matrices A and B are equivalent if one of them is the result of permuting the rows of the other. The total number of (0,1) matrices is in sequence A002416.

Row sums of A220886. - Geoffrey Critzer, Nov 20 2014

Harry J. Smith, Table of n, a(n) for n = 0..59

Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), this sequence (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
Cf. A002416, A060336, A088309, A163767.
Cf. A136555, A220886.
Main diagonal of A092056.
Central terms of A137153.

[Binomial(2^n +n-1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021

with(combinat): for n from 0 to 20 do printf(`%d,`,binomial(2^n+n-1, n)) od:

Table[Binomial[2^n+n-1,n],{n,0,20}] (* Harvey P. Dale, Apr 19 2012 *)

PARI
```
a(n)=binomial(2^n+n-1,n)
```

{a(n)=polcoeff(sum(k=0,n,(-log(1-2^k*x +x*O(x^n)))^k/k!),n)} \\ Paul D. Hanna, Dec 29 2007

a(n) = sum(k=0, n, stirling(n,k,1)*(2^n+n-1)^k/n!); \\ Paul D. Hanna, Nov 20 2014

from math import comb
def A060690(n): return comb((1<Chai Wah Wu, Jul 05 2024

[binomial(2^n +n-1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021

a(n) = [x^n] 1/(1-x)^(2^n).
a(n) = (1/n!)*Sum_{k=0..n} ( (-1)^(n-k)*Stirling1(n, k)*2^(k*n) ). - Vladeta Jovovic, May 28 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(2^n+n,k) - Vladeta Jovovic, Jan 21 2008
a(n) = Sum_{k=0..n} Stirling1(n,k)*(2^n+n-1)^k/n!. - Vladeta Jovovic, Jan 21 2008
G.f.: A(x) = Sum_{n>=0} [ -log(1 - 2^n*x)]^n / n!. More generally, Sum_{n>=0} [ -log(1 - q^n*x)]^n/n! = Sum_{n>=0} C(q^n+n-1,n)*x^n ; also Sum_{n>=0} log(1 + q^n*x)^n/n! = Sum_{n>=0} C(q^n,n)*x^n. - Paul D. Hanna, Dec 29 2007
a(n) ~ 2^(n^2) / n!. - Vaclav Kotesovec, Jul 02 2016
a(n) = A163767(2^n). - Alois P. Heinz, Jun 12 2024

More terms from James Sellers, Apr 20 2001

Edited by N. J. A. Sloane, Mar 17 2008

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

A116532 Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

Original entry on oeis.org

0, 0, 3, 285, 50820, 23551920, 31898503077, 134251404794199

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116506, A116527.

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

a(n) = A054780(n) - A088389(n).

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

A059084 Triangle T(n,m) of number of labeled n-node T_0-hypergraphs with m distinct hyperedges (empty hyperedge included), m=0,1,...,2^n.

Original entry on oeis.org

1, 1, 1, 2, 1, 0, 2, 5, 4, 1, 0, 0, 12, 44, 67, 56, 28, 8, 1, 0, 0, 12, 268, 1411, 4032, 7840, 11392, 12864, 11440, 8008, 4368, 1820, 560, 120, 16, 1, 0, 0, 0, 1120, 20160, 159656, 827092, 3251736, 10389635, 27934400, 64432160, 128980800, 225774640

Offset: 0

Goran Kilibarda, Vladeta Jovovic, Dec 27 2000

A hypergraph is a T_0 hypergraph if for every two distinct nodes there exists a hyperedge containing one but not the other node.

			Triangle begins:
   m   0   1   2   3   4   5   6   7   8        sums A059085(n)
n
0      1   1                                           2
1      1   2   1                                       4
1      0   2   5   4   1                              12
2      0   0  12  44  67  56  28   8   1             216
There are 12 labeled 3-node T_0-hypergraphs with 2 distinct hyperedges: {{3},{2}}, {{3},{2,3}}, {{2},{2,3}}, {{3},{1}}, {{3},{1,3}}, {{2},{1}}, {{2,3},{1,3}}, {{2},{1,2}}, {{2,3},{1,2}}, {{1},{1,3}}, {{1},{1,2}}, {{1,3},{1,2}}.

V. Jovovic, Illustration of initial terms of A059084, A059085

Cf. A059085, A059086.

Cf. A088309.

T[n_, m_] := Sum[StirlingS1[n, i] Binomial[2^i, m], {i, 0, n}]; Table[T[n, m], {n, 0, 5}, {m, 0, 2^n}] // Flatten (* Jean-François Alcover, Sep 02 2016 *)

T(n,m) = Sum_{i=0..n} Stirling1(n,i) * binomial(2^i,m).
T(n,m) = A181230(n,m) / m!.
From Vladeta Jovovic, May 19 2004: (Start)
T(n, m) = (1/m!)*Sum_{i=0..m} s(m, i)*fallfac(2^i, n).
E.g.f.: Sum_{n>=0} (1+x)^(2^n)*log(1+y)^n/n!. (End)

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

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

A060690 a(n) = binomial(2^n + n - 1, n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

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

A116532 Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

Views

Author

Keywords

Crossrefs

Formula

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