login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052283 Triangle read by rows giving numbers of directed graphs by numbers of nodes and arcs. 6
1, 1, 1, 1, 1, 1, 4, 4, 4, 1, 1, 1, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1, 1, 1, 5, 16, 61, 154, 379, 707, 1155, 1490, 1670, 1490, 1155, 707, 379, 154, 61, 16, 5, 1, 1, 1, 1, 5, 17, 76, 288, 1043, 3242, 8951, 21209, 43863, 78814, 124115, 171024, 207362, 220922 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,7

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

Table of n, a(n) for n=1..61.

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, 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,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

Cf. A000273 (row sums), A070166, A008406, A003085, A283753 (weakly connected).

Sequence in context: A073816 A084452 A176101 * A133889 A243756 A172985

Adjacent sequences:  A052280 A052281 A052282 * A052284 A052285 A052286

KEYWORD

nonn,tabf

AUTHOR

Vladeta Jovovic, Feb 07 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 00:06 EST 2018. Contains 317150 sequences. (Running on oeis4.)