

A001174


Number of oriented graphs (i.e., digraphs with no bidirected edges) on n unlabeled nodes. Also number of complete digraphs on n unlabeled nodes. Number of antisymmetric relations (i.e., oriented graphs with loops) on n unlabeled nodes is A083670.
(Formerly M1809 N0715)


13



1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, 816007449011040, 4374406209970747314, 64539836938720749739356, 2637796735571225009053373136, 300365896158980530053498490893399
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 133, c_p.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 1422.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486495.
F. Harary and E. M. Palmer, Enumeration of mixed graphs, Proc. Amer. Math. Soc., 17 (1966), 682687.
T. R. Hoffman, J. P. Solazzo, Complex TwoGraphs via Equiangular Tight Frames, arXiv preprint arXiv:1408.0334 [math.CO], 20142017.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 1422. [Annotated scanned copy]
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Eric Weisstein's World of Mathematics, Oriented Graph


FORMULA

There's an explicit formula  see for example Harary and Palmer (book), Eq. (5.4.14).
a(n) ~ 3^(n*(n1)/2)/n! [McIlroy, 1955].  Vaclav Kotesovec, Dec 19 2016


MATHEMATICA

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i  1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i  1}] + Total @ Quotient[v  1, 2];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 15] (* JeanFrançois Alcover, Jul 06 2018, after Andrew Howroyd *)


PROG

(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]1)\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Oct 23 2017


CROSSREFS

Cf. A000595, A001173, A281446.
Cf. A047656 (labeled case), A054941 (connected labeled case), A086345 (connected unlabeled case).
Sequence in context: A108042 A152559 A267239 * A067975 A065298 A091877
Adjacent sequences: A001171 A001172 A001173 * A001175 A001176 A001177


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Vladeta Jovovic
Revised description from Vladeta Jovovic, Jan 20 2005


STATUS

approved



