|
%I M3032 N1229 #116 Aug 29 2023 11:06:48
%S 1,1,3,16,218,9608,1540944,882033440,1793359192848,13027956824399552,
%T 341260431952972580352,32522909385055886111197440,
%U 11366745430825400574433894004224,14669085692712929869037096075316220928,70315656615234999521385506555979904091217920
%N Number of unlabeled simple digraphs with n nodes.
%D CRC Handbook of Combinatorial Designs, 1996, p. 651.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.
%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 225.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, Table 5.1.2 and p. 241, Table A4.
%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Keith Briggs, <a href="/A000273/b000273.txt">Table of n, a(n) for n = 0..64</a>
%H 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 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 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 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 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 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 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 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 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 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 J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>
%H L. Travis, <a href="https://arxiv.org/abs/math/9811127">Graphical Enumeration: A Species-Theoretic Approach</a>, arXiv:math/9811127 [math.CO], 1998.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SimpleDirectedGraph.html">Simple Directed Graph</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016
%p with(combinat):with(numtheory):
%p for n from 0 to 20 do p:=partition(n):
%p s:=0:for k from 1 to nops(p) do
%p q:=convert(p[k],multiset):
%p 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 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 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 s:=s+2^(g/ord)/c:
%p od:
%p print(n,s):
%p od:
%p # _Vladeta Jovovic_, Jun 06 2006
%p # second Maple program:
%p b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
%p igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
%p add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
%p end:
%p A000273 := n-> b(n$2, []):
%p seq(A000273(n), n=0..20); # _Alois P. Heinz_, Sep 04 2019
%t Table[CycleIndex[PairGroup[SymmetricGroup[n],Ordered],t]/.Table[t[i]->1+x^i,{i,1,n^2}]/.{x->1},{n,1,7}] (* or *)
%t Table[GraphPolynomial[n,t,Directed]/.{t->1},{n,1,20}]
%t (* _Geoffrey Critzer_, Mar 08 2011 *)
%t 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 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total[v-1];
%t a[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%o (PARI)
%o 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 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 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o (Python)
%o from math import gcd, factorial
%o from sympy.utilities.iterables import partitions
%o def permcount(v):
%o m, s, k = 1, 0, 0
%o for i, t in enumerate(v):
%o k = k+1 if i > 0 and t == v[i-1] else 1; m *= t*k; s += t
%o return factorial(s)//m
%o 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 def a(n):
%o s = 0
%o for p in partitions(n):
%o pvec = []
%o for i in sorted(p): pvec.extend([i]*p[i])
%o s += permcount(pvec)*2**edges(pvec)
%o return s//factorial(n)
%o print([a(n) for n in range(15)]) # _Michael S. Branicky_, Nov 14 2022 after _Andrew Howroyd_
%Y Row sums of A052283 and of A217654.
%K nonn,core,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Dec 14 1999
|
