|
|
A006905
|
|
Number of transitive relations on n labeled nodes.
(Formerly M2065)
|
|
28
|
|
|
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
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
|
|
FORMULA
|
|
|
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}];
transitive[r_]:=Catch[Do[If[a[[2]]==b[[1]]&&FreeQ[r, {a[[1]], b[[2]]}], Throw[False]], {a, r}, {b, r}]; True];
|
|
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)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
|
|
STATUS
|
approved
|
|
|
|