%I M1809 N0715 #54 Jul 15 2024 10:18:10
%S 1,2,7,42,582,21480,2142288,575016219,415939243032,816007449011040,
%T 4374406209970747314,64539836938720749739356,
%U 2637796735571225009053373136,300365896158980530053498490893399
%N 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.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 133, c_p.
%D 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. 14-22.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Andrew Howroyd, <a href="/A001174/b001174.txt">Table of n, a(n) for n = 1..50</a>
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H R. L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.
%H Musa Demirci, Ugur Ana, and Ismail Naci Cangul, <a href="https://doi.org/10.1007/978-981-16-1402-6">Properties of Characteristic Polynomials of Oriented Graphs</a>, Proc. Int'l Conf. Adv. Math. Comp. (ICAMC 2020) Springer, see p. 60.
%H F. Harary and E. M. Palmer, <a href="http://dx.doi.org/10.1090/S0002-9939-1966-0191845-4">Enumeration of mixed graphs</a>, Proc. Amer. Math. Soc., 17 (1966), 682-687.
%H T. R. Hoffman and J. P. Solazzo, <a href="http://arxiv.org/abs/1408.0334">Complex Two-Graphs via Equiangular Tight Frames</a>, arXiv preprint arXiv:1408.0334 [math.CO], 2014-2017.
%H M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
%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.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OrientedGraph.html">Oriented Graph</a>
%F There's an explicit formula - see for example Harary and Palmer (book), Eq. (5.4.14).
%F a(n) ~ 3^(n*(n-1)/2)/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016
%t 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];
%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total @ Quotient[v - 1, 2];
%t a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t Array[a, 15] (* _Jean-François Alcover_, Jul 06 2018, after _Andrew Howroyd_ *)
%o (PARI)
%o permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 23 2017
%o (Python)
%o from itertools import combinations
%o from math import prod, gcd, factorial
%o from fractions import Fraction
%o from sympy.utilities.iterables import partitions
%o def A001174(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q-1>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # _Chai Wah Wu_, Jul 15 2024
%Y Cf. A000595, A001173, A281446.
%Y Cf. A047656 (labeled case), A054941 (connected labeled case), A086345 (connected unlabeled case).
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_
%E Revised description from _Vladeta Jovovic_, Jan 20 2005