A059084 -id:A059084 - cp's OEIS frontend

A059201 Number of T_0-covers of a labeled n-set.

1, 1, 4, 96, 31692, 2147001636, 9223371991763269704, 170141183460469231473432887375376674952, 57896044618658097711785492504343953920509909728243389682424010192567186540224

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Jan 16 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.
From Gus Wiseman, Aug 13 2019: (Start)
A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges). For example, the a(2) = 4 covers are:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}
(End)

G. C. Greubel, Table of n, a(n) for n = 0..11
Vladeta Jovovic, T_0-covers of a labeled 3-set

Row sums of A059202.
Cf. A059203, A059084, A059085, A059086, A059087, A059088, A059089.
Covering set-systems are A003465.
The unlabeled version is A319637.
The version with empty edges allowed is A326939.
The non-covering version is A326940.
BII-numbers of T_0 set-systems are A326947.
The same with connected instead of covering is A326948.
The T_1 version is A326961.
Cf. A245567, A316978, A319559, A319564, A323818, A326941, A326946, A326970.

Table[Sum[StirlingS1[n + 1, k]*2^(2^(k - 1) - 1), {k, 0, n + 1}], {n,0,5}] (* G. C. Greubel, Dec 28 2016 *)
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 13 2019 *)

a(n) = Sum_{i=0..n+1} stirling1(n+1, i)*2^(2^(i-1)-1).
a(n) = Sum_{m=0..2^n-1} A059202(n,m).
Inverse binomial transform of A326940 and exponential transform of A326948. - Gus Wiseman, Aug 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

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

A059085 Number of labeled n-node T_0-hypergraphs without multiple hyperedges (empty hyperedge included).

Original entry on oeis.org

2, 4, 12, 216, 64152, 4294320192, 18446744009290559040, 340282366920938463075992982635439125760, 115792089237316195423570985008687907843742078391854287068422946583140399879680

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.

			There are 216 labeled 3-node T_0-hypergraphs without multiple hyperedges (empty hyperedge included): 12 with 2 hyperedges, 44 with 3 hyperedges,67 with 4 hyperedges, 56 with 5 hyperedges, 28 with 6 hyperedges, 8 with 7 hyperedges and 1 with 8 hyperedges.

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

Cf. A059084, A059086, A059087-A059089.

with(combinat): for n from 0 to 15 do printf(`%d,`,sum(stirling1(n,k)*2^(2^k), k=0..n)) od:

Row sums of A059084.
a(n) = Sum_{k=0..n} stirling1(n, k)*2^(2^k).
E.g.f.: Sum(2^(2^n)*log(1+x)^n/n!, n=0..infinity) = Sum(log(2)^n*(1+x)^(2^n)/n!, n=0..infinity). - Vladeta Jovovic, May 10 2004

More terms from James Sellers, Jan 24 2001

A059086 Number of labeled T_0-hypergraphs with n distinct hyperedges (empty hyperedge included).

Original entry on oeis.org

2, 5, 30, 18236, 2369751620679, 5960531437867327674541054610203768, 479047836152505670895481842190009123676957243077039693903470634823732317120870101036348

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.

			a(2)=30; There are 30 labeled T_0-hypergraphs with 2 distinct hyperedges (empty hyperedge included): 1 1-node hypergraph, 5 2-node hypergraphs, 12 3-node hypergraphs and 12 4-node hypergraphs.
a(3) = (1/3!)*(2*[2!*e]-3*[4!*e]+[8!*e]) = (1/3!)*(2*5-3*65+109601) = 18236, where [k!*e] := floor (k!*exp(1)).

Column sums of A059084.

Cf. A059084, A059085, A059087-A059089.

with(combinat): Digits := 1000: for n from 0 to 8 do printf(`%d,`,(1/n!)*sum(stirling1(n, k)*floor((2^k)!*exp(1)), k=0..n)) od:

a(n) = (1/n!)*Sum_{k = 0..n} stirling1(n, k)*floor((2^k)!*exp(1)).

More terms from James Sellers, Jan 24 2001

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

Original entry on oeis.org

1, 1, 1, 0, 2, 3, 1, 0, 0, 12, 32, 35, 21, 7, 1, 0, 0, 12, 256, 1155, 2877, 4963, 6429, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 0, 0, 0, 1120, 19040, 140616, 686476, 2565260, 7824375, 20110025, 44322135, 84658665, 141115975, 206252025, 265182375

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 starts:
[1],
[1,1],
[0,2,3,1],
[0,0,12,32,35,21,7,1],
...;
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 A059087, A059088

Cf. A059084, A059085, A059086, A059088, A059089.

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

T(n, m) = Sum_{i=0..n} s(n, i)*binomial(2^i-1, m), where s(n, i) are Stirling numbers of the first kind.

