login
A363834
Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.
0
1, 2, 15, 452, 58023, 31083662, 66296957895, 554842541248592, 18340342731323665263, 2411916363098805776251322, 1266238008719333748929247025455, 2657054767893996575723268008873476172, 22295054304671836968688374028608806896204023
OFFSET
0,2
COMMENTS
The sequence gives a good lower bound for the number of convergent binary relations (A365534) which is only known for n <= 6.
LINKS
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
FORMULA
Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(sm(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), sm(x) = Sum_{n>=0} (2^n-1)*A003030(n)*x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).
EXAMPLE
a(2) = 15 because there are 16 labeled digraphs with self loops on [2] and all of them are good except: [1->2,2->1].
MATHEMATICA
nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; sm[x_] := Total[Table[2^n - 1, {n, 1, Length[strong]}] strong Table[ x^i/i!, {i, 1, 58}]]; ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.
Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(sm[x] + x)]], {x, 0, nn}], x]
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Oct 19 2023
STATUS
approved