VOOZH about

URL: https://oeis.org/A006905

⇱ A006905 - OEIS

login
A006905
Number of transitive relations on n labeled nodes.
30
1, 2, 13, 171, 3994, 154303, 9415189, 878222530, 122207703623, 24890747921947, 7307450299510288, 3053521546333103057, 1797003559223770324237, 1476062693867019126073312, 1679239558149570229156802997, 2628225174143857306623695576671, 5626175867513779058707006016592954, 16388270713364863943791979866838296851, 64662720846908542794678859718227127212465
OFFSET
0,2
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, 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.
FORMULA
E.g.f.: A(x + exp(x) - 1) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014
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 *)
PROG
(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
CROSSREFS
Cf. A000595, A001173, A340264. See A091073 for unlabeled case.
Sequence in context: A078363 A143851 A088316 * A119400 A182314 A268988
KEYWORD
nonn,nice
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
STATUS
approved