Combinatorial Theory

In the combinatorial theory of continued fractions, the Foata-Zeilberger bijection and its variants have been extensively used to derive various continued fractions enumerating several (sometimes infinitely many) simultaneous statistics on permutations (combinatorial model for factorials) and D-permutations (combinatorial model for Genocchi and median Genocchi numbers). A Laguerre digraph is a digraph in which each vertex has in- and out-degrees $0$ or $1$. In this paper, we interpret the Foata-Zeilberger bijection in terms of Laguerre digraphs, which enables us to count cycles in permutations. Using this interpretation, we obtain Jacobi-type continued fractions for multivariate polynomials enumerating permutations, and also Thron-type and Stieltjes-type continued fractions for multivariate polynomials enumerating D-permutations, in both cases including the counting of cycles. This enables us to prove some conjectured continued fractions due to Sokal and Zeng (2022 Advances in Applied Mathematics) in the case of permutations, and Randrianarivony and Zeng (1996 Electronic Journal of Combinatorics) and Deb and Sokal (2024 Advances in Applied Mathematics) in the case of D-permutations.

Mathematics Subject Classifications: 05A19 (Primary); 05A05, 05A10, 05A15, 05A30, 11B68, 30B70 (Secondary).

Keywords: Permutations, D-permutations, continued fraction, Foata-Zeilberger bijection, S-fraction, J-fraction, T-fraction, Dyck path, almost-Dyck path, Motzkin path, Schröder path, Laguerre digraphs