A121933 -id:A121933 - cp's OEIS frontend

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

R. J. Mathar, Nov 20 2023

nonn

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

			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)

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

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

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

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

A121063 Number of labeled directed multigraphs with n arcs for which every vertex has in-degree at least one and out-degree at least one.

Original entry on oeis.org

1, 0, 1, 4, 27, 246, 2783, 37424, 582153, 10276452, 202894801, 4429522252, 105943672079, 2754788353526, 77371821493913, 2334279549290960, 75286455363538607, 2584971423426768872, 94138234184851584599, 3624294240897948371036, 147080227272202880297669

Offset: 0

Vladeta Jovovic, Sep 06 2006

Nathaniel Johnston, Table of n, a(n) for n = 0..60

Cf. A052170, A056078, A104209, A121933.

n:=20: t:=taylor(sum(sum((-1)^(s-k)*binomial(s,k)*((1+x/(1-x))^(k-1)-1)^k*((1+x/(1-x))^k-1)^(s-k),k=0..s),s=0..n),x,n+1): seq(coeff(t,x,s),s=0..n); # Nathaniel Johnston, Apr 28 2011

G.f.: A(x/(1-x)) where A(x) is g.f. for A121933.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions