A000798 -id:A000798 - cp's OEIS frontend

A085628 Number of antisymmetric transitive binary relations on n labeled points.

1, 2, 12, 152, 3504, 135392, 8321472, 784621952, 110521185024, 22789653765632, 6769730814753792, 2859584874712881152, 1699286839524775931904, 1407801166901961190203392, 1613567168628788544015286272, 2541721059997800475952740401152, 5470980000021882982488097199161344

Offset: 0

Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

nonn

Jean-François Alcover, Table of n, a(n) for n = 0..18
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.

Cf. A079265 (unlabeled antisymmetric transitive relations), A001035 (labeled partial orders), A000798 (labeled reflexive transitive relations), A006905 (labeled transitive relations).

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
a[n_] := 2^n A001035[[n + 1]];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 01 2020 *)

a(n) = 2^n * A001035(n) = A000079(n) * A001035(n)

E.g.f.: A(2*x) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014

2 more terms from Charles R Greathouse IV, Aug 31 2006

A326900 Number of set-systems on n vertices that are closed under union and intersection.

Original entry on oeis.org

1, 2, 6, 29, 232, 3032, 62837, 2009408, 97034882, 6952703663, 728107141058, 109978369078580, 23682049666957359, 7195441649260733390, 3056891748255795885338, 1801430622263459795017565, 1462231768717868324127642932, 1624751185398704445629757084188, 2457871026957756859612862822442301

Offset: 0

Gus Wiseman, Aug 04 2019

nonn

A set-system is a finite set of finite nonempty sets, so no two edges of such a set-system can be disjoint.

			The a(0) = 1 through a(3) = 29 set-systems:
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{2}}        {{2}}
             {{1,2}}      {{3}}
             {{1},{1,2}}  {{1,2}}
             {{2},{1,2}}  {{1,3}}
                          {{2,3}}
                          {{1,2,3}}
                          {{1},{1,2}}
                          {{1},{1,3}}
                          {{2},{1,2}}
                          {{2},{2,3}}
                          {{3},{1,3}}
                          {{3},{2,3}}
                          {{1},{1,2,3}}
                          {{2},{1,2,3}}
                          {{3},{1,2,3}}
                          {{1,2},{1,2,3}}
                          {{1,3},{1,2,3}}
                          {{2,3},{1,2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,2,3}}
                          {{2},{1,2},{1,2,3}}
                          {{2},{2,3},{1,2,3}}
                          {{3},{1,3},{1,2,3}}
                          {{3},{2,3},{1,2,3}}
                          {{1},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}

Binomial transform of A006058 (the covering case).
The case closed under union only is A102896.
The case with {} allowed is A306445.
The BII-numbers of these set-systems are A326876.
The case closed under intersection only is A326901.
The unlabeled version is A326908.
Cf. A000798, A001930, A102895, A102898, A326866, A326878, A326882.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],SubsetQ[#,Union[Union@@@Tuples[#,2],Intersection@@@Tuples[#,2]]]&]],{n,0,3}]
(* Second program: *)
A006058 = Cases[Import["https://oeis.org/A006058/b006058.txt", "Table"], {, }][[All, 2]];
a[n_] := Sum[Binomial[n, k] A006058[[k + 1]], {k, 0, n}];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 01 2020 *)

a(16)-a(18) from A006058 by Jean-François Alcover, Jan 01 2020

A326902 Number of set-systems (without {}) covering n vertices that are closed under intersection.

Original entry on oeis.org

1, 1, 3, 19, 319, 21881, 16417973, 1063459099837, 225402359008808647339

Offset: 0

Gus Wiseman, Aug 04 2019

A set-system is a finite set of finite nonempty sets, so no two edges of a set-system that is closed under intersection can be disjoint.

			The a(0) = 1 through a(3) = 19 set-systems:
  {}  {{1}}  {{1,2}}      {{1,2,3}}
             {{1},{1,2}}  {{1},{1,2,3}}
             {{2},{1,2}}  {{2},{1,2,3}}
                          {{3},{1,2,3}}
                          {{1,2},{1,2,3}}
                          {{1,3},{1,2,3}}
                          {{2,3},{1,2,3}}
                          {{1},{1,2},{1,3}}
                          {{2},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,2,3}}
                          {{2},{1,2},{1,2,3}}
                          {{2},{2,3},{1,2,3}}
                          {{3},{1,3},{1,2,3}}
                          {{3},{2,3},{1,2,3}}
                          {{1},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}

