A367500 - OEIS

%I #19 Jan 28 2024 20:33:57

%S 1,0,1,5,90,5332,1076904,713634480,1586714659885,12154215627095823,

%T 328282817968663707661,31834558934274542784372501,

%U 11234635799120735533158176241587,14576389568173850099660541344975456791,70075904848498231395100110985113641934719377

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

%C Digraphs counted here must be loopless, but not necessarily connected.

%C 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.

%C (The weakly connected digraphs of this type start 1,0,1,5,89,5327,...)

%H Andrew Howroyd, <a href="/A367500/b367500.txt">Table of n, a(n) for n = 0..50</a>

%H R. J. Mathar, <a href="/A367500/a367500.pdf">Illustrations</a> (2023), 335 pages

%e From _Andrew Howroyd_, Jan 02 2024: (Start)

%e Example of a digraph counted by this sequence but not by A361586:

%e    o <---> o ----> o ----> o <---> o

%e 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)

%o (PARI)

%o 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}

%o K(q, t)={sum(j=1, #q, gcd(t, q[j]))}

%o 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

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

%K nonn

%O 0,4

%A _R. J. Mathar_, Nov 20 2023

%E Terms a(6) and beyond from _Andrew Howroyd_, Jan 02 2024