cp's OEIS Frontend

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

%I A367500 #19 Jan 28 2024 20:33:57
%S A367500 1,0,1,5,90,5332,1076904,713634480,1586714659885,12154215627095823,
%T A367500 328282817968663707661,31834558934274542784372501,
%U A367500 11234635799120735533158176241587,14576389568173850099660541344975456791,70075904848498231395100110985113641934719377
%N A367500 The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.
%C A367500 Digraphs counted here must be loopless, but not necessarily connected.
%C A367500 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 A367500 (The weakly connected digraphs of this type start 1,0,1,5,89,5327,...)
%H A367500 Andrew Howroyd, <a href="/A367500/b367500.txt">Table of n, a(n) for n = 0..50</a>
%H A367500 R. J. Mathar, <a href="/A367500/a367500.pdf">Illustrations</a> (2023), 335 pages
%e A367500 From _Andrew Howroyd_, Jan 02 2024: (Start)
%e A367500 Example of a digraph counted by this sequence but not by A361586:
%e A367500    o <---> o ----> o ----> o <---> o
%e A367500 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 A367500 (PARI)
%o A367500 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 A367500 K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
%o A367500 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 A367500 Cf. A121933 (labeled version), A086193 (labeled digraphs), A002494 (undirected graphs), A361586 (all vertices in at least one directed cycle).
%K A367500 nonn
%O A367500 0,4
%A A367500 _R. J. Mathar_, Nov 20 2023
%E A367500 Terms a(6) and beyond from _Andrew Howroyd_, Jan 02 2024