A380374 Number of ways to topologically sort the strong components of a labeled digraph on [n].

1, 1, 5, 90, 5542, 1252120, 1152382456, 4491243320144, 72454914124818352, 4729326805677997351296, 1238455260161143286333919616, 1298230864749797963009864293455616, 5444709289384095954326434486307506566400, 91344784292457849099764110418297773249212062720

Offset: 0

Author

Geoffrey Critzer, Jan 23 2025

Keywords

• nonn

Comments

a(n) is the number of ways to choose a labeled digraph D with n vertices (as in A053763) and then topologically sort the condensation of D, i.e., the directed acyclic graph (A003024) obtained by contracting each strongly connected component of D to a single vertex.

The cases in which D is acyclic are counted by A011266.

Links

• E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
• Wikipedia, Strongly connected component
• Wikipedia, Topological sorting

Crossrefs

Cf. A053763, A003024, A011266, A003030.

Programs

Mathematica

nn = 13; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]];s[z_] := Total[strong Table[z^i/B[i], {i, 1, 58}]];
B[n_] := n! 2^Binomial[n, 2];Table[B[n], {n, 0, nn}] CoefficientList[ Series[1/(1 - s[z]), {z, 0, nn}], z]

Formula

Sum_{n>=0} a(n)*x^n/B(n) = 1/(1-s(x)) where B(n) = A011266(n) and s(x) = Sum_{n>=1} A003030(n)*x^n/B(n).