# Cyclic sieving phenomena via combinatorics of continued fractions

Bishal Deb

► To cite this version:

Bishal Deb. Cyclic sieving phenomena via combinatorics of continued fractions. 2025. hal-05236499

HAL Id: hal-05236499

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

Preprint submitted on 2 Sep 2025

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Cyclic sieving phenomena
via combinatorics of continued fractions

Bishal Deb¹

¹Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China

August 17, 2025

## Abstract

We will exhibit several instances of the cyclic sieving phenomenon involving statistics and involutions on the following combinatorial families of objects: permutations, set partitions, perfect matchings, D-permutations (and its subclasses). Our results will be based on continued fraction identities enumerating these objects. Our instances of cyclic sieving phenomenon for permutations involve the Corteel involution; this was first studied by Adams, Elder, Lafrenière, McNicholas, Striker and Welch (arxiv 2024). We will reprove several of their results using our setting of continued fractions; we will also prove two of their conjectures. Our study of set partitions and perfect matchings will involve the Kasraoui-Zeng involution and the Chen-Deng-Du-Stanley-Yan (CDDSY) involution. Finally, for D-permutations, we will construct a new involution which we call the Genocchi-Corteel involution. The common feature of all of these involutions, other than the CDDSY involution, is that they are constructed via bijections to weighted lattice paths, and that they exchange crossings and nestings on their respective objects.

**Key Words:** Cyclic sieving phenomenon, continued fractions, permutation, set partition, perfect matching, Genocchi numbers, median Genocchi numbers, D-permutation, D-semiderangement, D-derangement, FindStat, crossing, nesting

**Mathematics Subject Classification (MSC 2020) codes:** 05A19 (Primary); 05A05, 05A10, 05A15, 05A18, 05E18, 30B70
# Contents

<table><tr><td>1</td><td>Introduction</td><td>4</td></tr><tr><td>1.1</td><td>The cyclic sieving phenomena</td><td>6</td></tr><tr><td>1.2</td><td>Outline of the paper</td><td>7</td></tr><tr><td>2</td><td>Labelled Dyck, Motzkin and Schröder paths</td><td>7</td></tr><tr><td>3</td><td>Permutations</td><td>8</td></tr><tr><td>3.1</td><td>Permutation statistics</td><td>9</td></tr><tr><td>3.2</td><td>Reformulation of an identity of Deb using cycle valley minima</td><td>9</td></tr><tr><td>3.3</td><td>The Corteel involution on permutations</td><td>11</td></tr><tr><td>3.4</td><td>Sokal and Zeng's multivariate polynomials enumerating cyclic statistics on permutations</td><td>13</td></tr><tr><td>3.5</td><td>Instances of the cyclic sieving phenomenon</td><td>15</td></tr><tr><td>3.6</td><td>Some more instances of the cyclic sieving phenomenon</td><td>17</td></tr><tr><td>3.7</td><td>Equidistribution of wexx and cdes: Proof of [1, Conjecture 4.24]</td><td>18</td></tr><tr><td>3.8</td><td>Cyclic sieving phenomenon for Statistic 123: Proof of [1, Conjecture 4.23]</td><td>20</td></tr><tr><td>4</td><td>Set partitions</td><td>22</td></tr><tr><td>4.1</td><td>Statistics on set partitions</td><td>23</td></tr><tr><td>4.2</td><td>The Kasraoui-Zeng involution on set partitions</td><td>25</td></tr><tr><td>4.3</td><td>The Chen-Deng-Du-Stanley-Yan (CDDSY) involution on set partitions</td><td>26</td></tr><tr><td>4.4</td><td>Sokal and Zeng's multivariate polynomials enumerating statistics on set partitions</td><td>28</td></tr><tr><td>4.5</td><td>Instances of the cyclic sieving phenomenon</td><td>29</td></tr><tr><td>4.6</td><td>A remark on Mahonian statistics on set partitions</td><td>31</td></tr><tr><td>5</td><td>Perfect matchings</td><td>32</td></tr><tr><td>5.1</td><td>Statistics on perfect matchings</td><td>32</td></tr><tr><td>5.2</td><td>The Kasraoui-Zeng involution on perfect matchings</td><td>33</td></tr><tr><td>5.3</td><td>The Chen-Deng-Du-Stanley-Yan (CDDSY) involution on perfect matchings</td><td>34</td></tr><tr><td>5.4</td><td>Sokal and Zeng's multivariate polynomials enumerating statistics on perfect matchings</td><td>35</td></tr><tr><td>5.5</td><td>Instances of the cyclic sieving phenomenon</td><td>36</td></tr><tr><td>6</td><td>D-permutations and its subfamilies</td><td>38</td></tr><tr><td>6.1</td><td>Genocchi, median Genocchi numbers, and D-permutations</td><td>38</td></tr><tr><td>6.2</td><td>Deb-Sokal bijection and the Genocchi-Corteel involution</td><td>39</td></tr><tr><td>6.3</td><td>Deb and Sokal's multivariate polynomials enumerating statistics on D-permutations and its subclasses</td><td>42</td></tr><tr><td>6.4</td><td>Instances of the cyclic sieving phenomenon on D-permutations</td><td>44</td></tr></table>
<table><tr><td>6.5 Instances of the cyclic sieving phenomenon on D-semiderangements and D-derangements</td><td>45</td></tr><tr><td>A Positivity conjectures on distribution of vincular patterns</td><td>46</td></tr></table>
# 1 Introduction

The purpose of this paper is to exhibit several instances of the cyclic sieving phenomenon (see Section 1.1 for definitions) using the combinatorics of continued fractions. We will specifically study the following combinatorial families of objects: permutations, set partitions, perfect matchings, D-permutations.

In a recent work, Adams, Elder, Lafrenière, McNicholas, Striker and Welch [1], carried out a systematic search for instances of the cyclic sieving phenomenon on permutations. They searched the entire FindStat database [40] for maps and statistics on permutations. Their study involved three classes of involutions on permutations which they showed to be instances of the $q = -1$ phenomenon of Stembridge [44]. Along with several other contributions, Adams et al initiated the study of the *Corteel involution* [40, Map 239], [11] in the context of the cyclic sieving phenomenon. This involution uses the Foata-Zeilberger bijection [22]; it exchanges the number of crossings and nestings in permutations and is constructed by taking “complement” of associated labelled Motzkin paths. In this present paper, we continue this study that Adams et al initiated for the Corteel involution. This paper attempts to convince the reader that a natural setting to obtain instances of the cyclic sieving phenomenon with respect to the Corteel involution is via the combinatorial theory of continued fractions for multivariate polynomials counting permutation statistics. We will study this in great detail in Section 3.

Our first main result in this context is Proposition 3.5 where we provide a very general recipe to construct instances of the cyclic sieving phenomenon via three multivariate polynomials (3.4), (3.15), (3.16). Using this general recipe, we will reprove several, but not all, of the results from [1, Section 4]. Our second contribution in this context is to prove [1, Conjecture 4.24]; this conjecture asks for the equidistribution of two different permutation statistics:

**Conjecture 1.1 ([1, Conjecture 4.24]).** The number of weak excedances that are also mid-points of a decreasing subsequence of length 3 (Statistic 373 in FindStat) is equidistributed with the cycle descent number (Statistic 317 in FindStat) and thus exhibits the cyclic sieving phenomenon under involutions with 1 point for $n = 0$ and $2^{n-1}$ points for all $n \ge 1$. In particular, this statistic exhibits the cyclic sieving phenomenon with respect to the Corteel involution.

We will prove this conjecture in Theorem 3.11. We will need two ingredients for our proof, the first ingredient is to rewrite the two statistics in terms of simpler statistics; we do this in Lemma 3.10. The second ingredient, which we also think is independently an important contribution, is to reformulate a theorem of Deb [13, Theorem 3.1] in terms of *cycle valley minima*. This reformulation is in the same spirit as what was done in [13, Section 4.3] and in [14, Section 4.1.3]; this has been done in Theorem 3.1. The original theorem of Deb was first conjectured by Sokal and Zeng [43, Theorem 3.1].
Our third contribution for permutations is the proof of another conjecture of Adams et al [1, Conjecture 4.23]. We do this in Section 3.8. However, the general tools used in the rest of this paper do not work in this situation. We instead modify a proof of Adams et al to prove this result.

The Corteel involution forms the prototypical involution in this work. After our study involving permutations, we will look at other combinatorial objects and analogous maps. For set partitions, studied in Section 4, we will use an involution due to Kasraoui and Zeng [26]; for perfect matchings, studied in Section 5, we will study the restriction of this involution. The **Kasraoui–Zeng involution** also exchanges crossings and nestings, but on set partitions and perfect matchings, and is described by taking complements of labelled Motzkin paths (these are now the *Charlier diagrams* of Viennot [48].) For both of these objects, we will again provide a general recipe to construct instances of the cyclic sieving phenomenon, see Propositions 4.4 and 5.4. We show that the number of fixed points of these involutions are the *odd Fibonacci numbers* $F_{2n-1}$ [33, A001519] (Lemma 4.1) and 1 (Lemma 5.1), respectively.

Another involution on set partitions and perfect matchings is the **Chen–Deng–Du–Stanley–Yan (CDDSY) involution** [8]. Chen et al construct a bijection between set partitions and *vacillating tableaux*, which are certain walks on the Young's lattice. They use this bijection to construct their involution. We show that this involution also has the same number of fixed points as the Kasraoui–Zeng involution (Lemmas 4.3 and 5.3).

We will then shift our attention to *D-permutations* (Section 6); these are a class of permutations of $[2n]$ and are counted by the median Genocchi numbers. They were introduced by Lazar during his PhD [27, 28, 29]. More recently, Deb and Sokal constructed a bijection that resembles the Foata–Zeilberger bijection [14, Section 6]. Hence it is natural to ask if there is an adaptation of the Corteel involution to this setting. We will introduce such an involution in our paper (Section 6.2); we will call this the **Genocchi–Corteel involution**. Our construction is such that it can be restricted to the subclasses of *D-semiderangements* and also *D-derangements*. We count the number of fixed points for D-permutations and its subclasses of D-semiderangements, and D-derangements in Corollary 6.4; the number of fixed points are given by $2^n F_{2n-1}$ [33, A154626], $3^{n-1}$ [33, A133494] and $2^{n-1}$ [33, A011782], respectively. We will then use this involution on D-permutation and its subclasses to exhibit the cyclic sieving phenomena for various statistics; we provide a general recipe for this in Propositions 6.5 and 6.7.

We conclude this introduction with three remarks:

1. Prior to the work in [1], the method of searching the FindStat database for instances of dynamical phenomena was pioneered by Elder, Lafreniére, McNicholas, Striker, and Welch in [19]. In this article, the authors searched the FindStat database for pairs of maps and statistics which were instances of the *homomesy phenomenon*.
2. At this moment, the FindStat database contains statistics on set partitions and perfect matchings. It will be interesting to perform a systematic search on these classes for the cyclic sieving phenomenon similar to the search performed by Adams et al in [1].

3. An important ingredient of our results is plugging in $-1$ in some known continued fraction identity to yield a simple rational function. We mention a recent work [15] where results were obtained by plugging in $-1$ to a statistic, viz. to the number of cycles.

The rest of this introduction is structured as follows: in Section 1.1, we define the cyclic sieving phenomenon. Then in Section 1.2, we provide the outline of the rest of this paper.

## 1.1 The cyclic sieving phenomena

The cyclic sieving phenomenon was introduced by Reiner, Stanton and White [38]; also see the nice survey article of Sagan [41] and also [39].

Let $X$ be a finite set (usually a set of combinatorial objects). Next, let $C$ be a finite cyclic group of order $n$ with an action on $X$. Given $g \in C$, we use $X^g$ to denote the elements of $X$ invariant under the action of $g$, i.e.

$$X^g = \{y \in X : g \cdot y = y\}. \qquad (1.1)$$

Let $\omega$ be a generator of the group $C$, i.e., $C = \langle\omega\rangle$. We are now ready to define the cyclic sieving phenomenon.

**Definition 1.2.** Given a set $X$, a polynomial $f(q)$, and an action of $C$ on $X$, the triple $(X, C, f(q))$ exhibits the *cyclic sieving phenomenon* if, for all $d$ we have

$$|X^{\omega^d}| = f\left(\exp\left(2\pi i \frac{d}{n}\right)\right). \qquad (1.2)$$

Notice that when $d = n$, the identity (1.2) implies that $f(1) = |X|$. Thus, the coefficients of the polynomial $f(q)$ should sum up to the cardinality of $X$. For our purposes, $f(q)$ will be the generating polynomial of some statistic on the set $X$.

When $n = 2$, the action of the generator $\omega$ gives a bijection on the set $X$, $x \mapsto \omega \cdot x$. This bijection is, in fact, an involution. This special case, was first introduced as the “$q = -1$ phenomenon” by Stembridge [44]. Exhibiting the cyclic sieving phenomenon in this case is equivalent to showing that $f(1) = |X|$, and that $f(-1) = |X^\omega|$, the number of fixed points of the involution $x \mapsto \omega \cdot x$. In this paper, our instances of the cyclic sieving phenomenon will all be instances of the “$q = -1$” phenomenon.
The main idea in this paper can be summarised as follows: Let $(S_n)_{n \ge 0}$ be a com-
binatorial family of objects and let $\text{Stat} : S_n \to \mathbb{N}$ be some statistics on this set. Let
$F(t; q) = \sum_{n=0}^{\infty} \sum_{\sigma \in S_n} q^{\text{Stat}(\sigma)} t^n$ be its bivariate ordinary generating function. Here the
indeterminate $q$ will keep track of this statistic and $t$ will keep track of the set $S_n$. Also,
let $\phi_n : S_n \to S_n$ be an involution such that the number fixed points of this involution is
$a_n$. We think of this involution as the action of $\omega$ on the set $S_n$ where $\omega^2 = \text{id}_C$. Then
exhibiting the cyclic sieving phenomenon is equivalent to showing $F(t; -1) = \sum_{n=0}^{\infty} a_n t^n$.
We will specifically look at generating functions $F(t; q)$ which can be expressed as a nice
classical continued fraction; this will simplify the evaluation of the substitution $F(t; -1)$
and our results will seem to be easy consequences. Following [1], we will say that the statis-
tic Stat exhibits the cyclic sieving phenomenon to mean that the corresponding generating
polynomial $\sum_{\sigma \in S_n} q^{\text{Stat}(\sigma)}$ exhibits the cyclic sieving phenomenon.

## 1.2 Outline of the paper

The rest of the paper is structured as follows: in Section 2 we will establish notation for labelled Dyck, Motzkin and Schröder paths. We will then present in Sections 3–6 our results for permutations, set partitions, perfect matchings and finally, D-permutations and its subclasses.

In Appendix A, we present some positivity conjectures on the enumeration of certain
vincular patterns in permutations which we discovered while writing this paper.

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

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 $D = \bigcup_{n=0}^{\infty} D_{2n}$.

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.

