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

Author

R. J. Mathar, Nov 20 2023

Keywords

• nonn

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

Examples

			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)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• R. J. Mathar, Illustrations (2023), 335 pages

Crossrefs

Cf. A121933 (labeled version), A086193 (labeled digraphs), A002494 (undirected graphs), A361586 (all vertices in at least one directed cycle).

Programs

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

Extensions

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