cp's OEIS Frontend

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

%I A380374 #15 Jan 26 2025 15:04:55
%S A380374 1,1,5,90,5542,1252120,1152382456,4491243320144,72454914124818352,
%T A380374 4729326805677997351296,1238455260161143286333919616,
%U A380374 1298230864749797963009864293455616,5444709289384095954326434486307506566400,91344784292457849099764110418297773249212062720
%N A380374 Number of ways to topologically sort the strong components of a labeled digraph on [n].
%C A380374 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.
%C A380374 The cases in which D is acyclic are counted by A011266.
%H A380374 E. de Panafieu and S. Dovgal, <a href="https://arxiv.org/abs/1903.09454">Symbolic method and directed graph enumeration</a>, arXiv:1903.09454 [math.CO], 2019.
%H A380374 Wikipedia, <a href="http://en.wikipedia.org/wiki/Strongly_connected component">Strongly connected component</a>
%H A380374 Wikipedia, <a href="http://en.wikipedia.org/wiki/Topological_sorting">Topological sorting</a>
%F A380374 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).
%t A380374 nn = 13; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
%t A380374    Length@# == 2 &][[All, 2]];s[z_] := Total[strong Table[z^i/B[i], {i, 1, 58}]];
%t A380374 B[n_] := n! 2^Binomial[n, 2];Table[B[n], {n, 0, nn}] CoefficientList[ Series[1/(1 - s[z]), {z, 0, nn}], z]
%Y A380374 Cf. A053763, A003024, A011266, A003030.
%K A380374 nonn
%O A380374 0,3
%A A380374 _Geoffrey Critzer_, Jan 23 2025