<figure><img src="image_1.png" /></figure>

HAL
open science

# Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants

Bishal Deb

► To cite this version:

Bishal Deb. Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants. 2024. hal-04717197

HAL Id: hal-04717197

https://hal.science/hal-04717197v1

Preprint submitted on 3 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants

Bishal Deb¹,²

¹Department of Mathematics, University College London, London WC1E 6BT, United Kingdom

²Sorbonne Université and Université Paris Cité, CNRS, Laboratoire de Probabilités, Statistique et Modélisation, 75005 Paris, France

bishal@gonitsora.com

April 27, 2023

Revised on September 27, 2024

## Abstract

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.

**Key Words:** 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

**Mathematics Subject Classification (MSC 2020) codes:** 05A19 (Primary); 05A05, 05A10, 05A15, 05A30, 11B68, 30B70 (Secondary).
# Contents

<table><tr><td>1</td><td>Introduction</td><td>4</td></tr><tr><td>1.1</td><td>Foreword</td><td>4</td></tr><tr><td>1.2</td><td>Classical continued fractions: S-fractions, J-fractions and T-fractions</td><td>6</td></tr><tr><td>1.3</td><td>Permutation statistics: record and cycle classification</td><td>7</td></tr><tr><td>1.3.1</td><td>Running example 1</td><td>10</td></tr><tr><td>1.3.2</td><td>Running example 2</td><td>11</td></tr><tr><td>1.4</td><td>Permutations: Statement of conjecture</td><td>12</td></tr><tr><td>1.5</td><td>Genocchi, median Genocchi numbers, and D-permutations</td><td>13</td></tr><tr><td>1.6</td><td>D-Permutations: Statements of conjectures</td><td>15</td></tr><tr><td>1.7</td><td>Overview of proof for results on permutations</td><td>17</td></tr><tr><td>1.8</td><td>Outline of paper</td><td>19</td></tr><tr><td>2</td><td>Permutation statistics: Crossings and nestings</td><td>20</td></tr><tr><td>3</td><td>Permutations: Statements of results</td><td>23</td></tr><tr><td>3.1</td><td>J-fraction (Sokal-Zeng conjecture)</td><td>23</td></tr><tr><td>3.2</td><td>p, q-generalisation</td><td>24</td></tr><tr><td>3.3</td><td>Master J-fraction</td><td>25</td></tr><tr><td>4</td><td>D-permutations: Statements of results</td><td>27</td></tr><tr><td>4.1</td><td>Continued fractions using record classification</td><td>27</td></tr><tr><td>4.1.1</td><td>T-fraction (Deb-Sokal conjecture)</td><td>27</td></tr><tr><td>4.1.2</td><td>p, q-generalisation</td><td>29</td></tr><tr><td>4.1.3</td><td>Master T-fraction</td><td>31</td></tr><tr><td>4.2</td><td>Continued fractions using variant record classification</td><td>32</td></tr><tr><td>4.2.1</td><td>T-fraction</td><td>33</td></tr><tr><td>4.2.2</td><td>p, q-generalisation</td><td>33</td></tr><tr><td>4.2.3</td><td>Master T-fraction</td><td>34</td></tr><tr><td>4.3</td><td>Reformulation of results using cycle valley minima and the Randrianarivony-Zeng conjecture</td><td>35</td></tr><tr><td>5</td><td>Proof preliminaries</td><td>37</td></tr><tr><td>5.1</td><td>Combinatorial interpretation of continued fractions</td><td>37</td></tr><tr><td>5.2</td><td>Labelled Dyck, Motzkin and Schröder paths</td><td>39</td></tr><tr><td>6</td><td>Permutations: Proof of Theorems 3.1, 3.2, 3.3</td><td>41</td></tr><tr><td>6.1</td><td>Sokal-Zeng variant of the Foata-Zeilberger bijection</td><td>41</td></tr><tr><td>6.1.1</td><td>Running example 1</td><td>45</td></tr><tr><td>6.1.2</td><td>Running example 2</td><td>46</td></tr><tr><td>6.2</td><td>Combinatorial interpretation using Laguerre digraphs</td><td>47</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>6.3 Examples</td>
      <td>53</td>
    </tr>
    <tr>
      <td>6.3.1 Running example 1</td>
      <td>53</td>
    </tr>
    <tr>
      <td>6.3.2 Running example 2</td>
      <td>53</td>
    </tr>
    <tr>
      <td>6.4 Computation of weights</td>
      <td>53</td>
    </tr>
    <tr>
      <td><b>7 D-permutations: Proofs</b></td>
      <td><b>60</b></td>
    </tr>
    <tr>
      <td>7.1 Continued fractions using record classification:</td>
      <td></td>
    </tr>
    <tr>
      <td>Proof of Theorems 4.1, 4.3, 4.4</td>
      <td>62</td>
    </tr>
    <tr>
      <td>7.1.1 Description of labels and inverse bijection</td>
      <td>62</td>
    </tr>
    <tr>
      <td>7.1.2 Running example 2</td>
      <td>65</td>
    </tr>
    <tr>
      <td>7.1.3 Combinatorial interpretation using Laguerre digraphs</td>
      <td>66</td>
    </tr>
    <tr>
      <td>7.1.4 Running example 2</td>
      <td>69</td>
    </tr>
    <tr>
      <td>7.1.5 Computation of weights</td>
      <td>69</td>
    </tr>
    <tr>
      <td>7.2 Continued fractions using variant record classification:</td>
      <td></td>
    </tr>
    <tr>
      <td>Proof of Theorems 4.5, 4.6, 4.7</td>
      <td>73</td>
    </tr>
    <tr>
      <td>7.2.1 Description of labels and inverse bijection</td>
      <td>73</td>
    </tr>
    <tr>
      <td>7.2.2 Running example 2</td>
      <td>76</td>
    </tr>
    <tr>
      <td>7.2.3 Combinatorial interpretation using Laguerre digraphs</td>
      <td>77</td>
    </tr>
    <tr>
      <td>7.2.4 Running example 2</td>
      <td>79</td>
    </tr>
    <tr>
      <td>7.2.5 Computation of weights</td>
      <td>79</td>
    </tr>
    <tr>
      <td><b>8 Final remarks</b></td>
      <td><b>82</b></td>
    </tr>
    <tr>
      <td><b>Acknowledgements</b></td>
      <td><b>83</b></td>
    </tr>
    <tr>
      <td><b>Bibliography</b></td>
      <td><b>83</b></td>
    </tr>
  </tbody>
</table>
# 1 Introduction

## 1.1 Foreword

This paper will introduce new results to the combinatorial theory of continued fractions for multivariate polynomials generalising the following three sequences of integers: factorials $(n!)_{n \ge 0}$, the Genocchi numbers [26, A110501]

$$ (g_n)_{n \ge 0} = 1, 1, 3, 17, 155, 2073, 38227, 929569, 28820619, 1109652905, \dots \quad (1.1) $$

and the median Genocchi numbers [26, A005439]

$$ (h_n)_{n \ge 0} = 1, 1, 2, 8, 56, 608, 9440, 198272, 5410688, 186043904, \dots \quad (1.2) $$

We shall use permutations for studying factorials, and a subclass of permutations called *D-permutations* (first introduced in [24, 23]) for studying the Genocchi and median Genocchi numbers.

We shall consider continued fractions of Stieltjes-type (S-fraction),

$$ \sum_{n=0}^{\infty} a_n t^n = \frac{1}{1 - \frac{\alpha_1 t}{1 - \frac{\alpha_2 t}{1 - \dots}}} \quad (1.3) $$

as well as Jacobi-type and Thron-type (defined in (1.7),(1.8)). The ordinary generating functions of our integer sequences have S-fractions with coefficients $\alpha_{2k-1} = \alpha_{2k} = k$ for factorials [11, section 21], $\alpha_{2k-1} = k^2$ and $\alpha_{2k} = k(k+1)$ for the Genocchi numbers [36, eq. (7.5)] [37, p. V-9] [9, eqns. (1.4) and (3.9)], and $\alpha_{2k-1} = \alpha_{2k} = k^2$ for the Genocchi medians [36, eq. (9.7)] [37, p. V-15] [9, eqns. (1.5) and (3.8)].

A systematic study of some combinatorial families whose associated S-fraction coefficients $(\alpha_n)_{n \ge 0}$ grow linearly in $n$ was carried out by Sokal and Zeng in [34]. They introduced various “master polynomials” enumerating permutations, set partitions and perfect matchings with respect to a large (sometimes infinite) number of simultaneous statistics. A similar study was carried out for D-permutations and its subclasses by Deb and Sokal in [6]: here the associated T-fraction coefficients $(\alpha_n)_{n \ge 0}$ for these families grow quadratically in $n$. The continued fractions in [34, 6] were classified as “first” or “second” depending on whether they did not or did involve the count of cycles. Both Sokal-Zeng and Deb-Sokal were able to prove “second” continued fractions but by using two specialisations. They conjectured continued fractions with only one specialisation ([34, Conjecture 2.3] and [6, Conjecture 4.1]), but a proof was lacking. Here we prove these conjectures. We
will also prove a conjectured continued fraction of Randrianarivony and Zeng from 1996
[30, Conjecture 12] for D-o-semiderangements<fnref n="1" /> (a subclass of D-permutations).

Our proofs bring a surprising twist to this story. A common feature in the work of Sokal-Zeng [34] and Deb-Sokal [6] is that the proofs of the first and second continued fractions involve two different bijections: the first continued fractions were proved using bijections motivated from the Foata-Zeilberger bijection [15], whereas the second continued fractions used the Biane bijection [3] or a Biane-like bijection. However, we will prove these conjectured second continued fractions by precisely the same bijections that were used to prove the first bijections in these papers. We will show, perhaps surprisingly, that these variants of the Foata-Zeilberger bijection can be used to obtain the counting of cycles.

Let us mention the historical context for our bijections. The Foata-Zeilberger bijection [15] is a bijection between permutations and labelled Motzkin paths that has been very successfully employed to obtain continued fractions involving polynomial coefficients counting various permutation statistics (see for example [31, 4, 2, 34]). In a similar essence to the Foata-Zeilberger bijection, Randrianarivony [29] introduced a bijection between D-o-semiderangements and labelled Dyck paths to obtain continued fractions counting various statistics on D-o-semiderangements. Motivated by Randrianarivony's bijection, Deb and Sokal [6] introduced two new bijections involving all D-permutations, one of which extends Randrianarivony's bijection.

The fundamental idea in this paper is that we interpret the intermediate steps in these existing bijections in a new light in terms of *Laguerre digraphs*. A Laguerre digraph of size *n* is a directed graph where each vertex has a distinct label from the label set [*n*] and has indegree 0 or 1 and outdegree 0 or 1.<fnref n="2" /> Thus, the connected components in a Laguerre digraph are either directed paths or directed cycles. A path with one vertex and no edges will be called an isolated vertex, and a cycle with one vertex (and one edge) will be called a loop.

The Sokal-Zeng conjecture [34, Conjecture 2.3] is a multivariate continued fraction con-
taining 8 variables along with a one-parameter family of infinitely many variables (the latter
associated to fixed points) counting various simultaneous statistics for permutations. The
Deb-Sokal conjecture [6, Conjecture 4.1] is a multivariate continued fraction with 12 vari-
ables counting similar simultaneous statistics for D-permutations. The Randrianarivony-
Zeng conjecture from 1996 [30, Conjecture 12] is a 4-variable continued fraction for D-o-
semiderangements. In the same spirit as [10, 34, 6], we will generalise these conjectured
continued fractions and use our proofs to churn out continued fractions containing an

<footnote n="1">¹In their paper [30], Randrianarivony and Zeng call these Genocchi permutations. We will explain our nomenclature in subsection 1.5.</footnote>

<footnote n="2">²Foata and Strehl [14] introduced an equivalent class of combinatorial objects called Laguerre configurations as a combinatorial interpretation of the Laguerre polynomials. Laguerre digraphs in the form that we use in this paper were first defined in [33]. Also see [5].</footnote>
infinite number of variables.

The rest of the introduction is organised as follows: We begin by explaining briefly the types of continued fractions that will be employed (Section 1.2) and then introduce the required statistics (Section 1.3). We state the conjecture for permutations [34, Conjecture 2.3] in Section 1.4. We then define Genocchi, median Genocchi numbers and D-permutations in Section 1.5, and state the associated conjectures ([30, Conjecture 12] and [6, Conjecture 4.1]) in Section 1.6. Then, in Section 1.7, we summarise our main ideas by providing an overview of the Foata-Zeilberger bijection and our interpretation of this bijection using Laguerre digraphs. The outline of the rest of the paper is mentioned in Section 1.8.

Throughout this paper, including the rest of this introduction, we shall use two running examples. The first is the permutation

$$ \sigma = 9374611581012 = (1,9,10)(2,3,7,5,6,11)(4)(8) \in \mathfrak{S}_{11}; \quad (1.4) $$

the second is the permutation

$$ \begin{aligned} \sigma &= 719254861031121413 \\ &= (1,7,8,6,4,2)(3,9,10)(5)(11)(12)(13,14) \in \mathfrak{S}_{14}. \end{aligned} \quad (1.5) $$

We will see later in Section 1.5 that our second example is a D-permutation.

## 1.2 Classical continued fractions: S-fractions, J-fractions and T-fractions

If $(a_n)_{n \ge 0}$ is a sequence of combinatorial numbers or polynomials with $a_0 = 1$, it is often fruitful to seek to express its ordinary generating function as a continued fraction. The most commonly studied types of continued fractions are Stieltjes-type (S-fractions),

$$ \sum_{n=0}^{\infty} a_n t^n = \frac{1}{1 - \frac{\alpha_1 t}{1 - \frac{\alpha_2 t}{1 - \dots}}} , \quad (1.6) $$

and Jacobi-type (J-fractions),

$$ \sum_{n=0}^{\infty} a_n t^n = \frac{1}{1 - \gamma_0 t - \frac{\beta_1 t^2}{1 - \gamma_1 t - \frac{\beta_2 t^2}{1 - \dots}}} . \quad (1.7) $$
A less commonly studied type of continued fraction is the Thron-type (T-fraction):

$$ \sum_{n=0}^{\infty} a_n t^n = \frac{1}{1 - \delta_1 t - \frac{\alpha_1 t}{1 - \delta_2 t - \frac{\alpha_2 t}{1 - \dots}}} \quad (1.8) $$

(Both sides of all these expressions are to be interpreted as formal power series in the indeterminate t.) Flajolet [12] showed that any S-fraction (resp. J-fraction) can be interpreted combinatorially as a generating function for Dyck (resp. Motzkin) paths with suitable weights for each rise and fall (resp. each rise, fall and level step). More recently, several authors [18, 27, 21, 10] have found a similar combinatorial interpretation of the general T-fraction: namely, as a generating function for Schröder paths with suitable weights for each rise, fall and long level step. These interpretations will be reviewed in Section 5.1 below.

## 1.3 Permutation statistics: record and cycle classification

We will follow the terminology in [6].

We begin by introducing some statistics which have been called the *record-and-cycle classification* for permutations and D-permutations in [34] and [6, Section 2.7] respectively. These statistics will play a central role in what follows.

Given a permutation $\sigma \in \mathfrak{S}_N$, an index $i \in [N]$ is called

* cycle peak (cpeak) if $\sigma^{-1}(i) < i > \sigma(i)$;

* cycle valley (cval) if $\sigma^{-1}(i) > i < \sigma(i)$;

* cycle double rise (cdrise) if $\sigma^{-1}(i) < i < \sigma(i)$;

* cycle double fall (cdfall) if $\sigma^{-1}(i) > i > \sigma(i)$;

* fixed point (fix) if $\sigma^{-1}(i) = i = \sigma(i)$.

Clearly every index $i$ belongs to exactly one of these five types; we refer to this classification as the *cycle classification*.

On the other hand, an index $i \in [N]$ is called a

* record (rec) (or left-to-right maximum) if $\sigma(j) < \sigma(i)$ for all $j < i$ [note in particular that the indices 1 and $\sigma^{-1}(N)$ are always records];

* antirecord (arec) (or right-to-left minimum) if $\sigma(j) > \sigma(i)$ for all $j > i$ [note in particular that the indices $N$ and $\sigma^{-1}(1)$ are always antirecords];

* exclusive record (erec) if it is a record and not also an antirecord;
* exclusive antirecord (earec) if it is an antirecord and not also a record;

* record-antirecord (rar) (or pivot) if it is both a record and an antirecord;

* neither-record-antirecord (nrar) if it is neither a record nor an antirecord.

Every index $i$ thus belongs to exactly one of the latter four types; we refer to this classification as the record classification.

Furthermore, one can apply the record and cycle classifications simultaneously, to obtain 10 (not 20) disjoint categories:

<table><thead><tr><th></th><th>cpeak</th><th>cval</th><th>cdrise</th><th>cdfall</th><th>fix</th></tr></thead><tbody><tr><td>erec</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>earec</td><td>eareccpeak</td><td></td><td></td><td></td><td></td></tr><tr><td>rar</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>nrar</td><td>nrcpeak</td><td>nrcval</td><td>nrcdrise</td><td>nrcdfall</td><td>rar<br/>nrfix</td></tr></tbody></table>

Clearly every index $i$ belongs to exactly one of these 10 types; we call this the record-and-cycle classification.

A variant of this classification involving record and antirecord values rather than indices was used in [6, Section 3.5]. A value $i \in [N]$ is called a

