cp's OEIS Frontend

A000273 Number of unlabeled simple digraphs with n nodes.

%I A000273 M3032 N1229 #119 Jul 05 2024 16:13:01
%S A000273 1,1,3,16,218,9608,1540944,882033440,1793359192848,13027956824399552,
%T A000273 341260431952972580352,32522909385055886111197440,
%U A000273 11366745430825400574433894004224,14669085692712929869037096075316220928,70315656615234999521385506555979904091217920
%N A000273 Number of unlabeled simple digraphs with n nodes.
%D A000273 CRC Handbook of Combinatorial Designs, 1996, p. 651.
%D A000273 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.
%D A000273 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 225.
%D A000273 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, Table 5.1.2 and p. 241, Table A4.
%D A000273 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 A000273 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000273 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000273 Keith Briggs, <a href="/A000273/b000273.txt">Table of n, a(n) for n = 0..64</a>
%H A000273 R. Absil and H Mélot, <a href="http://arxiv.org/abs/1304.7993">Digenes: genetic algorithms to discover conjectures about directed and undirected graphs</a>, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
%H A000273 Fatemeh Arbabjolfaei and Young-Han Kim, <a href="http://dx.doi.org/10.1561/0100000094">Fundamentals of Index Coding</a>, Foundations and Trends in Communications and Information Theory (2018) Vol. 14, Issue 3-4.
%H A000273 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 A000273 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 A000273 A. Iványi, <a href="http://www.emis.de/journals/AUSM/C5-1/math51-5.pdf">Leader election in synchronous networks</a>, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
%H A000273 Gábor Kusper, Zijian Győző Yang, and Benedek Nagy, <a href="https://doi.org/10.33039/ami.2023.08.011">Using extended resolution to represent strongly connected components of directed graphs</a>, Ann. Math. Inf. (2023).
%H A000273 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 A000273 W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.
%H A000273 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 A000273 J. Qian, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p46">Enumeration of unlabeled directed hypergraphs</a>, Electronic Journal of Combinatorics, 20(1) (2013), #P46. - From _N. J. A. Sloane_, Mar 01 2013
%H A000273 J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>
%H A000273 L. Travis, <a href="https://arxiv.org/abs/math/9811127">Graphical Enumeration: A Species-Theoretic Approach</a>, arXiv:math/9811127 [math.CO], 1998.
%H A000273 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SimpleDirectedGraph.html">Simple Directed Graph</a>
%H A000273 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000273 a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016
%p A000273 with(combinat):with(numtheory):
%p A000273 for n from 0 to 20 do p:=partition(n):
%p A000273 s:=0:for k from 1 to nops(p) do
%p A000273 q:=convert(p[k],multiset):
%p A000273 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:
%p A000273 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:
%p A000273 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:
%p A000273 s:=s+2^(g/ord)/c:
%p A000273 od:
%p A000273 print(n,s):
%p A000273 od:
%p A000273 # _Vladeta Jovovic_, Jun 06 2006
%p A000273 # second Maple program:
%p A000273 b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
%p A000273       igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
%p A000273       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
%p A000273     end:
%p A000273 A000273 := n-> b(n$2, []):
%p A000273 seq(A000273(n), n=0..20);  # _Alois P. Heinz_, Sep 04 2019
%t A000273 Table[CycleIndex[PairGroup[SymmetricGroup[n],Ordered],t]/.Table[t[i]->1+x^i,{i,1,n^2}]/.{x->1},{n,1,7}] (* or *)
%t A000273   Table[GraphPolynomial[n,t,Directed]/.{t->1},{n,1,20}]
%t A000273 (* _Geoffrey Critzer_, Mar 08 2011 *)
%t A000273 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 A000273 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total[v-1];
%t A000273 a[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
%t A000273 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%o A000273 (PARI)
%o A000273 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 A000273 edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
%o A000273 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o A000273 (Python)
%o A000273 from math import gcd, factorial
%o A000273 from sympy.utilities.iterables import partitions
%o A000273 def permcount(v):
%o A000273     m, s, k = 1, 0, 0
%o A000273     for i, t in enumerate(v):
%o A000273         k = k+1 if i > 0 and t == v[i-1] else 1; m *= t*k; s += t
%o A000273     return factorial(s)//m
%o A000273 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)
%o A000273 def a(n):
%o A000273     s = 0
%o A000273     for p in partitions(n):
%o A000273         pvec = []
%o A000273         for i in sorted(p): pvec.extend([i]*p[i])
%o A000273         s += permcount(pvec)*2**edges(pvec)
%o A000273     return s//factorial(n)
%o A000273 print([a(n) for n in range(15)]) # _Michael S. Branicky_, Nov 14 2022 after _Andrew Howroyd_
%o A000273 (Python)
%o A000273 from itertools import combinations
%o A000273 from math import prod, factorial, gcd
%o A000273 from fractions import Fraction
%o A000273 from sympy.utilities.iterables import partitions
%o A000273 def A000273(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s)<<1 for r,s in combinations(p.keys(),2))+sum(r*(q*r-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 05 2024
%Y A000273 Row sums of A052283 and of A217654.
%K A000273 nonn,core,nice
%O A000273 0,3
%A A000273 _N. J. A. Sloane_
%E A000273 More terms from _Vladeta Jovovic_, Dec 14 1999