A091073 -id:A091073 - cp's OEIS frontend

A006905 Number of transitive relations on n labeled nodes.

1, 2, 13, 171, 3994, 154303, 9415189, 878222530, 122207703623, 24890747921947, 7307450299510288, 3053521546333103057, 1797003559223770324237, 1476062693867019126073312, 1679239558149570229156802997, 2628225174143857306623695576671, 5626175867513779058707006016592954, 16388270713364863943791979866838296851, 64662720846908542794678859718227127212465

Offset: 0

Simon Plouffe and N. J. A. Sloane

D. Ford and J. McKay, personal communication, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. R. Finch, Transitive relations, topologies and partial orders.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
J. Klaska, Transitivity and Partial Order, Mathematica Bohemica, 122 (1), 75-82 (1997). Based on a correspondence between transitive relations and partial orders, the author obtains a formula and calculates the first 14 terms. - Jeff McSweeney (jmcsween(AT)mtsu.edu), May 13 2000
Firdous Ahmad Mala, Three Open Problems in Enumerative Combinatorics, J. Appl. Math. Computation (2023) Vol. 7, No. 1, 24-27.
Firdous Ahmad Mala, Why the number of transitive relations is not an integer polynomial, BOHR Int'l J. Eng. (2023) Vol. 2, No. 1, pp. 30-31.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A000595, A001173, A340264. See A091073 for unlabeled case.

P = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
a[n_] := Sum[P[[k+1]] Sum[Binomial[n, s] StirlingS2[n-s, k-s], {s, 0, k}], {k, 0, n}];
a /@ Range[0, 18] (* Jean-François Alcover, Dec 29 2019, after Charles R Greathouse IV *)
transitive[r_]:=Catch[Do[If[a[[2]]==b[[1]]&&FreeQ[r,{a[[1]],b[[2]]}],Throw[False]],{a,r},{b,r}];True];
a[n_]:=Count[Subsets[Tuples[Range[n],2]],?transitive]; (* _Juan José Alba González, Jul 04 2022 *)

\\ P = [1, 1, 3, 19, ...] is A001035, starting from 0.
a(n)=sum(k=0,n,P[k+1]*sum(s=0,k,binomial(n,s)*stirling(n-s,k-s,2)))
\\ Charles R Greathouse IV, Sep 05 2011

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

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
a(15)-a(16) from Charles R Greathouse IV, Aug 30 2006
a(17)-a(18) from Charles R Greathouse IV, Sep 05 2011

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Original entry on oeis.org

1, 2, 7, 32, 192, 1490, 15067, 198296, 3398105, 75734592, 2191591226, 82178300654, 3984499220967, 249298391641352, 20089200308020179, 2081351202770089728

Offset: 0

N. J. A. Sloane, Feb 16 2003

Also, number of unconstrained mixed models with n factors.

A. Hess and H. Iyer, Enumeration of mixed linear models and SAS macro for computation of confidence intervals for variance components, presented at Applied Statistics in Agriculture Conference at Kansas State University 2001.

R. Bayon, N. Lygeros and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics : JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
Gunnar Brinkmann and Brendan D. McKay, Counting unlabelled topologies and transitive relations.
Gunnar Brinkmann and Brendan D. McKay, Counting Unlabelled Topologies and Transitive Relations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.1.
R. Fraïssé and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et "compenseurs", C. R. Acad. Sci. Paris, Vol. 313, series I, pp. 417-420, 1991.
Ann Marie Hess, Mixed Models Site
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A000112 (partial orders), A091073 (transitive relations), A001930 (quasi-orders), A085628 (labeled antisymmetric transitive relations).

Cf. A079263, A006126, A006602, A006896-A006898.

a(10)-a(12) and new description from Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

a(13)-a(15) from Brinkmann's and McKay's paper by Vladeta Jovovic, Jan 04 2006

A174137 Partial sums of A006905.

Original entry on oeis.org

1, 3, 16, 187, 4181, 158484, 9573673, 887796203, 123095499826, 25013843421773, 7332464142932061, 3060854010476035118, 1800064413234246359355, 1477862758280253372432667, 1680717420907850482529235664

Offset: 0

Jonathan Vos Post, Mar 09 2010

nonn

Partial sums of number of transitive relations on n labeled nodes. After 3, none of the values shown is prime.

Cf. A006905, A000595, A001173, A091073.

a(n) = Sum_{i=0..n} A006905(i).

A296105 a(n) is the number of connected transitive relations over n unlabeled nodes.

Original entry on oeis.org

1, 2, 5, 25, 157, 1325, 14358, 199763, 3549001, 80673244, 2352747542, 88240542454, 4261209044877, 264988507673267, 21207485269909946, 2182146922863398203

Offset: 0

Daniele P. Morelli, Dec 04 2017

Inverse Euler transform of A091073. Here "connected" means that it is possible to reach any vertex starting from any other vertex by traversing edges in some direction, i.e., not necessarily in the direction in which the edges point, as in weakly connected digraphs.

			a(2) = 5 because there are five connected transitive relations up to isomorphism: a->b with no loops, a->b with a loop on a, a->b with a loop on b, a->b->a with no loops, and a->b->a with loops on both a and b.

Cf. A091073 (all unlabeled transitive relations). For the labeled case, see A245731 (connected labeled transitive relations) and A006905 (all labeled transitive relations).

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

cp's OEIS Frontend

A006905 Number of transitive relations on n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A174137 Partial sums of A006905.

Views

Author

Keywords

Comments

Crossrefs

Formula

A296105 a(n) is the number of connected transitive relations over n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica