cp's OEIS Frontend

A006905 Number of transitive relations on n labeled nodes.

%I A006905 M2065 #62 Feb 17 2024 10:54:47
%S A006905 1,2,13,171,3994,154303,9415189,878222530,122207703623,24890747921947,
%T A006905 7307450299510288,3053521546333103057,1797003559223770324237,
%U A006905 1476062693867019126073312,1679239558149570229156802997,2628225174143857306623695576671,5626175867513779058707006016592954,16388270713364863943791979866838296851,64662720846908542794678859718227127212465
%N A006905 Number of transitive relations on n labeled nodes.
%D A006905 D. Ford and J. McKay, personal communication, 1991.
%D A006905 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006905 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>.
%H A006905 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 A006905 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 A006905 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 A006905 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 A006905 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 A006905 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 A006905 E.g.f.: A(x + exp(x) - 1) where A(x) is the e.g.f. for A001035. - _Geoffrey Critzer_, Jul 28 2014
%t A006905 P = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {_, _}][[All, 2]];
%t A006905 a[n_] := Sum[P[[k+1]] Sum[Binomial[n, s] StirlingS2[n-s, k-s], {s, 0, k}], {k, 0, n}];
%t A006905 a /@ Range[0, 18] (* _Jean-François Alcover_, Dec 29 2019, after _Charles R Greathouse IV_ *)
%t A006905 transitive[r_]:=Catch[Do[If[a[[2]]==b[[1]]&&FreeQ[r,{a[[1]],b[[2]]}],Throw[False]],{a,r},{b,r}];True];
%t A006905 a[n_]:=Count[Subsets[Tuples[Range[n],2]],_?transitive]; (* _Juan José Alba González_, Jul 04 2022 *)
%o A006905 (PARI) \\ P = [1, 1, 3, 19, ...] is A001035, starting from 0.
%o A006905 a(n)=sum(k=0,n,P[k+1]*sum(s=0,k,binomial(n,s)*stirling(n-s,k-s,2)))
%o A006905 \\ _Charles R Greathouse IV_, Sep 05 2011
%Y A006905 Cf. A000595, A001173, A340264. See A091073 for unlabeled case.
%K A006905 nonn,nice
%O A006905 0,2
%A A006905 _Simon Plouffe_ and _N. J. A. Sloane_
%E A006905 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
%E A006905 a(15)-a(16) from _Charles R Greathouse IV_, Aug 30 2006
%E A006905 a(17)-a(18) from _Charles R Greathouse IV_, Sep 05 2011