Let $\mathcal{A} = (A_h)_{h \ge 0}$, $\mathcal{B} = (B_h)_{h \ge 1}$ and $\mathcal{C} = (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} \qquad (2.1) $$

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 $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 $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled Schröder path in an analogous way; now the sets $C_h$ refer to long level steps. We denote by $S_{2n}(\mathcal{A}, \mathcal{B}, \mathcal{C})$ the set of $(\mathcal{A}, \mathcal{B}, \mathcal{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 $\omega$ is forbidden to take a step of the specified kind starting at the specified height.

## 3 Permutations

It is well known that the generating function of factorials can be represented as Stieltjes-type and Jacobi-type continued fractions as follows:

$$ \sum_{n=0}^{\infty} n! t^n = \frac{1}{1 - \frac{t}{1 - \frac{t}{1 - \frac{2t}{1 - \frac{2t}{1 - \dots}}}}} = \frac{1}{1 - t - \frac{t}{1 - 3t - \frac{4t}{1 - 5t - \frac{9t}{1 - \dots}}}}. \qquad (3.1) $$
We will use various generalisations of this identity in this section. We will replace $n!$ with various polynomials enumerating statistics on permutations.

In Section 3.1, we introduce notation for permutation statistics to be used in the rest of this paper. Then in Section 3.2, we reformulate a result of Deb [13, Theorem 3.1]; this will be one of our main technical tools to prove Conjecture 1.1. After this, we recall the Corteel involution in Section 3.3 in terms of weighted paths. Then in Section 3.4, we recall various multivariate polynomials studied by Sokal and Zeng in [43]. With this background, in Section 3.5, we then state a recipe for producing instances of the cyclic sieving phenomenon on permutations involving the Corteel involution and the Sokal–Zeng polynomials; here we reprove some of the results of Adams et al, viz., [1, Theorems 4.7,4.15] and the first statement in [1, Corollary 4.8]. Then in Section 3.6, we exhibit the cyclic sieving phenomenon for the count of some vincular patterns; these statistics are not covered by the Sokal–Zeng polynomials. Here, we will reprove the second and third statements in [1, Corollary 4.8] but we are unable to prove [1, Theorem 4.20].

In Section 3.7, we will prove Conjecture 1.1 and reprove [1, Theorem 4.10] using our continued-fractions set up. Finally, in Section 3.8, we will prove [1, Conjecture 4.23], respectively. However, for this result, we rely on another technique. In particular, we will use the notion of *positional marked patterns* and an involution defined by Adams et al.

## 3.1 Permutation statistics

We will use the glossary of permutation statistics as stated in [12, Section 2.5]; this includes the record-and-cycle classification [12, Section 2.5.1], and crossings and nestings [12, Section 2.5.2].

We will now describe a few additional statistics which will be used in this section. Given a permutation $\sigma \in \mathfrak{S}_n$, we use $wexx(\sigma)$ to denote [40, Statistic 373]: it is the number of weak excedances that are also mid-points of a decreasing subsequence of length 3, i.e.,

$$ wexx(\sigma) = |\{j : j \le \sigma(j)\} \cap \{j : \exists i, k \text{ with } i < j < k \text{ and } \sigma(i) > \sigma(j) > \sigma(k)\}|, \quad (3.2) $$

Also let $cdes(\sigma)$ denote *the cycle descent number* given in [40, Statistic 317], i.e.,

$$ cdes(\sigma) = |\{i : i > \sigma(i) \text{ and } \sigma(i) \text{ is not the smallest element in its cycle}\}|. \quad (3.3) $$

## 3.2 Reformulation of an identity of Deb using cycle valley minima

Few years ago, Sokal and Zeng [43] carried out a detailed investigation of continued fractions enumerating permutations, set partitions and perfect matchings with respect to
a large (sometimes infinite) defined in number of independent statistics. They conjectured a continued fraction for permutations [43, Conjecture 2.3], which was recently proved by Deb [13, Theorem 3.1]. However, [13, Theorem 3.1] does not explicitly include the count of the statistic *cycle valley minima* (minval).

The main purpose of this section is to state a reformulation of this result that includes the count of cycle valley minima; this reformulation is in the same spirit as what was done by Deb and Sokal in [14, Section 4.1.3] and by Deb in [13, Section 4.3]. Our result will help us to prove [1, Theorem 4.10 and Conjecture 4.24] in Section 3.7.

For a permutation $\sigma \in \mathfrak{S}_n$, a non-singleton cycle contains precisely one maximum element, which is necessarily a cycle peak, and precisely one minimum element, which is necessarily a cycle valley. We now introduce a polynomial that is similar to Sokal and Zeng's first master polynomial for permutations [43, eq. (2.23)], except the classification of cycle valleys as records or non-records is replaced by the classification of cycle valleys as minima or non-minima:

$$ \tilde{Q}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, \mathbf{w}) = \sum_{\sigma \in \mathfrak{S}_n} x_1^{\text{eareccpeak}(\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)} \mathbf{w}^{\text{fix}(\sigma)} \quad (3.4) $$

where

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

We have the following theorem:

**Theorem 3.1** (Reformulation of [13, Theorem 3.1] using cycle valley minima). *The ordinary generating function of the polynomials $\tilde{Q}_n$ defined in (3.4) has a Jacobi-type continued fraction*

$$ \sum_{n=0}^{\infty} \tilde{Q}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, \mathbf{w}) t^n = \frac{1}{1 - w_0 t - \frac{x_1 \tilde{y}_1 t^2}{1 - (x_2+y_2+w_1)t - \frac{(x_1+u_1)(\tilde{y}_1+\tilde{v}_1)t^2}{1 - (x_2+u_2+y_2+v_2+w_2)t - \frac{(x_1+2u_1)(\tilde{y}_1+2\tilde{v}_1)t^2}{1-\dots}}}} \quad (3.6) $$
with coefficients

$$ \gamma_0 = w_0 \qquad (3.7a) $$

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

$$ \beta_n = [x_1+(n-1)u_1][\tilde{y}_1+(n-1)\tilde{v}_1] \qquad (3.7c) $$

*Proof.* The proof follows from the proof of [13, Theorem 3.1] the only difference being that we replace the factor $(\lambda+n-1)y_1$ in [13, eq. (3.2c)] with the factor $\tilde{y}_1+(n-1)\tilde{v}_1$. We can do this because the variable $\tilde{y}_1$ now keeps track of cycle valley minima, (which were shown to be cycle closers in [13, Lemma 6.6]) and $\tilde{v}_1$ keep track of the other cycle valleys. $\square$

**Remark 3.2.** Note that the factors $\lambda$ multiplying the variables $w_n$ corresponding to fixed points in [13, Theorem 3.1] have now disappeared because we are no longer giving such factors to singleton cycles. Even more strikingly, our reformulation in Theorem 3.1 now looks identical to Sokal and Zeng's [43, Theorem 2.2] except that $y_1, v_1$ have been replaced by $\tilde{y}_1, \tilde{v}_1$; we will soon state this in Theorem 3.2'. Moreover, Deb's second and third versions of continued fractions for permutation [13, Theorems 3.2 and 3.3], respectively, can also be rewritten in a similar way, but we refrain from writing out the details.

## 3.3 The Corteel involution on permutations

In [11, Proposition 4], Corteel showed that the number of permutations with $l$ crossings and $m$ nestings is equal to the number of permutations with $m$ crossings and $l$ nestings.<fnref n="1" /> Her proof implicitly used an involution on permutations but this was only explicitly written down in [40, Map 239].

Corteel used the Foata-Zeilberger [22] bijection to construct her involution on permutations. This bijection 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 [37, 11, 6, 43]). More recently, Deb provided a reinterpretation of this bijection in terms of Laguerre digraphs [13]; we will follow his presentation.

$$ \text{crossings} = \text{ucross} + \text{lcross} + \text{cdrise} \qquad (3.8a) $$

$$ \text{nestings} = \text{unest} + \text{lnest} + \text{psnest} \qquad (3.8b) $$

See the historical remarks in [43, Section 2.5] for more on this story.

<footnote n="1">¹Warning: We should warn the reader that Corteel's definitions of crossings and nesting is different from ours; hers can be expressed in our notation as follows</footnote>
The Foata-Zeilberger bijection (as stated in [13, Section 6.1]) is a bijective correspondence between $\mathfrak{S}_n$ and the set of $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled Motzkin paths of length $n$, where the labels $\xi_i$ lie in the sets

$$ \mathcal{A}_h = \{0, \dots, h\} \qquad \text{for } h \ge 0 \qquad (3.9a) $$

$$ \mathcal{B}_h = \{0, \dots, h-1\} \qquad \text{for } h \ge 1 \qquad (3.9b) $$

$$ \mathcal{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 \qquad (3.9c) $$

where

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

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

$$ C_h^{(3)} = \{0\} \qquad \text{for } h \ge 0 \qquad (3.10c) $$

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$). Let $\mathfrak{SM}_n$ denote this set of $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled Motzkin paths of length $n$ with label sets given by (3.9), (3.10). The Foata-Zeilberger bijection as per [13, Section 6.1] is a bijective map $\varphi_n^{\text{FZ}} : \mathfrak{SM}_n \to \mathfrak{SM}_n$. For the convenience of the reader, we relate our terminology to that of Corteel's [11, Section 3.1]:

* rises correspond to steps $N$,

* falls correspond to steps $S$,

* level steps of type 1 correspond to steps $\bar{E}$,

* Corteel considers cycle double rises and fixed points together, and hence, her steps $E$ correspond to both level steps of types 2 and 3.

For what follows, we denote by $c_0, c_1, c_2, \dots, c_h$ the following labels at a level step at height $h$:

$$ c_i = \begin{cases} (3,0) & \text{if } i = h \\ (2,i) & \text{otherwise} \end{cases} \qquad (3.11) $$

$$ \text{Thus, } C_h = (\{1\} \times C_h^{(1)}) \cup \{c_0, \dots, c_h\}. $$

We will now describe an involution $\phi_n : \mathfrak{SM}_n \to \mathfrak{SM}_n$; the Corteel involution will then be obtained by the composition of bijections $(\varphi_n^{\text{FZ}})^{-1} \circ \phi_n \circ \varphi_n^{\text{FZ}}$.

Let $(\omega, \xi) \in \mathfrak{SM}_n$ where $\xi = (\xi_1, \dots, \xi_n)$. Let $\xi^c = (\xi_1^c, \dots, \xi_n^c)$ be a sequence where $\xi_i^c$
is given by

$$ \xi_i^c = \begin{cases} h - \xi_i & \text{if step } i \text{ is a rise} \\ h - 1 - \xi_i & \text{if step } i \text{ is a fall} \\ (1, h - 1 - k) & \text{if step } i \text{ is a level step of type 1 and } \xi_i = (1, k) \\ c_{h-k} & \text{if step } i \text{ is a level step of types 2 or 3 and } \xi_i = c_k \end{cases} \qquad (3.12) $$

It is clearly follows that $(\omega, \xi^c) \in \mathfrak{SM}_n$ and that $(\xi^c)^c = \xi$. Thus, the map $(\omega, \xi) \mapsto (\omega, \xi^c)$ is an involution on the set $\mathfrak{SM}_n$; we use $\phi_n$ to denote this involution. The Corteel involution on permutations is the the map $\phi_n^C := (\phi_n^{FZ})^{-1} \circ \phi_n \circ \phi_n^{FZ}$.

An important property of the Corteel involution is that crossings and nestings, in the sense of Corteel, are exchanged. More precisely, we state this in the following proposition without proof.

**Proposition 3.3.** For a permutation $\sigma \in \mathfrak{S}_n$ define $\hat{\sigma} := \phi_n^C(\sigma)$. Then if an index $i \in [n]$ is a cycle peak, cycle valley, or a cycle double fall in $\sigma$, it continues to have the same cycle type in $\hat{\sigma}$; if $i \in \text{Cdrise}(\sigma) \cup \text{Fix}(\sigma)$ then $i \in \text{Cdrise}(\hat{\sigma}) \cup \text{Fix}(\hat{\sigma})$. Also, we have the following equidistribution

$$ \begin{aligned} & (\text{ucross}(\sigma) + \text{lcross}(\sigma) + \text{cdrise}(\sigma), \text{unest}(\sigma) + \text{lnest}(\sigma) + \text{psnest}(\sigma)) \\ & = (\text{unest}(\hat{\sigma}) + \text{lnest}(\hat{\sigma}) + \text{psnest}(\hat{\sigma}), \text{ucross}(\hat{\sigma}) + \text{lcross}(\hat{\sigma}) + \text{cdrise}(\hat{\sigma})). \end{aligned} \qquad (3.13) $$

Adams et al counted the number of fixed points of the Corteel involution which we now recall.

**Lemma 3.4 ([1, Lemma 4]).** The number of fixed points of $\mathfrak{S}_n$ under the action of the Corteel involution $\phi_n^C$ is 1 when $n = 0$ and $2^{n-1}$ when $n \ge 1$.

Additionally, we mention that that this sequence has the following Jacobi-type continued fraction, albeit of finite depth:

$$ 1 + \sum_{n=1}^{\infty} 2^{n-1} t^n = \frac{1}{1 - t - \frac{t^2}{1-t}}. \qquad (3.14) $$

## 3.4 Sokal and Zeng's multivariate polynomials enumerating cyclic statistics on permutations

In this section, we recall two of Sokal and Zeng's multivariate polynomials enumerating statistics on permutations; first we shall state the first polynomial [43, eq. (2.23)], then we shall state their first $p, q$-generalisation involving crossings and nestings [43, eq. (2.51)]. We recall that we will use the glossary of permutation statistics as stated in [12, Section 2.5];
this includes the record-and-cycle classification [12, Section 2.5.1], and crossings and nestings [12, Section 2.5.2].

We first recall the polynomial [43, eq. (2.23)]:

$$Q_n^{(1)}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}) = \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)} \quad (3.15)$$

where $\mathbf{w}^{\text{fix}(\sigma)}$ was defined in (3.5). The polynomials (3.15) have a beautiful J-fraction [43, Theorem 2.2].

Next we recall the polynomial [43, eq. (2.51)] which is a p,q-generalisation of the polynomials $Q_n^{(1)}$:

$$Q_n^{(2)}(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) = \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)} \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)}. \quad (3.16)$$

These polynomials (3.16) also have a nice continued fraction [43, Theorem 2.7]. Sokal and Zeng have also introduced several other multivariate polynomials in their paper, in particular, their second polynomials involve the count of cycles. We, however, refrain from working with those. We will instead use our polynomial (3.4) which has the continued fraction in Theorem 3.1 which generalises their second J-fraction [43, Theorem 2.4].

Notice that we can use [43, Theorem 2.2] to restate Theorem 3.1.

**Theorem 3.2.** *The ordinary generating function of the polynomials*

$\tilde{Q}_n(x_1, x_2, \tilde{y}_1, y_2, u_1, u_2, \tilde{v}_1, v_2, \mathbf{w})$ defined in (3.4) along with the substitution $\tilde{y}_1 = y_1, \tilde{v}_1 = v_1$ has the same Jacobi-type continued fraction as the polynomial $Q_n^{(1)}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w})$ given in [43, Theorem 2.2]. Therefore,

$$\tilde{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}) = Q_n^{(1)}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w}). \quad (3.17)$$
## 3.5 Instances of the cyclic sieving phenomenon

We are now ready to state instances of the cyclic sieving phenomena on permutations with respect to the Corteel involution or as a matter of fact, for any involution having 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$.

We first state a very general result in Proposition 3.5.

**Proposition 3.5.** Let Stat : $\mathfrak{S}_n \to \mathbb{N}$ be a statistic defined on permutations. In each of the following cases the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions that have 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$.

(a) Stat is obtained as a specialisation of the polynomial

$Q_n^{(1)}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w})$ defined in (3.15), i.e., there exists polynomials $x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q) \in \mathbb{R}[q]$ and $w_k(q) \in \mathbb{R}[q]$ for $k \ge 0$ satisfying

$$ \sum_{\sigma \in \mathfrak{S}_n} q^{\text{Stat}} = Q_n^{(1)} \left( x_1(q), x_2(q), y_1(q), y_2(q), u_1(q), u_2(q), v_1(q), v_2(q), (w_k(q))_{k \ge 0} \right) \quad (3.18) $$

