This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A006905 Number of transitive relations on n labeled nodes. (Formerly M2065) 5

%I M2065

%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 Klaska (1997), Transitivity and Partial Order, Mathematica Bohemica, 122 (1), 75-82. 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

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

%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. See A091073 for unlabeled case.

%K nonn,nice,changed

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .