This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000273 Number of directed graphs (or digraphs) with n nodes.
(Formerly M3032 N1229)
1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848, 13027956824399552, 341260431952972580352, 32522909385055886111197440, 11366745430825400574433894004224, 14669085692712929869037096075316220928, 70315656615234999521385506555979904091217920 (list; graph; refs; listen; history; text; internal format)



CRC Handbook of Combinatorial Designs, 1996, p. 651.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.

F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 225.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, Table 5.1.2 and p. 241, Table A4.

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).


Keith Briggs, Table of n, a(n) for n = 0..64

R. Absil and H Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013

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.

A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

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]

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

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

J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), #P46. - From N. J. A. Sloane, Mar 01 2013

J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976

L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Eric Weisstein's World of Mathematics, Directed Graph

Index entries for "core" sequences


a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016



for n from 0 to 20 do p:=partition(n):

s:=0:for k from 1 to nops(p) do

q:=convert(p[k], multiset):

for i from 1 to n do a(i):=0:od:for i from 1 to nops(q) do a(q[i][1]):=q[i][2]:od:

c:=1:ord:=1:for i from 1 to n do c:=c*a(i)!*i^a(i): if a(i)<>0 then ord:=lcm(ord, i):fi:od:

g:=0:for d from 1 to ord do if ord mod d=0 then g1:=0:for del from 1 to d do if del<=n and d mod del=0 then g1:=g1+del*a(del):fi:od:g:=g+phi(ord/d)*g1*(g1-1):fi:od:



print(n, s):


# Vladeta Jovovic, Jun 06 2006


Table[CycleIndex[PairGroup[SymmetricGroup[n], Ordered], t]/.Table[t[i]->1+x^i, {i, 1, n^2}]/.{x->1}, {n, 1, 7}] (* or *)

  Table[GraphPolynomial[n, t, Directed]/.{t->1}, {n, 1, 20}]

(* Geoffrey Critzer, Mar 08 2011 *)

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[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total[v-1];

a[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);

Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)



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, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}

a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017


Row sums of A052283.

Sequence in context: A317073 A272658 A113597 * A071897 A182012 A272385

Adjacent sequences:  A000270 A000271 A000272 * A000274 A000275 A000276




N. J. A. Sloane


More terms from Vladeta Jovovic, Dec 14 1999



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 19 02:36 EST 2018. Contains 318245 sequences. (Running on oeis4.)