* record value (rec') (or left-to-right maximum value) if $\sigma(j) < i$ for all $j < \sigma^{-1}(i)$ [note in particular that the values $\sigma(1)$ and $N$ are always record values];

* antirecord value (arec') (or right-to-left minimum value) if $\sigma(j) > i$ for all $j > \sigma^{-1}(i)$ [note in particular that the values $\sigma(N)$ and 1 are always antirecord values].

Thus, $i$ is a record value (antirecord value resp.) if and only if $\sigma^{-1}(i)$ is a record (antirecord).

We also analogously define exclusive record value (erec'), exclusive antirecord value (earec'), record-antirecord value (rar') (or pivot value), neither-record-antirecord value (nrar'). Every index $i$ thus belongs to exactly one of these four types; we refer to this classification as the variant record classification.

We can similarly introduce the variant record-and-cycle classification consisting of the following 10 disjoint categories:

<table><thead><tr><th></th><th>cpeak</th><th>cval</th><th>cdrise</th><th>cdfall</th><th>fix</th></tr></thead><tbody><tr><td>erec'</td><td>ereccpeak'</td><td></td><td></td><td></td><td></td></tr><tr><td>earec'</td><td></td><td>eareccval'</td><td></td><td></td><td></td></tr><tr><td>rar'</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>nrar'</td><td>nrcpeak'</td><td>nrcval'</td><td>nrcdrise'</td><td>nrcdfall'</td><td>rar'<br/>nrfix'</td></tr></tbody></table>
Notice that in record-and-cycle classification, cycle valleys (cycle peaks resp.) can be exclusive records (exclusive anti-records) whereas in the variant record-and-cycle classification, cycle valleys (cycle peaks) can now be exclusive anti-records (exclusive records).

While working with D-permutations (defined in Section 1.5), we will refine the fixed points according to their parity:

$$ \bullet \textit{even fixed point (evenfix): } \sigma^{-1}(i) = i = \sigma(i) \text{ is even} \qquad (1.9) $$

$$ \bullet \textit{odd fixed point (oddfix): } \sigma^{-1}(i) = i = \sigma(i) \text{ is odd} $$

We therefore refine the record-and-cycle classification by distinguishing even and odd fixed points:

* evenrar: even record-antirecords (these are always fixed points);

* oddrar: odd record-antirecords (these are always fixed points);

* evennrfix: even neither-record-antirecords that are also fixed points;

* oddnrfix: odd neither-record-antirecords that are also fixed points.

We will use the *parity-refined record-and-cycle classification*, in which each index $i$ belongs to exactly one of 12 types. More precisely, we will see (by using Equation (1.27)) that each even index $i$ belongs to exactly one of the 6 types

eareccpeak, nrcpeak, eareccdfall, nrcdfall, evenrar, evennrfix,

while each odd index $i$ belongs to exactly one of the 6 types

ereccval, nrcval, ereccdrise, nrcdrise, oddrar, oddnrfix.

We can also similarly introduce *variant parity-refined record-and-cycle classification* for D-permutations. We will see (again by using Equation (1.27)) that each even index $i$ belongs to exactly one of the 6 types

ereccpeak', nrcpeak', eareccdfall', nrcdfall', evenrar', evennrfix',

while each odd index $i$ belongs to exactly one of the 6 types

eareccval', nrcval', ereccdrise', nrcdrise', oddrar', oddnrfix'.

Additionally, we define the *pseudo-nestings* of a fixed point [6, eq. (2.51)] by

$$ \text{psnest}(i, \sigma) \stackrel{\text{def}}{=} \#\{j < i : \sigma(j) > i\} = \#\{j > i : \sigma(j) < i\}. \qquad (1.10) $$

This quantity was called level of $i$ and was denoted as $\text{lev}(i, \sigma)$ in [34, eq. (2.20)]. In this paper, we prefer to use psnest.
Also, notice that each non-singleton cycle consists of exactly one minimum element, which must be a cycle valley, and one maximum element, which must be cycle peak. With this observation, the following four statistics were introduced in [6, Section 4.1.3].

* cycle valley minimum (minval): cycle valley that is the minimum in its cycle;

* cycle peak maximum (maxpeak): cycle peak that is the maximum in its cycle;

* cycle valley non-minimum (nminval): cycle valley that is not the minimum in its cycle;

* cycle peak non-maximum (nmaxpeak): cycle peak that is not the maximum in its cycle.

Finally, whenever we use the name of a statistic but with its first letter in capital, we will refer to the set of elements that belong to that statistic (in case that makes sense). For example, we use Cval to denote the set of all cycle valleys, or Evenfix to denote the set of even fixed points.

We now state the cycle and record classifications for our two running examples which will be of use throughout this introduction and the rest of this paper.

### 1.3.1 Running example 1

We consider our first running example in its cycle notation, $\sigma = (1, 9, 10) (2, 3, 7, 5, 6, 11) (4) (8) \in \mathfrak{S}_{11}$. The cycle classification of $\sigma$ partitions the index set $[11] \stackrel{\text{def}}{=} \{1, \dots, 11\}$ as follows:

$$ \text{Cpeak}(\sigma) = \{7, 10, 11\} \qquad \text{Cval}(\sigma) = \{1, 2, 5\} \qquad (1.11a) $$

$$ \text{Cdrise}(\sigma) = \{3, 6, 9\} \qquad \text{Cdfall}(\sigma) = \emptyset \qquad (1.11b) $$

$$ \text{Fix}(\sigma) = \{4, 8\} \qquad (1.11c) $$

Thus, the statistics cpeak, cval, cdrise, cdfall and fix are simply the cardinalities of these sets, respectively.

For the record classification, we write $\sigma$ as a word, i.e., $\sigma = 9 3 7 4 6 11 5 8 10 1 2$. The record and antirecord positions are therefore $\text{Rec}(\sigma) = \{1, 6\}$ and $\text{Arec}(\sigma) = \{10, 11\}$. (Also, notice that the record and antirecord values are $\text{Rec}'(\sigma) = \{9, 11\}$ and $\text{Arec}'(\sigma) = \{1, 2\}$.) The full record classification is

$$ \text{Erec}(\sigma) = \{1, 6\} \qquad \text{Earec}(\sigma) = \{10, 11\} \qquad (1.12a) $$

$$ \text{Rar}(\sigma) = \emptyset \qquad \text{Nrar}(\sigma) = \{2, 3, 4, 5, 7, 8, 9\} \qquad (1.12b) $$
Finally, the record-and-cycle classification gives us

$$ \text{Eareccpeak}(\sigma) = \{10, 11\} \qquad \text{Nrcpeak}(\sigma) = \{7\} \qquad (1.13a) $$

$$ \text{Ereccval}(\sigma) = \{1\} \qquad \text{Nrcval}(\sigma) = \{2, 5\} \qquad (1.13b) $$

$$ \text{Erecdrise}(\sigma) = \{6\} \qquad \text{Nrcdrise}(\sigma) = \{3, 9\} \qquad (1.13c) $$

$$ \text{Earecdfall}(\sigma) = \emptyset \qquad \text{Nrcdfall}(\sigma) = \emptyset \qquad (1.13d) $$

$$ \text{Rar}(\sigma) = \emptyset \qquad \text{Nrfix}(\sigma) = \{4, 8\} \qquad (1.13e) $$

We leave the variant record classification and the variant record-and-cycle classification as an exercise for the reader.

### 1.3.2 Running example 2

We now consider our second running example in its cycle notation, $\sigma = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathfrak{S}_{14}$. The cycle classification of $\sigma$ partitions the index set $[14] \stackrel{\text{def}}{=} \{1, \dots, 14\}$ as follows:

$$ \text{Cpeak}(\sigma) = \{8, 10, 14\} \qquad \text{Cval}(\sigma) = \{1, 3, 13\} \qquad (1.14a) $$

$$ \text{Cdrise}(\sigma) = \{7, 9\} \qquad \text{Cdfall}(\sigma) = \{2, 4, 6\} \qquad (1.14b) $$

$$ \text{Fix}(\sigma) = \{5, 11, 12\} \qquad (1.14c) $$

Thus, the statistics cpeak, cval, cdrise, cdfall and fix are simply the cardinalities of these sets.

For the record classification, we write $\sigma$ as a word, $\sigma = 719254861031121413$. The record and antirecord positions are therefore $\text{Rec}(\sigma) = \{1, 3, 9, 11, 12, 13\}$ and $\text{Arec}(\sigma) = \{2, 4, 10, 11, 12, 14\}$. The full record classification is

$$ \text{Erec}(\sigma) = \{1, 3, 9, 13\} \qquad \text{Earec}(\sigma) = \{2, 4, 10, 14\} \qquad (1.15a) $$

$$ \text{Rar}(\sigma) = \{11, 12\} \qquad \text{Nrar}(\sigma) = \{5, 6, 7, 8\} \qquad (1.15b) $$

Finally, the record-and-cycle classification gives us

$$ \text{Eareccpeak}(\sigma) = \{10, 14\} \qquad \text{Nrcpeak}(\sigma) = \{8\} \qquad (1.16a) $$

$$ \text{Ereccval}(\sigma) = \{1, 3, 13\} \qquad \text{Nrcval}(\sigma) = \emptyset \qquad (1.16b) $$

$$ \text{Erecdrise}(\sigma) = \{9\} \qquad \text{Nrcdrise}(\sigma) = \{7\} \qquad (1.16c) $$

$$ \text{Earecdfall}(\sigma) = \{2, 4\} \qquad \text{Nrcdfall}(\sigma) = \{6\} \qquad (1.16d) $$

$$ \text{Rar}(\sigma) = \{11, 12\} \qquad \text{Nrfix}(\sigma) = \{5\} \qquad (1.16e) $$

We leave the variant record classification and the variant record-and-cycle classification as an exercise for the reader.
## 1.4 Permutations: Statement of conjecture

The polynomial $\hat{Q}_n$ was defined in [34, Equation (2.29)]

$$ \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}, \lambda) = \sum_{\sigma \in \mathfrak{S}_n} x_1^{\text{eareccpeak}(\sigma)} x_2^{\text{eareccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \mathbf{w}^{\text{fix}(\sigma)} \lambda^{\text{cyc}(\sigma)} \quad (1.17) $$

where $\mathbf{w}^{\text{fix}(\sigma)}$ as defined in [34, Equation (2.22)] is

$$ \mathbf{w}^{\text{fix}(\sigma)} = \prod_{i \in \text{Fix}} w_{\text{psnest}(i, \sigma)}. \quad (1.18) $$

Sokal and Zeng stated the following conjecture in their paper:

**Conjecture 1.1** ([34, Conjecture 2.3]). The ordinary generating function of the polynomials $\hat{Q}_n$ specialised to $v_1 = y_1$ has the J-type continued fraction

$$ \sum_{n=0}^{\infty} \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, \mathbf{w}, \lambda) t^n = \frac{1}{1 - \lambda w_0 t - \frac{\lambda x_1 y_1 t^2}{1 - (x_2 + y_2 + \lambda w_1) t - \frac{(\lambda+1)(x_1+u_1)y_1 t^2}{1 - (x_2+y_2+u_2+v_2+\lambda w_2)t - \frac{(\lambda+2)(x_1+2u_1)y_1 t^2}{1-\dots}}}} \quad (1.19) $$

with coefficients

$$ \gamma_0 = \lambda w_0 \quad (1.20a) $$

$$ \gamma_n = [x_2+(n-1)u_2] + [y_2+(n-1)v_2] + \lambda w_n \quad \text{for } n \ge 1 \quad (1.20b) $$

$$ \beta_n = (\lambda + n - 1)[x_1 + (n-1)u_1]y_1 \quad (1.20c) $$

Sokal and Zeng [34, Theorem 2.4] proved this continued fraction subject to the further specialisation $v_2 = y_2$ using the Biane bijection. Here we will prove the full conjecture by using the Foata-Zeilberger bijection, suitably reinterpreted.

In Section 3, we will see that this conjecture is a special case of a more general J-fraction involving five families of infinitely many indeterminates and one additional variable. We will prove these results in Section 6.
## 1.5 Genocchi, median Genocchi numbers, and D-permutations

We will follow the terminology in [6].

The Genocchi numbers [26, A110501]

$$ (g_n)_{n \ge 0} = 1, 1, 3, 17, 155, 2073, 38227, 929569, 28820619, 1109652905, \dots \quad (1.21) $$

are odd positive integers [25, 1, 19] [16, pp. 217–218] defined by the exponential generating function

$$ t \tan(t/2) = \sum_{n=0}^{\infty} g_n \frac{t^{2n+2}}{(2n+2)!} \quad (1.22) $$

The median Genocchi numbers (or Genocchi medians for short) [26, A005439]

$$ (h_n)_{n \ge 0} = 1, 1, 2, 8, 56, 608, 9440, 198272, 5410688, 186043904, \dots \quad (1.23) $$

are defined by [20, p. 63]

$$ h_n = \sum_{i=0}^{n-1} (-1)^i \binom{n}{2i+1} g_{n-1-i} \quad (1.24) $$

See [6, Sections 2.5, 2.6] and references therein for continued fractions associated to the Genocchi and median Genocchi numbers.

The median Genocchi numbers enumerate a class of permutations called D-permutations (short for Dumont-like permutations), they were introduced by Lazar and Wachs in [24, 23]. A permutation of $[2n]$ is called a D-permutation in case $2k-1 \le \sigma(2k-1)$ and $2k \ge \sigma(2k)$ for all $k$, i.e., it contains no even excedances and no odd anti-excedances. Let us say also that a permutation is an *e-semiderangement* (resp. *o-semiderangement*) in case it contains no even (resp. odd) fixed points; it is a *derangement* in case it contains no fixed points at all. A D-permutation that is also an *e-semiderangement* (resp. *o-semiderangement*, *derangement*) will be called a *D-e-semiderangement* (resp. *D-o-semiderangement*, *D-derangement*). A D-permutation that contains exactly one cycle is called a *D-cycle*. Notice that a D-cycle is also a D-derangement. Let $\mathfrak{D}_{2n}$ (resp. $\mathfrak{D}_{2n}^e$, $\mathfrak{D}_{2n}^o$, $\mathfrak{D}_{2n}^{eo}$, $\mathfrak{D}_{2n}^{ec}$) denote the set of all D-permutations (resp. D-e-semiderangements, D-o-semiderangements, D-derangements, D-cycles) of $[2n]$. For instance,

$$ \mathfrak{D}_2 = \{12, 21^{\text{eo}}\} \quad (1.25a) $$

$$ \mathfrak{D}_4 = \{1234, 1243, 2134, 2143^{\text{eo}}, 3142^{\text{eo}}, 3241^{\text{o}}, 4132^{\text{e}}, 4231\} \quad (1.25b) $$

$$ \mathfrak{D}\mathfrak{C}_2 = \{21\} \quad (1.25c) $$

$$ \mathfrak{D}\mathfrak{C}_4 = \{3142\} \quad (1.25d) $$
where e denotes e-semiderangements that are not derangements, o denotes o-semiderangements that are not derangements, and eo denotes derangements. Additionally, our second running example (1.5) is also an example of a D-permutation where $n = 7$.

It is known [7, 8, 24, 23, 6] that

$$ |\mathfrak{D}_{2n}| = h_{n+1} \qquad (1.26a) $$

$$ |\mathfrak{D}_{2n}^{e}| = |\mathfrak{D}_{2n}^{o}| = g_n \qquad (1.26b) $$

$$ |\mathfrak{D}_{2n}^{eo}| = h_n \qquad (1.26c) $$

$$ |\mathfrak{D}_{2n}^{\mathfrak{C}}| = g_{n-1} \qquad (1.26d) $$

For a D-permutation $\sigma$, the cycle classification of a non-fixed-point index $i$ is equivalent to recording the parities of $\sigma^{-1}(i)$ and $i$ [6, eq. (2.47)]:

$$ \bullet \textit{ cycle peak: } \sigma^{-1}(i) < i > \sigma(i) \implies \sigma^{-1}(i) \text{ odd, } i \text{ even} $$
$$ \bullet \textit{ cycle valley: } \sigma^{-1}(i) > i < \sigma(i) \implies \sigma^{-1}(i) \text{ even, } i \text{ odd} \qquad (1.27) $$

$$ \bullet \textit{ cycle double rise: } \sigma^{-1}(i) < i < \sigma(i) \implies \sigma^{-1}(i) \text{ odd, } i \text{ odd} $$
$$ \bullet \textit{ cycle double fall: } \sigma^{-1}(i) > i > \sigma(i) \implies \sigma^{-1}(i) \text{ even, } i \text{ even} $$

For a fixed point $i$, we will need to explicitly record the parity of $i$. Thus, using Equation (1.27), it is clear that each even index $i$ belongs to exactly one of the following three types: cpeak, cdfall, evenfix; and each odd index $i$ belongs to exactly one of the following three types: cval, cdrise, oddfix. Combining this with the record-classification we get the *parity-refined record-and-cycle classification* for D-permutations: we see that each even index $i$ belongs to exactly one of the 6 types

eareccpeak, nrcpeak, eareccdfall, nrcdfall, evenrar, evennrfix,

while each odd index $i$ belongs to exactly one of the 6 types

ereccval, nrcval, ereccdrise, nrcdrise, oddrar, oddnrfix.

as was claimed in Section 1.3. Similarly, we also get the *variant parity-refined record-and-cycle classification* for D-permutations: we see that each even index $i$ belongs to exactly one of the 6 types

ereccpeak', nrcpeak', eareccdfall', nrcdfall', evenrar', evennrfix',

while each odd index $i$ belongs to exactly one of the 6 types

eareccval', nrcval', ereccdrise', nrcdrise', oddrar', oddnrfix'.
## 1.6 D-Permutations: Statements of conjectures

In [30], Randrianarivony and Zeng introduced two sequences of polynomials for D-o-semiderangements [30, eq. (3.3)]

$$R_n(x, y, \bar{x}, \bar{y}) = \sum_{\sigma \in \mathfrak{D}_{2n}^c} x^{\text{lema}(\sigma)} y^{\text{romi}(\sigma)} \bar{x}^{\text{fix}(\sigma)} \bar{y}^{\text{remi}(\sigma)} \quad (1.28)$$

and [30, p. 9]

$$G_n(x, y, \bar{x}, \bar{y}) = \sum_{\sigma \in \mathfrak{D}_{2n}^c} x^{\text{comi}(\sigma)} y^{\text{lema}(\sigma)} \bar{x}^{\text{cemi}(\sigma)} \bar{y}^{\text{remi}(\sigma)} \quad (1.29)$$

where the statistics lema, romi, remi, comi, cemi are defined as follows:

* lema – left-to-right maxima whose value is even,

* romi – right-to-left minima whose value is odd,

* remi – right-to-left minima whose value is even,

* comi – odd cycle minima,

* cemi – even cycle minima;

for a permutation $\sigma$, lema($\sigma$) denotes the number of left-to-right maxima (i.e. record) whose value $\sigma(i)$ is even, etc. See [30, p. 2] for a full description of these statistics.

In their paper, Randrianarivony and Zeng stated the following conjecture which we shall prove:

**Conjecture 1.2** ([30, Conjecture 12]). For $n \ge 1$ we have $R_n(x, y, \bar{x}, \bar{y}) = G_n(x, y, \bar{x}, \bar{y})$.

Using [30, Proposition 10], Conjecture 1.2 can be equivalently stated as

**Conjecture 1.2'.** The ordinary generating function of the polynomials $G_n(x, y, \bar{x}, \bar{y})$ defined in (1.28) has the S-type continued fraction

$$1 + \sum_{n=1}^{\infty} G_n(x, y, \bar{x}, \bar{y}) t^n = \frac{1}{1 - \frac{xyt}{1 - \frac{1(\bar{x} + \bar{y})t}{1 - \frac{(x+1)(y+1)t}{1 - \frac{2(\bar{x} + \bar{y}+1)t}{1 - \frac{(x+2)(y+2)t}{1 - \frac{3(\bar{x} + \bar{y}+2)t}{\dots}}}}}}} \quad (1.30)$$
It is worthwhile to translate the statistics of Randrianarivony and Zeng to the statistics we introduced in Section 1.3. This was already done for the statistics involved in the polynomials $R_n(x, y, \bar{x}, \bar{y})$ in [6, Remark p. 36]; the following statistics are identical for D-o-semiderangements:

* lema = ereccpeak

* remi = ereccdfall

* romi = ereccval

* fix = evennrfix

It remains to translate the statistics cemi and comi.

Notice that the smallest element $i$ of a cycle with at least two elements must be a cycle valley, and hence must be odd. As D-o-semiderangements do not have any odd fixed points, the cycle minima for fixed points are necessarily even. On the other hand, the smallest element $i$ of a cycle with at least two elements must be a cycle valley, and hence must be odd. Thus, $i$ is an even cycle minima if and only if it is an even fixed point, and $i$ is an odd cycle minima if and only if it is the minimum valley of cycle with at least two elements. Thus, we have shown that

* cemi = evennrfix

* comi = minval

This shows that

$$G_n(x, y, \bar{x}, \bar{y}) = \sum_{\sigma \in \mathcal{D}_{2n}^0} x^{\minval(\sigma)} y^{\text{ereccpeak}'(\sigma)} \bar{x}^{\text{evennrfix}(\sigma)} \bar{y}^{\text{ereccdfall}'(\sigma)}. \quad (1.31)$$

We will also look at the following sequence of polynomials introduced by Deb and Sokal for all D-permutations [6, Equation (4.2)]:

$$\begin{aligned} \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, w_e, w_o, z_e, z_o, \lambda) = & \\ & \sum_{\sigma \in \mathcal{D}_{2n}^0} x_1^{\text{ereccpeak}(\sigma)} x_2^{\text{ereccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times \\ & u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \times \\ & w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)} \lambda^{\text{cyc}(\sigma)}. \end{aligned} \quad (1.32)$$

We will prove the following conjectured Thron-type continued fraction involving the polynomials (1.32):
**Conjecture 1.3** ([6, Conjecture 4.1]). The ordinary generating function of the polynomials (1.32) specialised to $v_1 = y_1$ has the T-type continued fraction

$$ \sum_{n=0}^{\infty} \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, \lambda) t^n = \frac{1}{1 - \lambda^2 z_e z_o t - \frac{\lambda x_1 y_1 t}{1 - \frac{(x_2+\lambda w_e)(y_2+\lambda w_o)t}{1 - \frac{(\lambda+1)(x_1+u_1)y_1 t}{1 - \frac{(x_2+u_2+\lambda w_e)(y_2+v_2+\lambda w_o)t}{1 - \frac{(\lambda+2)(x_1+2u_1)y_1 t}{1 - \frac{(x_2+2u_2+\lambda w_e)(y_2+2v_2+\lambda w_o)t}{1-\dots}}}}}}} \quad (1.33) $$

with coefficients

$$ \alpha_{2k-1} = (\lambda + k - 1) [x_1 + (k-1)u_1] y_1 \quad (1.34a) $$

$$ \alpha_{2k} = [x_2 + (k-1)u_2 + \lambda w_e] [y_2 + (k-1)v_2 + \lambda w_o] \quad (1.34b) $$

$$ \delta_1 = \lambda^2 z_e z_o \quad (1.34c) $$

$$ \delta_n = 0 \quad \text{for } n \ge 2 \quad (1.34d) $$

If this continued fraction is further specialised to $v_2 = y_2$, the resulting continued fraction is the same as the second T-fraction for D-permutations of Deb and Sokal [6, Theorem 4.2] under the specialisation $\hat{v}_2 = \hat{y}_2$ and then identifying $\hat{y}_2$ with $y_2$. Deb and Sokal's second T-fraction was proved using a Biane-like bijection. Here we will prove the full conjecture using a Foata-Zeilberger-like bijection, suitably reinterpreted.

In Section 4, we will see that both of these conjectures are special cases of general T-fractions involving six families of infinitely many indeterminates and one additional variable. We will prove these results in Section 7.

## 1.7 Overview of proof for results on permutations

We now summarise our proof for permutations (described in Section 6). Our results for D-permutations are also obtained by using very similar ideas (described in Section 7). We first provide an overview of the Foata-Zeilberger bijection, and then briefly mention how we reinterpret it to obtain the count of cycles in a permutation.
Let $\sigma \in \mathfrak{S}_n$ be a permutation on $n$ letters. This permutation $\sigma$ partitions the set $[n]$ into excedance indices ($F = \{i \in [n] : \sigma(i) > i\}$), anti-excedance indices ($G = \{i \in [n] : \sigma(i) < i\}$), and fixed points ($H$). Similarly, $\sigma$ also partitions $[n]$ into excedance values ($F' = \{i \in [n] : i > \sigma^{-1}(i)\}$), anti-excedance values ($G' = \{i \in [n] : i < \sigma^{-1}(i)\}$), and fixed points. Clearly, $\sigma \upharpoonright F: F \to F'$, $\sigma \upharpoonright G: G \to G'$, and $\sigma \upharpoonright H: H \to H$ are bijections, and the permutation $\sigma$ can be obtained from the following data:

* Two partitions of the set $[n] = F \cup G \cup H = F' \cup G' \cup H$.

* The two subwords of $\sigma: \sigma(x_1)\sigma(x_2)\dots\sigma(x_m)$ and $\sigma(y_1)\sigma(y_2)\dots\sigma(y_l)$, where $G = \{x_1 < x_2 < \dots < x_m\}$ and $F = \{y_1 < y_2 < \dots < y_l\}$.

In their construction, Foata and Zeilberger [15] use these data to describe a bijection from $\mathfrak{S}_n$ to a set of labelled Motzkin paths of length $n$ (these will be completely defined in Section 5). One then uses Flajolet's theorem [12] to obtain continued fractions from this bijection while keeping track of various simultaneous permutation statistics.

The Foata-Zeilberger bijection consists of the following steps (following [34]):

* Step 1: A 3-coloured Motzkin path $\bar{\omega}$ is constructed from $\sigma$ (each level step is one of three colours). The path $\bar{\omega}$ is fully determined by the sets $F, F', G, G', H$.

* Step 2: The labels $\xi$ associated to $\bar{\omega}$ are constructed from $\sigma$. It turns out that the labels depend on the maps $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ and the set $H$, separately.

* Step 3: This step describes the construction of the inverse map $(\bar{\omega}, \xi) \mapsto \sigma$. This step is broken down as follows:

- Step 3(a): The sets $F, F', G, G', H$ are read off from the 3-coloured Motzkin path $\bar{\omega}$.

- Step 3(b): This description is the crucial part of the construction (at least for our purposes). We use *inversion tables* to construct the words $\sigma(x_1)\sigma(x_2)\dots\sigma(x_m)$ and $\sigma(y_1)\sigma(y_2)\dots\sigma(y_l)$; the former is constructed using a “right-to-left” inversion table and the latter is constructed using a “left-to-right” inversion table.

It is, a priori, unclear how one might be able to track the number of cycles of $\sigma$ in this construction. We resolve this issue by reinterpreting Step 3(b). We describe a “history” of this construction using Laguerre digraphs.

Recall that a Laguerre digraph of size $n$ is a directed graph where each vertex has a distinct label from the label set $[n]$ and has indegree 0 or 1 and outdegree 0 or 1. It follows that the connected components in a Laguerre digraph are either directed paths or directed cycles. Clearly, any subgraph of a Laguerre digraph is also a Laguerre digraph. A permutation $\sigma$ in cycle notation is equivalent to a Laguerre digraph $L$ with no paths ([35,
pp. 22-23]). The directed edges of $L$ are precisely $u \to \sigma(u)$. We will interpret Step 3(b) of the Foata-Zeilberger construction as building up a permutation as a sequence of Laguerre digraphs, starting from the empty digraph in which all vertices are isolated (i.e., have no adjacent edges), and ending with the digraph of the permutation $\sigma$ in which there are no paths.

For a subset $S \subseteq [n]$, we let $L|_S$ denote the subgraph of $L$, containing the same set of vertices $[n]$, but only the edges $u \to \sigma(u)$, with $u \in S$ (we are allowed to have $\sigma(u) \notin S$). Let $u_1, \dots, u_n$ be a rewriting of $[n]$. We consider the “history” $L|_{\emptyset} \subset L|_{\{u_1\}} \subset L|_{\{u_1, u_2\}} \subset \dots \subset L|_{\{u_1, \dots, u_n\}} = L$ as a process of building up the permutation $\sigma$ by successively considering the status of vertices $u_1, u_2, \dots, u_n$. At step $u$, we construct the edge $u \to \sigma(u)$. Thus, at each step we insert a new edge into the digraph, and at the end of this process, the resulting digraph obtained is the digraph of $\sigma$.

The crucial part of our construction is that we use a very special order $u_1, \dots, u_n$: we first go through $H$ in increasing order (we call this stage (a)), we then go through $G$ in increasing order (stage (b)), finally we go through $F$ but in decreasing order (stage (c)). This total order is suggested by the inversion tables. On building up the permutation $\sigma$ using this history, we will see that the cycles can only be obtained during stage (c) and we can now count the number of cycles.

Our total order on $[n]$ only depends on the sets $F, G, H$, and hence, only on the 3-coloured Motzkin path $\overline{\omega}$ and not on the full description of the labels $\xi$. This is crucial for our proof to work.

## 1.8 Outline of paper

The plan of this paper is as follows: In Section 2 we introduce some more permutation statistics as they play a central role in our results. We then state our results for permutations in Section 3; this will include the continued fraction [34, Conjecture 2.3] along with its generalisations. Next, we state our results for D-permutations in Section 4; this will include the continued fractions [30, Conjecture 12] and [6, Conjecture 4.1]. In Section 5 we recall how continued fractions can be proven by bijection to labelled Dyck, Motzkin or Schröder paths. In Section 6 we prove our continued fractions for permutations by reinterpreting Sokal and Zeng’s variant of the Foata-Zeilberger bijection [34, Section 6.1] using Laguerre digraphs. In Section 7 we prove our continued fractions for D-permutations by reinterpreting two bijections of Deb and Sokal [6, Sections 6.1-6.3 and 6.5] using Laguerre digraphs. We conclude (Section 8) with some brief remarks on our work.
<figure><img src="image_3.png" /><figcaption>Figure 1: Pictorial representation of the permutation $\sigma = 937461158102 = (1,9,10)(2,3,7,5,6,11)(4)(8) \in \mathfrak{S}_{11}$.</figcaption></figure>

## 2 Permutation statistics: Crossings and nestings

We now define (following [34, 6]) some permutation statistics that count *crossings* and *nestings*.

First we associate to each permutation $\sigma \in \mathfrak{S}_N$ a pictorial representation by placing vertices 1, 2, ..., $N$ along a horizontal axis and then drawing an arc from $i$ to $\sigma(i)$ above (resp. below) the horizontal axis in case $\sigma(i) > i$ [resp. $\sigma(i) < i$]; if $\sigma(i) = i$ we do not draw any arc. This idea was first introduced by Corteel in [4]. See Figures 1 and 2 for our two running examples.

Each vertex thus has either out-degree = in-degree = 1 (if it is not a fixed point) or out-degree = in-degree = 0 (if it is a fixed point). Of course, the arrows on the arcs are redundant, because the arrow on an arc above (resp. below) the axis always points to the right (resp. left); we therefore omit the arrows for simplicity.

We then say that a quadruplet $i < j < k < l$ forms an

* *upper crossing* (ucross) if $k = \sigma(i)$ and $l = \sigma(j)$;

* *lower crossing* (lcross) if $i = \sigma(k)$ and $j = \sigma(l)$;

* *upper nesting* (unest) if $l = \sigma(i)$ and $k = \sigma(j)$;

* *lower nesting* (lnest) if $i = \sigma(l)$ and $j = \sigma(k)$.

We also consider some “degenerate” cases with $j = k$, by saying that a triplet $i < j < l$ forms an
<figure><img src="image_4.png" /><figcaption>Figure 2: Pictorial representation of the permutation $\sigma = 719254861031121413 = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathfrak{S}_{14}$. This $\sigma$ is a D-permutation.</figcaption></figure>

* upper joining (ujoin) if $j = \sigma(i)$ and $l = \sigma(j)$ [i.e. the index $j$ is a cycle double rise];

* lower joining (ljoin) if $i = \sigma(j)$ and $j = \sigma(l)$ [i.e. the index $j$ is a cycle double fall];

* upper pseudo-nesting (upsnest) if $l = \sigma(i)$ and $j = \sigma(j)$;

* lower pseudo-nesting (lpsnest) if $i = \sigma(l)$ and $j = \sigma(j)$.

These are clearly degenerate cases of crossings and nestings, respectively. Note that upsnest($\sigma$) = lpsnest($\sigma$) for all $\sigma$, since for each fixed point $j$, the number of pairs $(i, l)$ with $i < j < l$ such that $l = \sigma(i)$ has to equal the number of such pairs with $i = \sigma(l)$; we therefore write these two statistics simply as

$$ \text{psnest}(\sigma) \stackrel{\text{def}}{=} \text{upsnest}(\sigma) = \text{lpsnest}(\sigma). \qquad (2.1) $$

And of course ujoin = cdrise and ljoin = cdfall. It is clear that

$$ \text{psnest}(\sigma) = \sum_{i \in \text{Fix}} \text{psnest}(i, \sigma) \qquad (2.2) $$

where psnest was defined in (1.10) and Fix denotes the set of all fixed points.

If $\sigma$ is a D-permutation, then its diagram has a special property: all arrows emanating from odd (resp. even) vertices are upper (resp. lower) arrows. Otherwise put, the leftmost (resp. rightmost) vertex of an upper (resp. lower) arc is always odd (resp. even). It follows that in an upper crossing or nesting $i < j < k < l$, the indices $i$ and $j$ must be odd; and in a lower crossing or nesting $i < j < k < l$, the indices $k$ and $l$ must be even. Similar comments apply to upper and lower joinings and pseudo-nestings.

