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

Author

Simon Plouffe and N. J. A. Sloane

Keywords

• nonn
• nice

References

• 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).

Links

• 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.

Crossrefs

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

Programs

Mathematica

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 *)

PARI

\\ 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

Formula

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

Extensions

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