for all $n \ge 0$. Further assume that the following equations are satisfied

$$ x_1(-1) \cdot y_1(-1) = 1 \quad (3.19a) $$

$$ w_0(-1) = 1 \quad (3.19b) $$

$$ x_2(-1) + y_2(-1) + w_1(-1) = 1 \quad (3.19c) $$

$$ \left[ x_1(-1) + u_1(-1) \right] \times \left[ y_1(-1) + v_1(-1) \right] = 0 \quad (3.19d) $$

(b) Stat is obtained as a specialisation of the polynomial

$\tilde{Q}_n(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, \mathbf{w})$ defined in (3.4). Also assume that equations (3.19) with $y_1, v_1$ replaced by $\tilde{y}_1, \tilde{v}_1$ are satisfied.

(c) Stat is obtained as a specialisation of the polynomial

$Q_n^{(2)}(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)$ defined in (3.16), i.e., there exists polynomials $x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q), p_{+1}(q), p_{+2}(q), p_{-1}(q), p_{-2}(q), q_{+1}(q), q_{+2}(q), q_{-1}(q), q_{-2}(q), s(q) \in \mathbb{R}[q]$ and $w_k(q) \in \mathbb{R}[q]$ for $k \ge 0$ such that

$$ \sum_{\sigma \in \mathfrak{S}_n} q^{\text{Stat}} = Q_n^{(2)} \left( x_1(q), x_2(q), y_1(q), y_2(q), u_1(q), u_2(q), v_1(q), v_2(q), (w_k(q))_{k \ge 0}, p_{+1}(q), p_{+2}(q), p_{-1}(q), p_{-2}(q), q_{+1}(q), q_{+2}(q), q_{-1}(q), q_{-2}(q), s(q) \right) \quad (3.20) $$
for all $n \ge 0$. Further assume that the equations (3.19a,b) along with the following equations are satisfied

$$x_2(-1) + y_2(-1) + s(-1) \cdot w_1(-1) = 1 \quad (3.21a)$$

$$\left[ p_{-1}(-1) \cdot x_1(-1) + q_{-1}(-1) \cdot u_1(-1) \right] \times$$

$$\left[ p_{+1}(-1) \cdot y_1(-1) + q_{+1}(-1) \cdot v_1(-1) \right] = 0 \quad (3.21b)$$

*Proof.* (a) We replace the variables in [43, Theorem 2.2] with polynomials $x_1(q)$, $x_2(q)$, $y_1(q)$, $y_2(q)$, $v_1(q)$, $v_2(q)$, $(w_k(q))_{k \ge 0}$ and then set $q = -1$. Using the conditions in (3.19), it follows that the continued fraction [43, eq. (2.24)/(2.25)] under this substitution becomes (3.14).

The proof of (b) and (c) is similar to that of (a) but instead we use Theorem 3.1 and [43, Theorem 2.7], respectively. □

As a consequence of Proposition 3.5, we can state our main theorem for permutations as an easy corollary:

**Theorem 3.6 (CSP for permutations).** Let $\text{Stat}, \text{Stat}_\gamma, \text{Stat}_\beta$ be three statistics on permutations satisfying $\text{Stat} = \text{Stat}_\beta + \text{Stat}_\gamma$. Assume that $\text{Stat}_\gamma$ is one of the following statistics:

exclusive antirecord cycle double fall, exclusive record cycle double rise, cycle double rise, cycle double fall,
neither-record-antirecord fixed point, pseudo-nesting.

Also, assume that $\text{Stat}_\beta$ is one of the following statistics:

neither-record antirecord cycle peaks, neither-record antirecord cycle valleys, cycle valley non-minima,
eareccpeak + ereccval, eareccpeak + minval
nrcpeak + nrcval + nrcdrise + nrcdfall,
lower crossings of type cpeak, lower crossings
lower nestings of type cpeak, lower nestings,
upper crossings of type cval, upper crossings,
upper nestings of type cval, upper nestings,
ucross + lcross, lnest + unest

Then $\text{Stat}$ exhibits the cyclic sieving phenomenon with respect to involutions that have 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$ (in particular, with respect to the Corteel involution).
We should mention that there are various other possibilites to exploit Proposition 3.5. We have only mentioned a few of these in Theorem 3.6.

As immediate consequences of Proposition 3.5 and Theorem 3.6, we will now re-establish several of the results in [1, Section 4].

**Corollary 3.7.** The following statistics exhibit the cyclic sieving phenomenon with respect to involutions that have 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$ (in particular, with respect to the Corteel involution).

(a) [1, Theorem 4.7] The number of crossings (in the sense of Corteel) [40, Statistic 39]; see (3.8a).

(b) [1, Corollary 4.8] The number of nestings (in the sense of Corteel) [40, Statistic 223]; see (3.8b).

(c) [1, Theorem 4.15] The number of midpoints of decreasing subsequences of length 3 [40, Statistic 371]; in our terminology, these are neither-record-antirecords (nrar).

## 3.6 Some more instances of the cyclic sieving phenomenon

We will now exhibit a few more instances of the cyclic sieving phenomenon for some statistics which are not directly obtained from the general recipe in Proposition 3.5. These will be the count of certain vincular patterns. In particular, we will reprove [1, Corollary 4.8].

**Theorem 3.8.** The generating function of the number of occurences of patterns $2-ab$ and $ab-2$ (these are all equidistributed) have the following Stieltjes-type continued fraction:

$$ \sum_{n=0}^{\infty} \sum_{\sigma \in \mathfrak{S}_n} q^{ab-2(\sigma)} t^n = \sum_{n=0}^{\infty} \sum_{\sigma \in \mathfrak{S}_n} q^{2-ab(\sigma)} t^n = \frac{1}{1 - \frac{[1]_q t}{1 - \frac{[1]_q t}{1 - \frac{[2]_q t}{1 - \frac{[2]_q}{1-\dots}}}}} \quad (3.22) $$

Hence, they exhibit the cyclic sieving phenomenon with respect to involutions that have 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$.

*Proof.* It is known that the generating function of the pattern $2-13$ has this Stieltjes-type continued fraction [10, Corollary 23]. Also, it is known that all patterns of the form $2-ab$ and $ab-2$ are equidistributed [9, Proposition 1], see also [10, Proposition 2]. This proves
the identity (3.22). Plugging in $q = -1$ in (3.22) gives us

$$ \frac{1}{1 - \frac{t}{1 - t}} = 1 + \sum_{n=1}^{\infty} 2^{n-1} \qquad (3.23) $$

which is what we want.

□

**Remark 3.9.** 1. Theorem 3.8 was already proved for patterns 13 – 2 and 31 – 2 in [1, Corollary 4.8]; we have now provided a new proof of this result.

2. We remark that in a recent work, Bitonti et al [4] provide a vast multivariate generalisation of the continued fraction (3.22), see [4, Theorems 7.2/3.5].

3. The vincular patterns 32 – 1 or 12 – 3, which have been studied in [1, Theorem 4.20, Corollary 4.22], do not have any known nice classical continued fractions. Therefore, we do not know (at present) how to use the techniques in the current paper to prove these results.

## 3.7 Equidistribution of wexx and cdes: Proof of [1, Conjecture 4.24]

In this section, we will prove [1, Conjecture 4.24] which has been stated in Conjecture 1.1; we will show that the statistic wexx($\sigma$), defined in (3.2), is equidistributed with cdes($\sigma$), the cycle descent number defined in (3.3). We do this by showing that the ordinary generating functions for permutations counted with respect to either statistic give the same continued fraction. We obtain the former statistic by using a specialization of the first J-fraction for permutations of Sokal and Zeng [43, Theorem 2.2], and we obtain the latter statistic from our Theorem 3.1, which is a variant of Deb’s continued fraction [13, Theorem 3.1].

Our first ingredient is the following lemma which expresses these two statistics as combinations of some statistics in [12, Section 2.5].

**Lemma 3.10.** (a) The statistic wexx($\sigma$), which counts the number of weak excedances of $\sigma$ that are also mid-points of a decreasing subsequence of length 3, can be expressed as

$$ \text{wexx}(\sigma) = \text{nrfix}(\sigma) + \text{nrcval}(\sigma) + \text{nrcdrise}(\sigma). \qquad (3.24) $$

(b) The statistic cdes($\sigma$), which is the cycle descent number of $\sigma$, can be expressed as

$$ \text{cdes}(\sigma) = \text{nminval}(\sigma) + \text{cdfall}(\sigma). \qquad (3.25) $$
Proof. (a) From the cycle classification for permutations, we know that a weak-excedance can either be a fixed point, a cycle valley or a cycle double rise. Next, we know that an index $i \in [n]$ is the midpoint of a decreasing subsequence of length 3 if and only if it is a neither-record-antirecord (nrar). Using these two pieces of information simultaneously in the record-and-cycle classification gives us (3.24).

(b) First replace $i$ with $\sigma^{-1}(i)$ in (3.3) to notice that cdes($\sigma$) is equal to the number of indices $i \in [n]$ such that $\sigma^{-1}(i) > i$ where $i$ is not the smallest element of a cycle. Such an index $i$ could either be a cycle double fall or a cycle valley that is not the smallest in its cycle (a cycle double fall can never be the smallest element of a cycle), or in other words

$$ cdes(\sigma) = nminval(\sigma) + cdfall(\sigma) \qquad (3.26) $$

which is what we want.

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

Let $P_n(x)$ and $Q_n(x)$ be the ordinary generating polynomials of the statistics wexx and cdes, respectively, i.e.,

$$ P_n(x) \stackrel{\text{def}}{=} \sum_{\sigma \in \mathfrak{S}_n} x^{\text{wexx}(\sigma)}, \qquad Q_n(x) \stackrel{\text{def}}{=} \sum_{\sigma \in \mathfrak{S}_n} x^{\text{cdes}(\sigma)}. \qquad (3.27) $$

The following theorem is now a straightforward consequence of Lemma 3.10 applied to [43, Theorem 2.2] and Theorem 3.1.

**Theorem 3.11.** The ordinary generating functions $\sum_{n=0}^{\infty} P_n(x)t^n$, and $\sum_{n=0}^{\infty} Q_n(x)t^n$, both have the following Jacobi-type continued fraction expansion

$$ \sum_{n=0}^{\infty} P_n(x)t^n = \sum_{n=0}^{\infty} Q_n(x)t^n = \frac{1}{1 - 1 \cdot t - \frac{1 \cdot 1 \cdot t^2}{1 - (2+x)t - \frac{2(1+x)t^2}{1 - (3+2x)t - \frac{3(1+2x)t^2}{1 - \dots}}}} \qquad (3.28) $$

with coefficients

$$ \beta_n = n(n-1+x), \qquad \gamma_n = n + (n-1)x. \qquad (3.29) $$

Thus, $P_n(x) = Q_n(x)$ for all $n \ge 0$. Hence, the statistics wexx and cdes are equidistributed [1, Conjecture 4.24].

Proof. From Lemma 3.10(a), we get that applying the substitutions $v_1 = v_2 = x$, $w_n = x$ for $n > 0$ and setting all other parameters to 1 to the polynomials $Q_n^{(1)}$, recalled in (3.15), gives us $P_n(x)$. The same substitutions applied to the continued fraction in the first J-fraction
for permutations of Sokal and Zeng [43, Theorem 2.2] gives us our continued fraction in $(3.28)/(3.29)$.

For the polynomials $Q_n(x)$ enumerating cdes, we instead infer from Lemma 3.10(b) that applying the following substitutions to Theorem 3.1 will give us the desired result: substitute $v_1 = x_2 = u_2 = x$ and set all other variables to 1. $\square$

Finally, notice that setting $x = -1$ to the continued fraction $(3.28)/(3.29)$ gives us (3.14). As a consequence, we have the following corollary:

**Corollary 3.12.** *The statistics wexx [40, Statistic 373] and cdes [40, Statistic 317] exhibits the cyclic sieving phenomenon with respect to involutions that have 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points when $n \ge 1$ (in particular, with respect to the Corteel involution).*

We remark that Corollary 3.12 for the statistic cdes was established in [1, Theorem 4.10].

## 3.8 Cyclic sieving phenomenon for Statistic 123: Proof of [1, Conjecture 4.23]

In this section, we will prove [1, Conjecture 4.23] which asserts that [40, Statistic 123] exhibits the cyclic sieving phenomenon with respect to the Corteel involution. The original description of this statistic involved the Simion-Schmidt map [42]; we will begin this section by first recalling this map. After this, we provide an alternate and better description of this statistic 123.

Let $\pi \in \mathfrak{S}_3$, be a permutation on 3 letters. The Simion-Schmidt map is a map $\Phi_\pi : \mathfrak{S}_n \to \mathfrak{S}_n$ with respect to the permutation pattern $\pi$; the map $\Phi_\pi$ satisfies the property that $\Phi_\pi(\sigma)$ has no occurrence of the pattern $\pi$. In this paper, we will only work with $\Phi_{321}$, and hence, we now provide its explicit description here:

Keep the records (left-to-right maxima) of $\sigma$ fixed, and then sort all the other entries of $\sigma$ in increasing order and put them in the remaining positions. The obtained permutation is $\Phi_\pi(\sigma)$. For example, consider

$$ \sigma = \underline{9374611581012}; \qquad (3.30) $$

here the records are underlined. Its image under the Simion-Schmidt map $\Phi_{321}$ is

$$ \Phi_{321}(\sigma) = \underline{9123411567810}. \qquad (3.31) $$

Here, the map $\Phi_{321}$ turns each occurrence of the pattern 321 in $\sigma$ into an occurrence of 312 in $\Phi_{321}(\sigma)$.

The original definition of [40, Statistic 123] is as follows:

$$ \mathrm{Stat123}(\sigma) \stackrel{\mathrm{def}}{=} \mathrm{inv}(\sigma) - \mathrm{inv}(\Phi_{321}(\sigma)) \qquad (3.32) $$
where recall that inv counts the number of inversions.

To prove [1, Conjecture 4.23], we will provide an alternate description of Stat123 in terms of positional marked patterns [46]. Consider a tuple $(\pi, I)$ where $\pi \in \mathfrak{S}_m$ and $I = \{i_1, i_2, \dots, i_k\} \subseteq [m]$ is a list of indices of $\pi$ which are to be circled. Using the tuple $(\pi, I)$, we define the following statistic on permutations:

$$ \mathrm{pmp}_{(\pi, I)}(\sigma) \stackrel{\mathrm{def}}{=} \#\{1 \le j_1 < j_2 < \dots < j_k \le n \mid \exists 1 \le \bar{j}_1 < \bar{j}_2 < \dots < \bar{j}_m \le n \\ \text{such that the subword } \sigma_{\bar{j}_1} \sigma_{\bar{j}_2} \dots \sigma_{\bar{j}_k} \text{ is an occurrence} \\ \text{of the pattern } \pi \text{ that satisfies } \bar{j}_{i_1} = j_1, \dots, \bar{j}_{i_m} = j_m \}. \quad (3.33) $$

In their paper, Remmel and Thamrongpairoj [46] only considered the situation where $|I| = 1$; they only studied positional marked patterns with respect to one position. However, in our paper, we will study the tuple $(321, \{2, 3\})$. Following the notation in [1], we will denote this as $3\textcircled{2}\textcircled{1}$. For the convenience of the reader, we restate (3.33) when $(\pi, I) = 3\textcircled{2}\textcircled{1}$

$$ \mathrm{pmp}_{3\textcircled{2}\textcircled{1}}(\sigma) = \#\{(j, k) \mid \text{there exists } i \text{ satisfying } 1 \le i < j < k \le n \\ \text{such that } \sigma_i > \sigma_j > \sigma_k \}. \quad (3.34) $$

