OFFSET
0,8
COMMENTS
Triangular array read by rows T(n,k) is the number of unlabeled directed graphs (no self loops allowed) on n nodes with exactly k edges where n >= 1, 0 <= k <= n(n-1). - Geoffrey Critzer, Nov 01 2011
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 247.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..2680 (rows 0..20)
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.
Philippe Ramirez and Stéphane Legendre, Revisiting asymmetric marriage rules, in Social Networks 52 (2017), pp. 261-269.
Stackexchange, Number of distinct connected digraphs..., (2017)
Eric Weisstein's World of Mathematics, Simple Directed Graph
FORMULA
T(n,0) = T(n,1) = T(n,n(n-1)-1) = T(n,n) = 1. - Geoffrey Critzer, Nov 01 2011
T(2k,k) = T(2k+1,k) = T(2k+2,k) =... and is the maximum value of column k. - Geoffrey Critzer, Nov 01 2011
EXAMPLE
[1],
[1],
[1,1,1],
[1,1,4,4,4,1,1],
[1,1,5,13,27,38,48,38,27,13,5,1,1];
(the last batch giving the numbers of directed graphs with 4 nodes and from 0 to 12 arcs).
MATHEMATICA
Table[CoefficientList[GraphPolynomial[n, x, Directed], x], {n, 1, 10}] (* Geoffrey Critzer, Nov 01 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_, t_] := Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^(2 g), {i, 2, Length[v]}, {j, 1, i-1}] * Product[ t[v[[i]]]^(v[[i]] - 1), {i, 1, Length[v]}];
gp[n_] := (s = 0; Do[s += permcount[p]*edges[p, 1 + x^# &], {p, IntegerPartitions[n]}]; s/n!);
A052283 = Reap[For[n = 1, n <= 6, n++, p = gp[n]; For[k = 0, k <= Exponent[p, x], k++, Sow[Coefficient[p, x, k]]]]][[2, 1]] (* Jean-François Alcover, Jul 09 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, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^(2*g))) * prod(i=1, #v, t(v[i])^(v[i]-1))}
gp(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
for(n=1, 6, my(p=gp(n)); for(k=0, poldegree(p), print1(polcoeff(p, k), ", ")); print); \\ Andrew Howroyd, Nov 05 2017
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Vladeta Jovovic, Feb 07 2000
EXTENSIONS
a(0)=1 prepended and terms a(62) and beyond from Andrew Howroyd, Apr 20 2020
STATUS
approved