Counting acyclic and strong digraphs by descents (Q2198383): Difference between revisions

In this paper, the authors refine the counting formulas for four classes of labeled directed graphs with \(n\) nodes and \(m\) edges by additional accounting for the number of descents. Hereby, a descent is a directed edge \((s,t)\) with \(s > t\). The considered classes are strongly connected tournaments, strongly connected directed graphs, acyclic directed graphs, and forests (or trees). Their method builds on the known recursive formulas for these classes which are enriched by the number of descents. Then, they use special types of generating functions, such as Eulerian generating functions and a new variant developed by them called graphic Eulerian generating function, to derive closed forms or functional equations.