We are now ready to state an alternate description of Stat123:

**Proposition 3.13.** *The following equality holds:*

$$ \mathrm{Stat123}(\sigma) = \mathrm{pmp}_{3\textcircled{2}\textcircled{1}}(\sigma). \quad (3.35) $$

In order to prove this Proposition, we require the following lemma:

**Lemma 3.14.** Let $\sigma \in \mathfrak{S}_n$ be a permutation that has its left-to-right maxima in positions $I = \{i_1, i_2, \dots, i_k\}$. Then the inversions contributed by the left-to-right maxima as the larger value is given by

$$ \#\{(i, j) \mid \sigma_i > \sigma_j \text{ and } i \in I\} = (\sigma_{i_1} - 1) + (\sigma_{i_2} - 2) + \dots + (\sigma_{i_k} - k). \quad (3.36) $$

We leave the proof of Lemma 3.14 to the reader. The important thing to notice is that (3.36) only depends on the positions and values of the left-to-right maxima. We now proceed to prove Proposition 3.13.

*Proof of Proposition 3.13.* Consider a pair of indices $(i, j)$ that forms an inversion in $\Phi_{321}(\sigma)$. From the description of $\Phi_{321}$, we see that for this to be true, $i$ must be the position of a
left-to-right maxima in $\sigma$. Thus, from Lemma 3.14 it follows that $\mathrm{inv}(\Phi_{321}(\sigma))$ is counted by (3.36), which is also the number of inversions of $\sigma$ contributed by its left-to-right maxima as the larger value. From this it follows that

$$ \begin{aligned} \mathrm{Stat123}(\sigma) &= \mathrm{inv}(\sigma) - \mathrm{inv}(\Phi_{321}(\sigma)) \\ &= \#\{(i, j) \mid \sigma_i > \sigma_j \text{ and } i \text{ is not the position of a left-to-right maximum}\}. \end{aligned} \tag{3.37} $$

However, this means that for every such position $i$ of the permutation $\sigma$, there exists a position $i_0 < i$ such that $i_0$ is the position of a left-to-right maximum. The triple $i_0 < i < j$ is an occurrence of the pattern 321, and thus, $\mathrm{Stat123}(\sigma)$ counts the occurrences of pairs which correspond to 2 and 1 positions in all such occurrences. $\square$

Having established Proposition 3.13, we now prove [1, Conjecture 4.23].

**Theorem 3.15** ([1, Conjecture 4.23]). The difference in the Coxeter length of a permutation and its image under the Simion-Schmidt map $\Phi_{321}$ [40, Statistic 123] exhibits the cyclic sieving phenomenon under involutions with 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points for all $n \ge 1$.

*Proof.* From Proposition 3.13, we know that $\mathrm{Stat123}(\sigma)$ is the number of positional marked patterns $3\textcircled{2}\textcircled{1}$ in the permutation $\sigma$. With this translation, we see that the involution $\Psi$ defined in [1, Proof of Theorem 4.15], that has 1 fixed point when $n = 0$ and $2^{n-1}$ fixed points for all $n \ge 1$, satisfies the following property:

$$ |\mathrm{pmp}_{3\textcircled{2}\textcircled{1}}(\sigma) - \mathrm{pmp}_{3\textcircled{2}\textcircled{1}}(\Psi(\sigma))| = \pm 1 \tag{3.38} $$

This finishes the proof. $\square$

**Remark 3.16.** After discovering the equivalence in Proposition 3.13, we updated the webpage of the statistic 123 on the FindStat website. It now displays the interpretation in terms of positional marked patterns $3\textcircled{2}\textcircled{1}$.

We also remark that there is no nice Jacobi-type continued fraction for this statistic. Hence, the techniques used in the rest of the paper do not work for this statistic.

# 4 Set partitions

A set partition of $[n]$ is a partition of the set $[n]$ into nonempty blocks; it is counted by the Bell number $B_n$. We use $\Pi_n$ to denote the set of all set-partitions of $[n]$. For a partition $\pi$, $|\pi|$ will denote its number of blocks. An important property of the Bell numbers $B_n$ is that they have the following J-fraction [47, 21]:
$$ \sum_{n=0}^{\infty} B_n t^n = \frac{1}{1 - t - \frac{t^2}{1 - 2t - \frac{2t^2}{1 - 3t - \frac{3t^2}{1 - \dots}}}} \quad (4.1) $$

We will use various generalisations of this identity in this section.

In Section 4.1 we define some statistics on set partitions. Then in Section 4.2 we recall the Kasraoui-Zeng involution [26] in terms of labelled Motzkin paths and count its number of fixed points. After this, in Section 4.3, we look at Chen et al's involution [8] and count its number of fixed points. Then in Section 4.4, we will use the statistics defined in Section 4.1 to recall multivariate generating polynomials introduced by Sokal and Zeng [43]. Finally, we state our main results in Section 4.5. Finally in Section 4.6, we conclude with a discussion on Mahonian statistics on set partitions.

## 4.1 Statistics on set partitions

Let $\pi \in \Pi_n$ be a set partition of $[n]$. Following Sokal and Zeng [43], we first classify each element $i \in [n]$ as follows:

* $i$ is an *opener* (op) if it is the smallest element of a block of size $\ge 2$;

* $i$ is a *closer* ($m_{\ge 2}$) if it is the largest element of a block of size $\ge 2$;

* $i$ is an *insider* (in) if it is a non-opener non-closer element of a block of size $\ge 3$;

* $i$ is a *singleton* ($m_1$) if it is the sole element of a block of size 1.

Clearly every element $i$ belongs to precisely one of these four classes; we will call this the *type classification for set partitions*<fnref n="2" />.

We say that an index $i$ is an *exclusive record* of $\pi$ if it is not the largest element in its block, (that is, it is either an opener or an insider) and its right neighbor (within its block) sticks out farther to the right than any right neighbor (within its block) of a vertex $< i$. With this notion of an exclusive record, we refine openers and insiders as follows:

* $i$ is an *exclusive record opener* (erecop) if it is an opener and also an exclusive record;

* $i$ is an *non-exclusive record opener* (nerecop) if it is an opener but not an exclusive record;

* $i$ is a *exclusive record closer* (erecin) if it is a closer and also an exclusive record;

<footnote n="2">²We borrow the term *type* from Kasraoui and Zeng [26]; their usage of the word type is different but in a similar context.</footnote>
• *i* is a non-exclusive record closer (nerecin) if it is a closer but not an exclusive record.

These four statistics along with insiders and singletons form 6 disjoint categories and we will call them the **record-and-type classification**.

After this, we introduce crossings, nestings, overlaps and coverings on set partitions.
But first, we recall the partition graph of $\pi$; we follow the convention of Sokal and Zeng.
We associate to the partition $\pi$ a graph $G_{\pi}$ with vertex set $[n]$ such that $i, j$ are joined by
an edge if and only if they are consecutive elements within the same block. (Thus, the
graph $G_{\pi}$ has $|\pi|$ connected components and $n - |\pi|$ edges.) With this in mind, we say that
a quadruplet $i < j < k < l$ forms a

• crossing (cr) if $(i, k)$ and $(j, l)$ are edges in $G_{\pi}$;

• nesting (ne) if $(i, l)$ and $(j, k)$ are edges in $G_{\pi}$.

Also, we say that a triple $i < j < l$ forms a

• pseudo-nesting (psne) if $j$ is a singleton and $(i, l)$ is an edge in $G_{\pi}$.

Sokal and Zeng further refine the categories of crossing and nesting depending on the
type of the second index $j$ and introduce the following four classes: crossing of opener type
(crop), crossing of insider type (crin), nesting of opener type (neop), nesting of insider type
(nein).

Let $B_1, B_2$ be blocks of $\pi$. We say that the pair $(B_1, B_2)$ forms

• an *overlap* (ov) if $\min B_1 < \min B_2 < \max B_1 < \max B_2$;

• a *covering* (cov) if $\min B_1 < \min B_2 < \max B_2 < \max B_1$;

• a pseudo-covering (pscov) if $\min B_1 < \min B_2 = \max B_2 < \max B_1$ (so that here $B_2$ is a singleton).

They also define two related quantities ovin and covin as follows:

$$
\operatorname{ovin}(\pi) = \sum_{j \in \text{insiders} \cap B_2} \#\{(B_1, B_2) : j \in B_2 \text{ and } \min B_1 < j < \max B_1 < \max B_2\} \quad (4.2a)
$$

$$
\operatorname{covin}(\pi) = \sum_{j \in \text{insiders} \cap B_2} \#\{(B_1, B_2) : j \in B_2 \text{ and } \min B_1 < j < \max B_2 < \max B_1\} \quad (4.2b)
$$

We also recall the notion of a *block record*. We say that *j* is a *block record* if it is either an opener or an insider and its block sticks out farther to the right than any block containing a vertex *<j*. We write
• brecin($\pi$) for the number of insiders that are block-records,

• nbrecin($\pi$) for the number of insiders that are not block-records,

• brecop($\pi$) for the number of openers that are block-records,

• nbrecop($\pi$) for the number of openers that are not block-records.

## 4.2 The Kasraoui–Zeng involution on set partitions

In [26], Kasraoui and Zeng constructed an involution on the set $\Pi_n$ that exchanges the number of crossings and nestings while keeping various other statistics fixed. We recall this involution and then count its number of fixed points. However, we will state this involution via labelled Motzkin paths (Charlier diagrams of Viennot) to be consistent with our formalism in the previous sections.

The Kasraoui–Zeng bijection (as stated by Sokal and Zeng [43, sec. 7.2]) is a correspondence between $\Pi_n$ and the set of ($\mathcal{A}, \mathcal{B}, \mathcal{C}$)-labelled Motzkin paths of length $n$, where the labels $\xi_i$ lie in the sets

$$ \mathcal{A}_h = \{0\} \quad \text{for } h \ge 0 \qquad (4.3a) $$

$$ \mathcal{B}_h = \{0, \dots, h-1\} \quad \text{for } h \ge 1 \qquad (4.3b) $$

$$ \mathcal{C}_0 = \{2\} \times \{0\} \qquad (4.3c) $$

$$ \mathcal{C}_h = \{1\} \times \{0, 1, \dots, h-1\} \cup \{2\} \times \{0\} \quad \text{for } h \ge 1 \qquad (4.3d) $$

Let $\Pi\mathcal{M}_n$ denote this set of ($\mathcal{A}, \mathcal{B}, \mathcal{C}$)-labelled Motzkin paths of length $n$ with label sets (4.3a,b,c). These are the Charlier diagrams of Viennot [48]. The Kasraoui–Zeng bijection as per [43, Section 7.2] is a bijective map $\varphi_n^{\text{KZ}} : \Pi_n \to \Pi\mathcal{M}_n$.

We say that a level step at height $h$ is of the first kind (second kind resp.) if the first index of $\xi_i \in \mathcal{C}_h$ is 1 (2).

We will now describe an involution $\phi_n : \Pi\mathcal{M}_n \to \Pi\mathcal{M}_n$; the Kasraoui–Zeng involution will then be obtained by the composition of bijections $(\varphi_n^{\text{KZ}})^{-1} \circ \phi_n \circ \varphi_n^{\text{KZ}}$. Let $(\omega, \xi) \in \Pi\mathcal{M}_n$ where $\xi = (\xi_1, \dots, \xi_n)$. Let $\xi^c = (\xi_1^c, \dots, \xi_n^c)$ be the sequence where $\xi_i^c$ is given by

$$ \xi_i^c = \begin{cases} \xi_i = 0 & \text{if step } i \text{ is a rise} \\ h-1-\xi_i & \text{if step } i \text{ is a fall} \\ (1, h-1-\xi_i) & \text{if step } i \text{ is a level step of the first kind} \\ (2, \xi_i) = (2, 0) & \text{if step } i \text{ is a level step of the second kind} \end{cases} \qquad (4.4) $$

It clearly follows that $(\omega, \xi^c) \in \Pi\mathcal{M}_n$ and that $(\xi^c)^c = \xi$. Thus, the map $(\omega, \xi) \mapsto (\omega, \xi^c)$ is an involution on the set $\Pi\mathcal{M}_n$; we use $\phi_n$ to denote this involution. The Kasraoui–Zeng involution on set partitions is the map $(\varphi_n^{\text{KZ}})^{-1} \circ \phi_n \circ \varphi_n^{\text{KZ}}$.
An important property of this involution is that crossings and nestings are exchanged; i.e., for a partition $\pi$ with $\hat{\pi} := ( (\varphi_n^{KZ})^{-1} \circ \phi_n \circ \varphi_n^{KZ} ) (\pi)$, we have

$$ (\mathrm{cr}(\pi), \mathrm{ne}(\pi)) = (\mathrm{ne}(\hat{\pi}), \mathrm{cr}(\hat{\pi})). \qquad (4.5) $$

We now establish the number of fixed points of the Kasraoui-Zeng involution. First, let $(a_n)_{n \ge 0}$ be the sequence of integers given by the linear recurrence

$$ a_n = 3a_{n-1} - a_{n-2} \qquad (4.6) $$

with initial conditions $a_0 = a_1 = 1$, see [33, A001519]. In fact, these numbers are the odd subsequence of the Fibonacci numbers and hence we will call them the *odd Fibonacci numbers*. The first few numbers of this sequence are

$$ 1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, \dots \qquad (4.7) $$

In the rest of this paper, we will use $F_{2n-1} := a_n$ to denote these numbers. (Here $F_{-1} = 1$.)

**Lemma 4.1.** *The number of fixed points of $\Pi_n$ under the action of the Kasraoui-Zeng involution $(\varphi_n^{KZ})^{-1} \circ \phi_n \circ \varphi_n^{KZ}$ is the odd Fibonacci number $F_{2n-1}$ [33, A001519].*

*Proof.* It suffices to count the number of labels $\xi$ such that $\xi = \xi^c$. Using general theory, we obtain that the generating function of labelled Motzkin paths that are fixed points of the involution $\phi_n$ is given by the Jacobi-type continued fraction:

$$ \frac{1}{1 - t - \frac{t^2}{1 - 2t}}. \qquad (4.8) $$

This finishes the proof. $\square$

## 4.3 The Chen-Deng-Du-Stanley-Yan (CDDSY) involution on set partitions

In [8], Chen et al gave a different involution on set partitions. In their paper, the authors introduced the notion of *vacillating tableaux*, which are certain walks on the Young's lattice, and they constructed a bijection between set partitions and vacillating tableaux. They then pullback a simple involution on vacillating tableaux via this bijection, to describe their involution on set partitions. We will refer to this involution as the *CDDSY involution*. In this section, we will show that the number of fixed points of the CDDSY involution is also given by Lemma 4.1.
We first recall some basic definitions. Let $\mathbb{Y}$ be the Young's lattice, that is, the set of all integer partitions ordered component-wise.

**Definition 4.2.** A vacillating tableaux $V_{\lambda}^{2n}$ of shape $\lambda$ and length $2n$ is a sequence $\emptyset = \lambda^0, \lambda^1, \lambda^2, \dots, \lambda^{2n} = \lambda$ of integer partitions with the property that $\lambda^{2i+1}$ is obtained by either setting $\lambda^{2i+1} = \lambda^{2i}$ or by deleting a square from $\lambda^{2i}$, and $\lambda^{2i}$ is obtained by either setting $\lambda^{2i} = \lambda^{2i-1}$ or by adding a square to $\lambda^{2i-1}$.

