login
A054733
Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).
9
1, 1, 0, 3, 4, 4, 1, 1, 0, 0, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008
OFFSET
2,4
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 2..2661 (rows 2..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 75.
EXAMPLE
1,1;
0,3,4,4,1,1;
0,0,8,22,37,47,38,27,13,5,1,1;
the last batch giving the numbers of connected digraphs with 4 nodes and from 1 to 12 arcs.
PROG
(PARI)
InvEulerMTS(p)={my(n=serprec(p, x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i)}
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, my(c=v[i]); t(c)^(c-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y)}
{ for(n=2, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022
CROSSREFS
Cf. A000238 (leading diagonal), A003085 (row sums), A053454 (column sums), A062735 (labeled).
Cf. A052283 (not necessarily connected), A283753 (another version), A057276 (strongly connected), A350789 (transpose).
Sequence in context: A260180 A057279 A350908 * A204255 A283753 A120649
KEYWORD
easy,nonn,tabf
AUTHOR
Vladeta Jovovic, Apr 21 2000
STATUS
approved