The case closed under union and intersection is A006058.
The case with union instead of intersection is A102894.
The unlabeled version is A108800(n - 1).
The non-covering case is A326901.
The connected case is A326903.
Cf. A000798, A001930, A102895, A102898, A182507, A326866, A326876, A326878, A326882, A326900, A326901, A326904.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

Inverse binomial transform of A326901. - Andrew Howroyd, Aug 10 2019

a(5)-a(8) from Andrew Howroyd, Aug 10 2019

A326903 Number of set-systems (without {}) on n vertices that are closed under intersection and have an edge containing all of the vertices, or Moore families without {}.

Original entry on oeis.org

0, 1, 3, 16, 209, 11851, 8277238, 531787248525, 112701183758471199051

Offset: 0

Gus Wiseman, Aug 04 2019

A set-system is a finite set of finite nonempty sets, so no two edges of such a set-system can be disjoint.

If {} is allowed, we get Moore families (A102896, cf A102895).

			The a(1) = 1 through a(3) = 16 set-systems:
  {{1}}  {{1,2}}      {{1,2,3}}
         {{1},{1,2}}  {{1},{1,2,3}}
         {{2},{1,2}}  {{2},{1,2,3}}
                      {{3},{1,2,3}}
                      {{1,2},{1,2,3}}
                      {{1,3},{1,2,3}}
                      {{2,3},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1},{1,3},{1,2,3}}
                      {{2},{1,2},{1,2,3}}
                      {{2},{2,3},{1,2,3}}
                      {{3},{1,3},{1,2,3}}
                      {{3},{2,3},{1,2,3}}
                      {{1},{1,2},{1,3},{1,2,3}}
                      {{2},{1,2},{2,3},{1,2,3}}
                      {{3},{1,3},{2,3},{1,2,3}}

M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math., 294 (2005), 291-296.

