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.
1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, 816007449011040, 4374406209970747314, 64539836938720749739356, 2637796735571225009053373136, 300365896158980530053498490893399
Offset: 1
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. 14-22.
- 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), 486-495.
- Musa Demirci, Ugur Ana, and Ismail Naci Cangul, Properties of Characteristic Polynomials of Oriented Graphs, Proc. Int'l Conf. Adv. Math. Comp. (ICAMC 2020) Springer, see p. 60.
- F. Harary and E. M. Palmer, Enumeration of mixed graphs, Proc. Amer. Math. Soc., 17 (1966), 682-687.
- T. R. Hoffman and J. P. Solazzo, Complex Two-Graphs via Equiangular Tight Frames, arXiv preprint arXiv:1408.0334 [math.CO], 2014-2017.
- 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. 14-22. [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
Crossrefs
Programs
-
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] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *) -
PARI
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} edges(v) = {sum(i=2, #v, sum(j=1, i-1, 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 -
Python
from itertools import combinations from math import prod, gcd, factorial from fractions import Fraction from sympy.utilities.iterables import partitions 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
Formula
There's an explicit formula - see for example Harary and Palmer (book), Eq. (5.4.14).
a(n) ~ 3^(n*(n-1)/2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016
Extensions
More terms from Vladeta Jovovic
Revised description from Vladeta Jovovic, Jan 20 2005