We can further refine the four crossing/nesting categories by examining more closely the status of the inner index ($j$ or $k$) whose outgoing arc belongs to the crossing or nesting:
<table><thead><tr><th></th><th>ucross</th><th>unest</th><th>lcross</th><th>lnest</th></tr></thead><tbody><tr><td>j &isin; Cval</td><td>ucrosscval</td><td>unestcval</td><td></td><td></td></tr><tr><td>j &isin; Cdrise</td><td>ucrosscdrise</td><td>unestcdrise</td><td></td><td></td></tr><tr><td>k &isin; Cpeak</td><td></td><td></td><td>lcrosscpeak</td><td>lnestcpeak</td></tr><tr><td>k &isin; Cdfall</td><td></td><td></td><td>lcrosscdfall</td><td>lnestcdfall</td></tr></tbody></table>

Please note that for the “upper” quantities the distinguished index (i.e. the one for which we examine both $\sigma$ and $\sigma^{-1}$) is in second position (j), while for the “lower” quantities the distinguished index is in third position (k).

In fact, a central role in our work will be played (just as in [34, 6]) by a refinement of these statistics: rather than counting the *total* numbers of quadruplets $i < j < k < l$ that form upper (resp. lower) crossings or nestings, we will count the number of upper (resp. lower) crossings or nestings that use a particular vertex j (resp. k) in second (resp. third) position. More precisely, we define the *index-refined crossing and nesting statistics*

$$ \text{ucross}(j, \sigma) = \#\{i < j < k < l: k = \sigma(i) \text{ and } l = \sigma(j)\} \quad (2.3a) $$

$$ \text{unest}(j, \sigma) = \#\{i < j < k < l: k = \sigma(j) \text{ and } l = \sigma(i)\} \quad (2.3b) $$

$$ \text{lcross}(k, \sigma) = \#\{i < j < k < l: i = \sigma(k) \text{ and } j = \sigma(l)\} \quad (2.3c) $$

$$ \text{lnest}(k, \sigma) = \#\{i < j < k < l: i = \sigma(l) \text{ and } j = \sigma(k)\} \quad (2.3d) $$

Note that $\text{ucross}(j, \sigma)$ and $\text{unest}(j, \sigma)$ can be nonzero only when $j$ is an excedance (that is, a cycle valley or a cycle double rise), while $\text{lcross}(k, \sigma)$ and $\text{lnest}(k, \sigma)$ can be nonzero only when $k$ is an anti-excedance (that is, a cycle peak or a cycle double fall). In a D-permutation, this means that $\text{ucross}(j, \sigma)$ and $\text{unest}(j, \sigma)$ can be nonzero only when $j$ is odd and not a fixed point, while $\text{lcross}(k, \sigma)$ and $\text{lnest}(k, \sigma)$ can be nonzero only when $k$ is even and not a fixed point.

We also use a variant of (2.3) in which the roles of second and third position are interchanged:

$$ \text{ucross}'(k, \sigma) = \#\{i < j < k < l: k = \sigma(i) \text{ and } l = \sigma(j)\} \quad (2.4a) $$

$$ \text{unest}'(k, \sigma) = \#\{i < j < k < l: k = \sigma(j) \text{ and } l = \sigma(i)\} \quad (2.4b) $$

$$ \text{lcross}'(j, \sigma) = \#\{i < j < k < l: i = \sigma(k) \text{ and } j = \sigma(l)\} \quad (2.4c) $$

$$ \text{lnest}'(j, \sigma) = \#\{i < j < k < l: i = \sigma(l) \text{ and } j = \sigma(k)\} \quad (2.4d) $$

We remark that since nestings join the vertices in second and third positions, we have

$$ \text{unest}'(k, \sigma) = \text{unest}(\sigma^{-1}(k), \sigma) \quad (2.5a) $$

$$ \text{lnest}'(j, \sigma) = \text{lnest}(\sigma^{-1}(j), \sigma) \quad (2.5b) $$
Note that $ucross'(k, \sigma)$ and $unest'(k, \sigma)$ can be nonzero only when $\sigma^{-1}(k)$ is an exceedance (that is, when $k$ is a cycle peak or a cycle double rise), while $lcross'(j, \sigma)$ and $lnest'(j, \sigma)$ can be nonzero only when $\sigma^{-1}(j)$ is an anti-exceedance (that is, $j$ is a cycle valley or a cycle double fall). In a D-permutation, this means that $ucross'(k, \sigma)$ and $unest'(k, \sigma)$ can be nonzero only when $\sigma^{-1}(k)$ is odd and not a fixed point, while $lcross'(j, \sigma)$ and $lnest'(j, \sigma)$ can be nonzero only when $\sigma^{-1}(j)$ is even and not a fixed point. We call (2.4) the *variant index-refined crossing and nesting statistics*.

We can also analogously define the statistics $ucrosscpeak'$, $unestcpeak'$, $lcrosscval'$, $lnestcval'$, $lcrosscdfall'$, $lnestcdfall'$, $ucrosscdrise'$, $ucrosscdrise'$. We leave the details to the reader.

# 3 Permutations: Statements of results

In this section, we state our continued fractions for permutations, in three increasingly more general versions. The first and most basic version (Theorem 3.1 is a J-fraction in 8 variables and another family of infinitely many variables that enumerates permutations with respect to the record-and-cycle classification except for the segregation of cycle valleys; it resolves [34, Conjecture 2.3]). The second version (Theorem 3.2) is a $(p, q)$-generalisation of the first one: it is a J-fraction with 16 variables along with one family of infinitely many variables that enumerates permutations with respect to the record-and-cycle classification (introduced in Section 1.3) together with three pairs of $(p, q)$-variables counting the refined categories of crossing and nesting except for cycle valleys, and one variable corresponding to pseudo-nestings of fixed points. Finally, our third version (Theorem 3.3) — is a J-fraction in five infinite families of indeterminates along with one additional variable that keeps track of the number of cycles; this generalises the previous two by employing the index-refined crossing and nesting statistics (2.3). All these results will be proved in Section 6.

## 3.1 J-fraction (Sokal–Zeng conjecture)

Recall the polynomial $\hat{Q}_n$ defined in Equation (1.17)/[34, Equation (2.29)]

$$ \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}, \lambda) = \sum_{\sigma \in \mathcal{S}_n} x_1^{\text{eareccpeak}(\sigma)} x_2^{\text{eareccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \mathbf{w}^{\text{fix}(\sigma)} \lambda^{\text{cyc}(\sigma)} $$

where $\mathbf{w}^{\text{fix}(\sigma)}$ is

$$ \mathbf{w}^{\text{fix}(\sigma)} = \prod_{i \in \text{Fix}} w_{\text{psnest}(i, \sigma)}. $$
Our first main result for permutations is [34, Conjecture 2.3].

**Theorem 3.1** ([34, Conjecture 2.3], J-fraction for permutations). *The ordinary generating function of the polynomials $\hat{Q}_n$ specialised to $v_1 = y_1$ has the J-type continued fraction*

$$ \sum_{n=0}^{\infty} \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, \mathbf{w}, \lambda) t^n = \\ \frac{1}{1 - \lambda w_0 t - \frac{\lambda x_1 y_1 t^2}{1 - (x_2+y_2+\lambda w_1)t - \frac{(\lambda+1)(x_1+u_1)y_1 t^2}{1 - (x_2+y_2+u_2+v_2+\lambda w_2)t - \frac{(\lambda+2)(x_1+2u_1)y_1 t^2}{1-\dots}}}} \quad (3.1) $$

with coefficients

$$ \gamma_0 = \lambda w_0 \quad (3.2a) $$

$$ \gamma_n = [x_2+(n-1)u_2] + [y_2+(n-1)v_2] + \lambda w_n \quad \text{for } n \ge 1 \quad (3.2b) $$

$$ \beta_n = (\lambda + n - 1)[x_1 + (n-1)u_1]y_1 \quad (3.2c) $$

The continued fraction (3.1)/(3.2) requires only one specialisation, namely $v_1 = y_1$. This clearly generalises the second J-fraction for permutations of Sokal and Zeng [34, Theorem 2.4] which also requires the specialisation $v_2 = y_2$.

We will prove Theorem 3.1 in Section 6.

## 3.2 p, q-generalisation

We now state a p, q-generalisation for Theorem 3.1 which also generalises [34, Theorem 2.12]. Let us first recall the polynomial $\hat{Q}_n$ defined in [34, Equation (2.92)]

$$ \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}, p_{+1}, p_{+2}, p_{-1}, p_{-2}, q_{+1}, q_{+2}, q_{-1}, q_{-2}, s, \lambda) = \\ \sum_{\sigma \in \mathfrak{S}_n} x_1^{\text{ereccpeak}(\sigma)} x_2^{\text{ereccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times \\ u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \mathbf{w}^{\text{fix}(\sigma)} \times \\ p_{+1}^{\text{ucrosscval}(\sigma)} p_{+2}^{\text{ucrosscdrise}(\sigma)} p_{-1}^{\text{lcrosscpeak}(\sigma)} p_{-2}^{\text{lcrosscdfall}(\sigma)} \times \\ q_{+1}^{\text{unestcval}(\sigma)} q_{+2}^{\text{unestcdrise}(\sigma)} q_{-1}^{\text{lnestcpeak}(\sigma)} q_{-2}^{\text{lnestcdfall}(\sigma)} s^{\text{psnest}(\sigma)} \lambda^{\text{cyc}(\sigma)}. \quad (3.3) $$
For the p, q-generalisation of their second J-fraction, involving the polynomials $\hat{Q}_n$, Sokal and Zeng needed the specialisations $v_1 = y_1$, $v_2 = y_2$, $q_{+1} = p_{+1}$, and $q_{+2} = p_{+2}$. However, we now state a J-fraction that only requires the specialisations $v_1 = y_1$ and $q_{+1} = p_{+1}$.

**Theorem 3.2** (J-fraction with p, q-generalisation for permutations). *The ordinary generating function of the polynomials $\hat{Q}_n$ specialised to $v_1 = y_1$ and $q_{+1} = p_{+1}$ has the J-type continued fraction*

$$ \sum_{n=0}^{\infty} \hat{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w, p_{+1}, p_{+2}, p_{-1}, p_{-2}, p_{+1}, q_{+2}, q_{-1}, q_{-2}, s, \lambda) t^n = \\ \frac{1}{1 - \lambda w_0 t - \frac{\lambda x_1 y_1 t^2}{1 - (x_2 + y_2 + \lambda s w_1) t - \frac{(\lambda+1)(p_{-1}x_1 + q_{-1}u_1)p_{+1}y_1 t^2}{1 - (p_{-2}x_2 + q_{-2}u_2 + p_{+2}y_2 + q_{+2}v_2 + \lambda s^2 w_2) t - \frac{(\lambda+2)(p_{-1}^2 x_1 + [q_{-1}p_{-1} + q_{-1}^2]u_1)p_{+1}^2 y_1 t^2}{1 - \dots}}} \quad (3.4) $$

with coefficients

$$ \gamma_0 = \lambda w_0 \quad (3.5a) $$

$$ \gamma_n = (p_{-2}^{n-1}x_2 + q_{-2}[n-1]_{p_{-2}, q_{-2}}u_2) + (p_{+2}^{n-1}y_2 + q_{+2}[n-1]_{p_{+2}, q_{+2}}v_2) + \lambda s^n w_n \quad \text{for } n \ge 1 \quad (3.5b) $$

$$ \beta_n = (\lambda + n - 1)(p_{-1}^{n-1}x_1 + q_{-1}[n-1]_{p_{-1}, q_{-1}}u_1)p_{+1}^{n-1}y_1 \quad (3.5c) $$

We will prove this theorem in Section 6, as a special case of a more general result.

## 3.3 Master J-fraction

We can go much farther and obtain a more general J-fraction generalising Theorems 3.1 and 3.2. We obtain a J-fraction in the following five families of infinitely many indeterminates: **a** = (aℓ)ℓ≥0, **b** = (bℓ,ℓ')ℓ,ℓ'≥0, **c** = (cℓ,ℓ')ℓ,ℓ'≥0, **d** = (dℓ,ℓ')ℓ,ℓ'≥0, **e** = (eℓ)ℓ≥0; please note that **a** and **e** have one index while **b**, **c** and **d** have two indices. Using the index-refined crossing and nesting statistics defined in (2.3), we define the polynomial $\hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \lambda)$ by

$$ \hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \lambda) = \sum_{\sigma \in S_n} \lambda^{\mathrm{cyc}(\sigma)} \prod_{i \in \mathrm{Cval}(\sigma)} \mathbf{a}_{\mathrm{ucross}(i, \sigma) + \mathrm{unest}(i, \sigma)} \prod_{i \in \mathrm{Cpeak}(\sigma)} \mathbf{b}_{\mathrm{lcross}(i, \sigma), \mathrm{lnest}(i, \sigma)} \times \\ \prod_{i \in \mathrm{Cdfall}(\sigma)} \mathbf{c}_{\mathrm{lcross}(i, \sigma), \mathrm{lnest}(i, \sigma)} \prod_{i \in \mathrm{Cdrise}(\sigma)} \mathbf{d}_{\mathrm{ucross}(i, \sigma), \mathrm{unest}(i, \sigma)} \prod_{i \in \mathrm{Fix}(\sigma)} \mathbf{e}_{\mathrm{psnest}(i, \sigma)} \quad (3.6) $$
where recall that Cval($\sigma$) = {$i: \sigma^{-1}(i) > i < \sigma(i)$} and likewise for the others.

The polynomials (3.6) have a beautiful J-fraction:

**Theorem 3.3 (Master J-fraction for permutations).** *The ordinary generating function of the polynomials $\hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \lambda)$ has the J-type continued fraction*

$$ \sum_{n=0}^{\infty} \hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \lambda) t^n = \frac{1}{1 - \lambda \mathbf{e}_0 t - \frac{\lambda \mathbf{a}_0 \mathbf{b}_0 t^2}{1 - (\mathbf{c}_{00} + \mathbf{d}_{00} + \lambda \mathbf{e}_1) t - \frac{(\lambda+1) \mathbf{a}_1 (\mathbf{b}_{01} + \mathbf{b}_{10}) t^2}{1 - (\mathbf{c}_{01} + \mathbf{c}_{10} + \mathbf{d}_{01} + \mathbf{d}_{10} + \lambda \mathbf{e}_2) t - \frac{(\lambda+2) \mathbf{a}_2 (\mathbf{b}_{02} + \mathbf{b}_{11} + \mathbf{b}_{20}) t^2}{1 - \dots}}} \quad (3.7) $$

with coefficients

$$ \gamma_0 = \lambda \mathbf{e}_0 \quad (3.8a) $$

$$ \gamma_n = \left( \sum_{\xi=0}^{n-1} \mathbf{c}_{n-1-\xi, \xi} \right) + \left( \sum_{\xi=0}^{n-1} \mathbf{d}_{n-1-\xi, \xi} \right) + \lambda \mathbf{e}_n \quad \text{for } n \ge 1 \quad (3.8b) $$

$$ \beta_n = (\lambda + n - 1) \mathbf{a}_{n-1} \left( \sum_{\xi=0}^{n-1} \mathbf{b}_{n-1-\xi, \xi} \right) \quad (3.8c) $$

(3.8d)

We will prove this theorem in Section 6. It implies Theorems 3.1 and 3.2 by straightforward specialisations.

**Remark 3.1.** 1. We remark that (3.6) is almost the same as the polynomial introduced in [34, eq. (2.77)], except for the extra factor $\lambda^{\text{cyc}(\sigma)}$ and the index of a depends on the sum $\text{ucross}(i, \sigma) + \text{unest}(i, \sigma)$. This is the price we have to pay in order to include the statistic cyc. See [34, p. 13].

2. We also note that (3.6) is almost the same as the polynomial [34, eq. (2.100)] as well, except our treatment of d is nicer as we are able to recover both $\text{ucross}(i, \sigma)$, $\text{unest}(i, \sigma)$, and not just their sum. In fact, this separation is what allows us to prove [34, Conjecture 2.3] by using [34, Lemma 2.10].

3. The continued fraction $(3.7)/(3.8)$ is the same as [34, eq. (2.101),(2.102),(2.103)] except for the indexing of d. ■
# 4 D-permutations: Statements of results

In this section, we state our continued fractions for D-permutations. Analogous to [6, Sections 3.2–3.4, and 3.5] our continued fractions have two variants: the first involve the record classification and the second involve the variant record classification, both have been introduced in Section 1.3. The most basic versions in each variant are a T-fraction (Theorems 4.1 and 4.5) in 12 variables that enumerates D-permutations with respect to the parity-refined record-and-cycle classification and the variant parity-refined record-and-cycle classification respectively; except for the segregation of cycle valleys. Theorem 4.1 resolves [6, Conjecture 4.1]. The second versions (Theorems 4.3 and 4.6) are respective (p, q)-generalisations of the first versions: they are a T-fraction with 21 variables that enumerates D-permutations with respect to the parity-refined record-and-cycle classification and variant parity-refined record-and-cycle classification respectively, together with three pairs of (p, q)-variables counting the refined categories of crossings and nestings except for cycle valleys. Finally, our third versions (Theorems 4.4 and 4.7) — is a T-fraction in six infinite families of indeterminates and one additional variable; this generalises the previous versions by employing the index-refined crossing and nesting statistics (2.3) and the variant index-refined crossing and nesting statistics (2.4). One of the variables (λ) in each version counts the number of cycles.

The first variants will be stated in Section 4.1 and will be proved in Section 7.1. The second variants will be stated in Section 4.2 and will be proved in Section 7.2.

We then rephrase Theorems 4.1 and 4.5 using cycle valley minima in Section 4.3; our approach will be similar to that in [6, Section 4.1.3]. This allows us to resolve [30, Conjecture 12].

## 4.1 Continued fractions using record classification

### 4.1.1 T-fraction (Deb–Sokal conjecture)

Recall the polynomial $\hat{P}_n$ defined in (1.32)/[6, Equation (4.2)]

$$ \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, w_e, w_o, z_e, z_o, \lambda) = \sum_{\sigma \in \mathcal{D}_{2n}} x_1^{\text{eareccpeak}(\sigma)} x_2^{\text{eareccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \times w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)} \lambda^{\text{cyc}(\sigma)}. $$

Our first main result for D-permutations is [6, Conjecture 4.1].
**Theorem 4.1** ([6, Conjecture 4.1]). The ordinary generating function of the polynomials (1.32) specialised to $v_1 = y_1$ has the T-type continued fraction

$$ \sum_{n=0}^{\infty} \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, \lambda) t^n = \frac{1}{1 - \lambda^2 z_e z_o t - \frac{\lambda x_1 y_1 t}{1 - \frac{(x_2+\lambda w_e)(y_2+\lambda w_o)t}{1 - \frac{(\lambda+1)(x_1+u_1)y_1 t}{1 - \frac{(x_2+u_2+\lambda w_e)(y_2+v_2+\lambda w_o)t}{1 - \frac{(\lambda+2)(x_1+2u_1)y_1 t}{1 - \frac{(x_2+2u_2+\lambda w_e)(y_2+2v_2+\lambda w_o)t}{1-\dots}}}}}}} \quad (4.1) $$

with coefficients

$$ \alpha_{2k-1} = (\lambda + k - 1) [x_1 + (k-1)u_1] y_1 \quad (4.2a) $$

$$ \alpha_{2k} = [x_2 + (k-1)u_2 + \lambda w_e] [y_2 + (k-1)v_2 + \lambda w_o] \quad (4.2b) $$

$$ \delta_1 = \lambda^2 z_e z_o \quad (4.2c) $$

$$ \delta_n = 0 \quad \text{for } n \ge 2 \quad (4.2d) $$

We will prove Theorem 4.1 in Section 7.1.

**Remark 4.1.** 1. The continued fraction $(4.1)/(4.2)$ is almost similar to [6, eq. (3.3), (3.4)] except for the extra factor $\lambda$ and the specialisation $v_1 = y_1$. This continued fraction is also the same as [6, eq. (4.7), (4.8)] which proves the equidistribution of statistics for D-permutations in [6, Conjecture 4.1'].

2. The continued fraction of Theorem 4.1 specialised to $x_1 = x_2 = y_1 = y_2 = u_1 = u_2 = v_1 = v_2 = 1$, $w_e = z_e$, $w_o = z_o$, enumerates D-permutations of $[2n]$ with a weight $\lambda$ for each cycle, $z_e$ for each even fixed point and $z_o$ for each odd fixed point. By applying [6, Proposition 2.1], to the resulting T-fraction, we obtain a J-fraction with coefficients $\gamma_n = (\lambda z_e + n)(\lambda z_o + n) + (\lambda + n)(n+1)$ and $\beta_n = n(\lambda + n - 1)(\lambda z_e + n)(\lambda z_o + n)$. This J-fraction was first proved by Pan and Zeng [28, eq. (4.11)] and they used this continued fraction to establish [24, Conjecture 6.5]. ■
We can also enumerate D-cycles by extracting the coefficient of $\lambda^1$ in Theorem 4.1 to prove [6, Conjecture 4.5]. The analogous polynomials $P_n^{\mathfrak{D}\mathfrak{e}}$ defined in [6, eq. (4.17)] are

$$ P_n^{\mathfrak{D}\mathfrak{e}}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2) = \sum_{\sigma \in \mathfrak{D}\mathfrak{e}_{2n}} x_1^{\text{eareccpeak}(\sigma)} x_2^{\text{eareccdfall}(\sigma)} y_1^{\text{ereccval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} v_1^{\text{nrcval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)}. \quad (4.3) $$

**Corollary 4.2** ([6, Conjecture 4.5]). The ordinary generating function of the polynomials (4.3) specialised to $v_1 = y_1$ has the S-type continued fraction

$$ \sum_{n=0}^{\infty} P_{n+1}^{\mathfrak{D}\mathfrak{e}}(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2) t^n = \frac{x_1 y_1}{1 - \frac{x_2 y_2 t}{1 - \frac{(x_1+u_1)y_1 t}{1 - \frac{(x_2+u_2)(y_2+v_2)t}{1 - \frac{(x_1+2u_1)2y_1 t}{1 - \frac{(x_2+2u_2)(y_2+2v_2)t}{1-\dots}}}}}} \quad (4.4) $$

with coefficients

$$ \alpha_{2k-1} = [x_2 + (k-1)u_2] [y_2 + (k-1)v_2] \quad (4.5a) $$

$$ \alpha_{2k} = [x_1 + ku_1] ky_1 \quad (4.5b) $$

### 4.1.2 p, q-generalisation

In this subsection, we shall provide a p, q-generalisation for Theorem 4.1 by including four pairs of (p, q)-variables corresponding to the four refined types of crossings and nestings,
with coefficients

$$ \alpha_{2k-1} = (\lambda + k - 1) p_{+1}^{k-1} y_1 \left( p_{-1}^{k-1} x_1 + q_{-1}[k-1]_{p-1,q-1} u_1 \right) \quad (4.8a) $$

$$ \alpha_{2k} = \left( p_{-2}^{k-1} x_2 + q_{-2}[k-1]_{p-2,q-2} u_2 + \lambda s_e^k w_e \right) \times \left( p_{+2}^{k-1} y_2 + q_{+2}[k-1]_{p+2,q+2} v_2 + \lambda s_o^k w_o \right) \quad (4.8b) $$

$$ \delta_1 = \lambda^2 z_c z_o \quad (4.8c) $$

$$ \delta_n = 0 \quad \text{for } n \ge 2 \quad (4.8d) $$

We will prove this theorem in Section 7.1, as a special case of a more general result.

### 4.1.3 Master T-fraction

In this subsection, we shall provide a master T-fraction generalising Theorems 4.1 and 4.3. Let us introduce a polynomial in six infinite families of indeterminates $a = (a_\ell)_{\ell \ge 0}$, $b = (b_{\ell, \ell'})_{\ell, \ell' \ge 0}$, $c = (c_{\ell, \ell'})_{\ell, \ell' \ge 0}$, $d = (d_{\ell, \ell'})_{\ell, \ell' \ge 0}$, $e = (e_\ell)_{\ell \ge 0}$, $f = (f_\ell)_{\ell \ge 0}$ that will have a nice T-fraction and that will include the polynomials (1.32) and (4.6) as specialisations. Please note that $a, e$ and $f$ have one index while $b, c$ and $d$ have two indices. Using the index-refined crossing and nesting statistics defined in (2.3), we define the polynomial $\hat{Q}_n(a, b, c, d, e, f, \lambda)$ by

$$ \begin{aligned} \hat{Q}_n(a, b, c, d, e, f, \lambda) = & \sum_{\sigma \in \mathfrak{D}_{2n}} \lambda^{\mathrm{cyc}(\sigma)} \prod_{i \in \mathrm{Cval}(\sigma)} a_{\mathrm{ucross}(i, \sigma) + \mathrm{unest}(i, \sigma)} \prod_{i \in \mathrm{Cpeak}(\sigma)} b_{\mathrm{lcross}(i, \sigma), \mathrm{lnest}(i, \sigma)} \times \\ & \prod_{i \in \mathrm{Cdfall}(\sigma)} c_{\mathrm{lcross}(i, \sigma), \mathrm{lnest}(i, \sigma)} \prod_{i \in \mathrm{Cdrise}(\sigma)} d_{\mathrm{ucross}(i, \sigma), \mathrm{unest}(i, \sigma)} \times \\ & \prod_{i \in \mathrm{Evenfix}(\sigma)} e_{\mathrm{psnest}(i, \sigma)} \prod_{i \in \mathrm{Oddfix}(\sigma)} f_{\mathrm{psnest}(i, \sigma)}. \end{aligned} \quad (4.9) $$

where recall that $\mathrm{Cval}(\sigma) = \{i: \sigma^{-1}(i) > i < \sigma(i)\}$ and likewise for the others.

We remark that (4.9) is almost the same as the polynomial introduced in [6, eq. (3.30)], except for the extra factor $\lambda^{\mathrm{cyc}(\sigma)}$ and the index of $a$ depends on the sum $\mathrm{ucross}(i, \sigma) + \mathrm{unest}(i, \sigma)$. That is the price we have to pay in order to include the statistic cyc. See [6, Appendix A]. We also note that (4.9) is almost the same as the polynomial (3.6) as well, but restricted to D-permutations and refined to record the parity of fixed points.

The polynomials (4.9) have a beautiful T-fraction:
**Theorem 4.4 (Master T-fraction for D-permutations).** *The ordinary generating function of the polynomials $\hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda)$ has the T-type continued fraction*

$$ \sum_{n=0}^{\infty} \hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda) t^n = \frac{1}{1 - \lambda^2 \mathbf{e}_0 \mathbf{f}_0 t - \frac{\lambda \mathbf{a}_0 \mathbf{b}_0 t}{1 - \frac{(\mathbf{c}_0 + \lambda \mathbf{e}_1)(\mathbf{d}_0 + \lambda \mathbf{f}_1)t}{1 - \frac{(\lambda+1)\mathbf{a}_1(\mathbf{b}_0 + \mathbf{b}_{10})t}{1 - \frac{(\mathbf{c}_0 + \mathbf{c}_{10} + \lambda \mathbf{e}_2)(\mathbf{d}_0 + \mathbf{d}_{10} + \lambda \mathbf{f}_2)t}{1 - \dots}}}}} \quad (4.10) $$

with coefficients

$$ \alpha_{2k-1} = (\lambda + k - 1)\mathbf{a}_{k-1} \left( \sum_{\xi=0}^{k-1} \mathbf{b}_{k-1-\xi, \xi} \right) \quad (4.11a) $$

$$ \alpha_{2k} = \left( \lambda \mathbf{e}_k + \sum_{\xi=0}^{k-1} \mathbf{c}_{k-1-\xi, \xi} \right) \left( \lambda \mathbf{f}_k + \sum_{\xi=0}^{k-1} \mathbf{d}_{k-1-\xi, \xi} \right) \quad (4.11b) $$

$$ \delta_1 = \lambda^2 \mathbf{e}_0 \mathbf{f}_0 \quad (4.11c) $$

$$ \delta_n = 0 \quad \text{for } n \ge 2 \quad (4.11d) $$

We will prove this theorem in Section 7.1. It implies Theorems 4.1 and 4.3 by straightforward specialisations.

**Remark 4.2.** We remark that (4.9) is almost the same as the polynomial [6, eq. (4.34)] as well, except our treatment of d is different: we are able to recover the statistics ucross(i, σ), unest(i, σ), and not the statistics ucross'(i, σ), unest'(i, σ). In fact, this separation is what allows us to prove [6, Conjecture 4.1]. ■

## 4.2 Continued fractions using variant record classification

Similar to [6, Section 3.5], our T-fractions for D-permutations (Theorems 4.1, 4.3, 4.4) also have variant forms in which we use the variant index-refined crossing and nesting statistics (2.4). We shall state these variants in this subsection.
### 4.2.1 T-fraction

Let $\hat{P}'_n$ be the polynomials defined as follows:

$$ \hat{P}'_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, w_e, w_o, z_e, z_o, \lambda) = \sum_{\sigma \in \mathfrak{D}_{2n}} x_1^{\text{ereccpeak}'(\sigma)} x_2^{\text{ereccdfall}'(\sigma)} y_1^{\text{ereccval}'(\sigma)} y_2^{\text{ereccdrise}'(\sigma)} \times u_1^{\text{nrcpeak}'(\sigma)} u_2^{\text{nrcdfall}'(\sigma)} v_1^{\text{nrcval}'(\sigma)} v_2^{\text{nrcdrise}'(\sigma)} \times w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)} \lambda^{\text{cyc}(\sigma)}. \quad (4.12) $$

We have the following variant of Theorem 4.1.

**Theorem 4.5.** The ordinary generating function of the polynomials $\hat{P}'_n$ defined in (4.12) specialised to $v_1 = y_1$ has the same T-type continued fraction (4.1)/(4.2) as the polynomials $\hat{P}_n$ defined in (1.32). Therefore,

$$ \hat{P}'_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, \lambda) = \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, \lambda). \quad (4.13) $$

We will prove Theorem 4.5 in Section 7.2.

### 4.2.2 p, q-generalisation

We shall now provide a p, q-generalisation for Theorem 4.5 by including four pairs of (p, q)-variables corresponding to the four variants of the refined types of crossings and nestings, as well as two variables corresponding to pseudo-nestings for fixed points:

$$ \begin{aligned} \hat{P}'_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, w_e, w_o, z_e, z_o, p_{-1}, p_{-2}, p_{+1}, p_{+2}, q_{-1}, q_{-2}, q_{+1}, q_{+2}, s_e, s_o, \lambda) = & \\ & \sum_{\sigma \in \mathfrak{D}_{2n}} x_1^{\text{ereccpeak}'(\sigma)} x_2^{\text{ereccdfall}'(\sigma)} y_1^{\text{ereccval}'(\sigma)} y_2^{\text{ereccdrise}'(\sigma)} \times \\ & u_1^{\text{nrcpeak}'(\sigma)} u_2^{\text{nrcdfall}'(\sigma)} v_1^{\text{nrcval}'(\sigma)} v_2^{\text{nrcdrise}'(\sigma)} \times \\ & w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)} \times \\ & p_{-1}^{\text{ucrosspeak}'(\sigma)} p_{-2}^{\text{lcrossdfall}'(\sigma)} p_{+1}^{\text{lcrosscval}'(\sigma)} p_{+2}^{\text{ucrosscdrise}'(\sigma)} \times \\ & q_{-1}^{\text{unestcpeak}'(\sigma)} q_{-2}^{\text{lnestdfall}'(\sigma)} q_{+1}^{\text{lnestcval}'(\sigma)} q_{+2}^{\text{unestcdrise}'(\sigma)} \times \\ & s_e^{\text{epsnest}(\sigma)} s_o^{\text{opsnest}(\sigma)} \lambda^{\text{cyc}(\sigma)}. \end{aligned} \quad (4.14) $$
This is the same as [6, Equation (3.35)] except for the extra factor of $\lambda^{cyc}(\sigma)$. We now state a J-fraction under the specialisations $v_1 = y_1$ and $q_{+1} = p_{+1}$:

**Theorem 4.6.** The ordinary generating function of the polynomials $\hat{P}'_n$ defined in (4.14) specialised to $v_1 = y_1$ and $q_{+1} = p_{+1}$ has the same T-type continued fraction (4.7)/(4.8) as the polynomials $\hat{P}_n$ defined in (4.6). Therefore

$$ \hat{P}'_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, p_{-1}, p_{-2}, p_{+1}, p_{+2}, q_{-1}, q_{-2}, p_{+1}, q_{+2}, s_e, s_o, \lambda) \\ = \hat{P}_n(x_1, x_2, y_1, y_2, u_1, u_2, y_1, v_2, w_e, w_o, z_e, z_o, p_{-1}, p_{-2}, p_{+1}, p_{+2}, q_{-1}, q_{-2}, p_{+1}, q_{+2}, s_e, s_o, \lambda). \quad (4.15) $$

We will prove this theorem in Section 7.2, as a special case of a more general result.

### 4.2.3 Master T-fraction

We introduce a polynomial in six infinite families of indeterminates $a, b, c, d, e, f$ as before but by using the variant index-refined crossing and nesting statistics (2.4):

$$ \hat{Q}'_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda) = \sum_{\sigma \in \mathfrak{D}_{2n}} \lambda^{\mathrm{cyc}(\sigma)} \prod_{i \in \mathrm{Cval}(\sigma)} \mathbf{a}_{\mathrm{lcross}'(i, \sigma) + \mathrm{lnest}'(i, \sigma)} \prod_{i \in \mathrm{Cpeak}(\sigma)} \mathbf{b}_{\mathrm{ucross}'(i, \sigma), \mathrm{unest}'(i, \sigma)} \times \\ \prod_{i \in \mathrm{Cdfall}(\sigma)} \mathbf{c}_{\mathrm{lcross}'(i, \sigma), \mathrm{lnest}'(i, \sigma)} \prod_{i \in \mathrm{Cdrise}(\sigma)} \mathbf{d}_{\mathrm{ucross}'(i, \sigma), \mathrm{unest}'(i, \sigma)} \times \\ \prod_{i \in \mathrm{Evenfix}(\sigma)} \mathbf{e}_{\mathrm{psnest}(i, \sigma)} \prod_{i \in \mathrm{Oddfix}(\sigma)} \mathbf{f}_{\mathrm{psnest}(i, \sigma)}. \quad (4.16) $$

We remark that (4.16) is almost the same as the polynomial introduced in [6, eq. (3.33)], except for the extra factor $\lambda^{cyc}(\sigma)$ and the index of $\mathbf{a}$ depends on the sum $\mathrm{lcross}'(i, \sigma) + \mathrm{lnest}'(i, \sigma)$.

We have the following variant of Theorem 4.4

**Theorem 4.7.** The ordinary generating function of the polynomials $\hat{Q}'_n$ defined in (4.16) has the same T-type continued fraction (4.10)/(4.11) as the polynomials $\hat{Q}_n$ defined in (4.9). Therefore

$$ \hat{Q}'_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda) = \hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda). \quad (4.17) $$

Theorem 4.7 will be proved in Section 7.2. It implies Theorems 4.5 and 4.6 by straightforward specialisations.

**Open Problem 4.8.** Is there a simple bijective proof of Theorem 4.7?
## 4.3 Reformulation of results using cycle valley minima and the Randrianarivony-Zeng conjecture

We will now rephrase our results in this section using some new statistics which will also help us to prove Conjecture 1.2' as a corollary. Our approach here will be the same as that of [6, Section 4.1.3].

We notice that the number of cycles in a permutation can be recovered if we know the number of (even and odd) fixed points and the number of cycle valley minima (or the number of cycle peak maxima). We will rephrase our results by distributing the weight $\lambda$, that we had been using for the number of cycles, among fixed points and cycle valley minima. In [6], this was done by introducing the polynomial $\tilde{P}_n$ in [6, eq. (4.14)] which we recall here:

$$ \tilde{P}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, w_e, w_o, z_e, z_o) = \sum_{\sigma \in \mathfrak{S}_{2n}} x_1^{\text{eareccpeak}(\sigma)} x_2^{\text{eareccdfall}(\sigma)} \tilde{y}_1^{\text{nminval}(\sigma)} y_2^{\text{ereccdrise}(\sigma)} \times u_1^{\text{nrcpeak}(\sigma)} u_2^{\text{nrcdfall}(\sigma)} \tilde{v}_1^{\text{nminval}(\sigma)} v_2^{\text{nrcdrise}(\sigma)} \times w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)}. \quad (4.18) $$

