login
A367500
The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.
2
1, 0, 1, 5, 90, 5332, 1076904, 713634480, 1586714659885, 12154215627095823, 328282817968663707661, 31834558934274542784372501, 11234635799120735533158176241587, 14576389568173850099660541344975456791, 70075904848498231395100110985113641934719377
OFFSET
0,4
COMMENTS
Digraphs counted here must be loopless, but not necessarily connected.
The definition is not strictly saying that there is no (global) source or sink, because the graphs are counted without considering (strong or weak) connectivity.
(The weakly connected digraphs of this type start 1,0,1,5,89,5327,...)
LINKS
R. J. Mathar, Illustrations (2023), 335 pages
EXAMPLE
From Andrew Howroyd, Jan 02 2024: (Start)
Example of a digraph counted by this sequence but not by A361586:
o <---> o ----> o ----> o <---> o
In the above example, the 3rd vertex has both an in arc and an out arc, but is not part of any directed cycle. (End)
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}
K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
a(n) = {if(n==0, 1, sum(k=1, n, my(s=0, m=n-k); forpart(p=k, s += permcount(p) * prod(i=1, #p, 2^(K(p, p[i])-1)-1) * polcoef(exp(sum(t=1, m, (1-2^K(p, t))/t*x^t) + O(x*x^m)), m)); s/k!))} \\ Andrew Howroyd, Jan 02 2024
CROSSREFS
Cf. A121933 (labeled version), A086193 (labeled digraphs), A002494 (undirected graphs), A361586 (all vertices in at least one directed cycle).
Sequence in context: A323570 A295766 A361586 * A216693 A158073 A038636
KEYWORD
nonn
AUTHOR
R. J. Mathar, Nov 20 2023
EXTENSIONS
Terms a(6) and beyond from Andrew Howroyd, Jan 02 2024
STATUS
approved