In terms of the $U, D$ and $I$ operators on the Young's lattice $\mathbb{Y}$, we can restate the conditions in this definition as follows: given a $\lambda^{2i-2}$ in the sequence of a vacillating tableaux, the integer partition $\lambda^{2i-1}$ is obtained by applying the operator $I+D$ to $\lambda^{2i-2}$ and then picking one of the summands, and similarly, the integer partition $\lambda^{2i}$ is obtained by applying the operator $I+U$ to $\lambda^{2i-1}$ and then selecting one of the summands.

Let $\mathcal{V}\mathcal{T}_n$ denote the set of all vacillating tableaux of shape $\emptyset$ and length $2n$. In [8, Section 3], the authors constructed a bijection $\varphi_n^{\text{CDDSY}}: \Pi_n \to \mathcal{V}\mathcal{T}_n$. Let $\tau_n: \mathcal{V}\mathcal{T}_n \to \mathcal{V}\mathcal{T}_n$ be the involution defined by taking the conjugate to each partition $\lambda^i$. The CDDSY involution on set partitions (defined in [8, proof of Theorem 1]) is the map $(\varphi_n^{\text{CDDSY}})^{-1} \circ \tau_n \circ \varphi_n^{\text{CDDSY}}$.

We now establish the number of fixed points of the CDDSY involution.

**Lemma 4.3.** *The number of fixed points of $\Pi_n$ under the action of the CDDSY involution $(\varphi_n^{\text{CDDSY}})^{-1} \circ \tau_n \circ \varphi_n^{\text{CDDSY}}$ is the odd Fibonacci number $F_{2n-1}$ [33, A001519].*

*Proof.* It suffices to count the number of fixed points of the involution $\tau_n$. Let $\mathcal{V}\mathcal{T}_n^{\flat}$ denote the set of all vacillating tableau $(\lambda^0, \dots, \lambda^{2n})$ such that each integer partition $\lambda^i$ is either $\emptyset$ or 1. We will show that $\mathcal{V}\mathcal{T}_n^{\flat}$ is the set of fixed points of $\tau_n$. In fact, it is immediate that an element of $\mathcal{V}\mathcal{T}_n^{\flat}$ is always a fixed point of $\tau_n$. On the other hand, any vacillating tableaux not in the set $\mathcal{V}\mathcal{T}_n^{\flat}$ must have index $i$ such that $\lambda^i \vdash 2$. For such an index $i$, the partition $\lambda^i$ and its conjugate must be different. Hence, such a vacillating tableaux cannot be a fixed point of $\tau_n$.

Let $M_n^{\flat}$ denote the set of Motzkin paths of length $n$ which never cross the line $x=1$, where the level steps at height 1 gets a label 0 or 1. From [21], we know that the ordinary generating function of the cardinalities of $M_n^{\flat}$ is given by the continued fraction

$$ \sum_{n=0}^{\infty} |M_n^{\flat}| t^n = \frac{1}{1 - t - \frac{t^2}{1 - 2t}}. \qquad (4.9) $$

Notice that the right-hand side is the same as in (4.8). Thus, a bijection between the sets $\mathcal{V}\mathcal{T}_n^{\flat}$ and $M_n^{\flat}$ will prove this lemma. We construct such a bijection now.
Let $(\lambda^0, \dots, \lambda^{2n}) \in \mathcal{V}\mathcal{T}_n^b$ and let $\omega_i \in \mathbb{N} \times \{0, 1\}$ be the pair

$$ \omega_i = \begin{cases} (i, 0) & \text{if } \lambda^{2i} = \emptyset \\ (i, 1) & \text{if } \lambda^{2i} = 1 \end{cases}. \qquad (4.10) $$

The sequence $\omega = (\omega_0, \omega_1, \dots, \omega_n)$ is a path of length $n$ which never crosses the line $x = 1$. By construction, step $i$ is a level step at height 1 if and only if $\lambda^{2i-2} = \lambda^{2i} = 1$. In this situation, the integer partition $\lambda^{2i-1}$ can be either 1 or $\emptyset$, and step $i$ gets label 0 and 1, respectively. This gives us a Motzkin path $\omega$ where each level step at height 1 gets a label 0 or 1. This is our desired bijection. $\square$

## 4.4 Sokal and Zeng's multivariate polynomials enumerating statistics on set partitions

In this section, we recall three of Sokal-Zeng's multivariate polynomials enumerating statistics on set partitions; first we shall state [43, eq. (3.6)] which does not have any $p, q$-statistics, then we shall state their first $p, q$-generalisation involving crossings and nestings [43, eq. (3.11)], and then finally we state their second $p, q$-generalisation involving overlaps and coverings.

The first polynomial is [43, eq. (3.6)]

$$ B_n^{(1)}(x_1, x_2, y_1, y_2, v_1, v_2) = \sum_{\pi \in \Pi_n} x_1^{m_1(\pi)} x_2^{m_2(\pi)} y_1^{\text{erecin}(\pi)} y_2^{\text{erecop}(\pi)} v_1^{\text{nerecin}(\pi)} v_2^{\text{nerecop}(\pi)}. \qquad (4.11) $$

The ordinary generating function of these polynomials have a nice Jacobi-type continued fraction [43, Theorem 3.2].

The second polynomial is [43, eq. (3.11)]

$$ \begin{aligned} B_n^{(2)}(x_1, x_2, y_1, y_2, v_1, v_2, p_1, p_2, q_1, q_2, r) \\ = \sum_{\pi \in \Pi_n} x_1^{m_1(\pi)} x_2^{m_2(\pi)} y_1^{\text{erecin}(\pi)} y_2^{\text{erecop}(\pi)} v_1^{\text{nerecin}(\pi)} v_2^{\text{nerecop}(\pi)} \times \\ p_1^{\text{crin}(\pi)} p_2^{\text{crop}(\pi)} q_1^{\text{nein}(\pi)} q_2^{\text{neop}(\pi)} r^{\text{psne}(\pi)}. \end{aligned} \qquad (4.12) $$

The ordinary generating function of these polynomials have a nice Jacobi-type continued fraction as well [43, Theorem 3.3].

Our third polynomial is analogous to (4.12) but uses block-records, overlaps, coverings and pseudo-coverings in place of exclusive records, crossings, nestings and pseudo-
nestings:

$$
\begin{align}
& B_n^{(3)}(x_1, x_2, y_1, y_2, v_1, v_2, p_1, p_2, q_1, q_2, r) \nonumber \\
& = \sum_{\pi \in \Pi_n} x_1^{m_1(\pi)} x_2^{m_{\ge 2}(\pi)} y_1^{\text{brecin}(\pi)} y_2^{\text{brecop}(\pi)} v_1^{\text{nbrecin}(\pi)} v_2^{\text{nbrecop}(\pi)} \times \nonumber \\
& \qquad p_1^{\text{ovin}(\pi)} p_2^{\text{ov}(\pi)} q_1^{\text{covin}(\pi)} q_2^{\text{cov}(\pi)} r^{\text{pscov}(\pi)}. \tag{4.13}
\end{align}
$$

It turns out that these polynomials are not merely analogous to (4.12); they are identical to (4.12) [43, Theorem 3.5]. See historical remark in [43, Section 3.4].

In this paper, we refrain from working with Sokal and Zeng’s master continued fractions for set partitions which involve infinitely many statistics on set partitions [43, Sections 3.7-3.10]. However, it is easy to generalise our results to the infinite-variable setting.

4.5 Instances of the cyclic sieving phenomenon

We are now ready to state instances of the cyclic sieving phenomena on set partitions with respect to the Kasraoui–Zeng involution or the CDDSY involution, or as a matter of fact, for any involution having $F_{2n-1}$ fixed points.

We first state a very general result in Proposition 4.4.

**Proposition 4.4.** Let Stat : $\Pi_n \to \mathbb{N}$ be a statistic defined on set partitions.

(a) Assume that Stat is obtained as a specialisation of the polynomial $B_n^{(1)}(x_1, x_2, y_1, y_2, v_1, v_2)$ defined in (4.11), i.e., there exists polynomials $x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q) \in \mathbb{R}[q]$ satisfying

$$
\sum_{\pi \in \Pi_n} q^{\text{Stat}} = B_n^{(1)}(x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q)) \quad (4.14)
$$

for all $n \ge 0$. Further assume that the following equations are satisfied

$$
x_1(-1) = y_1(-1) = 1 \qquad (4.15a)
$$

$$
x_2(-1) \cdot y_2(-1) = 1 \qquad (4.15b)
$$

$$
x_2(-1) \cdot v_2(-1) = -1 \qquad (4.15c)
$$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involu-
tions having $F_{2n-1}$ fixed points [33, A001519].

(b) Assume that Stat is obtained as a specialisation of the polynomial

$B_n^{(2)}(x_1, x_2, y_1, y_2, v_1, v_2, p_1, p_2, q_1, q_2, r)$ defined in (4.12), i.e., there exists polynomi-
als $x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q), p_1(q), p_2(q), q_1(q), q_2(q), r(q) \in \mathbb{R}[q]$ satisfy-
ing

$$
\sum_{\pi \in \Pi_n} q^{\mathrm{Stat}} = B_n^{(2)}(x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q), p_1(q), p_2(q), q_1(q), q_2(q), r(q)) \tag{4.16}
$$

for all $n \ge 0$. Further assume that the following equations are satisfied

$$
x_1(-1) = 1 \qquad (4.17a)
$$

$$
x_2(-1) \cdot y_2(-1) = 1 \qquad (4.17b)
$$

$$
r(-1) + y_1(-1) = 2 \qquad (4.17c)
$$

$$
p_2(-1) + q_2(-1) \cdot x_2(-1) \cdot v_2(-1) = 0 \quad (4.17d)
$$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involu-
tions having $F_{2n-1}$ fixed points.

(c) Assume that Stat is obtained as a specialisation of the polynomial

$B_n^{(3)}(x_1, x_2, y_1, y_2, v_1, v_2, p_1, p_2, q_1, q_2, r)$ defined in (4.13). Further assume that equa-
tions (4.17) are satisfied. Then the statistic Stat exhibits the cyclic sieving phe-
nomenon with respect to involutions having $F_{2n-1}$ fixed points.

Proof. (a) We replace the variables in [43, Theorem 3.2] with polynomials $x_1(q)$, $x_2(q)$, $y_1(q)$, $y_2(q)$, $v_1(q)$, $v_2(q)$ and then set $q = -1$. Using the conditions in (4.15), it follows that the continued fraction [43, eq. (3.7)] under this substitution becomes

$$
\sum_{n=0}^{\infty} B_n^{(1)}(x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q)) \Big|_{q=-1} t^n = \frac{1}{1-t - \frac{t^2}{1-2t}}. \quad (4.18)
$$

The right-hand side is the generating function for the odd Fibonacci numbers $F_{2n-1}$.

The proof of (b) and (c) is similar to that of (a) but now we use [43, Theorems 3.3 and 3.5]. $\square$

As a consequence of Proposition 4.4, we can state our main theorem for set partitions
as an easy corollary:

**Theorem 4.5 (CSP for set partitions).** The following statistics on set partitions exhibit the cyclic sieving phenomenon with respect to involutions having $F_{2n-1}$ fixed points [33, A001519], (in particular, with respect to the Kasraoui-Zeng and the CDDSY involutions):

non-exclusive records (= $n - |\pi| - \mathrm{erec}(\pi)$), non-exclusive record openers,

crossings, nestings, crossing of opener type, nesting of opener type
non-block records (insiders and openers), openers that are not block-records,
overlaps, coverings

4.6 A remark on Mahonian statistics on set partitions

In [32], Milne introduced the inversion statistic on set partitions; following Wachs and White [49] we write it as [43, eq. (3.61a)]

$$
\mathrm{lb}(\pi) \stackrel{\mathrm{def}}{=} \#\{(B_1, B_2, k) : \min B_1 < \min B_2 < k \in B_1\}. \quad (4.19)
$$

The following continued fraction identity was proved in [50]

$$
\sum_{n=0}^{\infty} \sum_{\pi \in \Pi_n} q^{\text{lb}(\pi)} t^n = \frac{1}{1 - \frac{t}{1 - \frac{qt}{1 - \frac{(1+q)t}{1 - \frac{q^2 t}{1 - \frac{(1+q+q^2)t}{1-\dots}}}}}}. \quad (4.20)
$$

Various other statistics have been shown to be equidistributed with the inversion statistic
lb(π), see more details in [43, Sections 3.11, 3.12] and in [30]; these are known as the
*Mahonian statistics on set partitions*.

Notice that on setting $q = -1$ in the continued fraction (4.20), we get

$$
\sum_{n=0}^{\infty} \sum_{\pi \in \Pi_n} (-1)^{\text{lb}(\pi)} t^n = \frac{1}{1 - t - t^2} \quad (4.21)
$$

where clearly the right-hand side is the generating function of the Fibonacci numbers $F_n$.
Thus, an involution $\phi : \Pi_n \to \Pi_n$ must have Fibonacci many fixed points if any Mahonian
statistic were to exhibit the cyclic-sieving phenomenon with respect to $\phi$.

We will now construct such an involution by using the Kasraoui–Zeng bijection $\phi_n^{\text{KZ}} : \Pi_n \to \Pi \mathcal{M}_n$. For a level step of a Motzkin path $\omega \in \Pi \mathcal{M}_n$ we rewrite some labels as $c_0, c_1, \dots, c_h$ where

$$
c_i = \begin{cases} (2,0) & \text{if } i = h \\ (1,i) & \text{otherwise.} \end{cases} \tag{4.22}
$$
Now let $\bar{\phi}: \Pi\mathcal{M}_n \to \Pi\mathcal{M}_n$ be the following involution on Charlier diagrams that sends $(\omega, \xi)$ to $(\omega, \hat{\xi})$ where $\hat{\xi} = (\hat{\xi}_1, \dots, \hat{\xi}_n)$ is given by

$$ \hat{\xi}_i = \begin{cases} \xi_i = 0 & \text{if step } i \text{ is a rise} \\ h-1-\xi_i & \text{if step } i \text{ is a fall} \\ c_{h-k} & \text{if step } i \text{ is a level step and } \xi_i = c_k \end{cases}. \quad (4.23) $$

It is clear that $\bar{\phi}$ is an involution on $\Pi\mathcal{M}_n$ with $F_n$ fixed points. The composition of maps $\phi := (\varphi_n^{KZ})^{-1} \circ \bar{\phi} \circ \varphi_n^{KZ}$ gives us an involution on set partitions with the same number of fixed points. We leave out all the details and state the following result.

**Theorem 4.6.** *The Mahonian statistics on set partitions exhibit the cyclic sieving phenomenon with respect to involutions have $F_n$ fixed points (in particular the involution $(\varphi_n^{KZ})^{-1} \circ \bar{\phi} \circ \varphi_n^{KZ}$).*

# 5 Perfect matchings

A perfect matching of $[2n]$ is an involution on the set $[2n]$ with no fixed points; we use $\mathcal{I}_{2n} \subseteq \mathcal{S}_{2n}$ to denote the set of perfect matchings. It is known that the cardinality of this set is $|\mathcal{I}_{2n}| = (2n-1)!!$. An important property of the sequence of numbers $(2n-1)!!$ is that they have the following Stieltjes-type continued fraction [20, sec. 29]

$$ \sum_{n=0}^{\infty} (2n-1)!! t^n = \frac{1}{1 - \frac{t}{1 - \frac{2t}{1 - \frac{3t}{1 - \dots}}}}. \quad (5.1) $$

We will use various generalisations of this identity in this section.