We can rephrase Theorem 4.1 by replacing the factor $(\lambda + k - 1)y_1$ with $\tilde{y} + (k - 1)\tilde{v}$ and removing the factors of $\lambda$ multiplying $w_e, w_o, z_e, z_o$.

**Theorem 4.2** ([6, Conjecture 4.2']). *The ordinary generating function of the polynomials (4.18) has the T-type continued fraction*

$$ \sum_{n=0}^{\infty} \tilde{P}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, w_e, w_o, z_e, z_o) t^n = \frac{1}{1 - z_e z_o t - \frac{x_1 \tilde{y}_1 t}{1 - \frac{(x_2+w_e)(y_2+w_o)t}{1 - \frac{(x_1+u_1)(\tilde{y}_1+\tilde{v}_1)t}{1 - \frac{(x_2+u_2+w_e)(y_2+v_2+w_o)t}{1 - \frac{(x_1+2u_1)(\tilde{y}_1+2\tilde{v}_1)t}{1 - \frac{(x_2+2u_2+w_e)(y_2+2v_2+w_o)t}{1 - \dots}}}}}}} \quad (4.19) $$
with coefficients

$$ \alpha_{2k-1} = [x_1 + (k-1)u_1] [\tilde{y}_1 + (k-1)\tilde{v}_1] \quad (4.20a) $$

$$ \alpha_{2k} = [x_2 + (k-1)u_2 + w_e] [y_2 + (k-1)v_2 + w_o] \quad (4.20b) $$

$$ \delta_1 = z_e z_o \quad (4.20c) $$

$$ \delta_n = 0 \quad \text{for } n \ge 2 \quad (4.20d) $$

We leave the rephrasings of Theorems 4.3 and 4.4 to the reader and directly proceed to rephrase Theorem 4.5. To do this, we introduce the following polynomial:

$$ \begin{aligned} \tilde{P}'_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, w_e, w_o, z_e, z_o) = & \sum_{\sigma \in \mathcal{D}_{2n}} x_1^{\text{ereccpeak}'(\sigma)} x_2^{\text{eareccdfall}'(\sigma)} \tilde{y}_1^{\text{minval}(\sigma)} y_2^{\text{ereccdrise}'(\sigma)} \times \\ & u_1^{\text{nrcpeak}'(\sigma)} u_2^{\text{nrcdfall}'(\sigma)} \tilde{v}_1^{\text{nminval}(\sigma)} v_2^{\text{nrcdrise}'(\sigma)} \times \\ & w_e^{\text{evennrfix}(\sigma)} w_o^{\text{oddnnrfix}(\sigma)} z_e^{\text{evenrar}(\sigma)} z_o^{\text{oddrar}(\sigma)}. \end{aligned} \quad (4.21) $$

Theorem 4.5 can now simply be restated as follows:

**Theorem 4.6'.** The ordinary generating function of the polynomials $\tilde{P}'_n$ defined in (4.21) has the same T-type continued fraction (4.19)/(4.20) as the polynomials $\tilde{P}_n$ defined in (4.18). Therefore,

$$ \tilde{P}'_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, w_e, w_o, z_e, z_o) = \tilde{P}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, w_e, w_o, z_e, z_o). \quad (4.22) $$

Recall that we observed in Section 1.6 the equivalence between [30, Conjecture 12] and Conjecture 1.2'. We now obtain Conjecture 1.2' as a corollary of Theorem 4.5'.

**Corollary 4.9** (Conjecture 1.2'). Recall the polynomials $G_n$, defined in (1.29)/(1.31),

$$ \begin{aligned} G_n(x, y, \bar{x}, \bar{y}) &= \sum_{\sigma \in \mathcal{D}_{2n}^0} x^{\text{comi}(\sigma)} y^{\text{lema}(\sigma)} \bar{x}^{\text{cemi}(\sigma)} \bar{y}^{\text{remi}(\sigma)} \\ &= \sum_{\sigma \in \mathcal{D}_{2n}^0} x^{\text{minval}(\sigma)} y^{\text{ereccpeak}'(\sigma)} \bar{x}^{\text{evennrfix}(\sigma)} \bar{y}^{\text{eareccdfall}'(\sigma)}. \end{aligned} $$
The ordinary generating functions of $G_n$ has the S-type continued fraction

$$1 + \sum_{n=1}^{\infty} G_n(x, y, \bar{x}, \bar{y}) t^n = \frac{1}{1 - \frac{xyt}{1 - \frac{1(\bar{x} + \bar{y})t}{1 - \frac{(x+1)(y+1)t}{1 - \frac{2(\bar{x} + \bar{y})+1}{1 - \frac{(x+2)(y+2)t}{1 - \frac{3(\bar{x} + \bar{y})+2)t}{\dots}}}}} \quad (4.23)$$

with coefficients

$$\alpha_{2k-1} = (x + k - 1)(y + k - 1) \quad (4.24a)$$

$$\alpha_{2k} = k(\bar{x} + \bar{y} + k - 1) \quad (4.24b)$$

*Proof.* It is evident from $(1.31)/(4.21)$ that $G_n$ can be obtained from $\tilde{P}'_n$ by specialising $\tilde{y}_1 = x, x_1 = y, w_e = \bar{x}, x_2 = \bar{y}$ and $w_o = z_o = 0$, and setting all other variables to 1. This along with Theorems 4.2'/4.5' proves the result. $\square$

# 5 Proof preliminaries

A powerful way to prove continued fraction results is Flajolet's [12] combinatorial interpretation of continued fractions which interprets Jacobi and Stieltjes-type continued fractions in terms of Motzkin and Dyck paths and its generalisation [18, 27, 21, 32, 10] to Schröder paths. One then uses a bijection from the combinatorial object of study to labelled paths. In our situation, the later bijections are the variant Foata-Zeilberger bijection used in [34, Section 6.1] (for permutations), and the two bijections in [6, Section 6] (for D-permutations). We begin by reviewing briefly these two ingredients.

Our exposition in this section will closely follow [34, 6].

## 5.1 Combinatorial interpretation of continued fractions

Recall that a **Motzkin path** of length $n \ge 0$ is a path $\omega = (\omega_0, \dots, \omega_n)$ in the right quadrant $\mathbb{N} \times \mathbb{N}$, starting at $\omega_0 = (0, 0)$ and ending at $\omega_n = (n, 0)$, whose steps $s_j = \omega_j - \omega_{j-1}$ are $(1, 1)$ ["rise" or "up step"], $(1, -1)$ ["fall" or "down step"] or $(1, 0)$ ["level step"). We write $h_j$ for the **height** of the Motzkin path at abscissa $j$, i.e. $\omega_j = (j, h_j)$; note in particular that $h_0 = h_n = 0$. We write $M_n$ for the set of Motzkin paths of length $n$, and $M = \bigcup_{n=0}^{\infty} M_n$.
A Motzkin path is called a **Dyck path** if it has no level steps. A Dyck path always has even length; we write $D_{2n}$ for the set of Dyck paths of length $2n$, and $\mathcal{D} = \bigcup_{n=0}^{\infty} D_{2n}$.

Let $\mathbf{a} = (a_i)_{i \ge 0}$, $\mathbf{b} = (b_i)_{i \ge 1}$ and $\mathbf{c} = (c_i)_{i \ge 0}$ be indeterminates; we will work in the ring $\mathbb{Z}[\mathbf{a}, \mathbf{b}, \mathbf{c}]$ of formal power series in these indeterminates. To each Motzkin path $\omega$ we assign a weight $W(\omega) \in \mathbb{Z}[\mathbf{a}, \mathbf{b}, \mathbf{c}]$ that is the product of the weights for the individual steps, where a rise starting at height $i$ gets weight $a_i$, a fall starting at height $i$ gets weight $b_i$, and a level step at height $i$ gets weight $c_i$. Flajolet [12] showed that the generating function of Motzkin paths can be expressed as a continued fraction:

**Theorem 5.1** (Flajolet's master theorem). We have

$$ \sum_{\omega \in \mathcal{M}} W(\omega) = \frac{1}{1 - c_0 - \frac{a_0 b_1}{1 - c_1 - \frac{a_1 b_2}{1 - c_2 - \frac{a_2 b_3}{1 - \dots}}} \quad (5.1) $$

as an identity in $\mathbb{Z}[\mathbf{a}, \mathbf{b}, \mathbf{c}]$.

In particular, if $a_{i-1}b_i = \beta_i t^2$ and $c_i = \gamma_i t$ (note that the parameter $t$ is conjugate to the length of the Motzkin path), we have

$$ \sum_{n=0}^{\infty} t^n \sum_{\omega \in \mathcal{M}_n} W(\omega) = \frac{1}{1 - \gamma_0 t - \frac{\beta_1 t^2}{1 - \gamma_1 t - \frac{\beta_2 t^2}{1 - \dots}}} \quad (5.2) $$

so that the generating function of Motzkin paths with height-dependent weights is given by the J-type continued fraction (1.7). Similarly, if $a_{i-1}b_i = \alpha_i t$ and $c_i = 0$ (note that $t$ is now conjugate to the semi-length of the Dyck path), we have

$$ \sum_{n=0}^{\infty} t^n \sum_{\omega \in \mathcal{D}_{2n}} W(\omega) = \frac{1}{1 - \frac{\alpha_1 t}{1 - \frac{\alpha_2 t}{1 - \dots}}} \quad (5.3) $$

so that the generating function of Dyck paths with height-dependent weights is given by the S-type continued fraction (1.3).

Let us now show how to handle Schröder paths within this framework. A **Schröder path** of length $2n$ ($n \ge 0$) is a path $\omega = (\omega_0, \dots, \omega_{2n})$ in the right quadrant $\mathbb{N} \times \mathbb{N}$, starting at $\omega_0 = (0, 0)$ and ending at $\omega_{2n} = (2n, 0)$, whose steps are $(1, 1)$ ["rise" or "up step",
(1, -1) ["fall" or "down step"] or (2, 0) ["long level step"). We write $s_j$ for the step starting at abscissa $j - 1$. If the step $s_j$ is a rise or a fall, we set $s_j = \omega_j - \omega_{j-1}$ as before. If the step $s_j$ is a long level step, we set $s_j = \omega_{j+1} - \omega_{j-1}$ and leave $\omega_j$ undefined; furthermore, in this case there is no step $s_{j+1}$. We write $h_j$ for the height of the Schröder path at abscissa $j$ whenever this is defined, i.e. $\omega_j = (j, h_j)$. Please note that $\omega_{2n} = (2n, 0)$ and $h_{2n} = 0$ are always well-defined, because there cannot be a long level step starting at abscissa $2n - 1$. Note also that a long level step at even (resp. odd) height can occur only at an odd-numbered (resp. even-numbered) step. We write $S_{2n}$ for the set of Schröder paths of length $2n$, and $S = \bigcup_{n=0}^{\infty} S_{2n}$.

There is an obvious bijection between Schröder paths and Motzkin paths: namely, every long level step is mapped onto a level step. If we apply Flajolet's master theorem with $a_{i-1}b_i = \alpha_i t$ and $c_i = \delta_{i+1}t$ to the resulting Motzkin path (note that $t$ is now conjugate to the semi-length of the underlying Schröder path), we obtain

$$ \sum_{n=0}^{\infty} t^n \sum_{\omega \in S_{2n}} W(\omega) = \frac{1}{1 - \delta_1 t - \frac{\alpha_1 t}{1 - \delta_2 t - \frac{\alpha_2 t}{1 - \dots}}} \quad (5.4) $$

so that the generating function of Schröder paths with height-dependent weights is given by the T-type continued fraction (1.8). More precisely, every rise gets a weight 1, every fall starting at height $i$ gets a weight $\alpha_i$, and every long level step at height $i$ gets a weight $\delta_{i+1}$. This combinatorial interpretation of T-fractions in terms of Schröder paths was found recently by several authors [18, 27, 21, 32].

## 5.2 Labelled Dyck, Motzkin and Schröder paths

Let $\mathcal{A} = (\mathcal{A}_h)_{h \ge 0}$, $\mathcal{B} = (\mathcal{B}_h)_{h \ge 1}$ and $\mathcal{C} = (\mathcal{C}_h)_{h \ge 0}$ be sequences of finite sets. An $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled Motzkin path of length $n$ is a pair $(\omega, \xi)$ where $\omega = (\omega_0, \dots, \omega_n)$ is a Motzkin path of length $n$, and $\xi = (\xi_1, \dots, \xi_n)$ is a sequence satisfying

$$ \xi_i \in \begin{cases} \mathcal{A}(h_{i-1}) & \text{if step } i \text{ is a rise (i.e. } h_i = h_{i-1} + 1) \\ \mathcal{B}(h_{i-1}) & \text{if step } i \text{ is a fall (i.e. } h_i = h_{i-1} - 1) \\ \mathcal{C}(h_{i-1}) & \text{if step } i \text{ is a level step (i.e. } h_i = h_{i-1}) \end{cases} \quad (5.5) $$

where $h_{i-1}$ (resp. $h_i$) is the height of the Motzkin path before (resp. after) step $i$. [For typographical clarity we have here written $\mathcal{A}(h)$ as a synonym for $\mathcal{A}_h$, etc.] We call $\xi_i$ the *label* associated to step $i$. We call the pair $(\omega, \xi)$ an $(\mathcal{A}, \mathcal{B})$-labelled Dyck path if $\omega$ is a Dyck path (in this case $\mathcal{C}$ plays no role). We denote by $M_n(\mathcal{A}, \mathcal{B}, \mathcal{C})$ the set of $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled Motzkin paths of length $n$, and by $D_{2n}(\mathcal{A}, \mathcal{B})$ the set of $(\mathcal{A}, \mathcal{B})$-labelled Dyck paths of length $2n$.
We define a (A, B, C)-labelled Schröder path in an analogous way; now the sets C_h refer to long level steps. We denote by S_2n(A, B, C) the set of (A, B, C)-labelled Schröder paths of length 2n.

Let us stress that the sets A_h, B_h and C_h are allowed to be empty. Whenever this happens, the path ω is forbidden to take a step of the specified kind starting at the specified height.

Following Flajolet [12, Proposition 7A], we can state a “master J-fraction” for (A, B, C)-labelled Motzkin paths. Let **a** = (a<sub>h,ξ</sub>)<sub>h≥0</sub>, ξ∈A(h), **b** = (b<sub>h,ξ</sub>)<sub>h≥1</sub>, ξ∈B(h) and **c** = (c<sub>h,ξ</sub>)<sub>h≥0</sub>, ξ∈C(h) be indeterminates; we give an (A, B, C)-labelled Motzkin path (ω, ξ) a weight W(ω, ξ) that is the product of the weights for the individual steps, where a rise starting at height h with label ξ gets weight a<sub>h,ξ</sub>, a fall starting at height h with label ξ gets weight b<sub>h,ξ</sub>, and a level step at height h with label ξ gets weight c<sub>h,ξ</sub>. Then:

**Theorem 5.2** (Flajolet’s master theorem for labelled Motzkin paths). We have

$$
\sum_{n=0}^{\infty} t^n \sum_{(\omega, \xi) \in \mathcal{M}_n(\mathcal{A}, \mathcal{B}, \mathcal{C})} W(\omega, \xi) = \frac{1}{1 - c_0 t - \frac{a_0 b_1 t^2}{1 - c_1 t - \frac{a_1 b_2 t^2}{1 - c_2 t - \frac{a_2 b_3 t^2}{1 - \dots}}}} \quad (5.6)
$$

as an identity in $\mathbb{Z}[\mathbf{a}, \mathbf{b}, \mathbf{c}][[t]]$, where

$$
a_h = \sum_{\xi \in \mathcal{A}(h)} a_{h,\xi}, \quad b_h = \sum_{\xi \in \mathcal{B}(h)} b_{h,\xi}, \quad c_h = \sum_{\xi \in \mathcal{C}(h)} c_{h,\xi}. \quad (5.7)
$$

This is an immediate consequence of Theorem 5.1 together with the definitions.

By specialising to **c** = **0** and replacing *t*² by *t*, we obtain the corresponding theorem for
(**A**, **B**)–labelled Dyck paths:

**Corollary 5.3** (Flajolet’s master theorem for labelled Dyck paths). We have

$$
\sum_{n=0}^{\infty} t^n \sum_{(\omega, \xi) \in \mathcal{D}_{2n}(\mathcal{A}, \mathcal{B})} W(\omega, \xi) = \frac{1}{1 - \frac{a_0 b_1 t}{1 - \frac{a_1 b_2 t}{1 - \frac{a_2 b_3 t}{1 - \dots}}}} \quad (5.8)
$$

as an identity in $\mathbb{Z}[\mathbf{a}, \mathbf{b}][[t]]$, where $a_h$ and $b_h$ are defined by (5.7).
Similarly, for labelled Schröder paths we have:

**Theorem 5.4** (Flajolet's master theorem for labelled Schröder paths). We have

$$ \sum_{n=0}^{\infty} t^n \sum_{(\omega, \xi) \in S_{2n}(A, B, C)} W(\omega, \xi) = \frac{1}{1 - c_0 t - \frac{a_0 b_1 t}{1 - c_1 t - \frac{a_1 b_2 t}{1 - c_2 t - \frac{a_2 b_3 t}{1 - \dots}}} \quad (5.9) $$

as an identity in $Z[a, b, c][[t]]$, where $a_h, b_h, c_h$ are defined by (5.7), with $c_{h,\xi}$ now referring to long level steps.

# 6 Permutations: Proof of Theorems 3.1, 3.2, 3.3

Sokal and Zeng [34, Section 6.1] used a variant of the Foata-Zeilberger bijection [15] to prove [34, Theorems 2.1(a), 2.2, 2.5, 2.7 and 2.9] i.e., their “first theorems” for permutations. We will provide a new interpretation to this bijection in terms of Laguerre digraphs and then use this interpretation to prove our theorems for permutations.

We first recall Sokal and Zeng’s bijection in Subsection 6.1, and then introduce our interpretation in Subsection 6.2. In Subsection 6.3, we write out our construction explicitly for our two running examples. Finally, we complete our proofs in Subsection 6.4.

## 6.1 Sokal-Zeng variant of the Foata-Zeilberger bijection

Sokal and Zeng employed a variant of the Foata-Zeilberger bijection to prove [34, Theorems 2.1(a), 2.2, 2.5, 2.7, and 2.9], i.e., their “first theorems” for permutations. We begin by recalling this bijection which is a correspondence between $S_n$ and the set of $(A, B, C)$-labelled Motzkin paths of length $n$, where the labels $\xi_i$ lie in the sets

$$ A_h = \{0, \dots, h\} \qquad \text{for } h \ge 0 \quad (6.1a) $$

$$ B_h = \{0, \dots, h-1\} \qquad \text{for } h \ge 1 \quad (6.1b) $$

$$ C_h = (\{1\} \times C_h^{(1)}) \cup (\{2\} \times C_h^{(2)}) \cup (\{3\} \times C_h^{(3)}) \qquad \text{for } h \ge 0 \quad (6.1c) $$

where

$$ C_h^{(1)} = \{0, \dots, h-1\} \qquad \text{for } k \ge 0 \quad (6.2a) $$

$$ C_h^{(2)} = \{0, \dots, h-1\} \qquad \text{for } k \ge 0 \quad (6.2b) $$

$$ C_h^{(3)} = \{0\} \qquad \text{for } k \ge 0 \quad (6.2c) $$
Notice that our convention for labels in this paper are slightly different from [34] and we instead follow those in [6, Section 5]. A key difference is that our label set starts at 0 and not at 1. A level step that has label $\xi_h \in \{i\} \times C_h^{(i)}$ will be called a level step of type $i$ ($i = 1, 2, 3$). By a 3-coloured Motzkin path, we will refer to a Motzkin path $\omega$ where each of its level steps is assigned a type. We will use $\bar{\omega}$ to denote a 3-coloured Motzkin path.

We will begin by recalling how the Motzkin path $\omega$ is defined; then we will explain how the labels $\xi$ are defined; next we sketch the proof that the mapping is indeed a bijection. There were two more steps in [34, Section 6.1] which we will not recall; these were the translation of the various statistics from $\mathfrak{S}_n$ to labelled Motzkin paths; and summing over labels $\xi$ to obtain the weight $W(\omega)$.

**Step 1: Definition of the Motzkin path.** Given a permutation $\sigma \in \mathfrak{S}_n$, we classify the indices $i \in [n]$ according to the cycle classification. We then define a path $\omega = (\omega_0, \dots, \omega_n)$ starting at $\omega_0 = (0, 0)$ and ending at $\omega_n = (n, 0)$, with steps $s_1, \dots, s_n$, as follows:

* If $i$ is a cycle valley, then $s_i$ is a rise.

* If $i$ is a cycle peak, then $s_i$ is a fall.

* If $i$ is a cycle double fall, then $s_i$ is a level step of type 1.

* If $i$ is a cycle double rise, then $s_i$ is a level step of type 2.

* If $i$ is a fixed point, then $s_i$ is a level step of type 3.

The fact that the resulting path is indeed a Motzkin path was proved by providing an interpretation of the height $h_i$ which we recall here:

**Lemma 6.1 ([34, Lemma 6.1]).** For $i \in [n+1]$ we have

$$h_{i-1} = \#\{j < i : \sigma(j) \ge i\} \qquad (6.3a)$$

$$= \#\{j < i : \sigma^{-1}(j) \ge i\}. \qquad (6.3b)$$

We also recall ([34, eq. (6.4)]) which is an equivalent formulation of Equation (6.3):

$$h_i = \#\{j \le i : \sigma(j) > i\} \qquad (6.4a)$$

$$= \#\{j \le i : \sigma^{-1}(j) > i\}. \qquad (6.4b)$$

Notice that if $i$ is a fixed point, then by comparing (6.3a)/(6.4a) with (1.10) we see that the height of the Motzkin path after (or before) step $i$ equals the number of pseudo-nestings
of the fixed point:

$$h_{i-1} = h_i = \text{psnest}(i, \sigma). \tag{6.5}$$

**Step 2: Definition of the labels $\xi_i$.** We now recall the definition of the labels

$$\xi_i = \begin{cases} \#\{j: j < i \text{ and } \sigma(j) > \sigma(i)\} & \text{if } \sigma(i) > i \quad \text{i.e. } i \in \text{Cval} \cup \text{Cdrise} \\ \#\{j: j > i \text{ and } \sigma(j) < \sigma(i)\} & \text{if } \sigma(i) < i \quad \text{i.e. } i \in \text{Cpeak} \cup \text{Cdfall} \\ 0 & \text{if } \sigma(i) = i \quad \text{i.e. } i \in \text{Fix} \end{cases} \tag{6.6}$$

where recall that Cval is the set of all cycle valleys of $\sigma$ and likewise for the others. For sake of brevity, we are abusing notation for fixed points, cycle double rises and cycle double falls by dropping the first index of $\xi_i$.

Compare our definition (6.6) with [34, (6.5)] and notice the shift from 1 to 0. These definitions have a simple interpretation in terms of the nesting statistics defined in (2.3b,d):

$$\xi_i = \begin{cases} \text{unest}(i, \sigma) & \text{if } \sigma(i) > i \quad \text{i.e. } i \in \text{Cval} \cup \text{Cdrise} \\ \text{lnest}(i, \sigma) & \text{if } \sigma(i) < i \quad \text{i.e. } i \in \text{Cpeak} \cup \text{Cdfall} \\ 0 & \text{if } \sigma(i) = i \quad \text{i.e. } i \in \text{Fix} \end{cases} \tag{6.7}$$

To verify that the inequalities (5.5)/(6.1) are satisfied; to do this, we interpret $h_{i-1} - \xi_i$ in terms of the crossing statistics defined in (2.3a,c):

**Lemma 6.2 (Crossing statistics).** We have

$$h_{i-1} - \xi_i = \text{ucross}(i, \sigma) \quad \text{if } i \in \text{Cval} \tag{6.8}$$

$$h_{i-1} - 1 - \xi_i = \text{ucross}(i, \sigma) \quad \text{if } i \in \text{Cdrise} \tag{6.9}$$

$$h_{i-1} - 1 - \xi_i = \text{lcross}(i, \sigma) \quad \text{if } i \in \text{Cpeak} \cup \text{Cdfall} \tag{6.10}$$

Again compare Lemma 6.2 with [34, Lemma 6.2] to see how the shift of 1 affects these quantities.

Since the quantities (6.8)-(6.10) are manifestly nonnegative, it follows immediately that the inequalities (5.5)/(6.1) are satisfied.

**Step 3: Proof of bijection.** We recall the description of the inverse map for the mapping $\sigma \mapsto (\omega, \xi)$.
First, some preliminaries: Given a permutation $\sigma \in \mathfrak{S}_n$, we define five subsets of $[n]$:

$$F = \{i: \sigma(i) > i\} = \text{positions of excedances} \qquad (6.11a)$$

$$F' = \{i: i > \sigma^{-1}(i)\} = \text{values of excedances} \qquad (6.11b)$$

$$G = \{i: \sigma(i) < i\} = \text{positions of anti-excedances} \qquad (6.11c)$$

$$G' = \{i: i < \sigma^{-1}(i)\} = \text{values of anti-excedances} \qquad (6.11d)$$

$$H = \{i: \sigma(i) = i\} = \text{fixed points} \qquad (6.11e)$$

Let us observe that

$$F \cap F' = \text{cycle double rises} \qquad (6.12a)$$

$$G \cap G' = \text{cycle double falls} \qquad (6.12b)$$

$$F \cap G' = \text{cycle valleys} \qquad (6.12c)$$

$$F' \cap G = \text{cycle peaks} \qquad (6.12d)$$

$$F \cap G = \emptyset \qquad (6.12e)$$

$$F' \cap G' = \emptyset \qquad (6.12f)$$

and of course $H$ is disjoint from $F, F', G, G'$.

Let us also recall the notion of an *inversion table*: Let $S$ be a totally ordered set of cardinality $k$, and let $\boldsymbol{x} = (x_1, \dots, x_k)$ be an enumeration of $S$; then the (left-to-right) inversion table corresponding to $\boldsymbol{x}$ is the sequence $\boldsymbol{p} = (p_1, \dots, p_k)$ of nonnegative integers defined by $p_\alpha = \#\{\beta < \alpha: x_\beta > x_\alpha\}$. Note that $0 \le p_\alpha \le \alpha - 1$ for all $\alpha \in [k]$, so there are exactly $k!$ possible inversion tables. Given the inversion table $\boldsymbol{p}$, we can reconstruct the sequence $\boldsymbol{x}$ by working from right to left, as follows: There are $p_k$ elements of $S$ larger than $x_k$, so $x_k$ must be the $(p_k+1)$th largest element of $S$. Then there are $p_{k-1}$ elements of $S\setminus\{x_k\}$ larger than $x_{k-1}$, so $x_{k-1}$ must be the $(p_{k-1}+1)$th largest element of $S\setminus\{x_k\}$. And so forth. [Analogously, the right-to-left inversion table corresponding to $\boldsymbol{x}$ is the sequence $\boldsymbol{p} = (p_1, \dots, p_k)$ of nonnegative integers defined by $p_\alpha = \#\{\beta > \alpha: x_\beta < x_\alpha\}$.]

With these preliminaries out of the way, we can now describe the map $(\omega, \xi) \mapsto \sigma$. Given a Motzkin path along with an assignment of types for its level steps $\bar{\omega}$, we read off which indices $i$ correspond to cycle valleys, cycle peaks, cycle double falls, cycle double rises, and fixed points; this allows us to reconstruct the sets $F, F', G, G', H$. We now use the labels $\xi$ to reconstruct the maps $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$, as follows: Let $i_1, \dots, i_k$ be the elements of $F$ written in increasing order; then the sequence $j_1, \dots, j_k$ defined by $j_\alpha = \sigma(i_\alpha)$ is a listing of $F'$ whose inversion table is given by $p_\alpha = \xi_{i_\alpha}$: this is the content of (6.6) in the case $\sigma(i) > i$. So we can use $\xi \upharpoonright F$ to reconstruct $\sigma \upharpoonright F$. In a similar way we can use $\xi \upharpoonright G$ to reconstruct $\sigma \upharpoonright G$, but now we must use the right-to-left inversion table because of how (6.6) is written in the case $\sigma(i) < i$.
**Remark 6.1.** In the original version of the bijection by Foata and Zeilberger [15], fixed points were treated differently and were clubbed together with anti-excedances (thus forming the set of non-excedances). Also, the notion of inversion table was different; unlike the “position-based” inversion table by Sokal and Zeng [34], Foata and Zeilberger used a “value-based” inversion table. We will employ both versions of inversion tables in Section 7.

<figure><img src="image_5.png" /></figure>

We will now look at the Foata-Zeilberger bijection for our two running examples in Sections 6.1.1 and 6.1.2.

### 6.1.1 Running example 1

First let us take $\sigma = 9\ 3\ 7\ 4\ 6\ 11\ 5\ 8\ 10\ 1\ 2 = (1,9,10)(2,3,7,5,6,11)(4)(8) \in S_{11}$ which was depicted in Figure 1. From the cycle classification of $\sigma$, which was recorded in Equation (1.11), we immediately obtain the Motzkin path $\omega$ corresponding to $\sigma$ which has been drawn in Figure 3.

<figure><img src="image_6.png" /><figcaption>Figure 3: Motzkin path $\omega$ corresponding to the permutation $\sigma = 9\ 3\ 7\ 4\ 6\ 11\ 5\ 8\ 10\ 1\ 2 = (1,9,10)(2,3,7,5,6,11)(4)(8)$.</figcaption></figure>

The sets $F, F', G, G', H$ are

$$F = \{1, 2, 3, 5, 6, 9\} \qquad (6.13a)$$

$$F' = \{3, 6, 7, 9, 10, 11\} \qquad (6.13b)$$

$$G = \{7, 10, 11\} \qquad (6.13c)$$

$$G' = \{1, 2, 5\} \qquad (6.13d)$$

$$H = \{4, 8\} \qquad (6.13e)$$
and the labels $\xi_i$ are given in Equation (6.14).

$$ i \in F = \{1, 2, 3, 5, 6, 9\} \qquad F' = \{\sigma(i) \mid i \in F\} \qquad \left( \begin{array}{cccccc} 1 & 2 & 3 & 5 & 6 & 9 \\ 9 & 3 & 7 & 6 & 11 & 10 \\ 0 & 1 & (2, 1) & 2 & (2, 0) & (2, 1) \end{array} \right) \tag{6.14a} $$

$$ i \in G = \{7, 10, 11\} \qquad G' = \{\sigma(i) \mid i \in G\} \qquad \left( \begin{array}{ccc} 7 & 10 & 11 \\ 5 & 1 & 2 \\ 2 & 0 & 0 \end{array} \right) \tag{6.14b} $$

### 6.1.2 Running example 2

Next let us take

$$ \sigma = \begin{aligned} & 7192548610311121413 \\ & = (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathfrak{S}_{14} \end{aligned} \tag{6.15} $$

which was depicted in Figure 2. From the cycle classification of $\sigma$, which was recorded in Equation (1.14), we immediately obtain the Motzkin path $\omega$ corresponding to $\sigma$ which has been drawn in Figure 4.

<figure><img src="image_7.png" /><figcaption>Figure 4: Motzkin path $\omega$ corresponding to the permutation $\sigma = 7192548610311121413 = (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathfrak{S}_{14}$.</figcaption></figure>
The sets $F, F', G, G', H$ are

$$F = \{1, 3, 7, 9, 13\} \qquad (6.16a)$$

$$F' = \{7, 8, 9, 10, 14\} \qquad (6.16b)$$

$$G = \{2, 4, 6, 8, 10, 14\} \qquad (6.16c)$$

$$G' = \{1, 2, 3, 4, 6, 13\} \qquad (6.16d)$$

$$H = \{5, 11, 12\} \qquad (6.16e)$$

and the labels $\xi_i$ are given in Equation (6.17).

$$i \in F = \{1, 3, 7, 9, 13\} \quad \begin{pmatrix} 1 & 3 & 7 & 9 & 13 \\ 7 & 9 & 8 & 10 & 14 \\ 0 & 0 & (2, 2) & (2, 0) & 0 \end{pmatrix} \\ F' = \{\sigma(i) \mid i \in F\} \qquad (6.17a)$$

Left-to-right inversion table: $\xi_i$

$$i \in G = \{2, 4, 6, 8, 10, 14\} \quad \begin{pmatrix} 2 & 4 & 6 & 8 & 10 & 14 \\ 1 & 2 & 4 & 6 & 3 & 13 \\ (1, 0) & (1, 0) & (1, 1) & 1 & 0 & 0 \end{pmatrix} \\ G' = \{\sigma(i) \mid i \in G\} \qquad (6.17b)$$

Right-to-left inversion table: $\xi_i$

## 6.2 Combinatorial interpretation using Laguerre digraphs

We begin with a Motzkin path $\omega$ and an assignment of labels $\xi$ satisfying $(5.5)/(6.1)$. The inverse bijection (Section 6.1 Step 3), gives us a permutation $\sigma$. We will now break this process into several intermediate steps and reinterpret it using Laguerre digraphs. Recall that a Laguerre digraph of size $n$ is a directed graph where each vertex has a distinct label from the label set $[n]$ and has indegree 0 or 1 and outdegree 0 or 1. Clearly, any subgraph of a Laguerre digraph is also a Laguerre digraph. The connected components in a Laguerre digraph are either directed paths or directed cycles, where a path with one vertex is called an isolated vertex and a cycle with one vertex is called a loop.

Notice that a Laguerre digraph with no paths is a diagrammatic representation of a permutation in cycle notation (see [35, pp. 22-23]). Let $L^\sigma$ denote this Laguerre digraph corresponding to a permutation $\sigma \in S_n$. The directed edges of $L^\sigma$ are precisely $u \to \sigma(u)$. Also for $S \subseteq [n]$, we let $L^\sigma|_S$ denote the subgraph of $L^\sigma$, containing the same set of vertices $[n]$, but only the edges $u \to \sigma(u)$, with $u \in S$ (we are allowed to have $\sigma(u) \notin S$). Thus, $L^\sigma|_{[n]} = L^\sigma$, and $L^\sigma|_\emptyset$ is the digraph containing $n$ vertices and no edges. Whenever the permutation $\sigma$ is understood, we shall drop the superscript and use $L|_S$ to denote this digraph.
Recall that the inverse bijection in Step 3 Section 6.1, begins by obtaining the sets $F, F', G, G', H$ from the 3-coloured Motzkin path $\bar{\omega}$. We then construct $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ separately by using the labels $\xi \upharpoonright F$ and $\xi \upharpoonright G$ respectively. (Note that just knowing the set $H$ suffices to reconstruct $\sigma \upharpoonright H$.)

In this interpretation, we start with the digraph $L|_{\emptyset}$. We then go through the set $[n]$. However, the crucial part of our approach is that we use the following unusual total order on $[n]$ (notice that $[n] = F \cup G \cup H$):

• Stage (a): We first go through the set $H$ in increasing order.

• Stage (b): We then go through the set $G$ in increasing order.

• Stage (c): Finally, we go through the set $F$ but in decreasing order.

As $F, G$ and $H$ are entirely determined by the 3-coloured path $\bar{\omega}$, we call the above order the FZ order on $[n]$ with respect to the 3-coloured Motzkin path $\bar{\omega}$. Thus, the FZ order corresponding to two different permutations $\sigma$ and $\sigma'$ coming from the same 3-coloured Motzkin path $\bar{\omega}$ are the same.

Let $u_1, \dots, u_n$ be a rewriting of $[n]$ as per the FZ order. We now consider the “FZ history” $L|_{\emptyset} \subset L|_{\{u_1\}} \subset L|_{\{u_1, u_2\}} \subset \dots \subset L|_{\{u_1, \dots, u_n\}} = L$ as a process of building up the permutation $\sigma$ by successively considering the status of vertices $u_1, u_2, \dots, u_n$. Thus, at step $u$ (where the step number is given by the vertex $u \in [n]$) we use the inversion tables to construct the edge $u \to \sigma(u)$. Thus, at each step we insert a new edge into the digraph, and at the end of this process, the resulting digraph obtained is the permutation $\sigma$ in cycle notation.

Let us now look at the intermediate Laguerre digraphs obtained during stages (a), (b) and (c) more closely.

**Stage (a): Going through $H$:**

For each vertex $u \in H$, we introduce a loop edge $u \to u$ thus creating a new loop at the end of each step. After all steps $u \in H$ have been carried out, the resulting Laguerre digraph $L|_H$ consists of loops at all vertices in $H$. All other vertices are isolated vertices, i.e., have no adjacent edges.

**Stage (b): Going through $G$:**

From (6.12), we know that $G = \text{Cdfall}(\sigma) \cup \text{Cpeak}(\sigma)$ where $\sigma$ is the resulting permutation obtained at the end of the inverse bijection. Let us recall the construction for this case. We construct $\sigma \upharpoonright G: G \to G'$ using the right-to-left inversion table. Let $G = \{x_1 < x_2 < \dots < x_k\}$ be the elements of $G$ arranged in increasing order, and similarly let $G' = \{x'_1 < x'_2 < \dots < x'_k\}$. Then the $(p_j+1)$th smallest element of $G'\setminus\{\sigma(x_1), \dots, \sigma(x_{j-1})\}$ is chosen to be $\sigma(x_j)$ where $p_j = \xi_{x_j}$.
Let us reinterpret this in terms of Laguerre digraphs. At this stage, the vertices in $G$ (resp. $G'$) are our designated starting vertices (ending vertices) arranged in increasing order. We then look through the starting vertices in increasing order. At the end of step $x_{j-1}$, directed edges $x_1 \to \sigma(x_1), \dots, x_{j-1} \to \sigma(x_{j-1})$ have been inserted, the available starting vertices are $x_j, \dots, x_k$ and the available ending vertices belong to $G'\setminus\{\sigma(x_1), \dots, \sigma(x_{j-1})\}$. We then pick the smallest available starting vertex, which is $x_j$, and connect it to the $(p_j+1)$th smallest ending vertex available, i.e., the $(p_j+1)$th smallest element of the set $G'\setminus\{\sigma(x_1), \dots, \sigma(x_{j-1})\}$. (This is analogous to the partial interpretation of the labels in terms of bipartite digraph for cycle double falls and cycle peaks on [34, p. 96].)

The vertices in $L|_{H \cup \{x_1, \dots, x_j\}}$ have out-edges in the following situations:

* if $u \in H$, $u$ is a loop.

* if $u$ is one of the $j$ smallest elements of $G$, it has an edge going to some vertex $v \neq u$ and $v \in G'$.

* All other vertices have no out-edges.

Also, from definition of $G$ in (6.11c), it follows that for any non-loop edge $u \to v$, we must have $u > v$. Thus, the Laguerre digraph $L|_{H \cup \{x_1, \dots, x_j\}}$ only consists of decreasing directed paths (including isolated vertices) and loops; there are no non-loop cycles.

**Lemma 6.3.** *The Laguerre digraph $L|_{H \cup G}$ consists of the following connected components:*

* loops on vertices $u \in H$,

* directed paths with at least two vertices, in which the initial vertex of the path is a cycle peak in $\sigma$ (i.e. contained in the set $F' \cap G$), the final vertex is a cycle valley in $\sigma$ (i.e. contained in the set $F \cap G'$), and the intermediate vertices (if any) are cycle double falls (i.e. contained in the set $G \cap G'$).

* isolated vertices at $u \in F \cap F' = \text{Cdrise}(\sigma)$.

Furthermore, it contains no directed cycles.

*Proof.* It suffices to prove that for a directed path with at least two vertices, the initial vertex is a cycle peak in $\sigma$ (i.e. contained in the set $F' \cap G$) and the final vertex is a cycle valley in $\sigma$ (i.e. contained in the set $F \cap G'$).

Notice that the initial vertex $u$ of such a path must already have an out-neighbour and hence must belong to the set $G$ as only the elements of the sets $G$ and $H$ have been assigned out-neighbours. As all vertices in $G'$ have already been assigned in-neighbours, $u \notin G'$ and using the fact that $G = \text{Cdfall} \cup \text{Cpeak}$ (from (6.12)), we get that $u \in \text{Cpeak} = F' \cap G$. The proof for the final vertex is similar and we omit it. $\square$
**Stage (c): Going through F:**

Similar to both the previous cases, at each step we introduce edges $u \to \sigma(u)$. However, now we go through elements of $F$ in decreasing order.

From (6.12), we know that $F = \text{Cdrise} \cup \text{Cval}$. Let us now recall the construction for this case. We construct $\sigma \upharpoonright F: F \to F'$ using the left-to-right inversion table. Let $F = \{y_1 < y_2 < \dots < y_l\}$ be the elements of $F$ arranged in increasing order. Then the $(p_j+1)$th largest element of $F'\setminus\{\sigma(y_l), \dots, \sigma(y_{j+1})\}$ is chosen to be $\sigma(y_j)$ where $p_j = \xi_{y_j}$.

We now reinterpret this in terms of Laguerre digraphs. At this stage, the vertices in $F$ ($F'$) are our designated starting vertices (ending vertices). We look through the starting vertices in decreasing order. At the end of step $y_{j+1}$, directed edges $y_l \to \sigma(y_l), \dots, y_{j+1} \to \sigma(y_{j+1})$ have been inserted, the available starting vertices are $y_j, \dots, y_1$ and the available ending vertices belong to $F'\setminus\{\sigma(y_l), \dots, \sigma(y_{j+1})\}$. We then pick the largest available starting vertex, which is $y_j$ and connect it to the $(p_j+1)$th largest ending vertex available, i.e., the $(p_j+1)$th largest element of the set $F'\setminus\{\sigma(y_l), \dots, \sigma(y_{j+1})\}$.

**Lemma 6.4.** Let $u$ be the final vertex of a path with at least two vertices in $L|_{H \cup G \cup \{y_1, \dots, y_j\}}$. Then $u \in \text{Cval} = F \cap G'$.

*Proof.* Since all vertices in $H \cup G$ were already assigned out-neighbours during stages (a) and (b), it must be that $u \in F$. As $F = \text{Cdrise} \cup \text{Cval}$, $u$ is either a cycle valley or a cycle double rise in $\sigma$.

Let us assume that $u$ is a cycle double rise in $\sigma$, i.e., $\sigma^{-1}(u) < u < \sigma(u)$. We know that $u$ must have an in-neighbour $v$ as its path has atleast two vertices. Thus, $v = \sigma^{-1}(u) < u$, which implies $v \in F$ (from definition of $F$ in (6.11a)). However, this is a situation where we have two vertices $u, v \in F$ with $u > v$ such that the smaller vertex has an out-neighbour even though the larger vertex does not. This clearly cannot happen as we assign out-neighbours to vertices in $F$ in descending order. This is a contradiction and thus $u \in \text{Cval} = F \cap G'$. $\square$

Let $u_1, \dots, u_n$ be the elements of $[n]$ rearranged as per the FZ order with respect to the 3-coloured Motzkin path $\bar{\omega}$. We say that $u_j \in [n]\setminus H$ is a *cycle closer* if the edge $u_j \to \sigma(u_j)$ is introduced in $L|_{\{u_1, \dots, u_{j-1}\}}$ as an edge between the two ends of a path turning the path into a cycle. The following lemma classifies all cycle closers:

**Lemma 6.5. (Classifying cycle closers)** Given a permutation $\sigma$, an element $u \in [n]$ is a cycle closer if and only if it is a cycle valley minimum, i.e., it is the smallest element in its cycle.

*Proof.* Let $u_j$ be a cycle closer. Notice that $u_j$ must have been the final vertex of a path in $L|_{\{u_1, \dots, u_{j-1}\}}$ that contains at least two vertices. From Lemma 6.4, $u_j \in F \cap G' = \text{Cval}$.
Any other cycle valley $v \neq u_j$ in the resulting cycle must have already been present in this path and hence must have an out-neighbour. Hence, it must be that $v > u_j$ as Cval $\subseteq F$ and we assign out-neighbours to vertices belonging to $F$ in descending order. Thus, the cycle closer $u_j$ is the smallest cycle valley in its cycle in $\sigma$. $\square$

As each non-singleton cycle has exactly one cycle closer, counting cycle closers will give us the number of non-singleton cycles. This is what we do next. But before doing that, we require a technical lemma. However, before going into the lemma, recall that if $y_j \in F \cap G' = \text{Cval}(\sigma)$, step $s_{y_j}$ must be a rise from height $h_{y_{j-1}}$ to height $h_{y_j}$ and hence, $h_{y_{j-1}} + 1 = h_{y_j}$.

**Lemma 6.6.** Given a permutation $\sigma$ and associated sets $F, F', G, G', H$ with $F = \{y_1 < y_2 < \dots < y_l\}$, and an index $j$ ($1 \le j \le l$) such that $y_j \in F \cap G'$. Then the following is true:

$$ |\{u \in F' \setminus \{\sigma(y_l), \dots, \sigma(y_{j+1})\} : u > y_j\}| = h_{y_{j-1}} + 1 = h_{y_j} \quad (6.18) $$

where $h_i$ denotes the height at position $i$ of the Motzkin path $\omega$ associated to $\sigma$ in Step 1.

*Proof.* We first establish the following equality of sets:

$$ \{u > y_j : \sigma^{-1}(u) \le y_j\} = \{u \in F' \setminus \{\sigma(y_l), \dots, \sigma(y_{j+1})\} : u > y_j\}. \quad (6.19) $$

Whenever $u \in F'$, we have that $\sigma^{-1}(u) \in F$ (by description of $F, F'$ in (6.11a,b)). Additionally, if $u \notin \{\sigma(y_l), \dots, \sigma(y_{j+1})\}$ then it must be that $\sigma^{-1}(u) \le y_j$. This establishes the containment $\{u > y_j : \sigma^{-1}(u) \le y_j\} \supseteq \{u \in F' \setminus \{\sigma(y_l), \dots, \sigma(y_{j+1})\} : u > y_j\}$.

On the other hand, if $u > y_j$ and $\sigma^{-1}(u) \le y_j$, then $u > \sigma^{-1}(u)$ and hence $u \in F'$. As $\sigma^{-1}(u) \le y_j < y_{j+1} < \dots < y_l$, $u$ cannot be one of $\sigma(y_{j+1}), \dots, \sigma(y_l)$. Therefore, $u \in F' \setminus \{\sigma(y_l), \dots, \sigma(y_{j+1})\}$. This establishes (6.19).

To obtain Equation (6.18), it suffices to show that the cardinality of the set $\{u > y_j : \sigma^{-1}(u) \le y_j\}$ is $h_{y_j}$. To do this, recall the interpretation of heights in Equation (6.4a) and observe that

$$ \begin{aligned} h_{y_j} &= \#\{u \le y_j : \sigma(u) > y_j\} \\ &= \#\{u > y_j : \sigma^{-1}(u) \le y_j\} \end{aligned} \quad (6.20) $$

where the second equality is obtained by replacing $u$ with $\sigma^{-1}(u)$. $\square$

We are now ready to count the number of cycle closers.

**Lemma 6.7 (Counting of cycle closers for permutations).** Fix a 3-coloured Motzkin path $\bar{\omega}$ of length $n$ and construct the sets $F, F', G, G', H$ (these are totally determined by $\bar{\omega}$). Let $F = \{y_1 < y_2 < \dots < y_l\}$ and fix an index $j$ ($1 \le j \le l$) such that $y_j \in F \cap G'$. Also fix labels $\xi_u$ for vertices $u \in H \cup G \cup \{y_l, y_{l-1}, \dots, y_{j+1}\}$ satisfying (5.5)/(6.1). Then
(a) The value of $\xi_{y_j}$ completely determines if $y_j$ is a cycle closer or not.

(b) There is exactly one value $\xi_{y_j} \in \{0, 1, \dots, h_{y_j-1}\}$ that makes $y_j$ a cycle closer, and conversely.

*Proof.* As $y_j \in F \cap G'$, it must be that $y_j$ is a cycle valley in $\sigma$. As $y_j$ does not have an out-neighbour in the Laguerre digraph $L|_{H \cup G \cup \{y_1, \dots, y_{j+1}\}}$, it must be the final vertex of a path. Let $v$ be the initial vertex of this path. During step $y_j$, we choose one of the available ending vertices from the set $F'\setminus\{\sigma(y_1), \dots, \sigma(y_{j+1})\}$ to be $\sigma(y_j)$.

For $y_j$ to be a cycle closer, it must be that $\sigma(y_j) = v$ (so that inserting the edge $y_j \to v$ turns its path into a cycle). As each value for label $\xi_{y_j} \in \{0, 1, \dots, h_{y_j-1}\}$ assigns a different vertex to be $\sigma(y_j)$, there is at most one label for which $y_j$ is a cycle closer.

Next we observe that $v \notin G'$. This is because $v$ does not have an in-neighbour in $L|_{H \cup G \cup \{y_1, \dots, y_{j+1}\}}$ whereas all $v \in G'$ had in-neighbours at the end of stage (b). Therefore, $v \in F'$ and $y_j \neq v$ as $y_j \in G'$. To show that there is a $\xi_{y_j} \in \{0, 1, \dots, h_{y_j-1}\}$ which can connect $y_j$ to $v$, we must show that $v$ is among the largest $h_{y_j-1} + 1$ elements of $F'\setminus\{\sigma(y_1), \dots, \sigma(y_{j+1})\}$. However, from Lemma 6.6, we only need to show that $v > y_j$. The remainder of the proof does this.

Let $v = v_0, v_1, \dots, v_\alpha = y_j$ be the vertices of the path containing $y_j$ and $v$ with edges $v_i \to v_{i+1}$. Let $\beta$ be the smallest index such that $v_\beta \in F$. Using the description of $G$ in (6.11c), we get $v = v_0 > \dots > v_\beta$ when $\beta > 0$. Thus,

$$v = v_0 \le v_\beta \qquad (6.21)$$

with equality if and only if $\beta = 0$. On the other hand, if $\beta < \alpha$, then $v_\beta$ already has an out-neighbour and thus $v_\beta > y_j$ (as we are going through elements of $F$ in descending order). Thus,

$$v_\beta \le v_\alpha = y_j \qquad (6.22)$$

with equality if and only if $\beta = \alpha$. Using (6.21), (6.22) and the fact that $v \neq y_j$, we obtain $v > y_j$. This completes the proof. $\square$

**Remark 6.2.** 1. Notice that one can also construct a variant of this interpretation where stage (c) occurs before stage (b). The role of cycle closer will then be played by cycle peak maxima.

2. In fact, for our results to hold, we could carry out stages (a) and (b) in any order as we only require the digraph $L|_{H \cup G}$ and not the previous ones for our Lemmas 6.3-6.7 to hold. $\blacksquare$
## 6.3 Examples

### 6.3.1 Running example 1

We will now draw the FZ history of our first example $\sigma = 9\ 3\ 7\ 4\ 6\ 11\ 5\ 8\ 10\ 1\ 2 = (1, 9, 10)(2, 3, 7, 5, 6, 11)(4)(8) \in \mathfrak{S}_{11}$.

The sets $F, G$ and $H$ were already recorded in (6.13) and we recall that $F = \{1, 2, 3, 5, 6, 9\}, G = \{7, 10, 11\}$ and $H = \{4, 8\}$. Thus, the FZ order consists of the following stages:

* Stage (a): 4, 8

* Stage (b): 7, 10, 11

* Stage (c): 9, 6, 5, 3, 2, 1

Stages (a) and (b) of the FZ history of $\sigma$ has been drawn in Figure 5, and Stage (c) has been drawn in Figure 6. Non-singleton cycles are formed in Stage (c) when the edges $2 \to 3$ and $1 \to 9$ are inserted.

### 6.3.2 Running example 2

Let us now look at the FZ history of our second example $\sigma = 7\ 1\ 9\ 2\ 5\ 4\ 8\ 6\ 10\ 3\ 11\ 12\ 14\ 13 = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathfrak{S}_{14}$. The sets $F, G$ and $H$ were already recorded in (6.16) and we recall that $F = \{1, 3, 7, 9, 13\}, G = \{2, 4, 6, 8, 10, 14\}$ and $H = \{5, 11, 12\}$. Thus, the FZ order consists of the following stages:

* Stage (a): 5, 11, 12

* Stage (b): 2, 4, 6, 8, 10, 14

* Stage (c): 13, 9, 7, 3, 1

Stages (a) and (b) of the FZ history of $\sigma$ has been drawn in Figure 7, and Stage (c) has been drawn in Figure 8. Non-singleton cycles are formed in Stage (c) when the edges $13 \to 14, 3 \to 9$ and $1 \to 7$ are inserted.

## 6.4 Computation of weights

To each index $i \in [n]$ of a given permutation $\sigma \in \mathfrak{S}_n$, we assign a weight $\mathrm{wt}(i)$ as follows:

* if $i$ is a cycle valley minimum, we set $\mathrm{wt}(i) = \lambda a_{\mathrm{ucross}(i,\sigma)+\mathrm{unest}(i,\sigma)}$. For all other cycle valleys, we set $\mathrm{wt}(i) = a_{\mathrm{ucross}(i,\sigma)+\mathrm{unest}(i,\sigma)}$,

* if $i$ is a cycle peak, we set $\mathrm{wt}(i) = b_{\mathrm{lcross}(i,\sigma), \mathrm{lnest}(i,\sigma)}$,
<figure><img src="image_8.png" /><figcaption>Figure 5: Stages (a) and (b) of the FZ history for the permutation $\sigma = 9 \ 3 \ 7 \ 4 \ 6 \ 11 \ 5 \ 8 \ 10 \ 1 \ 2 = (1, 9, 10) (2, 3, 7, 5, 6, 11) (4) (8) \in \mathfrak{S}_{11}$.</figcaption></figure>
Stage (c): $F = \{9, 6, 5, 3, 2, 1\}$ in decreasing order

<figure><img src="image_9.png" /><figcaption>Figure 6: Stage (c) of the FZ history for the permutation $\sigma = 9\ 3\ 7\ 4\ 6\ 11\ 5\ 8\ 10\ 1\ 2 = (1, 9, 10)(2, 3, 7, 5, 6, 11)(4)(8) \in \mathfrak{S}_{11}$.</figcaption></figure>
Stage (c): $F = \{13, 9, 7, 3, 1\}$ in decreasing order

<figure><img src="image_10.png" /><figcaption>Figure 8: Stage (c) of the FZ history for the permutation $\sigma = 719254861031121413 = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathfrak{S}_{14}$.</figcaption></figure>
* if $i$ is a cycle double fall, we set $\mathrm{wt}(i) = c_{\mathrm{lcross}(i,\sigma), \mathrm{lnest}(i,\sigma)}$,

* if $i$ is a cycle double rise, we set $\mathrm{wt}(i) = d_{\mathrm{ucross}(i,\sigma), \mathrm{unest}(i,\sigma)}$,

* and finally, if $i$ is a fixed point, we set $\mathrm{wt}(i) = \lambda e_{\mathrm{psnest}(i,\sigma)}$.

We then set the weight of the permutation $\sigma$ to be $\mathrm{wt}(\sigma) = \prod_{i=1}^{n} \mathrm{wt}(i)$. It is clear that our polynomial $\hat{Q}_n$ defined in (3.6) is simply $\hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \lambda) = \sum_{\sigma \in S_n} \mathrm{wt}(\sigma)$.

We now use the bijection $\sigma \mapsto (\omega, \xi)$ to transfer the weights $\mathrm{wt}(i)$ onto the pair $(\omega, \xi)$. Let $k = h_{i-1}$ the height at which step $s_i$ starts. From 6.5, 6.7, and Lemma 6.2, we immediately see that

* if $s_i$ is a rise, then $\mathrm{wt}(i) = (1 + \mathrm{I}[i \text{ is a cycle valley minimum}](\lambda - 1)) a_k$. (Here $\mathrm{I}[proposition] = 1$ if proposition is true, and 0 if it is false.)

* if $s_i$ is a fall, then $\mathrm{wt}(i) = b_{k-1-\xi_i, \xi_i}$,

* if $s_i$ is a level step of type 1 (here $i$ is a cycle double fall), $\mathrm{wt}(i) = c_{k-1-\xi_i, \xi_i}$,

* if $s_i$ is a level step of type 2 (here $i$ is a cycle double rise), $\mathrm{wt}(i) = d_{k-1-\xi_i, \xi_i}$,

* if $s_i$ is a level step of type 3 (here $i$ is a fixed point), $\mathrm{wt}(i) = \lambda e_k$,

Next, we fix a Motzkin path $\omega$ and sum over all labels $\xi \in [0, k]$ to obtain the weight $W(\omega)$. This weight is then factorised over the individual steps $s_i$ to obtain the weight contributed by each step $s_i$. As all the variables involved commute, we can consider the weights for the steps $s_i$ in any order. We do this in the FZ order as follows:

* if $s_i$ is a rise, then $i$ is a cycle valley. Among the possible choices of labels $\xi \in [0, k]$ there is exactly one which closes a cycle and the others don't (Lemma 6.7). Therefore, we obtain

$$a_k \stackrel{\text{def}}{=} \sum_{\xi_i} (1 + \mathrm{I}[i \text{ is a cycle valley minimum}](\lambda - 1)) a_k = (\lambda + k)a_k. \quad (6.23)$$

* if $s_i$ is a fall, then the weight is

$$b_k = \sum_{\xi_i} b_{k-\xi_i-1, \xi_i} \quad (6.24)$$

* if $s_i$ is a level step of type 1, then the weight is

$$c_k = \sum_{\xi_i} c_{k-\xi_i-1, \xi_i} \quad (6.25)$$
• if $s_i$ is a level step of type 2, then the weight is

$$d_k = \sum_{\xi_i} d_{k-\xi_i-1, \xi_i} \qquad (6.26)$$

• if $s_i$ is a level step of type 3, then the weight is

$$e_k = \lambda e_k \qquad (6.27)$$

Setting $\beta_k = a_{k-1}b_k$ and $\gamma_k = c_k + d_k + e_k$ as instructed in Theorem 5.2, we obtain the weights 3.8. This completes the proof of Theorem 3.3. □

**PROOF OF THEOREM 3.2.** We recall [34, Lemma 2.10] which was used to separate records and antirecords: Let $\sigma \in \mathfrak{S}_n$ and $i \in [n]$.

(a) If $i$ is a cycle valley or cycle double rise, then $i$ is a record if and only if $\mathrm{unest}(i, \sigma) = 0$; and in this case it is an exclusive record.

(b) If $i$ is a cycle peak or cycle double fall, then $i$ is an antirecord if and only if $\mathrm{lnest}(i, \sigma) = 0$; and in this case it is an exclusive antirecord.

We then specialise Theorem 3.3 to

$$a_{\ell} = p_{+1}^{\ell} y_1 \qquad (6.28a)$$

$$b_{\ell, \ell'} = p_{-1}^{\ell} q_{-1}^{\ell'} \times \begin{cases} x_1 & \text{if } \ell' = 0 \\ u_1 & \text{if } \ell' \ge 1 \end{cases} \qquad (6.28b)$$

$$c_{\ell, \ell'} = p_{-2}^{\ell} q_{-2}^{\ell'} \times \begin{cases} x_2 & \text{if } \ell' = 0 \\ u_2 & \text{if } \ell' \ge 1 \end{cases} \qquad (6.28c)$$

$$d_{\ell, \ell'} = p_{+2}^{\ell} q_{+2}^{\ell'} \times \begin{cases} y_2 & \text{if } \ell' = 0 \\ v_2 & \text{if } \ell' \ge 1 \end{cases} \qquad (6.28d)$$

$$e_{\ell} = s^{\ell} w_{\ell} \qquad (6.28e)$$

<figure><img src="image_11.png" /></figure>

**Remark 6.3.** Notice that the specialisation in the above proof is almost the same as [34, eq. (2.81)], except for the treatment of a. ■

**PROOF OF THEOREM 3.1.** Specialise Theorem 3.2 to $p_{+1} = p_{-1} = p_{+2} = p_{-2} = q_{-1} = q_{+2} = q_{-2} = s = 1$. □
* If $\sigma^{-1}(i)$ is even, then $s_i$ is a rise. (Note that in this case we must have $\sigma^{-1}(i) \ge i$, by definition of D-permutation.)

* If $\sigma^{-1}(i)$ is odd, then $s_i$ is a fall. (Note that in this case we must have $\sigma^{-1}(i) \le i$, by definition of D-permutation.)

An alternative way of saying this is:

* If $i$ is a cycle valley, cycle double fall or even fixed point, then $s_i$ is a rise.

* If $i$ is a cycle peak, cycle double rise or odd fixed point, then $s_i$ is a fall.

The resulting path is indeed an almost-Dyck path; this was proved by obtaining a precise interpretation of the height $h_i$, which then implied for every $i \in [2n]$, $h_i \ge -1$, and also $h_{2n} = 0$. We recall this interpretation here:

**Lemma 7.1** ([6, Lemma 6.1]). For $k \in [2n]$ we have

$$h_k = \begin{cases} 2f_k - 1 & \text{if } k \text{ is odd} \\ 2f_k & \text{if } k \text{ is even} \end{cases} \qquad (7.2)$$

where $f_k$ is defined as [6, eq. (6.2)/(6.3)]

$$f_k = \#\{i \le k : \sigma(i) > k\} = \#\{i \le k : \sigma^{-1}(i) > k\}. \qquad (7.3)$$

By [6, Lemma 3.2], we have that $2i-1$ and $2i$ are record-antirecords if and only if $\sigma$ maps $\{1, \dots, 2i-1\}$ onto itself and this is the only situation when $h_k = -1$ where $k = 2i-1$ and $f_k = 0$. In this situation, $f_{2i-2} = f_{2i-1} = f_{2i} = 0$, so that $(h_{2i-2}, h_{2i-1}, h_{2i}) = (0, -1, 0)$.

**Remark 7.1.** We will now show that the almost-Dyck path $\omega$ described here can be obtained from the Motzkin path of length $2n$ used in the Foata-Zeilberger bijection. For a given D-permutation $\sigma \in \mathfrak{D}_{2n}$, let $\tilde{\omega}$ be the Motzkin path of length $2n$ constructed in Step 1 of Section 6.1. We now construct a path $\omega'$ of length $2n$ which will consist only of rises and falls (with no level steps) as follows:

* if step $i$ in $\tilde{\omega}$ is a rise (fall resp.) then step $i$ in $\omega'$ is also a rise (fall resp.).

* if step $i$ in $\tilde{\omega}$ is a level step, then step $i$ in $\omega'$ is a rise if $i$ is even, else it is a fall when $i$ is odd.

We now note down the steps of $\omega'$ according to the different cycle types of indices in $\sigma$:

* if $i$ is a cycle valley (cycle peak resp.) in $\sigma$ then step $i$ in both $\tilde{\omega}$ and $\omega'$ are rises (falls resp.).
* if $i$ is a cycle double fall or an even fixed point in $\sigma$, $i$ must be even and step $i$ in $\tilde{\omega}$ must be a level step. Thus, step $i$ in $\omega'$ is a rise.

* similarly, if $i$ is a cycle double rise or an odd fixed point in $\sigma$, $i$ must be odd and step $i$ in $\tilde{\omega}$ must be a level step. Thus, step $i$ in $\omega'$ is a fall.

From this description, it is clear that the path $\omega'$ is identical to the almost-Dyck path $\omega$ which we just constructed. Furthermore, comparing $f_k$ in Lemma 7.1 with Equation 6.4, we get that Lemma 7.1 can be thought of as the relation between heights of steps in $\tilde{\omega}$ (given by $f_i$) and the corresponding heights in $\omega = \omega'$ (given by $h_i$).

For their first bijection, Deb and Sokal noted that the labels were exactly the same except for the treatment of fixed points; they said “The surprise was that the definitions of the labels in our constructions turned out to be almost identical to those employed in [34] (where “almost” means that fixed points are treated differently)”. We have shown here that even the path, and not just the labels, can be obtained from the bijection of Sokal and Zeng [34] (which we recalled in Section 6.1.) ■

## 7.1 Continued fractions using record classification: Proof of Theorems 4.1, 4.3, 4.4

We first recall the description of labels and the inverse bijection from [6, Sections 6.2, 6.3] in Subsection 7.1.1. We then reinterpret the inverse bijection in Subsection 7.1.3.

### 7.1.1 Description of labels and inverse bijection

**Step 2: Definition of the labels $\xi_i$.** We now recall the definition of the labels [6, eq. (6.9)]

$$ \xi_i = \begin{cases} \#\{j: \sigma(j) < \sigma(i) \le i < j\} & \text{if } i \text{ is even} \\ \#\{j: j < i \le \sigma(i) < \sigma(j)\} & \text{if } i \text{ is odd} \end{cases} \qquad (7.4) $$

The definition (7.4) can be written equivalently as [6, eq. (6.10)]

$$ \xi_i = \begin{cases} \#\{2l > 2k: \sigma(2l) < \sigma(2k)\} & \text{if } i = 2k \\ \#\{2l - 1 < 2k - 1: \sigma(2l - 1) > \sigma(2k - 1)\} & \text{if } i = 2k - 1 \end{cases} \qquad (7.5) $$

since $\sigma(j) < j$ implies that $j$ is even, and $j < \sigma(j)$ implies that $j$ is odd.
These definitions have a simple interpretation in terms of the nesting statistics defined in (1.10)/(2.3b,d):

$$ \xi_i = \begin{cases} \text{lnest}(i, \sigma) & \text{if } i \text{ is even and } \neq \sigma(i) \text{ [equivalently, } i > \sigma(i) \text{]} \\ \text{unest}(i, \sigma) & \text{if } i \text{ is odd and } \neq \sigma(i) \text{ [equivalently, } i < \sigma(i) \text{]} \\ \text{psnest}(i, \sigma) & \text{if } i = \sigma(i) \text{ (that is, } i \text{ is a fixed point)} \end{cases} \quad (7.6) $$

We state the inequalities (5.5)/(7.1) satisfied by the labels:

**Lemma 7.2 ([6, Lemma 6.3]).** We have

$$ 0 \le \xi_i \le \left\lfloor \frac{h_i - 1}{2} \right\rfloor = \left\lfloor \frac{h_{i-1}}{2} \right\rfloor \quad \text{if } \sigma^{-1}(i) \text{ is even (i.e., } s_i \text{ is a rise)} \quad (7.7a) $$

$$ 0 \le \xi_i \le \left\lfloor \frac{h_i}{2} \right\rfloor = \left\lfloor \frac{h_{i-1} - 1}{2} \right\rfloor \quad \text{if } \sigma^{-1}(i) \text{ is odd (i.e., } s_i \text{ is a fall)} \quad (7.7b) $$

To verify that the inequalities (7.7) are satisfied, we interpret $\left\lfloor \frac{h_i - 1}{2} \right\rfloor - \xi_i$ when $s_i$ is a rise, and $\left\lfloor \frac{h_i}{2} \right\rfloor - \xi_i$ when $s_i$ is a fall, in terms of the crossing statistics defined in (2.3a,c):

**Lemma 7.3 ([6, Lemma 6.4]).**

(a) If $s_i$ a rise and $i$ (hence also $h_i$) is odd, then

$$ \left\lfloor \frac{h_i - 1}{2} \right\rfloor - \xi_i = \text{ucross}(i, \sigma). \quad (7.8) $$

(b) If $s_i$ a rise and $i$ (hence also $h_i$) is even, then

$$ \left\lfloor \frac{h_i - 1}{2} \right\rfloor - \xi_i = \text{lcross}(i, \sigma) + \text{I}[\sigma(i) \neq i] \quad (7.9a) $$

$$ = \text{lcross}(i, \sigma) + \text{I}[i \text{ is a cycle double fall}] . \quad (7.9b) $$

(c) If $s_i$ a fall and $i$ (hence also $h_i$) is odd, then

$$ \left\lfloor \frac{h_i}{2} \right\rfloor - \xi_i = \text{ucross}(i, \sigma) + \text{I}[\sigma(i) \neq i] \quad (7.10a) $$

$$ = \text{ucross}(i, \sigma) + \text{I}[i \text{ is a cycle double rise}] . \quad (7.10b) $$
(d) If $s_i$ a fall and $i$ (hence also $h_i$) is even, then

$$ \left\lfloor \frac{h_i}{2} \right\rfloor - \xi_i = \mathrm{lcross}(i, \sigma). \qquad (7.11) $$

(Here $I[proposition] = 1$ if proposition is true, and $0$ if it is false.)

Since the quantities (7.8)-(7.11) are manifestly nonnegative, the inequalities (7.7) are satisfied.

**Step 3: Proof of bijection.** We recall the description of the inverse map for the mapping $\sigma \mapsto (\omega, \xi)$.

First, some preliminaries: Given a D-permutation $\sigma \in \mathfrak{D}_{2n}$ we can define four subsets of $[2n]$:

$$ F = \{2, 4, \dots, 2n\} = \text{even positions} \qquad (7.12a) $$

$$ F' = \{i: \sigma^{-1}(i) \text{ is even}\} = \{\sigma(2), \sigma(4), \dots, \sigma(2n)\} \qquad (7.12b) $$

$$ G = \{1, 3, \dots, 2n-1\} = \text{odd positions} \qquad (7.12c) $$

$$ G' = \{i: \sigma^{-1}(i) \text{ is odd}\} = \{\sigma(1), \sigma(3), \dots, \sigma(2n-1)\} \qquad (7.12d) $$

Note that $F'$ (resp. $G'$) are the positions of the rises (resp. falls) in the almost-Dyck path $\omega$.

Let us observe that

$$ F \cap F' = \text{cycle double falls and even fixed points} \qquad (7.13a) $$

$$ G \cap G' = \text{cycle double rises and odd fixed points} \qquad (7.13b) $$

$$ F \cap G' = \text{cycle peaks} \qquad (7.13c) $$

$$ F' \cap G = \text{cycle valleys} \qquad (7.13d) $$

$$ F \cap G = \emptyset \qquad (7.13e) $$

$$ F' \cap G' = \emptyset \qquad (7.13f) $$

We can now describe the map $(\omega, \xi) \mapsto \sigma$. Given the almost-Dyck path $\omega$, we can immediately reconstruct the sets $F, F', G, G'$. We now use the labels $\xi$ to reconstruct the maps $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ as follows: The even subword $\sigma(2)\sigma(4)\dots\sigma(2n)$ is a listing of $F'$ whose right-to-left inversion table is given by $q_\alpha = \xi_{2\alpha}$; this is the content of (7.5a). Similarly, the odd subword $\sigma(1)\sigma(3)\dots\sigma(2n-1)$ is a listing of $G'$ whose left-to-right inversion table is given by $p_\alpha = \xi_{2\alpha-1}$; this is the content of (7.5b).
**Remark 7.2.** Using Remark 7.1 and the fact that the description of labels (7.4) other than fixed points is exactly the same as that in (6.6), we can think of this bijection of Deb and Sokal [6, Sections 6.1-6.3] as almost a special case of the variant Foata-Zeilberger bijection of Sokal and Zeng [34, Section 6.1] when restricted to D-permutations, except for the treatment of fixed points; they are distinguished by parity. The odd fixed points are clubbed together with excedances and the even fixed points are clubbed together with anti-excedances.<fnref n="3" /> ■

### 7.1.2 Running example 2

Now let us take our second running example

$$ 
\begin{aligned}
\sigma &= 7192548610311121413 \\
&= (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathfrak{D}_{14}
\end{aligned}
\qquad (7.14) 
$$

which was depicted in Figure 2. From the cycle classification of $\sigma$, which was recorded in Equation (1.14), we immediately obtain the sets $F', G'$:

$$ F' = \{1, 2, 3, 4, 6, 12, 13\}, \qquad (7.15a) $$

$$ G' = \{5, 7, 8, 9, 10, 11, 14\}. \qquad (7.15b) $$

This also gives us the positions of rises and falls in the almost-Dyck path $\omega$ corresponding to $\sigma$ which has been drawn in Figure 9.

The labels $\xi_i$ are given in Equation (7.16).

$$ 
\begin{array}{l}
2i \in F \quad \begin{pmatrix} 2 & 4 & 6 & 8 & 10 & 12 & 14 \\ 1 & 2 & 4 & 6 & 3 & 12 & 13 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} \\
F' = \{\sigma(2i) \mid i \in [7]\} \\
\text{Right-to-left inversion table: } \xi_{2i}
\end{array}
\qquad (7.16a) 
$$

$$ 
\begin{array}{l}
2i - 1 \in G \quad \begin{pmatrix} 1 & 3 & 5 & 7 & 9 & 11 & 13 \\ 7 & 9 & 5 & 8 & 10 & 11 & 14 \\ 0 & 0 & 2 & 1 & 0 & 0 & 0 \end{pmatrix} \\
G' = \{\sigma(2i - 1) \mid i \in [7]\} \\
\text{Left-to-right inversion table: } \xi_{2i-1}
\end{array}
\qquad (7.16b) 
$$

<footnote n="3">³We thank the anonymous referee for their suggestion using which we were able to formalise why this bijection seems to be almost a special case of the bijection in Section 6.1.</footnote>
<figure><img src="image_12.png" /><figcaption>Figure 9: Almost Dyck path $\omega$ corresponding to the permutation
$\sigma = 7192548610311121413 = (1,7,8,6,4,2)(3,9,10)(5)(11)(12)(13,14) \in \mathcal{S}_{14}$.</figcaption></figure>

### 7.1.3 Combinatorial interpretation using Laguerre digraphs

The construction here will almost mirror the construction in Section 6.2. We will only include the necessary details and state the necessary lemmas and will omit most of the proofs.

We begin with an almost-Dyck path $\omega$ and an assignment of labels $\xi$ satisfying (7.7). The inverse bijection in Section 7.1.1 Step 3, gives us a D-permutation $\sigma$. We will again break this process into several intermediate steps and provide a reinterpretation using Laguerre digraphs. We will use the same conventions for denoting Laguerre digraphs as in Section 6.2.

Recall that the inverse bijection (Section 7.1.1 Step 3) begins by obtaining the sets $F, G$ (which are fixed for any given $n$) and $F', G'$ from the almost-Dyck path $\omega$. We then construct $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ separately by using the labels $\xi \upharpoonright F$ and $\xi \upharpoonright G$ respectively.

We again start with the digraph $L|_{\emptyset}$ and then go through the set $[2n]$. However, we first go through $F$ and then go through $G$, i.e., the order of our steps is now $2, 4, \dots, 2n, 2n-1, \dots, 3, 1$. In this situation, stage (a) will involve going through the even vertices in increasing order and then stage (b) will involve going through the odd vertices but in decreasing order. Thus, unlike the situation in Section 6.2, the FZ order corresponding to two different D-permutations $\sigma, \sigma' \in \mathcal{D}_{2n}$ are the same, irrespective of the underlying almost-Dyck path.

Let us now look at the intermediate Laguerre digraphs obtained during stages (a) and (b).
**Stage (a): Going through $F = \{2, 4, \dots, 2n\}$:**

We go through the even vertices in increasing order. From (7.13), we know that $F = \text{Cdfall}(\sigma) \cup \text{Evenfix}(\sigma) \cup \text{Cpeak}(\sigma)$ and $F' = \text{Cdfall}(\sigma) \cup \text{Evenfix}(\sigma) \cup \text{Cval}(\sigma)$ where $\sigma$ is the resulting D-permutation obtained at the end of the inverse bijection.

The construction here is similar to the construction in stage (b) Section 6.2. The connected components at the end of this stage can be described as follows:

**Lemma 7.4.** *The Laguerre digraph $L|_F$ consists of the following connected components:*

* loops on vertices $u \in \text{Evenfix}$,

* directed paths with at least two vertices, in which the initial vertex of the path is a cycle peak in $\sigma$ (i.e. contained in the set $F \cap G'$), the final vertex is a cycle valley in $\sigma$ (i.e. contained in the set $F' \cap G$), and the intermediate vertices (if any) are cycle double falls (which belong to the set $F \cap F'$).

* isolated vertices at $u \in G \cap G' = \text{Cdrise}(\sigma) \cup \text{Oddfix}(\sigma)$.

Furthermore, it contains no directed cycles.

**Stage (b): Going through $G = \{2n-1, \dots, 3, 1\}$:**

We now go through the odd vertices in decreasing order. From (7.13), we know that $G = \text{Cdrise}(\sigma) \cup \text{Oddfix}(\sigma) \cup \text{Cval}(\sigma)$, and $G' = \text{Cdrise}(\sigma) \cup \text{Oddfix}(\sigma) \cup \text{Cpeak}(\sigma)$, where $\sigma$ is the resulting D-permutation obtained at the end of the inverse bijection.

The construction here is similar to stage (c) in Section 6.2. The final vertices of a path with at least two vertices have the following description:

**Lemma 7.5.** Let $u$ be the final vertex of a path with at least two vertices in $L|_{F \cup \{2n-1, \dots, 2(n-j)+1\}}$ for some index $j$ ($1 \le j \le n$). Then $u \in \text{Cval}$.

Our definition of cycle closers is again the same as in Section 6.2. The following lemma classifies all cycle closers.

**Lemma 7.6. (Classifying cycle closers)** *Given a D-permutation $\sigma$, an element $u \in [2n]$ is a cycle closer if and only if it is a cycle valley minimum, i.e., it is the smallest element in its cycle.*

Next, we will count the number of cycle closers. But before doing that, we require a technical lemma similar to Lemma 6.6 for the case of permutations. However, first notice that if $i \in G \cap F' = \text{Cval}(\sigma)$, step $s_i$ must be a rise from height $h_{i-1}$ to height $h_i$ and hence, $h_{i-1} + 1 = h_i$. Also, from the interpretation of the heights in Lemma 7.1, we must have $\lceil h_{i-1}/2 \rceil + 1 = \lceil (h_i + 1)/2 \rceil = f_i$.

**Lemma 7.7.** *Given a D-permutation $\sigma$ and associated sets $F', G'$ and an odd
$y \in \{2n-1, \dots, 3, 1\}$ such that $y \in G \cap F' = \text{Cval}$. Then the following is true:

$$ \begin{aligned} \#\{u \in G' \setminus \{\sigma(2n-1), \sigma(2n-3), \dots, \sigma(y+2)\} : u > y\} &= \lceil h_{y-1}/2 \rceil + 1 \\ &= \lceil (h_y + 1)/2 \rceil \\ &= f_y \end{aligned} \tag{7.17} $$

where $h_i$ denotes the height at position $i$ of the almost-Dyck path $\omega$ associated to $\sigma$ in Step 1, and $f_i$ is defined in (7.3).

*Proof.* We first establish the following equality of sets:

$$ \{u > y : \sigma^{-1}(u) \le y\} = \{u \in G' \setminus \{\sigma(2n-1), \sigma(2n-3), \dots, \sigma(y+2)\} : u > y\}. \tag{7.18} $$

Whenever $u \in G'$, we have that $\sigma^{-1}(u) \in G$ (by description of $G$, $G'$ in (7.12)). Additionally, if $u \notin \{\sigma(2n-1), \sigma(2n-3), \dots, \sigma(y+2)\}$ then it must be that $\sigma^{-1}(u) \le y$. This establishes the containment

$$ \{u > y : \sigma^{-1}(u) \le y\} \supset \{u \in G' \setminus \{\sigma(2n-1), \sigma(2n-3), \dots, \sigma(y+2)\} : u > y\}. $$

On the other hand, if $u > y$ and $\sigma^{-1}(u) \le y$, then $u > \sigma^{-1}(u)$ and as $\sigma$ is a D-permutation, $\sigma^{-1}(u)$ must be odd. Therefore, $u \in G'$. As $\sigma^{-1}(u) \le y$, $u$ cannot be one of $\sigma(y+2), \dots, \sigma(2n-3), \sigma(2n-1)$. Therefore, $u \in G' \setminus \{\sigma(2n-1), \sigma(2n-3), \dots, \sigma(y+2)\}$. This establishes (7.18).

To obtain Equation (7.17), it suffices to show that the cardinality of the set $\{u > y : \sigma^{-1}(u) \le y\}$ is $f_y$. To do this, recall the description of $f_y$ in Equation (7.3) and observe that

$$ \begin{aligned} f_y &= \#\{u \le y : \sigma(u) > y\} \\ &= \#\{u > y : \sigma^{-1}(u) \le y\} \end{aligned} \tag{7.19} $$

where the second equality is obtained by replacing $u$ with $\sigma^{-1}(u)$. $\square$

We are now ready to state the counting of cycle closers.

**Lemma 7.8 (Counting of cycle closers for D-permutations).** Fix an almost-Dyck path $\omega$ of length $2n$ and construct $F', G'$ (these are completely determined by $\omega$). Also fix labels $\xi_u$ for vertices $u \in \{2, 4, \dots, 2n\} \cup \{2n-1, \dots, 2(n-j)+1\}$ satisfying (7.7). Also let $y = 2(n-j)-1 \in G \cap F' = \text{Cval}(\sigma)$. Then

(a) The value of $\xi_y$ completely determines if $y$ is a cycle closer or not.

(b) There is exactly one value $\xi_y \in \{0, 1, \dots, \lceil h_{y-1}/2 \rceil\}$ that makes $y$ a cycle closer, and conversely.
**Remark 7.3.** Notice that one can also construct a variant of this interpretation where stage (b) occurs before stage (a). The role of cycle closer will then be played by cycle peak maximum. ■

### 7.1.4 Running example 2

Let us now look at the DS history of our running example for D-permutation

$$ 
\begin{aligned}
\sigma &= 7192548610311121413 \\
&= (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathcal{D}_{14}.
\end{aligned} 
\quad (7.20) $$

It consists of the following stages:

* Stage (a): 2, 4, 6, 8, 10, 12, 14

* Stage (b): 13, 11, 9, 7, 5, 3, 1

Stage (a) of the history of $\sigma$ has been drawn in Figure 10 and Stage (b) has been drawn in Figure 11. Non-singleton cycles are formed in Stage (b) when the edges $13 \to 14$, $3 \to 9$ and $1 \to 7$ are inserted.

### 7.1.5 Computation of weights

The steps in this subsection will be similar to that in Section 6.4. We first assign weights to each index $i \in [2n]$ of a given D-permutation $\sigma \in \mathcal{D}_{2n}$, and then the weight of a permutation is defined to be the weights of its indices. We then use the bijection to transfer the weights to 0-Schröder paths and then factorise the total weight for each of the steps which then finally leads us to Theorem 4.4.

The index weights are assigned as follows:

* if $i$ is a cycle valley minimum, we set $\text{wt}(i) = \lambda a_{\text{ucross}(i,\sigma)+\text{unest}(i,\sigma)}$. For all other cycle valleys, we set $\text{wt}(i) = a_{\text{ucross}(i,\sigma)+\text{unest}(i,\sigma)}$,

* if $i$ is a cycle peak, we set $\text{wt}(i) = b_{\text{lcross}(i,\sigma), \text{lnest}(i,\sigma)}$,

* if $i$ is a cycle double fall, we set $\text{wt}(i) = c_{\text{lcross}(i,\sigma), \text{lnest}(i,\sigma)}$,

* if $i$ is a cycle double rise, we set $\text{wt}(i) = d_{\text{ucross}(i,\sigma), \text{unest}(i,\sigma)}$,

* and finally, if $i$ is a fixed point, we set

$$ \text{wt}(i) = \begin{cases} \lambda e_{\text{psnest}(i,\sigma)} & \text{if } i \text{ is even} \\ \lambda f_{\text{psnest}(i,\sigma)} & \text{if } i \text{ is odd} \end{cases} $$
<table><caption>Stage (b): $G = \{13, 11, 9, 7, 5, 3, 1\}$ in decreasing order</caption><tbody><tr><td>L|{2,4,6,8,10,12,14,13}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11,9}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11,9,7}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11,9,7,5}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11,9,7,5,3}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr><tr><td>L|{2,4,6,8,10,12,14,13,11,9,7,5,3,1}</td><td>1 2 4<br>●<br>7 8 6</td><td>3<br>●<br>9 10</td><td>13<br>●<br>14</td><td>●<br>5 11 12</td></tr></tbody></table>

<caption>Figure 11: Stage (b) of the DS history for the D-permutation</caption>

$$ \sigma = 719254861031121413 = (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathcal{D}_{14}. $$
We set the weight of the D-permutation $\sigma$ to be $wt(\sigma) = \prod_{i=1}^{2n} wt(i)$. It is clear that our polynomial $\hat{Q}_n$ defined in (4.9) is simply $\hat{Q}_n(\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}, \lambda) = \sum_{\sigma \in \mathcal{D}_{2n}} wt(\sigma)$.

We now use the bijection $\sigma \mapsto (\hat{\omega}, \xi)$ to transfer the weights $wt(i)$ onto the pair $(\hat{\omega}, \xi)$. As our polynomial $\hat{Q}$ is almost the same as the polynomial introduced in [6, eq. (3.30)] except for the extra factor $\lambda^{\text{cyc}(\sigma)}$ and the index of $\mathbf{a}$, the dependence on cycle peaks, cycle double rises, cycle double falls, are same as in [6, eq. (3.30)] but the treatment of cycle valleys and also fixed points is different. As we use the same bijection used to obtain the continued fraction ([6, eq. (3.31)/(3.32)]) the computation of weights corresponding to the variables $\mathbf{b}, \mathbf{c}, \mathbf{d}$ are going to be exactly the same. The weights corresponding to the fixed points are almost same except $\mathbf{e}_k$ and $\mathbf{f}_k$ are now replaced with $\lambda \mathbf{e}_k$ and $\lambda \mathbf{f}_k$, respectively. Hence, we skip the details for all cycle types and the corresponding steps in the 0-Schröder path $\hat{\omega}$ except for cycle valleys.

Let us now compute the weights contributed by cycle valleys. These correspond to steps $s_i$ in $\hat{\omega}$ where $s_i$ is a rise starting at height $h_{i-1} = 2k$. Then from Equations (7.6)/(7.8) we get $\lceil(h_{i-1}-1)/2\rceil = \lceil h_i/2\rceil = \text{ucross}(i, \sigma) + \text{unest}(i, \sigma) (= k)$. Also among the possible choices of labels $\xi \in [0, k]$ there is exactly one which closes a cycle and the others don't (Lemma 7.8). Therefore, we obtain

$$a_{2k} \stackrel{\text{def}}{=} \sum_{\xi} a_{2k,\xi} = (\lambda + k)\mathbf{a}_{2k}. \qquad (7.21)$$

This completes the proof of Theorem 4.4. $\square$
PROOF OF THEOREM 4.3. Specialise Theorem 4.4 to

$$a_{k-1} = p_{+1}^{k-1} \times y_1 \qquad (7.22)$$

$$b_{k-1-\xi, \xi} = p_{-1}^{k-1-\xi} q_{-1}^{\xi} \times \begin{cases} x_1 & \text{if } \xi = 0 \\ u_1 & \text{if } 1 \le \xi \le k-1 \end{cases} \qquad (7.23)$$

$$c_{k-1-\xi, \xi} = p_{-2}^{k-1-\xi} q_{-2}^{\xi} \times \begin{cases} x_2 & \text{if } \xi = 0 \\ u_2 & \text{if } 1 \le \xi \le k-1 \end{cases} \qquad (7.24)$$

$$d_{k-1-\xi, \xi} = p_{+2}^{k-1-\xi} q_{+2}^{\xi} \times \begin{cases} y_2 & \text{if } \xi = 0 \\ v_2 & \text{if } 1 \le \xi \le k-1 \end{cases} \qquad (7.25)$$

$$e_k = \begin{cases} z_e & \text{if } k = 0 \\ s_e^k w_e & \text{if } k \ge 1 \end{cases} \qquad (7.26)$$

$$f_k = \begin{cases} z_o & \text{if } k = 0 \\ s_o^k w_o & \text{if } k \ge 1 \end{cases} \qquad (7.27)$$

<figure><img src="image_13.png" /></figure>

**Remark 7.4.** Notice that the specialisation in the above proof is almost the same as [6, eq. (6.40-45)], except for the treatment of a. ■

PROOF OF THEOREM 4.1. Specialise Theorem 4.3 to

$$p_{+1} = p_{-1} = p_{+2} = p_{-2} = q_{-1} = q_{+2} = q_{-2} = s_e = s_o = 1. \qquad (7.28)$$

<figure><img src="image_14.png" /></figure>

## 7.2 Continued fractions using variant record classification: Proof of Theorems 4.5, 4.6, 4.7

We first recall the description of the alternate labels and the inverse bijection from [6, Section 6.5] in Subsection 7.2.1. We then reinterpret the inverse bijection in Subsection 7.2.3.

### 7.2.1 Description of labels and inverse bijection

**Step 2: Definition of the labels $\hat{\xi}_i$.**
We recall the alternate definition of labels introduced in [6, eq. (6.46)]

$$ \hat{\xi}_i = \begin{cases} \#\{2l > 2k: \sigma(2l) < \sigma(2k)\} & \text{if } i = \sigma(2k) \\ \#\{2l - 1 < 2k - 1: \sigma(2l - 1) > \sigma(2k - 1)\} & \text{if } i = \sigma(2k - 1) \end{cases} \qquad (7.29a) $$

$$ = \begin{cases} \#\{j: j < i \le \sigma^{-1}(i) < \sigma^{-1}(j)\} & \text{if } \sigma^{-1}(i) \text{ is even} \\ \#\{j: \sigma^{-1}(j) < \sigma^{-1}(i) \le i < j\} & \text{if } \sigma^{-1}(i) \text{ is odd} \end{cases} \qquad (7.29b) $$

These labels have a simple interpretation, but now we use the variant nesting statistics (2.4b,d).

**Lemma 7.9** ([6, Lemma 6.7]). We have

$$ \hat{\xi}_i = \begin{cases} \text{lnest}'(i, \sigma) & \text{if } \sigma^{-1}(i) \text{ is even (i.e., } s_i \text{ is a rise) and } i \neq i \\ \text{unest}'(i, \sigma) & \text{if } \sigma^{-1}(i) \text{ is odd (i.e., } s_i \text{ is a fall) and } i \neq i \\ \text{psnest}(i, \sigma) & \text{if } \sigma^{-1}(i) = i \text{ (i.e., } i \text{ is a fixed point)} \end{cases} \qquad (7.30) $$

The labels $\hat{\xi}_i$ satisfy the following inequalities:

**Lemma 7.10** ([6, Lemma 6.8]). We have

$$ 0 \le \hat{\xi}_i \le \left\lfloor \frac{h_i - 1}{2} \right\rfloor = \left\lfloor \frac{h_{i-1}}{2} \right\rfloor \quad \text{if } \sigma^{-1}(i) \text{ is even (i.e., } s_i \text{ is a rise)} \qquad (7.31a) $$

$$ 0 \le \hat{\xi}_i \le \left\lfloor \frac{h_i}{2} \right\rfloor = \left\lfloor \frac{h_{i-1} - 1}{2} \right\rfloor \quad \text{if } \sigma^{-1}(i) \text{ is odd (i.e., } s_i \text{ is a fall)} \qquad (7.31b) $$

The inequalities (7.31) are proved by providing an interpretation of the variant crossing statistics defined in (2.4a,c) in terms of these labels.

**Lemma 7.11** ([6, Lemma 6.9]).

(a) If $s_i$ a rise (i.e. $\sigma^{-1}(i)$ is even), then

$$ \left\lfloor \frac{h_i - 1}{2} \right\rfloor - \hat{\xi}_i = \text{lcross}'(i, \sigma) + \text{I}[i \text{ is even and } \sigma(i) \neq i] \qquad (7.32a) $$

$$ = \text{lcross}'(i, \sigma) + \text{I}[i \text{ is a cycle double fall}] . \qquad (7.32b) $$

(b) If $s_i$ a fall (i.e. $\sigma^{-1}(i)$ is odd), then

$$ \left\lfloor \frac{h_i}{2} \right\rfloor - \hat{\xi}_i = \text{ucross}'(i, \sigma) + \text{I}[i \text{ is odd and } \sigma(i) \neq i] \qquad (7.33a) $$

$$ = \text{ucross}'(i, \sigma) + \text{I}[i \text{ is a cycle double rise}] . \qquad (7.33b) $$
Since the quantities (7.32), (7.33) are manifestly nonnegative, the inequalities (7.31) are satisfied.

**Step 3: Proof of bijection.** The proof is similar to that presented in Step 3 Section 7.1.1, but using a value-based rather than position-based notion of inversion table. Recall that if $S = \{s_1 < s_2 < \dots < s_k\}$ is a totally ordered set of cardinality $k$, and $\boldsymbol{x} = (x_1, \dots, x_k)$ is a permutation of $S$, then the (left-to-right) (position-based) inversion table corresponding to $\boldsymbol{x}$ is the sequence $\boldsymbol{p} = (p_1, \dots, p_k)$ of nonnegative integers defined by $p_\alpha = \#\{\beta < \alpha : x_\beta > x_\alpha\}$. We now define the (left-to-right) *value-based inversion table* $\boldsymbol{p}'$ by $p'_{x_i} = p_i$; note that $\boldsymbol{p}'$ is a map from $S$ to $\{0, \dots, k-1\}$, such that $p'_{x_i}$ is the number of entries to the left of $x_i$ (in the word $\boldsymbol{x}$) that are larger than $x_i$. In particular, $0 \le p'_{s_i} \le k-i$. Given the value-based inversion table $\boldsymbol{p}'$, we can reconstruct the sequence $\boldsymbol{x}$ by working from largest to smallest value, as follows [22, section 5.1.1]: We start from an empty sequence, and insert $s_k$. Then we insert $s_{k-1}$ so that the resulting word has $p'_{s_{k-1}}$ entries to its left. Next we insert $s_{k-2}$ so that the resulting word has $p'_{s_{k-2}}$ entries to its left, and so on. [The right-to-left value-based inversion table $\boldsymbol{q}'$ is defined analogously, and the reconstruction proceeds from smallest to largest.]

We now recall the definitions

$$F = \{2, 4, \dots, 2n\} = \text{even positions} \qquad (7.34a)$$

$$F' = \{i: \sigma^{-1}(i) \text{ is even}\} = \{\sigma(2), \sigma(4), \dots, \sigma(2n)\} \qquad (7.34b)$$

$$G = \{1, 3, \dots, 2n-1\} = \text{odd positions} \qquad (7.34c)$$

$$G' = \{i: \sigma^{-1}(i) \text{ is odd}\} = \{\sigma(1), \sigma(3), \dots, \sigma(2n-1)\} \qquad (7.34d)$$

Note that $F'$ (resp. $G'$) are the positions of the rises (resp. falls) in the almost-Dyck path $\omega$.

We can now describe the map $(\omega, \hat{\xi}) \mapsto \sigma$. Given the almost-Dyck path $\omega$, we can immediately reconstruct the sets $F, F', G, G'$. We now use the labels $\hat{\xi}$ to reconstruct the maps $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ as follows: The even subword $\sigma(2)\sigma(4)\dots\sigma(2n)$ is a listing of $F'$ whose right-to-left value-based inversion table is given by $q'_i = \hat{\xi}_i$ for all $i \in F'$; this is the content of (7.29a). Similarly, the odd subword $\sigma(1)\sigma(3)\dots\sigma(2n-1)$ is a listing of $G'$ whose left-to-right value-based inversion table is given by $p'_i = \hat{\xi}_i$ for all $i \in G'$; this again is the content of (7.29a).

Additionally, we state a lemma which gives an alternate way of constructing a value-based inversion table for D-permutation.

**Lemma 7.12.** Let $\sigma \in \mathfrak{D}_{2n}$ and let $(\omega, \hat{\xi})$ be its associated almost-Dyck path with an assignment of labels determined by (7.29). Also let $G' = \{x_1 < \dots < x_n\}$ and let $F' = \{y_1 < \dots < y_n\}$. Then
(a) For any index $j$ ($1 \le j \le n$), $\sigma^{-1}(x_j)$ is the $(\hat{\xi}_{x_j} + 1)$th smallest element of $G \setminus \{\sigma^{-1}(x_1), \dots, \sigma^{-1}(x_{j-1})\}$.

(b) For any index $j$ ($1 \le j \le n$), $\sigma^{-1}(y_j)$ is the $(\hat{\xi}_{y_j} + 1)$th largest element of $F \setminus \{\sigma^{-1}(y_n), \dots, \sigma^{-1}(y_{j+1})\}$.

This lemma can be proved using (7.29a) and we omit the details.

**Remark 7.5.** For this bijection, a comment similar to Remark 7.2 can be made. As mentioned earlier in Remark 6.1, Foata and Zeilberger used value-based inversion tables for their presentation of the bijection. We think that it is possible to write a variant of the Foata-Zeilberger bijection in which fixed points are treated separately and for which the definition of the Motzkin path is identical to the one in Step 1 of Section 6.1 but the description of the labels will be different. We expect that the inversion tables used in the reverse bijection to be value-based. We refrain from writing out the details. With this, the bijection in this section can be seen as almost a special case of this variant Foata-Zeilberger bijection except for the treatment of fixed points. ■

### 7.2.2 Running example 2

Now let us take our second running example

$$ 
\begin{aligned}
\sigma &= 719254861031121413 \\
&= (1, 7, 8, 6, 4, 2) (3, 9, 10) (5) (11) (12) (13, 14) \in \mathcal{D}_{14}
\end{aligned} 
\qquad (7.35) 
$$

which was depicted in Figure 2. The almost-Dyck path is the same as the one in Figure 9. The sets $F', G'$ were also already recorded in (7.15).

The labels $\xi_i$ in (7.36) are now assigned to $\sigma(i)$:

$$ 
\begin{array}{l@{\qquad}l}
2i \in F & F' = \{\sigma(2i) \mid i \in [7]\} \begin{pmatrix} 2 & 4 & 6 & 8 & 10 & 12 & 14 \\ 1 & 2 & 4 & 6 & 3 & 12 & 13 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} \quad (7.36a) \\ \\
\text{Right-to-left inversion table: } \hat{\xi}_{\sigma(2i)} & 
\end{array} 
$$

$$ 
\begin{array}{l@{\qquad}l}
2i - 1 \in G & G' = \{\sigma(2i - 1) \mid i \in [7]\} \begin{pmatrix} 1 & 3 & 5 & 7 & 9 & 11 & 13 \\ 7 & 9 & 5 & 8 & 10 & 11 & 14 \\ 0 & 0 & 2 & 1 & 0 & 0 & 0 \end{pmatrix} \quad (7.36b) \\ \\
\text{Left-to-right inversion table: } \hat{\xi}_{\sigma(2i-1)} & 
\end{array} 
$$
### 7.2.3 Combinatorial interpretation using Laguerre digraphs

The construction here will again be similar to those in Sections 6.2 and 7.1.3. We will only include the necessary details and state the necessary lemmas, and will omit most of the proofs.

We begin with an almost-Dyck path $\omega$ and an assignment of labels $\hat{\xi}$ satisfying (7.31). The inverse bijection in Section 7.2.1 Step 3, gives us a D-permutation $\sigma$. We will again break this process into several intermediate steps and provide a reinterpretation using Laguerre digraphs.

This time however, we will use a different convention for denoting Laguerre digraphs than the one used in Sections 6.2 and 7.1.3. Let $\sigma \in \mathfrak{S}_n$ be a permutation on $[n]$. For $S \subseteq [n]$, we let $L'|_S$ denote the subgraph of $L^\sigma$, containing the same set of vertices $[n]$, but only containing the edges $\sigma^{-1}(i) \to i$, whenever $i \in S$ (we are allowed to have $\sigma^{-1}(i) \notin S$). Thus, $L'|_{[n]} = L^\sigma$, and $L'|_\emptyset = L^\sigma|_\emptyset$ is the digraph containing $n$ vertices and no edges. Whenever the permutation $\sigma$ is understood, we shall drop the superscript and denote it as $L'|_S$.

Now, let $\sigma \in \mathfrak{D}_{2n}$ be a D-permutation. Similar to the construction in Section 7.1.1, recall that the inverse bijection begins by obtaining the sets $F, G, F', G'$ (the sets $F, G$ are fixed for any given $n$ and the sets $F', G'$ are obtained from the almost-Dyck path $\omega$). We then construct $\sigma \upharpoonright F: F \to F'$ and $\sigma \upharpoonright G: G \to G'$ separately but by using the labels $\hat{\xi} \upharpoonright F'$ and $\hat{\xi} \upharpoonright G'$ respectively.

In this interpretation, we start with the digraph $L'|_\emptyset$ and then go through the set $[2n]$. This time, we first go through the elements of $G'$ in increasing order (stage (a)) and then through the elements of $F'$ in decreasing order (stage (b)). We call this the *variant DS order* on the set $[2n]$.

Here however, the history that we consider is different from the one in Section 7.1.3. Let $u_1, \dots, u_{2n}$ be a rewriting of $[2n]$ as per the variant DS order. We now consider the “variant DS history” $L'|_\emptyset \subset L'|_{\{u_1\}} \subset L'|_{\{u_1, u_2\}} \subset \dots \subset L'|_{\{u_1, \dots, u_{2n}\}} = L$. Thus, at step $u$ as per the variant DS order, we use the (value-based) inversion tables and Lemma 7.12 to construct the edge $\sigma^{-1}(u) \to u$. Similar to the previous histories, at each step we insert a new edge into the digraph, and at the end of this process, the resulting digraph obtained is the permutation $\sigma$ in cycle notation.

Let us now look at the intermediate Laguerre digraphs obtained during stages (a) and (b).

**Stage (a): Going through $G'$:**

From (7.34), we know that $G = \text{Cdrise}(\sigma) \cup \text{Oddfix}(\sigma) \cup \text{Cval}(\sigma)$ and $G' = \text{Cdrise}(\sigma) \cup \text{Oddfix}(\sigma) \cup \text{Cpeak}(\sigma)$ where $\sigma$ is the resulting D-permutation obtained at the end of the
inverse bijection.

The connected components at the end of this stage can be described as follows:

**Lemma 7.13.** *The Laguerre digraph $L'|_{G'}$ consists of the following connected components:*

• loops on vertices $u \in \text{Oddfix}$,

• directed paths with at least two vertices, in which the initial vertex of the path is a cycle valley in $\sigma$ (i.e. contained in the set $F' \cap G$) and the final vertex is a cycle peak in $\sigma$ (i.e. contained in the set $F \cap G'$), and the intermediate vertices (if any) are cycle double rises (which belong to the set $G \cap G'$).

• isolated vertices at $u \in F \cap F' = \text{Cdfall}(\sigma) \cup \text{Evenfix}(\sigma)$.

Furthermore, it contains no directed cycles.

**Stage (b): Going through $F'$:**

We now go through the elements of $F'$ in decreasing order. From (7.34), we know that $F = \text{Cdfall}(\sigma) \cup \text{Evenfix}(\sigma) \cup \text{Cpeak}(\sigma)$ and $F' = \text{Cdfall}(\sigma) \cup \text{Evenfix}(\sigma) \cup \text{Cval}(\sigma)$ where $\sigma$ is the resulting D-permutation obtained at the end of the inverse bijection. We let $F' = \{y_1 < \dots < y_n\}$.

This time, we describe the *initial vertices* of paths with at least two vertices (and not the final vertices):

**Lemma 7.14.** *Let $u$ be the initial vertex of a path with at least two vertices in $L'|_{G' \cup \{y_n, \dots, y_{j+1}\}}$ for some index $j$ ($1 \le j \le n$). Then $u \in \text{Cval}$.*

Our definition of cycle closers here is different. Let $u_1, \dots, u_{2n}$ be the vertices $[2n]$ arranged according to the variant DS order. We say that $u_j \in [2n]$ is a *cycle closer* if the edge $\sigma^{-1}(u_j) \to u_j$ is introduced in $L'|_{\{u_1, \dots, u_{j-1}\}}$ as an edge between the two ends of a path turning the path to a cycle. The following lemma classifies all cycle closers.

**Lemma 7.15.** *(Classifying cycle closers)* *Given a D-permutation $\sigma$, an element $u \in [2n]$ is a cycle closer if and only if it is a cycle valley minimum, i.e., it is the smallest element in its cycle.*

Next, we will count the number of cycle closers. But before doing that, we require a technical lemma similar to Lemmas 6.6, 7.7. (As before, recall that if $i \in G \cap F' = \text{Cval}(\sigma)$, step $s_i$ must be a rise from height $h_{i-1}$ to height $h_i$ and hence, $h_{i-1} + 1 = h_i$. Also, from the interpretation of the heights in Lemma 7.1, we must have $\lceil h_{i-1}/2 \rceil + 1 = \lceil (h_i+1)/2 \rceil = f_i$.)

**Lemma 7.16.** *Given a D-permutation $\sigma$ and associated sets $F, G, F', G'$ where $F' = \{y_1 < \dots < y_n\}$, and an index $j$ ($1 \le j \le n$) such that $y_j \in G \cap F' = \text{Cval}$. Then the following*
is true:

$$ \#\{u \in F\setminus\{\sigma^{-1}(y_n), \dots, \sigma^{-1}(y_{j+1})\}: u > y_j\} = \lceil h_{y_j-1}/2 \rceil + 1 = \lceil (h_{y_j}+1)/2 \rceil = f_{y_j} \quad (7.37) $$

where $h_i$ denotes the height at position $i$ of the almost-Dyck path $\omega$ associated to $\sigma$ in Step 1 and $f_i$ is defined in (7.3).

*Proof.* Notice the equality of the following sets:

$$ \{u \in F\setminus\{\sigma^{-1}(y_n), \dots, \sigma^{-1}(y_{j+1})\}: u > y_j\} = \{u > y_j: \sigma(u) \le y_j\}. \quad (7.38) $$

Next use (7.3) to notice that the set on the right hand side of (7.38) has cardinality $f_{y_j}$. $\square$

We are now ready to count the number of cycle closers.

**Lemma 7.17** (Counting of cycle closers for D-permutations using variant labels). Fix an almost-Dyck path $\omega$ of length $2n$ and construct $F'$, $G'$ (these are completely determined by $\omega$). Let $y_j \in G \cap F'$. Also fix labels $\hat{\xi}_u$ for vertices $u \in G' \cup \{y_n, \dots, y_{j+1}\}$ satisfying (7.31). Then

(a) The value of $\hat{\xi}_{y_j}$ completely determines if $y_j$ is a cycle closer or not.

(b) There is exactly one value $\hat{\xi}_{y_j} \in \{0, 1, \dots, \lceil h_{y_j-1}/2 \rceil\}$ that makes $y_j$ a cycle closer, and conversely.

### 7.2.4 Running example 2

Let us now look at the variant DS history of our running example for D-permutation $\sigma = 719254861031121413 = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathcal{D}_{14}$. The sets $G'$ and $F'$ are $G' = \{5, 7, 8, 9, 10, 11, 14\}$ and $F' = \{13, 12, 6, 4, 3, 2, 1\}$. The variant DS order consists of the following stages:

* Stage (a): $G' = \{5, 7, 8, 9, 10, 11, 14\}$ in increasing order

* Stage (b): $F' = \{13, 12, 6, 4, 3, 2, 1\}$ in decreasing order

Stage (a) of the history of $\sigma$ has been drawn in Figure 12 and Stage (b) has been drawn in Figure 13. Non-singleton cycles are formed in Stage (b) when the edges $14 \to 13$, $10 \to 3$ and $2 \to 1$ are inserted.

### 7.2.5 Computation of weights

*PROOF OF THEOREM 4.7.* The computation of weights is completely analogous to what was done in Section 7.1.5, but using Lemma 7.17 in place of Lemma 7.8. We leave the details to the reader: the upshot (similar to the proof of [6, Theorem 3.12]) is that for cycle
<figure><img src="image_15.png" /><figcaption>Figure 12: Stage (a) of the variant DS history for the D-permutation
$\sigma = 719254861031121413 = (1, 7, 8, 6, 4, 2)(3, 9, 10)(5)(11)(12)(13, 14) \in \mathcal{D}_{14}$.</figcaption></figure>
valleys and cycle peaks, “u” and “l” are interchanged compared to Section 7.1.5, and all
the statistics are primed. It therefore completes the proof of Theorem 4.7. □

PROOF OF THEOREMS 4.6 AND 4.5. Comparing (4.14) with (4.16) we see that the needed specialisation in (4.16) are the same as given in (7.22)–(7.27). Inserting these into Theorem 4.7 gives Theorem 4.6.

Similarly, the proof of Theorem 4.5 follows by specialising the weights in Theorem 4.6
to (7.28). □

**8 Final remarks**

We began this work only hoping to prove [34, Conjecture 2.3]. Our initial guess was that
this would involve constructing a new bijection from permutations to labelled Motzkin
paths, possibly by tweaking the Biane bijection [3]. However, on discovering our proof, we
were surprised to see that not only did we not construct any new bijection, but we used
the same variant of the Foata–Zeilberger bijection, which Sokal and Zeng use to prove their
“first” continued fractions for permutations. As the proofs of the “first” theorems in [6] for
D-permutations are *parallel* to the proofs of the “first” theorems in [34] for permutations
(as mentioned in [6, Section 8]), we managed to then prove [30, Conjecture 12] and [6,
Conjecture 4.1].

We had to introduce a new total order on $[n]$ ($[2n]$ for D-permutations) to describe
histories for these bijections. The crucial reason why our proof works is that the total
order is the same for any given Motzkin path (almost-Dyck path for D-permutations),
and also because the associated weights are commutative. Thus, the order in which we
multiply them has no effect on the product as long as we stick to the same order for any
given path.

On the other hand, Flajolet [12] provides a more general combinatorial interpretation
with non-commutative weights, as long as these weights are multiplied using the natural
order of the path. With this in mind, we think that it will probably not be too difficult
to generalize the “second” theorems for permutations in [34], and for D-permutations in
[6] to obtain continued fractions with non-commutative weights. We predict that this will
also be possible for continued fractions obtained using the Françon–Viennot bijection [17].
However, why such continued fractions might be of interest is not immediate to us, and at
the present moment, we refrain from working out the details.
Acknowledgements

We wish to thank Alan Sokal and Jiang Zeng for helpful conversations and for their advice on drafts of this work. We also thank Ashvni Narayanan for her comments on the title and abstract of this paper. We thank the anonymous referees whose comments have vastly improved the exposition of this paper.

This work was supported by a teaching assistantship from the Department of Mathemat-
ics, University College London. The author is currently supported by the DIMERS project
ANR-18-CE40-0033 funded by Agence Nationale de la Recherche (ANR, France).

References

[1] D. Barsky, Congruences pour les nombres de Genocchi de 2e espèce [extrait d'un tra-vail en commun avec Dominique Dumont], Groupe d'étude d'Analyse ultramétrique, 8e année (1980/81), Exposé no. 34, 13 pp.

[2] N. Blitvić and E. Steingrimsson, Permutations, moments, measures, Trans. Amer. Math. Soc. **374**, 5473-5508 (2021).

[3] P. Biane, Permutations suivant le type d'excédance et le nombre d'inversions et interprétation combinatoire d'une fraction continue de Heine, European J. Combin. **14**, 277-284 (1993).

[4] S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math. **38**, 149–163 (2007).

[5] B. Deb, A. Dyachenko, M. Pétréolle and A.D. Sokal, Lattice paths and branched continued fractions III: Generalizations of the Laguerre, rook and Lah polynomials, preprint (December 2023), arXiv:2312.11081 [math.CO] at arXiv.org.

[6] B. Deb and A.D. Sokal, Classical continued fractions for some multivariate polyno-
mials generalizing the Genocchi and median Genocchi numbers, Adv. Appl. Math. **161**, 102756 (2024).

[7] D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. **41**, 305–318 (1974).

[8] D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. **132**, 37–49 (1994).

[9] D. Dumont and J. Zeng, Further results on the Euler and Genocchi numbers, Aequationes Math. **47**, 31–42 (1994).
[10] A. Elvey Price and A.D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, Electron. J. Combin. **27**(4), article P4.6 (2020).

[11] L. Euler, De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae **5**, 205-237 (1760); reprinted in *Opera Omnia*, ser. 1, vol. 14, pp. 585-617. [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E247.html]

[12] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. **32**, 125-161 (1980).

[13] P. Flajolet and R. Sedgewick, *Analytic Combinatorics* (Cambridge University Press, Cambridge, 2009).

[14] D. Foata and V. Strehl, Combinatorics of Laguerre polynomials, in *Enumeration and Design*, edited by D.M. Jackson and S.A. Vanstone (Academic Press, Toronto, 1984), pp. 123-140.

[15] D. Foata and D. Zeilberger, Denert's permutation statistic is indeed Euler-Mahonian, *Stud. Appl. Math.* **83**, 31-59 (1990).

[16] D. Foata and G.-N. Han, *Principes de combinatoire classique: Cours et exercices corrigés* (Université Louis Pasteur, Strasbourg, Département de mathématique, 2008). Available on-line at https://irma.math.unistra.fr/~foata/AlgComb.pdf

[17] J. Françon and G. Viennot, Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d'Euler et nombres de Genocchi. Discrete Mathematics, **28**(1) 21-35 (1979).

[18] E. Fusy and E. Guitter, Comparing two statistical ensembles of quadrangulations: A continued fraction approach, Ann. Inst. Henri Poincaré D **4**, 125-176 (2017).

[19] G.-N. Han and J.-Y. Liu, Combinatorial proofs of some properties of tangent and Genocchi numbers, European J. Combin. **71**, 99-110 (2018).

[20] G.-N. Han and J. Zeng, On a *q*-sequence that generalizes the median Genocchi numbers, Ann. Sci. Math. Québec **23**, 63-72 (1999).

[21] M. Josuat-Vergès, A *q*-analog of Schläfli and Gould identities on Stirling numbers, *Ramanujan J.* **46**, 483-507 (2018).

[22] D.E. Knuth, *The Art of Computer Programming*, vol. 3, 2nd ed. (Addison-Wesley, Reading MA, 1998).

[23] A.L. Lazar, The homogenized Linear arrangement and its consequences in enumerative combinatorics, Ph.D. thesis, University of Miami (August 2020),
[24] A. Lazar and M.L. Wachs, The homogenized Linial arrangement and Genocchi numbers, arXiv:1910.07651 [math.CO], Combin. Theory 2, issue 1, paper no. 2 (2022), 34 pp.

[25] É. Lucas, Sur les théorèmes de Binet et de Staudt concernant les nombres de Bernoulli, Nouvelles Annales de Mathématiques (2ᵉ série) **16**, 157-160 (1877).

[26] The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org

[27] R. Oste and J. Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electron. J. Combin. **22**, no. 2, #P2.8 (2015).

[28] Q. Pan and J. Zeng, Cycles of even-odd drop permutations and continued fractions of Genocchi numbers, J. Combin. Theory A **199**, no. 105778 (2023).

[29] A. Randrianarivony, Fractions continues, *q*-nombres de Catalan et *q*-polynômes de Genocchi, Europ. J. Combin. **18**, 75-92 (1997).

[30] A. Randrianarivony and J. Zeng, Some equidistributed statistics on Genocchi permutations, Electron. J. Combin. **3**, no. 2, Research Paper #22 (1996), 11 pp.

[31] A. Randrianarivony, Moments des polynômes orthogonaux unitaires de Sheffer généralisés et spécialisations, European J. Combin. **19**, 507-518 (1998).

[32] A.D. Sokal, Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials, in preparation.

[33] A.D. Sokal, Multiple Laguerre polynomials: Combinatorial model and Stieltjes moment representation, Amer. Math. Soc. **150**, 1997-2005 (2022).

[34] A.D. Sokal and J. Zeng, Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions, Adv. Appl. Math. **138**, 102341 (2022).

[35] R.P. Stanley, *Enumerative Combinatorics*, vol. 1, Second Edition, Cambridge University Press, 2012.

[36] G. Viennot, Interprétations combinatoires des nombres d'Euler et de Genocchi, Séminaire de Théorie des Nombres (Bordeaux), Année 1980-81, exposé no. 11 (1981).
https://www.jstor.org/stable/44165433

[37] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Notes de conférences données à l'Université du Québec à Montréal, septembre-octobre 1983. Available on-line at http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html