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.

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

Table of n, a(n) for n=0..12.

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

Cf. A365534, A070322, A003030.

Sequence in context: A145328 A139810 A012943 * A013059 A013098 A365534

Adjacent sequences: A363831 A363832 A363833 * A363835 A363836 A363837

Keyword

nonn

Author

Geoffrey Critzer, Oct 19 2023

Status

approved