In Section 5.1 we define some statistics on set partitions. Then in Section 5.2 we recall the Kasraoui-Zeng involution [26] on perfect matchings in terms of labelled Dyck paths and count its number of fixed points. After this, in Section 5.3, we look at Chen et al's involution [8] on perfect matchings and count its number of fixed points. Then in Section 5.4, we will use the statistics defined in Section 5.1 to recall multivariate generating polynomials introduced by Sokal and Zeng [43]. Finally, we state our main results in Section 5.5.

## 5.1 Statistics on perfect matchings

Let $\sigma \in \mathcal{I}_{2n}$ be a perfect matching on $[2n]$. Each $\sigma$ has $n$ cycles of size 2, and each cycle has a cycle peak and a cycle valley. Following Sokal and Zeng [43], we classify these according to their *parity* and their *record classification* (by considering them as permutations of $[2n]$). We then obtain the following eight statistics, the following four for cycle
peaks: even cycle-peak antirecord (ecpar), odd cycle-peak antirecord (ocpar), even cycle-peak non-antirecord (ecpnar), odd cycle-peak non-antirecord (ocpnar), and the remaining four for cycle valleys: even cycle-valley record (ecvr), odd cycle-valley record (ocvr), even cycle-valley non-record (ecvnr), odd cycle-valley non-record (ocvnr).

After this, we introduce crossings and nestings on perfect matchings. We think of $\sigma$ as a permutation and notice that for involutions we always have $ucross(\sigma) = lcross(\sigma)$ and $unest(\sigma) = lnest(\sigma)$; so we denote these quantities simply as $cr(\sigma)$ and $ne(\sigma)$, respectively.

We then further refine crossings and nestings as follows: we say that a quadruplet $i < j < k < l$ is an even (resp. odd) crossing if the index $j$ is even (resp. odd) and the quadruplet forms a (upper) crossing; we use $ecr(\sigma)$, and $ocr(\sigma)$ to denote the number of even and odd crossings, respectively. Similarly, we define even and odd nestings according to the parity of the second index $j$ for quadruplets which form upper nestings; we use $ene(\sigma)$, and one($\sigma$) to denote the number of even and odd nestings, respectively.

## 5.2 The Kasraoui-Zeng involution on perfect matchings

The Kasraoui-Zeng involution on set partitions can be restricted down to perfect matchings. This restriction to perfect matchings exchanges the number of crossings and nestings while keeping various other statistics fixed. We now state it this involution via labelled Dyck paths.

Consider the set of $(\mathcal{A}, \mathcal{B})$-labelled Dyck paths of length $2n$, where the labels $\xi_i$ lie in the sets

$$ \mathcal{A}_h = \{0\} \quad \text{for } h \ge 0 \qquad (5.2a) $$

$$ \mathcal{B}_h = \{0, \dots, h-1\} \quad \text{for } h \ge 1 \qquad (5.2b) $$

Let $\mathcal{ID}_n$ denote this set of $(\mathcal{A}, \mathcal{B})$-labelled Dyck paths of length $2n$ with label sets (5.2a,b). The Kasraoui-Zeng bijection as per [43] is a bijective map $\varphi_{2n}^{\mathrm{KZ}} : \mathcal{I}_{2n} \to \mathcal{ID}_{2n}$ (seen as the restriction of the bijection $\varphi_{2n}^{\mathrm{KZ}} : \Pi_{2n} \to \Pi \mathcal{M}_{2n}$ when there are no level steps).

Let $(\omega, \xi) \in \mathcal{ID}_{2n}$ where $\xi = (\xi_1, \dots, \xi_{2n})$. Let $\xi^c = (\xi_1^c, \dots, \xi_n^c)$ be a sequence where $\xi_i^c$ is given by

$$ \xi_i^c = \begin{cases} \xi_i = 0 & \text{if step } i \text{ is a rise} \\ h-1-\xi_i & \text{if step } i \text{ is a fall} \end{cases} \qquad (5.3) $$

It is clearly follows that $(\omega, \xi^c) \in \mathcal{ID}_{2n}$ and that $(\xi^c)^c = \xi$. Thus, the map $(\omega, \xi) \mapsto (\omega, \xi^c)$ is an involution on the set $\mathcal{ID}_{2n}$; we use $\phi_{2n}$ to denote this involution. The Kasraoui-Zeng involution on perfect matchings is the map $(\varphi_{2n}^{\mathrm{KZ}})^{-1} \circ \phi_{2n} \circ \varphi_{2n}^{\mathrm{KZ}}$.
$$ \text{As in the set partition case, we have for a perfect matching } \sigma \text{ with } \hat{\sigma} := \left( (\varphi_{2n}^{\text{KZ}})^{-1} \circ \phi_{2n} \circ \varphi_{2n}^{\text{KZ}} \right) (\sigma), \text{ we have} \\ \qquad (\text{cr}(\sigma), \text{ne}(\sigma)) = (\text{ne}(\hat{\sigma}), \text{cr}(\hat{\sigma})). \qquad (5.4) $$

We now establish the number of fixed points of the Kasraoui-Zeng involution on perfect matchings.

**Lemma 5.1.** The number of fixed points of $\mathcal{I}_{2n}$ under the action of the Kasraoui-Zeng involution $(\varphi_{2n}^{\text{KZ}})^{-1} \circ \phi_{2n} \circ \varphi_{2n}^{\text{KZ}}$ is 1 and thus is generated by the continued fraction

$$ \frac{1}{1-t}. \qquad (5.5) $$

The proof of this lemma is similar to that of Lemma 4.1 and hence, we leave it to the reader.

## 5.3 The Chen-Deng-Du-Stanley-Yan (CDDSY) involution on perfect matchings

In [8], Chen et al showed that the bijection $\varphi_n^{\text{CDDSY}}$ can be restricted to perfect matchings. Now this bijection is to a subclass of vacillating tableaux, called oscillating tableaux, which were studied by Sundaram in her PhD thesis [45].

We now recall the definition of oscillating tableaux.

**Definition 5.2.** An oscillating tableaux $T_\lambda$ of shape $\lambda$ and length $n$ is a sequence $\emptyset = \lambda^0, \lambda^1, \lambda^2, \dots, \lambda^n = \lambda$ of integer partitions with the property that $\lambda^i$ is obtained either deleting or adding a square to $\lambda^{i-1}$.

In terms of the $U, D$ and $I$ operators on the Young's lattice $\mathbb{Y}$, we can restate this definition as follows: given a $\lambda^{i-1}$ in the sequence of a vacillating tableaux, the integer partition $\lambda^i$ is obtained by applying the operator $U+D$ to $\lambda^{i-1}$ and then picking one of the summands.

Let $\mathcal{O}\mathcal{T}_n$ denote the set of all oscillating tableaux of shape $\emptyset$ and length $n$. The CDDSY bijection is a bijective map $\varphi_{2n}^{\text{CDDSY}}: \mathcal{I}_{2n} \to \mathcal{O}\mathcal{T}_{2n}$ (seen as the restriction of the bijection $\varphi_{2n}^{\text{CDDSY}}: \Pi_{2n} \to \mathcal{V}\mathcal{T}_{2n}$ when the partition $\pi$ has no insiders or singletons and all consecutive repetitions are removed from the vacillating tableau). Let $\tau_n: \mathcal{O}\mathcal{T}_n$ be the involution on oscillating tableaux that is obtained by sending each integer partition to its conjugate. Then the CDDSY involution for perfect matchings is the map $(\varphi_{2n}^{\text{CDDSY}})^{-1} \circ \tau_{2n} \circ \varphi_{2n}^{\text{CDDSY}}$.
We now show that the number of fixed points of the CDDSY involution is also given by Lemma 5.1.

**Lemma 5.3.** The number of fixed points of $\mathcal{I}_{2n}$ under the action of the CDDSY involution $(\varphi_{2n}^{\text{CDDSY}})^{-1} \circ \tau_{2n} \circ \varphi_{2n}^{\text{CDDSY}}$ is 1 and thus is generated by the continued fraction

$$ \frac{1}{1-t}. \qquad (5.6) $$

*Proof.* It suffices to count the number of fixed points of the involution $\tau_{2n}$. Notice that an oscillating tableau $(\lambda^0, \dots, \lambda^{2n}) \in \mathcal{OT}_{2n}$ is a fixed point of $\tau_{2n}$ if and only if $\lambda^{2i} = \emptyset$ and $\lambda^{2i-1} = 1$. This finishes the proof. $\square$

## 5.4 Sokal and Zeng's multivariate polynomials enumerating statistics on perfect matchings

In this section, we recall two of Sokal and Zeng's multivariate polynomials enumerating statistics on perfect matchings; first we shall state [43, eq. (4.4)] which does not have any $p, q$-statistics, then we shall state their $p, q$-generalisation involving crossings and nestings [43, eq. (4.22)].

The first polynomial is [43, eq. (4.4)]

$$ M_n(x, y, u, v) = \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{ecpar}(\sigma)} y^{\text{ocpar}(\sigma)} u^{\text{ecpnar}(\sigma)} v^{\text{ocpnar}(\sigma)} \quad (5.7a) $$

$$ = \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{ocvr}(\sigma)} y^{\text{ecvr}(\sigma)} u^{\text{ocvnr}(\sigma)} v^{\text{ecvnr}(\sigma)}. \quad (5.7b) $$

The equality between the two descriptions follows from applying reversal followed by complementation to $\sigma$. The ordinary generating function of these polynomials have a nice Stieltjes-type continued fraction [43, eq. (4.2), Theorem 4.1].

The second polynomial is [43, eq. (4.22)]

$$ M_n(x, y, u, v, p_+, p_-, q_+, q_-) = \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{ecpar}(\sigma)} y^{\text{ocpar}(\sigma)} u^{\text{ecpnar}(\sigma)} v^{\text{ocpnar}(\sigma)} p_+^{\text{ocr}(\sigma)} p_-^{\text{ecr}(\sigma)} q_+^{\text{one}(\sigma)} q_-^{\text{ene}(\sigma)} \quad (5.8a) $$

$$ = \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{ocvr}(\sigma)} y^{\text{ecvr}(\sigma)} u^{\text{ocvnr}(\sigma)} v^{\text{ecvnr}(\sigma)} p_+^{\text{ecr}(\sigma)} p_-^{\text{ocr}(\sigma)} q_+^{\text{ene}(\sigma)} q_-^{\text{one}(\sigma)}, \quad (5.8b) $$

The equality between the two descriptions again follows from applying reversal followed by complementation to $\sigma$. The ordinary generating function of these polynomials have a nice Stieltjes-type continued fraction [43, Theorem 4.4].
## 5.5 Instances of the cyclic sieving phenomenon

We are now ready to state instances of the cyclic sieving phenomena on perfect matchings with respect to the Kasraoui-Zeng involution on perfect matchings or the CDDSY involution on perfect matchings, or as a matter of fact, for any involution having 1 fixed point for every $n \ge 0$.

We first state a very general result in Proposition 5.4.

**Proposition 5.4.** Let Stat : $\mathcal{I}_{2n} \to \mathbb{N}$ be a statistic defined on perfect matchings.

(a) Assume that Stat is obtained as a specialisation of the polynomial $M_n(x, y, u, v)$ defined in (5.7), i.e., there exists polynomials $x(q), y(q), u(q), v(q) \in \mathbb{R}[q]$ satisfying

$$ \sum_{\sigma \in \mathcal{I}_{2n}} q^{\text{Stat}} = M_n(x(q), y(q), u(q), v(q)) \quad (5.9) $$

for all $n \ge 0$. Further assume that the following equations are satisfied

$$ x(-1) = 1 \quad (5.10a) $$

$$ y(-1) + v(-1) = 0 \quad (5.10b) $$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having 1 fixed point for every $n \ge 0$.

(b) Assume that Stat is obtained as a specialisation of the polynomial $M_n(x, y, u, v, p_+, p_-, q_+, q_-)$ defined in (5.8), i.e., there exists polynomials $x(q), y(q), u(q), v(q), p_+(q), p_-(q), q_+(q), q_-(q) \in \mathbb{R}[q]$ satisfying

$$ \sum_{\sigma \in \mathcal{I}_{2n}} q^{\text{Stat}} = M_n(x(q), y(q), u(q), v(q), p_+(q), p_-(q), q_+(q), q_-(q)) \quad (5.11) $$

for all $n \ge 0$. Further assume that the following equations are satisfied

$$ x(-1) = 1 \quad (5.12a) $$

$$ p_+( -1) \cdot y(-1) + q_+(-1) \cdot v(-1) = 0 \quad (5.12b) $$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having 1 fixed point for every $n \ge 0$.

*Proof.* (a) We replace the variables in [43, Theorem 4.1] with polynomials $x_1(q), x_2(q), y_1(q), y_2(q), v_1(q), v_2(q)$ and then set $q = -1$. Using the conditions in (5.10), it follows that the continued fraction [43, eq. (4.2)] under this substitution becomes

$$ \sum_{n=0}^{\infty} M_n(x(q), y(q), u(q), v(q))|_{q=-1} t^n = \frac{1}{1-t} \quad (5.13) $$
The proof of (b) but now we use [43, Theorem 4.4].

☐

As a consequence of Proposition 5.4, we can state our main theorem for perfect matchings as an easy corollary:

**Theorem 5.5 (CSP for perfect matchings).** The following statistics on perfect matchings exhibit the cyclic sieving phenomenon with respect to involutions having 1 fixed point, (in particular, with respect to the Kasraoui-Zeng involution on perfect matchings or the CDDSY involution on perfect matchings):

odd cycle peak antirecord, odd cycle peak non-antirecord, even cycle valley record, even cycle valley non-record,

crossing, nesting, odd crossing, odd nesting, even crossing, even nesting

We conclude this section by a discussion on the *roof* statistic of Benaych-Georges, Cuenca and Gorin [3, Section 4.1] which exhibits the cyclic sieving phenomenon only when $n$ is even.

For a perfect matching $\sigma \in \mathcal{I}_{2n}$, we say that an index $i$ forms a non-crossing roof if $i$ is an opener and $cr(i, \sigma) = 0$; we use $\text{roof}(\sigma)$ to denote the number of non-crossing roofs of $\sigma$ [43, see footnote 27]. Thus, we can obtain the generating polynomial for $\text{roof}(\sigma)$ as follows:

$$ \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{roof}(\sigma)} = M_n(x, x, 1, 1). \qquad (5.14) $$

We immediately obtain the following result:

**Theorem 5.6.** The statistic $\text{roof}(\sigma)$ exhibits the cyclic sieving phenomenon with respect to involutions having 1 fixed point (in particular, with respect to the Kasraoui-Zeng involution on perfect matchings or the CDDSY involution on perfect matchings) when $n$ is even.

*Proof.* By (5.14), we get that the generating function for this statistic can be expressed as a continued fraction [43, Theorem 4.1]:

$$ \sum_{n=0}^{\infty} \sum_{\sigma \in \mathcal{I}_{2n}} x^{\text{roof}(\sigma)} t^n = \frac{1}{1 - \frac{xt}{1 - \frac{(x+1)t}{1 - \frac{(x+2)t}{1 - \frac{(x+3)t}{1 - \dots}}}}} \qquad (5.15) $$

Plugging in $x = -1$ in this equation, the right-hand-side reduces to

$$ \frac{1}{1+t} \qquad (5.16) $$

which gives us the desired outcome.

☐
# 6 D-permutations and its subfamilies

We begin by recalling the definitions of D-permutations and its subfamilies in Section 6.1. Then we introduce a new involution, the Genocchi-Corteel involution, in Section 6.2; we also count its number of fixed points. After this, in Section 6.3, we recall multivariate generating polynomials introduced by Deb and Sokal [14]. Finally, we state our results for D-permutations in Section 6.4, and its subfamilies (D-semiderangements and D-derangements) in Section 6.5.

