A367500 The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.

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

Andrew Howroyd, Table of n, a(n) for n = 0..50

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

Adjacent sequences: A367497 A367498 A367499 * A367501 A367502 A367503

Keyword

nonn

Author

R. J. Mathar, Nov 20 2023

Extensions

Terms a(6) and beyond from Andrew Howroyd, Jan 02 2024

Status

approved