The case closed under union and intersection is A006058.
The case with union instead of intersection is A102894.
The unlabeled version is A193674.
The case without requiring the maximum edge is A326901.
The covering case is A326902.
Cf. A000798, A001930, A102895, A102898, A326866, A326876, A326878, A326882, A326904.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],MemberQ[#,Range[n]]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

a(n) = A326901(n) / 2 for n > 0. - Andrew Howroyd, Aug 10 2019

a(5)-a(8) from Andrew Howroyd, Aug 10 2019

A326908 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and intersection.

Original entry on oeis.org

2, 4, 9, 23, 70, 256, 1160, 6599, 48017, 452518, 5574706, 90198548, 1919074899, 53620291147, 1962114118390, 93718030190126, 5822768063787557

Offset: 0

Gus Wiseman, Aug 03 2019

			Non-isomorphic representatives of the a(0) = 2 through a(3) = 23 sets of subsets:
  {}    {}       {}              {}
  {{}}  {{}}     {{}}            {{}}
        {{1}}    {{1}}           {{1}}
        {{}{1}}  {{12}}          {{12}}
                 {{}{1}}         {{}{1}}
                 {{}{12}}        {{123}}
                 {{2}{12}}       {{}{12}}
                 {{}{2}{12}}     {{}{123}}
                 {{}{1}{2}{12}}  {{2}{12}}
                                 {{3}{123}}
                                 {{}{2}{12}}
                                 {{23}{123}}
                                 {{}{3}{123}}
                                 {{}{23}{123}}
                                 {{}{1}{2}{12}}
                                 {{3}{23}{123}}
                                 {{}{1}{23}{123}}
                                 {{}{3}{23}{123}}
                                 {{3}{13}{23}{123}}
                                 {{}{2}{3}{23}{123}}
                                 {{}{3}{13}{23}{123}}
                                 {{}{2}{3}{13}{23}{123}}
                                 {{}{1}{2}{3}{12}{13}{23}{123}}

The labeled version is A306445.
Taking first differences and prepending 1 gives A326898.
Taking second differences and prepending two 1's gives A001930.
Cf. A000612, A000798, A003180, A108798, A108800, A193675, A326867, A326876, A326878, A326882, A326883.

Table[Length[Select[Subsets[Subsets[Range[n]]],SubsetQ[#,Union@@@Tuples[#,2]]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}]

A001928 Number of connected topologies with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 6, 21, 94, 512, 3485, 29515, 314474, 4255727, 73831813, 1653083021, 47941962135, 1803010446411, 87882300251730, 5543501326580737

Offset: 0

N. J. A. Sloane

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
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).
J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.
J. A. Wright, personal communication.

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences

Cf. A001929, A001930.

A001930 = Cases[Import["https://oeis.org/A001930/b001930.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
{1} ~Join~ EulerInvTransform[Rest[A001930]] (* Jean-François Alcover, Jan 01 2020, updated Mar 17 2020 *)

Inverse Euler transform of A001930. - Vladeta Jovovic, Jan 06 2006

More terms from Vladeta Jovovic, Jan 06 2006

A046908 Number of irreducible posets with n labeled points.

Original entry on oeis.org

1, 1, 1, 7, 97, 2251, 80821, 4305127, 332273257, 36630174931, 5711638291981, 1249898984911567, 381230073532620577, 161042140788424003291, 93667063572594041040421, 74610767840852891620692727, 80997478506602342803118178457, 119313601058907927882431190269731, 237541348427311374857037021264415741

Offset: 0

John A. Wright

nonn

J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.

G. Brinkmann, B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table III, up to 18 points)
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for sequences related to posets

Cf. A046907.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]]; lg = Length[A001035];
B[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, lg - 1}];
A[x_] = 2 - 1/B[x];
CoefficientList[A[x] + O[x]^lg, x]*Range[0, lg - 1]! (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(x) = 2-1/B(x), where B(x) is e.g.f. of A001035. - Vladeta Jovovic, Jan 10 2006

More terms from Vladeta Jovovic, Jan 10 2006

a(16)-a(18) from A001035 by Jean-François Alcover, Jan 01 2020

A122835 Number of topologies on n labeled elements in which no element belongs to any pair of noncomparable members of the topology.

Original entry on oeis.org

1, 1, 4, 19, 112, 811, 7024, 70939, 818752, 10630891, 153371344, 2433948859, 42137351392, 790287522571, 15962014455664, 345424786466779, 7973482022972032, 195556150543703851, 5078301994885267984

Offset: 0

Nathan K. McGregor (mcgregnk(AT)ese.wustl.edu), Sep 15 2006

The number of topologies on n labeled elements is a fundamental sequence (A000798), which many mathematicians believe is impossible to completely determine.
The present sequence is an elegant recursion that enumerates the topologies on n labeled elements that can be "drawn" (as, for example, on page 76 of Munkres) in such a way that the boundaries of the subsets do not "cross" one another. Thus I recommend that topologies be classified as "planar" if their members can be drawn without crossings and "non-planar" otherwise.
This is analogous to the way in which subgroup lattices are called planar or non-planar. Using this terminology, the above sequence gives the number of planar topologies on n labeled elements. If the number of non-planar topologies on n labeled elements (see A122836) could be enumerated, then so could the total number of topologies on n labeled elements.
Another way to state the definition is that any two members of the topology are comparable or disjoint. - Rainer Rosenthal, Jan 02 2011
Conjectural closed form for n>0: 3*2^(k-3)(LerchPhi[1/4, -k, 1/2] + 2 PolyLog[-k, 1/4]) - 1/2. - Vladimir Reshetnikov, Jan 07 2011

J. Munkres, Topology, Prentice Hall, (2000), p. 76.

Cf. A000798, A122836.

a122835:=proc(n) option remember; if n=0 then 1 else 2^(n-1) - 1 + add(a122835(n-k)*binomial(n,k),k=1..n); fi; end;

a[n_]:=a[n]=2^(n-1)-1+Sum[a[n-k]*Binomial[n,k],{k,1,n}]; a[0]=1; Table[a[n],{n,0,25}]
a[ n_] := (3/4) * (PolyLog[ -n, 1/2] + Boole[n==0]) - 1/2 (* Michael Somos, Jan 07 2011 *)

{a(n) = local(A); if( n<1, n==0, A = exp(x + x * O(x^n)) / 2; n! * polcoeff( (3/4) / (1 - A) - A, n))} /* Michael Somos, Jan 07 2011 */

a(n) = 2^(n-1) - 1 + Sum{C(n,k)*a(n-k), k = 1 ... n}
E.g.f.: (3/4) / (1 - exp(x)/2) - exp(x)/2. - Michael Somos, Jan 07 2011
a(n) = (A000629(n) + 0^n) * (3/4) - 1/2. - Michael Somos, Jan 07 2011

A366866 Number of binary relations R on [n] such that the transitive closure of R contains the identity relation.

Original entry on oeis.org

1, 1, 7, 253, 39463, 24196201, 56481554827, 502872837857293, 17309567681965278223, 2333553047265268677638161, 1243013506394568266481053180947, 2629978323181659930952963974617537173, 22170279317365870690118601982232935268994583

Offset: 0

Geoffrey Critzer, Oct 25 2023

nonn

Equivalently, a(n) is the number of n X n Boolean relation matrices whose Frobenius normal form contains no 0-blocks on the diagonal.  See Gregory, Kirkland, and Pullman.
Equivalently, a(n) is the number of labeled directed graphs on [n] (with self loops allowed) such that every strongly connected component contains at least one arc.
This sequence is a good upper-bound for the number of relations that converge to a quasi-order (A366252) which is only known for n <= 6.
If the transitive closure of a relation R contains the identity relation then there is exactly one transitive relation in {R,R^2,R^3...}.  See Schwarz link.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
S. Schwarz, On the semigroup of binary relations on a finite set , Czechoslovak Mathematical Journal, 1970.

Cf. A366252, A003030, A000798.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i,1,58}]];ggf[egf_]:=Normal[Series[egf, {x, 0, nn}]] /.Table[x^i ->x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[
  Series[1/ggf[Exp[- (s[2 x] - x)]], {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(2^n*binomial(n,2)) = 1/(E(x) @ exp(-(s(2x)-x))) where E(x) = Sum_{n>=0} x^n/(2^n*binomial(n,2)), s(x) is the e.g.f. for A003030, and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A046912 Number of irreducible quasiorders with n labeled points.

Original entry on oeis.org

1, 1, 2, 11, 147, 3412, 121553, 6353629, 476850636, 50811255045, 7636459252135, 1610584897516674, 474333338553730879, 194055026319667963777, 109692570582311591696890, 85221064877720762475072503, 90542406571528792666541430863, 130936936785995060562730057163556, 256634185641525450158992588551158389

Offset: 0

John A. Wright

J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences

Cf. A046911.

A000798 = Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {, }][[All, 2]]; lg = Length[A000798];
B[x_] = Sum[A000798[[n + 1]] x^n/n!, {n, 0, lg - 1}];
A[x_] = 2 - 1/B[x];
CoefficientList[A[x] + O[x]^lg, x]*Range[0, lg - 1]! (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(x) = 2-1/B(x), where B(x) is e.g.f. of A000798. - Vladeta Jovovic, Jan 10 2006

Corrected and extended by Vladeta Jovovic, Jan 10 2006

a(16)-a(18) from A000798 by Jean-François Alcover, Jan 01 2020

cp's OEIS Frontend

A085628 Number of antisymmetric transitive binary relations on n labeled points.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326900 Number of set-systems on n vertices that are closed under union and intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A326902 Number of set-systems (without {}) covering n vertices that are closed under intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326903 Number of set-systems (without {}) on n vertices that are closed under intersection and have an edge containing all of the vertices, or Moore families without {}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326908 Number of non-isomorphic sets of subsets of {1..n} that are closed under union and intersection.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A001928 Number of connected topologies with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A046908 Number of irreducible posets with n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A122835 Number of topologies on n labeled elements in which no element belongs to any pair of noncomparable members of the topology.

Views

Author

Keywords

Comments

References