## 6.1 Genocchi, median Genocchi numbers, and D-permutations

We follow the terminology and conventions in [14] and in [13].

The Genocchi numbers [33, A110501]

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

are odd positive integers [31, 2, 25] [23, 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 (6.2) $$

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

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

are defined by [24, p. 63]

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

See [14, 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 [27, 28, 29]. 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 $\mathcal{D}_{2n}$ (resp. $\mathcal{D}_{2n}^e, \mathcal{D}_{2n}^o, \mathcal{D}_{2n}^{eo}, \mathcal{D}\mathcal{C}_{2n}$) denote the set of all D-permutations (resp. D-e-semiderangements, D-o-semiderangements, D-derangements, D-cycles) of $[2n]$. For instance,

$$ \mathcal{D}_2 = \{12, 21^{\mathrm{eo}}\} \qquad (6.5a) $$

$$ \mathcal{D}_4 = \{1234, 1243, 2134, 2143^{\mathrm{eo}}, 3142^{\mathrm{eo}}, 3241^{\mathrm{o}}, 4132^{\mathrm{e}}, 4231\} \qquad (6.5b) $$

$$ \mathcal{D}\mathcal{C}_2 = \{21\} \qquad (6.5c) $$

$$ \mathcal{D}\mathcal{C}_4 = \{3142\} \qquad (6.5d) $$

where e denotes e-semiderangements that are not derangements, o denotes o-semiderangements that are not derangements, and eo denotes derangements.

It is known [16, 17, 28, 27, 14] that

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

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

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

$$ |\mathcal{D}\mathcal{C}_{2n}| = g_{n-1} \qquad (6.6d) $$

## 6.2 Deb–Sokal bijection and the Genocchi–Corteel involution

Randrianarivony [36] introduced a bijection between D-o-semiderangements and labelled Dyck paths which is in a similar essence to the Foata–Zeilberger bijection [22]; he used this bijection to obtain continued fractions counting various statistics on D-o-semiderangements. Motivated by Randrianarivony’s bijection, Deb and Sokal [14] introduced two new bijections involving all D-permutations, one of which extends Randrianarivony’s bijection.

Both bijections of Deb and Sokal ([14, Sections 6.1-6.3]) and [14, Section 6.5]) are correspondences between $\mathcal{D}_{2n}$ and the set of $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled 0-Schröder paths of length $2n$, where the labels $\xi_i$ lie in the sets [14, eq. (6.1)]

$$ \mathcal{A}_h = \{0, \dots, \lceil h/2 \rceil\} \quad \text{for } h \ge 0 \qquad (6.7a) $$

$$ \mathcal{B}_h = \{0, \dots, \lceil (h-1)/2 \rceil\} \quad \text{for } h \ge 1 \qquad (6.7b) $$

$$ \mathcal{C}_0 = \{0\} \qquad (6.7c) $$

$$ \mathcal{C}_h = \emptyset \quad \text{for } h \ge 1 \qquad (6.7d) $$

Let $\mathcal{DS}_{2n}$ denote this set of $(\mathcal{A}, \mathcal{B}, \mathcal{C})$-labelled 0-Schröder paths of length $2n$ with label sets (6.7).

In this paper, we only focus on their first bijection which involves record classification [14, Sections 6.1-6.3]. Let $\varphi_{2n}^{\mathrm{DS}} : \mathcal{D}_{2n} \to \mathcal{DS}_{2n}$ denote this bijection.
We now describe an involution which is the analog of the **Corteel** involution in this setting; we call it the **Genocchi–Corteel** involution.

**Description of the Genocchi–Corteel involution:**

Let $(\omega, \xi) \in \mathcal{D}\mathcal{S}_{2n}$ where $\xi = (\xi_1, \dots, \xi_{2n})$. Let $\xi^c = (\xi_1^c, \dots, \xi_{2n}^c)$ be a sequence where $\xi_i^c$ is given by

$$ \xi_i^c = \begin{cases} \xi_i = \lceil h/2 \rceil & \text{if } i \text{ is even, step } i \text{ is a rise and } \xi_i = \lceil h/2 \rceil \\ \lceil h/2 \rceil - 1 - \xi_i & \text{if } i \text{ is even and step } i \text{ is a rise and } \xi_i < \lceil h/2 \rceil \\ \lceil (h-1)/2 \rceil - \xi_i & \text{if } i \text{ is even and step } i \text{ is a fall} \\ \lceil h/2 \rceil - \xi_i & \text{if } i \text{ is odd and step } i \text{ is a rise} \\ \lceil (h-1)/2 \rceil - 1 - \xi_i & \text{if } i \text{ is odd, step } i \text{ is a fall and } \xi_i < \lceil (h-1)/2 \rceil \\ \xi_i = \lceil (h-1)/2 \rceil & \text{if } i \text{ is odd, step } i \text{ is a fall and } \xi_i = \lceil (h-1)/2 \rceil \\ \xi_i = 0 & \text{if step } i \text{ is a long level step at height 0} \end{cases} \qquad (6.8) $$

It clearly follows that $(\omega, \xi^c) \in \mathcal{D}\mathcal{S}_{2n}$ and that $(\xi^c)^c = \xi$. Thus, the map $(\omega, \xi) \mapsto (\omega, \xi^c)$ is an involution on the set $\mathcal{D}\mathcal{S}_{2n}$; we use $\phi_{2n}$ to denote this involution. We define the **Genocchi–Corteel involution on D-permutations** to be the map

$$ \phi_{2n}^{\text{GC}} \stackrel{\text{def}}{=} (\varphi_{2n}^{\text{DS}})^{-1} \circ \phi_{2n} \circ \varphi_{2n}^{\text{DS}}. \qquad (6.9) $$

(We call it the **Genocchi–Corteel involution** as we think it is the analog of the Corteel involution for objects counted by the Genocchi and median–Genocchi numbers, we will expand on this in Proposition 6.1 and Corollary 6.2.)

We now state some properties of the involution $\phi_{2n}^{\text{GC}}$; in particular, we will show that the cycle classification is preserved under this involution but the crossings and nestings are exchanged.

**Proposition 6.1.** Let $\sigma \in \mathcal{D}_{2n}$ be a D-permutation on $2n$ letters. The following holds true under the **Genocchi–Corteel involution**:

* If $i$ is a cycle valley (cycle double rise resp.) of $\sigma$ then $i$ is also a cycle valley (cycle double rise) of $\phi_{2n}^{\text{GC}}(\sigma)$, and furthermore, $\text{unest}(i, \sigma) = \text{ucross}(i, \phi_{2n}^{\text{GC}}(\sigma))$.

* If $i$ is a cycle peak (cycle double fall resp.) of $\sigma$ then $i$ is also a cycle peak (cycle double fall) of $\phi_{2n}^{\text{GC}}(\sigma)$, and furthermore, $\text{lnest}(i, \sigma) = \text{lcross}(i, \phi_{2n}^{\text{GC}}(\sigma))$.

* If $i$ is an even fixed point (odd fixed point resp.) of $\sigma$ then $i$ is also an even fixed point (odd fixed point) of $\phi_{2n}^{\text{GC}}(\sigma)$, and furthermore, $\text{psnest}(i, \sigma) = \text{psnest}(i, \phi_{2n}^{\text{GC}}(\sigma))$).

*Proof.* As the Schröder path $\omega$ stays the same under the involution, the sets $F, G, F', G'$ introduced in [14, Section 6.3], which only depend on $\omega$ are the same for both $\sigma$ as well
as $\phi_{2n}^{GC}(\sigma)$. This along with the fact that $\xi_i = \xi_i^c$ whenever $i$ corresponds to (even or odd) fixed point shows that the cycle types are preserved under the involution $\phi_{2n}^{GC}$.

The exchange of crossing and nestings follows from the definition of $\xi^c$ and [14, Lemmas 6.2 and 6.4]. $\square$

As a corollary of Proposition 6.1, we immediately obtain the following:

**Corollary 6.2.** The Genocchi–Corteel $\phi_{2n}^{GC}$ involution on the set of D-permutations $\mathcal{D}_{2n}$ can be restricted down to involutions on the subclasses of D-e-semiderangements

$$ \phi_{2n}^{GC}|_{\mathcal{D}_{2n}^e} : \mathcal{D}_{2n}^e \to \mathcal{D}_{2n}^e, $$

D-o-semiderangements

$$ \phi_{2n}^{GC}|_{\mathcal{D}_{2n}^o} : \mathcal{D}_{2n}^o \to \mathcal{D}_{2n}^o, $$

and D-derangements

$$ \phi_{2n}^{GC}|_{\mathcal{D}_{2n}^{eo}} : \mathcal{D}_{2n}^{eo} \to \mathcal{D}_{2n}^{eo}. $$

For each of these subclasses, their respective involutions preserve the cycle classification of indices, and exchange crossings and nestings statistics as mentioned in Proposition 6.1.

**Fixed points of the Genocchi–Corteel involution:**

Let $\mathcal{G}\mathcal{C}\mathcal{D}_{2n}$ denote the set of fixed points of the Genocchi–Corteel involution, i.e.,

$$ \mathcal{G}\mathcal{C}\mathcal{D}_{2n} \stackrel{\text{def}}{=} \{\sigma \in \mathcal{D}_{2n} : \phi_{2n}^{\mathcal{G}\mathcal{C}}(\sigma) = \sigma\}. \qquad (6.10) $$

Similarly, let $\mathcal{G}\mathcal{C}\mathcal{D}_{2n}^e$, $\mathcal{G}\mathcal{C}\mathcal{D}_{2n}^o$, and $\mathcal{G}\mathcal{C}\mathcal{D}_{2n}^{eo}$ denote the sets of fixed points of the Genocchi–Corteel involution restricted to the subclasses $\mathcal{D}_{2n}^e$, $\mathcal{D}_{2n}^o$, and $\mathcal{D}_{2n}^{eo}$, respectively. We will now compute the cardinality of these sets.

Define the following polynomial counting even and odd fixed points on the set $\mathcal{G}\mathcal{C}\mathcal{D}_{2n}$:

$$ \mathcal{G}\mathcal{C}P_n(w_e, w_o) = \sum_{\sigma \in \mathcal{G}\mathcal{C}\mathcal{D}_{2n}} w_e^{\text{evenfix}(\sigma)} w_o^{\text{oddfix}(\sigma)}. \qquad (6.11) $$

The ordinary generating functions of the polynomials $\mathcal{G}\mathcal{C}P_n$ is a nice rational function:

**Theorem 6.3** (Ordinary generating function for fixed points of the Genocchi–Corteel involution). The ordinary generating function of the polynomials (6.11) is given by

$$ \sum_{n=0}^{\infty} \mathcal{G}\mathcal{C} P_n(w_e, w_o) = \frac{1}{1 - w_e w_o t - \frac{t}{1 - (1 + w_e)(1 + w_o)t}}. \qquad (6.12) $$
*Proof.* We will enumerate labels $\xi$ such that $\xi = \xi^c$ while assigning the following weights to the steps $s_i$ of $\omega$:

$$ \mathrm{wt}(s_i) = \begin{cases} w_e \cdot w_o & \text{if } s_i \text{ is a long level step at height 0} \\ w_e & \text{if } s_i \text{ is a rise from height 1 with label } \xi_i = 1 \\ w_o & \text{if } s_i \text{ is a fall to height 1 with label } \xi_i = 1 \\ 1 & \text{otherwise} \end{cases} \qquad (6.13) $$

Notice that if for some index $i$, step $i$ is a rise starting at height 3 or a fall ending at height 3, we can never have $\xi_i = \xi_i^c$. Therefore, the fixed points of the involution $\phi_{2n}$ are exactly the pairs $(\omega, \xi)$ where the 0-Schröder path $\omega$ does not go above height 3. Using general theory of combinatorics of Thron-type continued fractions, we obtain the continued fraction (6.12). $\square$

We will finally substitute $(w_e, w_o) = (1, 1)$, $(w_e, w_o) = (1, 0)$, $(w_e, w_o) = (0, 1)$, and $(w_e, w_o) = (0, 0)$, in Theorem 6.3 to obtain the number of fixed points under the action of the Genocchi–Corteel involution on D-permutations and its subclasses; we state this in the following corollary.

**Corollary 6.4.** (a) The cardinality of the set $^{\mathrm{GC}}\mathfrak{D}_{2n}$ is given by the sequence [33, A154626]

$$ |^{\mathrm{GC}}\mathfrak{D}_{2n}| = 2^n F_{2n-1}. \qquad (6.14) $$

(b) The cardinality of the sets $^{\mathrm{GC}}\mathfrak{D}_{2n}^e$ and $^{\mathrm{GC}}\mathfrak{D}_{2n}^o$ are given by the sequence [33, A133494]

$$ |^{\mathrm{GC}}\mathfrak{D}_{2n}^e| = |^{\mathrm{GC}}\mathfrak{D}_{2n}^o| = \begin{cases} 1 & \text{for } n = 0 \\ 3^{n-1} & \text{for } n \ge 1. \end{cases} \qquad (6.15) $$

(c) The cardinality of the set $^{\mathrm{GC}}\mathfrak{D}_{2n}^{\mathrm{eo}}$ is given by the sequence [33, A011782]

$$ |^{\mathrm{GC}}\mathfrak{D}_{2n}^{\mathrm{eo}}| = \begin{cases} 1 & \text{for } n = 0 \\ 2^{n-1} & \text{for } n \ge 1. \end{cases} \qquad (6.16) $$

## 6.3 Deb and Sokal’s multivariate polynomials enumerating statistics on D-permutations and its subclasses

In this section, we recall two of Deb and Sokal’s multivariate polynomials enumerating statistics on D-permutations and its subclasses; first we shall state first polynomial [14, eq. (3.2)] then we shall state their first $p, q$-generalisation involving crossings and nestings
[14, eq. (3.21)]. As in Section 3, we will use the glossary of permutation statistics as stated in [12, section 2.5]; this includes the record-and-cycle classification [12, section 2.5.1], and crossings and nestings [12, section 2.5.2].

We now introduce a polynomial in 12 variables that enumerates D-permutations according to the parity-refined record-and-cycle classification:

$$ P_n^{(1)}(x_1, x_2, y_1, y_2, u_1, u_2, v_1, v_2, w_e, w_o, z_e, z_o) = \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)}. \quad (6.17) $$

The polynomials (6.17) have a beautiful T-fraction [14, Theorem 3.3].

Our second polynomial is a polynomial in 22 variables that generalizes (6.17) by including four pairs of $(p, q)$-variables corresponding to the four refined types of crossings and nestings as well as two variables corresponding to pseudo-nestings of fixed points:

$$ P_n^{(2)}(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) = \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)} \times p_{-1}^{\text{lcrosspeak}(\sigma)} p_{-2}^{\text{lcrossdfall}(\sigma)} p_{+1}^{\text{ucrosscval}(\sigma)} p_{+2}^{\text{ucrosscdrise}(\sigma)} \times q_{-1}^{\text{lnestpeak}(\sigma)} q_{-2}^{\text{lnestdfall}(\sigma)} q_{+1}^{\text{unestcval}(\sigma)} q_{+2}^{\text{unestcdrise}(\sigma)} \times s_e^{\text{epsnest}(\sigma)} s_o^{\text{opsnest}(\sigma)} \quad (6.18) $$

where

$$ \text{epsnest}(\sigma) = \sum_{i \in \text{Evenfix}} \text{psnest}(i, \sigma), \quad \text{opsnest}(\sigma) = \sum_{i \in \text{Oddfix}} \text{psnest}(i, \sigma). \quad (6.19) $$

