A086366
Number of labeled n-node digraphs in which every node belongs to a directed cycle.
Original entry on oeis.org
1, 0, 1, 18, 1699, 587940, 750744901, 3556390155318, 63740128872703879, 4405426607409460017480, 1190852520892329350092354441, 1270598627613805616203391468226138, 5381238039128882594932248239301142751179, 90766634183072089515270648224715368261615375340
Offset: 0
-
G(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k/2^(k*(k-1)/2), O(x^n)))}
U(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k*2^(k*(k-1)/2), O(x^n)))}
DigraphEgf(n)={sum(k=0, n, 2^(k*(k-1))*x^k/k!, O(x*x^n) )}
seq(n)={Vec(serlaplace(U(1/G(exp(x+log(U(1/G(DigraphEgf(n)))))))))} \\ Andrew Howroyd, Jan 15 2022
a(0)=1 prepended and terms a(12) and beyond from
Andrew Howroyd, Jan 15 2022
A361590
Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with exactly k strongly connected components of size 1.
Original entry on oeis.org
1, 0, 1, 1, 0, 2, 5, 5, 0, 6, 90, 55, 42, 0, 31, 5289, 2451, 974, 592, 0, 302, 1071691, 323709, 94332, 29612, 15616, 0, 5984, 712342075, 135208025, 25734232, 6059018, 1650492, 795930, 0, 243668, 1585944117738, 181427072519, 21650983294, 3358042412, 704602272, 174576110, 79512478, 0, 20286025
Offset: 0
Triangle begins:
1;
0, 1;
1, 0, 2;
5, 5, 0, 6;
90, 55, 42, 0, 31;
5289, 2451, 974, 592, 0, 302;
1071691, 323709, 94332, 29612, 15616, 0, 5984;
...
A367500
The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.
Original entry on oeis.org
1, 0, 1, 5, 90, 5332, 1076904, 713634480, 1586714659885, 12154215627095823, 328282817968663707661, 31834558934274542784372501, 11234635799120735533158176241587, 14576389568173850099660541344975456791, 70075904848498231395100110985113641934719377
Offset: 0
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)
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
Showing 1-3 of 3 results.
Comments