|
%I M2065 #62 Feb 17 2024 10:54:47
%S 1,2,13,171,3994,154303,9415189,878222530,122207703623,24890747921947,
%T 7307450299510288,3053521546333103057,1797003559223770324237,
%U 1476062693867019126073312,1679239558149570229156802997,2628225174143857306623695576671,5626175867513779058707006016592954,16388270713364863943791979866838296851,64662720846908542794678859718227127212465
%N Number of transitive relations on n labeled nodes.
%D D. Ford and J. McKay, personal communication, 1991.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>.
%H S. R. Finch, <a href="/A000798/a000798_12.pdf">Transitive relations, topologies and partial orders</a>, June 5, 2003. [Cached copy, with permission of the author]
%H Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, <a href="https://arxiv.org/abs/2302.08265">MC-finiteness of restricted set partition functions</a>, arXiv:2302.08265 [math.CO], 2023.
%H J. Klaska, <a href="https://mb.math.cas.cz/mb122-1/7.html">Transitivity and Partial Order</a>, 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
%H Firdous Ahmad Mala, <a href="https://doi.org/10.26855/jamc.2023.03.004">Three Open Problems in Enumerative Combinatorics</a>, J. Appl. Math. Computation (2023) Vol. 7, No. 1, 24-27.
%H Firdous Ahmad Mala, <a href="https://doi.org/10.54646/bije.2023.14">Why the number of transitive relations is not an integer polynomial</a>, BOHR Int'l J. Eng. (2023) Vol. 2, No. 1, pp. 30-31.
%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%F E.g.f.: A(x + exp(x) - 1) where A(x) is the e.g.f. for A001035. - _Geoffrey Critzer_, Jul 28 2014
%t P = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {_, _}][[All, 2]];
%t a[n_] := Sum[P[[k+1]] Sum[Binomial[n, s] StirlingS2[n-s, k-s], {s, 0, k}], {k, 0, n}];
%t a /@ Range[0, 18] (* _Jean-François Alcover_, Dec 29 2019, after _Charles R Greathouse IV_ *)
%t transitive[r_]:=Catch[Do[If[a[[2]]==b[[1]]&&FreeQ[r,{a[[1]],b[[2]]}],Throw[False]],{a,r},{b,r}];True];
%t a[n_]:=Count[Subsets[Tuples[Range[n],2]],_?transitive]; (* _Juan José Alba González_, Jul 04 2022 *)
%o (PARI) \\ P = [1, 1, 3, 19, ...] is A001035, starting from 0.
%o a(n)=sum(k=0,n,P[k+1]*sum(s=0,k,binomial(n,s)*stirling(n-s,k-s,2)))
%o \\ _Charles R Greathouse IV_, Sep 05 2011
%Y Cf. A000595, A001173, A340264. See A091073 for unlabeled case.
%K nonn,nice
%O 0,2
%A _Simon Plouffe_ and _N. J. A. Sloane_
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
%E a(15)-a(16) from _Charles R Greathouse IV_, Aug 30 2006
%E a(17)-a(18) from _Charles R Greathouse IV_, Sep 05 2011
|