These polynomials (6.18) also have a nice continued fraction [14, Theorem 3.9].

Deb and Sokal have also introduced several other multivariate polynomials in their paper. We, however, refrain from working with those.
## 6.4 Instances of the cyclic sieving phenomenon on D-permutations

We are now ready to state instances of the cyclic sieving phenomena on D-permutations and its subfamilies with respect to the Genocchi–Corteel involution.

We first state a very general result in Proposition 6.5.

**Proposition 6.5.** Let Stat : $\mathcal{D}_{2n} \to \mathbb{N}$ be a statistic defined on D-permutations.

(a) Assume that Stat is obtained as a specialisation of the polynomial $P_n^{(1)}$ defined in (6.17), i.e., as a specialisation of the associated variables. Further assume that the following equations are satisfied

$$z_e(-1) = z_o(-1) = w_e(-1) = w_o(-1) = 1 \quad (6.20a)$$

$$x_1(-1) \cdot y_1(-1) = 1 \quad (6.20b)$$

$$\left[x_2(-1) + 1\right] \times \left[y_2(-1) + 1\right] = 4 \quad (6.20c)$$

$$\left[x_1(-1) + u_1(-1)\right] \times \left[y_1(-1) + v_1(-1)\right] = 0 \quad (6.20d)$$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having $2^n F_{2n-1}$ fixed points.

(b) Assume that Stat is obtained as a specialisation of the polynomial $P_n^{(2)}$ defined in (6.18), i.e., as a specialisation of the associated variables. Further assume that the following equations are satisfied

$$z_e(-1) = z_o(-1) = w_e(-1) = w_o(-1) = s_e(-1) = s_o(-1) = 1 \quad (6.21a)$$

$$x_1(-1) \times y_1(-1) = 1 \quad (6.21b)$$

$$\left[x_2(-1) + 1\right] \times \left[y_2(-1) + 1\right] = 4 \quad (6.21c)$$

$$\left[p_{-1}(-1)x_1(-1) + q_{-1}(-1)u_1(-1)\right] \times \left[p_{+1}(-1)y_1(-1) + q_{+1}(-1)v_1(-1)\right] = 0 \quad (6.21d)$$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having $2^n F_{2n-1}$ fixed points.

*Proof.* We perform these substitutions in [14, Theorems 3.3 and 3.9], respectively, and in both cases obtain the rational function in (6.12) substituted to $w_e = w_o = 1$. $\square$

As a consequence of Proposition 6.5, we can state our main theorem for D-permutations as an easy corollary:
**Theorem 6.6 (CSP for D-permutations).** The following statistics on D-permutations exhibit the cyclic sieving phenomenon on D-permutations with respect to involutions having $2^n F_{2n-1}$ fixed points (in particular, with respect to the Genocchi–Corteel involution on D-permutations):

neither-record-antirecord cycle peaks, neither-record-antirecord cycle valleys, neither-record-antirecords which are not fixed points,

lower crossing of type cpeak, lower nesting of type cpeak, upper crossing of type cval, upper nesting of type cval, lower crossings, lower nestings, upper crossings, upper nestings, crossings, nestings

## 6.5 Instances of the cyclic sieving phenomenon on D-semiderangements and D-derangements

We will now state instances of the cyclic sieving phenomena on D-e-semiderangements, D-o-semiderangements, and D-derangements with respect to the respective restrictions of the Genocchi–Corteel involution.

Analogous to Proposition 6.5, we have the following very general proposition, but, we only state the p,q-versions:

**Proposition 6.7.**

(a) Let Stat : $\mathfrak{D}_{2n}^e \to \mathbb{N}$ be a statistic defined on D-e-semiderangements. Assume that Stat is obtained as a specialisation of the polynomial of the polynomial $P_n^{(2)}|_{z_e=w_e=0}$ defined in (6.18). Further assume that equations (6.21b,d) along with the following equations are satisfied:

$$w_o(-1) = s_o(-1) = 1 \qquad (6.22a)$$

$$x_2(-1) \times [y_2(-1) + 1] = 2 \qquad (6.22b)$$

Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having $3^{n-1}$ fixed points.

(b) Let Stat : $\mathfrak{D}_{2n}^{\mathrm{co}} \to \mathbb{N}$ be a statistic defined on D-derangements. Assume that Stat is obtained as a specialisation of the polynomial of the polynomial $P_n^{(2)}|_{z_e=w_e=z_o=w_o=0}$ defined in (6.18). Further assume that the equations (6.21b,d) along with

$$x_2(-1) \times y_2(-1) = 1 \qquad (6.23)$$

are satisfied. Then the statistic Stat exhibits the cyclic sieving phenomenon with respect to involutions having $2^{n-1}$ fixed points.
Finally, as a corollary we immediately obtain the following theorem:

**Theorem 6.8.** All statistics stated in Theorem 6.6 also exhibit the cyclic sieving phenomenon on D-e-semiderangements, D-o-semiderangements, and D-derangements, respect to involutions having 1 fixed point when $n = 0$, and $3^{n-1}, 3^{n-1}, 2^{n-1}$ fixed points, respectively, for $n \ge 1$ (in particular, with the respective Genocchi-Corteel involutions on these classes of permutations.)

## Acknowledgements

We would like to thank Ashleigh Adams who informed us of this conjecture during AlCoVE 2024 where this work was initiated. We would also like to thank Jessica Striker for fruitful discussions and advice on this article. We also thank Martin Rubey and Christian Stump for helping with updating the description of Statistic 123.

This work was supported by the DIMERS project ANR-18-CE40-0033 funded by Agence Nationale de la Recherche (ANR, France). The author is currently supported by the Tsinghua University Shuimu scholarship.

## A Positivity conjectures on distribution of vincular patterns

Several sequences of numbers and polynomials associated to counting permutation patterns, or pattern-avoiding permutations have been conjectured to be Stieltjes moment sequences, see [7, Section 4.2, Open question], [5]. In this appendix, we introduce two new conjectures that adds to this growing list of “positivity questions” associated with permutation patterns. Our conjectures here involve the distribution of occurrences of vincular patterns of the form $a - bc$ and $bc - a$.

We first recall [9, Proposition 1] as stated in [10, Proposition 2]:

**Proposition A.1.** With respect to being equidistributed, the twelve vincular patterns of the form $a - bc$ or $bc - a$ fall into the three classes

$$ \{1 - 23, 3 - 21, 12 - 3, 32 - 1\} $$

$$ \{1 - 32, 3 - 12, 21 - 3, 23 - 1\} $$

$$ \{2 - 13, 2 - 31, 13 - 2, 31 - 2\} $$

Following Claesson and Mansour [10], we refer to these classes as Class 1, 2 and 3, respectively. Finally, let $P_n^{(1)}(x), P_n^{(2)}(x)$, and $P_n^{(3)}(x)$ denote the generating polynomials of these three classes, respectively.
We have already noted in Theorem 3.8 that the generating function $\sum_{n=0}^{\infty} P_n^{(3)}(x)t^n$ can be written as a Stieltjes-type continued fraction. However, it seems that the generating function of the polynomial sequences $(P_n^{(1)}(x))_{n \ge 0}$, $(P_n^{(2)}(x))_{n \ge 0}$ do not have any nice continued fraction. A consequence of this continued fraction is that the sequence of polynomials $(P_n^{(3)}(x))_{n \ge 0}$ forms a Stieltjes moment sequence for $x \ge 0$. Hence, it is natural to ask if the same is true for the polynomial sequences $(P_n^{(1)}(x))_{n \ge 0}$, $(P_n^{(2)}(x))_{n \ge 0}$ even though they do not have a nice continued fraction. We have the following conjecture:

**Conjecture A.2.** The sequences of polynomials $(P_n^{(1)}(x))_{n \ge 0}$, $(P_n^{(2)}(x))_{n \ge 0}$, where the polynomials $P_n^{(1)}(x)$ and $P_n^{(2)}(x)$ are the generating polynomials for the number of occurrences of a vincular pattern of Class 1 or of Class 2, respectively, are both Stieltjes moment sequences for $x \ge 0$.

To verify this conjecture, for each of the two sequences we computed its S-fraction coefficients; these are rational functions in the variable $x$. We then used the Reduce function in Mathematica to compute the subdomain of $\mathbb{R}$ in which these are non-negative. For the sequence $(P_n^{(1)}(x))_{n \ge 0}$, we were able to do this for the first 30 S-fraction coefficients, and for the sequence $(P_n^{(2)}(x))_{n \ge 0}$ we tested the first 37 S-fraction coefficients. In both cases, we found that these initial S-fraction coefficients are non-negative whenever $x \ge 0$.

A stronger consequence of the existence of the Stieltjes-type continued fraction for the sequence $(P_n^{(3)}(x))_{n \ge 0}$ is that it is coefficientwise-Hankel totally positive [34, Theorem 9.9]. Hence, we tested if the polynomial sequences $(P_n^{(1)}(x))_{n \ge 0}$, $(P_n^{(2)}(x))_{n \ge 0}$ are also coefficientwise Hankel totally positive. Unfortunately, this is not the case. However, this seems to be true after a shift $x \mapsto x+1$; we state this as a conjecture:

**Conjecture A.3.** The sequences of polynomials $(P_n^{(1)}(x+1))_{n \ge 0}$, $(P_n^{(2)}(x+1))_{n \ge 0}$, where the polynomials $P_n^{(1)}(x)$ and $P_n^{(2)}(x)$ are the generating polynomials for the number of occurrences of a vincular pattern of Class 1 or of Class 2, respectively, are both coefficientwise Hankel totally positive with respect to the variable $x$.

We have verified this conjecture for the first $10 \times 10$ submatrix. It is clear that Conjecture A.3 implies that Conjecture A.2 holds for $x \ge 1$.

## References

[1] A. Adams, J. Elder, N. Lafrenière, E. McNicholas, J. Striker, and A. Welch, Cyclic Sieving on permutations - an analysis of maps and statistics in the FindStat database, arxiv:2402.16251 [math.CO].
[2] D. Barsky, Congruences pour les nombres de Genocchi de 2e espèce [extrait d'un travail en commun avec Dominique Dumont], Groupe d'étude d'Analyse ultramétrique, 8e année (1980/81), Exposé no. 34, 13 pp.

[3] F. Benaych-Georges, C. Cuenca and V. Gorin, Matrix addition and the Dunkl transform at high temperature, Commun. Math. Phys. **394**, 735-795 (2022).

[4] V. Bitonti, B. Deb, and A.D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, preprint (December 2024), arXiv:2412.10214 [math.CO].

[5] N. Blitvić, M.S. Kammoun, and E. Steingrímsson, A new perspective on positivity in (consecutive) permutation patterns, Séminaire Lotharingien de Combinatoire 89B, Article #61, 12 pp., Proceedings of the 35th Conference on Formal Power Series and Algebraic Combinatorics (Davis), (2023).

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

[7] A. Bostan, A. Elvey Price, A. J. Guttmann, and J.-M. Maillard, Stieltjes moment sequences for pattern-avoiding permutations, Electron. J. Combin. **27**, no. 4, P4.20, (2020).

[8] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley and C.H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. **359**, 1555-1575 (2007).

[9] A. Claesson, Generalized pattern avoidance, European J. Combin. **22**, 961-971 (2001).

[10] A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations, Adv. Appl. Math. **29**, 293-310 (2002).

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

[12] B. Deb, Enumerative Combinatorics, Continued Fractions and Total Positivity, Ph.D. thesis, University College London (2023), https://discovery.ucl.ac.uk/id/eprint/10179955/

[13] B. Deb, Continued fractions using a Laguerre digraph interpretation of the Foata-Zeilberger bijection and its variants, Combinatorial Theory **5**(1), (2025).

[14] B. Deb and A.D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, Adv. Appl. Math. **161**, 1027-1056 (2024).
[15] B. Deb and A.D. Sokal, A remark on continued fractions for permutations and D-permutations with a weight $-1$ per cycle, Electron. J. Combin. **31**(2), Article number P2.14 (2024).

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

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

[18] D. Dumont and G. Kreweras, Sur le développement d'une fraction continue liée à la série hypergéométrique et son interprétation en termes de records et anti-records dans les permutations, European J. Combin. **9**, 27-32 (1988).

[19] J. Elder, N. Lafreniére, E. McNicholas, J. Striker, and A. Welch, Homomesies on permutations: An analysis of maps and statistics in the FindStat database, Math. Comp. **93**(346), 921-976 (2023).

[20] L. Euler, De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae **5**, 205-237 (1760). [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E247.html]

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

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

[23] 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

[24] 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).

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

[26] A. Kasraoui and J. Zeng, Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. **13**, #R33 (2006).

[27] A.L. Lazar, The homogenized Linear arrangement and its consequences in enumerative combinatorics, Ph.D. thesis, University of Miami (August 2020), https://scholarship.miami.edu/discovery/delivery/01UOML_INST:ResearchRepository/12367619000002976?1#13367618990002976
[28] A. Lazar and M.L. Wachs, The homogenized Linial arrangement and Genocchi numbers, Combin. Theory **2**, issue 1, paper no. 2 (2022), 34 pp.

[29] A. Lazar, Ferrers graphs, D-permutations, and surjective staircases, Ramanujan J., **60**(2), 391–426, (2023).

[30] S.-H. Liu, Mahonian and Euler-Mahonian statistics for set partitions, J. Combin. Theory A **192**, article 105668 (2022).

[31] É. 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).

[32] S.C. Milne, Restricted growth functions, rank row matchings of partition lattices, and q-Stirling numbers, Adv. Math. **43**, 173–196 (1982).

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

[34] M. Pétréolle, A.D. Sokal, and B.-X. Zhu. Lattice paths and branched continued fractions: An infinite sequence of generalizations of the Stieltjes-Rogers and Thron-Rogers polynomials, with coefficientwise Hankel-total positivity, Mem. Amer. Math. Soc., **291**, no. 1450 (2023).

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

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

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

[38] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, J. Combin. Theory A **108**(1), 17–50 (2004).

[39] V. Reiner, D. Stanton and D. White, What is ... cyclic sieving? Notices Amer. Math. Soc., **61**(2), 169–171, (2014).

[40] M. Rubey, C. Stump, et al. FindStat - The combinatorial statistics database, www.FindStat.org (2022).

[41] B. Sagan, The cyclic sieving phenomenon: a survey. In *Surveys in Combinatorics 2011*. Cambridge University Press, (2011).

[42] R. Simion and F.W. Schmidt, Restricted Permutations, Europ. J. Comb., **6**, 383–406 (1985).
[43] 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).

[44] J. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions. J. Comb. Theory Ser. A., **68**(2), 372–409, (1994).

[45] S. Sundaram, On the Combinatorics of Representations of $Sp(2n, \mathbb{C})$. Ph.D. thesis, Massachusetts Institute of Technology (1986), https://dspace.mit.edu/handle/1721.1/15060

[46] S. Thamrongpairoj, and J.B. Remmel, Positional marked patterns in permutations, Discrete Math. Theor. Comput. Sci., **24**(1), (2022).

[47] J. Touchard, Nombres exponentiels et nombres de Bernoulli, Canad. J. Math. **8**, 305–320 (1956).

[48] 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

[49] M. Wachs and D. White, *p*, *q*-Stirling numbers and set partition statistics, J. Combin. Theory A **56**, 27–46 (1991).

[50] J. Zeng, The *q*-Stirling numbers, continued fractions and the *q*-Charlier and *q*-Laguerre polynomials, J. Comput. Appl. Math. **57**, 413–424 (1995).