A000273 - OEIS

%I M3032 N1229 #119 Jul 05 2024 16:13:01

%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_

%o (Python)

%o from itertools import combinations

%o from math import prod, factorial, gcd

%o from fractions import Fraction

%o from sympy.utilities.iterables import partitions

%o 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 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