login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000273 Number of unlabeled simple digraphs with n nodes.
(Formerly M3032 N1229)
49
1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848, 13027956824399552, 341260431952972580352, 32522909385055886111197440, 11366745430825400574433894004224, 14669085692712929869037096075316220928, 70315656615234999521385506555979904091217920 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
REFERENCES
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).
LINKS
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.
Fatemeh Arbabjolfaei and Young-Han Kim, Fundamentals of Index Coding, Foundations and Trends in Communications and Information Theory (2018) Vol. 14, Issue 3-4.
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.
Gábor Kusper, Zijian Győző Yang, and Benedek Nagy, Using extended resolution to represent strongly connected components of directed graphs, Ann. Math. Inf. (2023).
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, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.
Eric Weisstein's World of Mathematics, Simple Directed Graph
FORMULA
a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016
MAPLE
with(combinat):with(numtheory):
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:
s:=s+2^(g/ord)/c:
od:
print(n, s):
od:
# Vladeta Jovovic, Jun 06 2006
# second Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
end:
A000273 := n-> b(n$2, []):
seq(A000273(n), n=0..20); # Alois P. Heinz, Sep 04 2019
MATHEMATICA
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 *)
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[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
(Python)
from math import gcd, factorial
from sympy.utilities.iterables import partitions
def permcount(v):
m, s, k = 1, 0, 0
for i, t in enumerate(v):
k = k+1 if i > 0 and t == v[i-1] else 1; m *= t*k; s += t
return factorial(s)//m
def edges(v): return sum(sum(2*gcd(v[i], v[j]) for j in range(i)) for i in range(1, len(v))) + sum(vi-1 for vi in v)
def a(n):
s = 0
for p in partitions(n):
pvec = []
for i in sorted(p): pvec.extend([i]*p[i])
s += permcount(pvec)*2**edges(pvec)
return s//factorial(n)
print([a(n) for n in range(15)]) # Michael S. Branicky, Nov 14 2022 after Andrew Howroyd
CROSSREFS
Row sums of A052283 and of A217654.
Sequence in context: A326903 A113597 A361366 * A071897 A182012 A272385
KEYWORD
nonn,core,nice
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Dec 14 1999
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:24 EDT 2024. Contains 370951 sequences. (Running on oeis4.)