login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006905 Number of transitive relations on n labeled nodes.
(Formerly M2065)
5
1, 2, 13, 171, 3994, 154303, 9415189, 878222530, 122207703623, 24890747921947, 7307450299510288, 3053521546333103057, 1797003559223770324237, 1476062693867019126073312, 1679239558149570229156802997, 2628225174143857306623695576671, 5626175867513779058707006016592954, 16388270713364863943791979866838296851, 64662720846908542794678859718227127212465 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

REFERENCES

D. Ford and J. McKay, personal communication, 1991.

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=0..18.

S. R. Finch, Transitive relations, topologies and partial orders

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

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

Sequence in context: A078363 A143851 A088316 * A119400 A182314 A183606

Adjacent sequences:  A006902 A006903 A006904 * A006906 A006907 A006908

KEYWORD

nonn,nice

AUTHOR

Simon Plouffe and N. J. A. Sloane.

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

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

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

Last modified April 24 11:13 EDT 2014. Contains 240983 sequences.