Also T(n, m) = (1/m!)*Sum_{i=0..m+1} s(m+1, i)*fallfac(2^(i-1), n). E.g.f: Sum((1+x)^(2^n-1)*log(1+y)^n/n!, n=0..infinity). - Vladeta Jovovic, May 19 2004

A059089 Number of labeled T_0-hypergraphs with n distinct hyperedges (empty hyperedge excluded).

Original entry on oeis.org

2, 3, 27, 18209, 2369751602470, 5960531437867327674538684858601298, 479047836152505670895481842190009123676957243077039687942939196956404642582185242435050

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.

			a(2)=27; There are 27 labeled T_0-hypergraphs with 2 distinct hyperedges (empty hyperedge excluded): 3 2-node hypergraphs, 12 3-node hypergraphs and 12 4-node hypergraphs.
a(3) = (1/3!)*(-6*[1!*e]+11*[2!*e]-6*[4!*e]+[8!*e]) = (1/3!)*(-6*2+11*5-6*65+109601) = 18209, where [k!*e] := floor(k!*exp(1)).

Cf. A059084-A059088.

with(combinat): Digits := 1000: for n from 0 to 8 do printf(`%d,`,(1/n!)*sum(stirling1(n+1,k)*floor((2^(k-1))!*exp(1)), k=0..n+1)) od:

Column sums of A059087.

a(n) = Sum_{k = 0..n} (-1)^(n-k)*A059086(k); a(n) = (1/n!)*Sum_{k = 0..n+1} stirling1(n+1, k)*floor(( 2^(k-1))!*exp(1)).

More terms from James Sellers, Jan 24 2001

A059088 Number of labeled n-node T_0-hypergraphs without multiple hyperedges (empty hyperedge excluded).

Original entry on oeis.org

1, 2, 6, 108, 32076, 2147160096, 9223372004645279520, 170141183460469231537996491317719562880, 57896044618658097711785492504343953921871039195927143534211473291570199939840

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.

			There are 108 labeled 3-node T_0-hypergraphs without multiple hyperedges (empty hyperedge excluded): 12 with 2 hyperedges, 32 with 3 hyperedges,35 with 4 hyperedges, 21 with 5 hyperedges, 7 with 6 hyperedges and 1 with 7 hyperedges.

Illustration of initial terms of A059087, A059088

Cf. A059084-A059087, A059089.

with(combinat): for n from 0 to 15 do printf(`%d,`,(1/2)*sum(stirling1(n,k)*2^(2^k), k= 0..n)) od:

Table[Sum[StirlingS1[n, k]*2^((2^k)-1), {k,0,n}], {n,0,10}] (* G. C. Greubel, Oct 06 2017 *)

Row sums of A059087.
a(n) = A059085(n)/2.
a(n) = Sum_{k=0..n} stirling1(n, k)*2^((2^k)-1).

More terms from James Sellers, Jan 24 2001

A059203 Number of n-block T_0-covers of a labeled set.

Original entry on oeis.org

1, 1, 6, 2270, 148109472315, 186266607433353989829111737621541, 7485122439882901107741903784218892557452456923078744798141861944074340339271507786827

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.

			a(4) = 1 + (1/4!)*( - 50*[1!*e] + 35*[3!*e] - 10*[7!*e] + [15!*e]) = 1 + (1/4!)*( - 50*2 + 35*16 - 10*13700 + 3554627472076) = 148109472315, where [k!*e] := floor(k!*exp(1)).

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

Cf. A059201, column sums of A059202, A059084 - A059089, A000522.

with(combinat): Digits := 1500: f := n->(-1)^n+(1/n!)*sum(stirling1(n+1,i)*floor((2^(i-1)-1)!*exp(1)), i=2..n+1): for n from 1 to 10 do printf(`%d,`,f(n)) od:

a[0] := 1; a[n_] := (-1)^n + (1/n!)*Sum[StirlingS1[n + 1, k]*Floor[(2^(k - 1) - 1)!*E], {k, 2, n + 1}]; Table[a[n], {n, 0, 5}] (* G. C. Greubel, Dec 28 2016 *)

a(n) = (- 1)^n + (1/n!)*Sum_{i = 2,..,n + 1} stirling1(n + 1, i)*floor((2^(i - 1) - 1)!*exp(1)), n>0, a(0) = 1.

a(n) = (1/n!)*Sum_{i = 1,..,n + 1} stirling1(n + 1, i)*A000522(2^(i - 1) - 1).

More terms from James Sellers, Jan 24 2001

cp's OEIS Frontend

A059201 Number of T_0-covers of a labeled n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

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

A059085 Number of labeled n-node T_0-hypergraphs without multiple hyperedges (empty hyperedge included).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A059086 Number of labeled T_0-hypergraphs with n distinct hyperedges (empty hyperedge included).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica