A000273 Number of unlabeled simple digraphs with n nodes.
1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848, 13027956824399552, 341260431952972580352, 32522909385055886111197440, 11366745430825400574433894004224, 14669085692712929869037096075316220928, 70315656615234999521385506555979904091217920
Offset: 0
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
- 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.
- 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
- Index entries for "core" sequences
Programs
-
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 *) -
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 -
Python
from itertools import combinations from math import prod, factorial, gcd from fractions import Fraction from sympy.utilities.iterables import partitions def A000273(n): return int(sum(Fraction(1<
Formula
a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016
Extensions
More terms from Vladeta Jovovic, Dec 14 1999