# Classical continued fractions
for some multivariate polynomials
generalizing the Genocchi and median Genocchi numbers

Bishal Deb1 and Alan D. Sokal1,2
1Department of Mathematics, University College London, London WC1E 6BT, UK
2Department of Physics, New York University, New York, NY 10003, USA

<EMAIL_ADDRESS><EMAIL_ADDRESS>

(December 14, 2022)

###### Abstract

A D-permutation is a permutation of $[2n]$ satisfying $2k-1\leq\sigma(2k-1)$
and $2k\geq\sigma(2k)$ for all $k$; they provide a combinatorial model for the
Genocchi and median Genocchi numbers. We find Stieltjes-type and Thron-type
continued fractions for some multivariate polynomials that enumerate
D-permutations with respect to a very large (sometimes infinite) number of
simultaneous statistics that measure cycle status, record status, crossings
and nestings.

Key Words: Genocchi numbers, median Genocchi numbers, permutation,
D-permutation, D-semiderangement, D-derangement, D-cycle, continued fraction,
J-fraction, S-fraction, T-fraction, Dyck path, almost-Dyck path, Schröder
path.

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

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Classical continued fractions: S-fractions, J-fractions and T-fractions
    2. 2.2 Contraction formulae
    3. 2.3 Transformation formula
    4. 2.4 Euler numbers and augmented Euler numbers
    5. 2.5 Genocchi numbers
    6. 2.6 Median Genocchi numbers
    7. 2.7 Permutation statistics: The record-and-cycle classification
    8. 2.8 Permutation statistics: Crossings and nestings
  3. 3 First T-fraction and its generalizations
    1. 3.1 Preliminaries on record-antirecords
    2. 3.2 First T-fraction
      1. 3.2.1 Main theorem and its corollaries
      2. 3.2.2 Alternative T-fraction, and specializations leading to S-fraction
    3. 3.3 $p,q$-generalizations of the first T-fraction
    4. 3.4 First master T-fraction
    5. 3.5 Variant forms of the first T-fractions
  4. 4 Second T-fraction and its generalizations
    1. 4.1 Second T-fraction
      1. 4.1.1 Conjectured T-fraction and main theorem
      2. 4.1.2 Specialization leading to S-fraction
      3. 4.1.3 Reformulation using cycle valley minima
      4. 4.1.4 S-fraction for D-cycles
    2. 4.2 $p,q$-generalizations of the second T-fraction
    3. 4.3 Second master T-fraction
  5. 5 Preliminaries for the proofs
    1. 5.1 Combinatorial interpretation of continued fractions
    2. 5.2 Labeled Dyck, Motzkin and Schröder paths
  6. 6 First T-fraction: Proof of Theorems 3.3, 3.9, 3.11, 3.12 and 3.13
    1. 6.1 Step 1: Definition of the almost-Dyck path
    2. 6.2 Step 2: Definition of the labels $\xi_{i}$
    3. 6.3 Step 3: Proof of bijection
    4. 6.4 Step 4: Computation of the weights
    5. 6.5 An alternative label $\widehat{\xi}_{i}$: Proof of Theorems 3.12 and 3.13
  7. 7 Second T-fraction: Proof of Theorems 4.2, 4.7 and 4.10
    1. 7.1 Step 1: Definition of the almost-Dyck path
    2. 7.2 Step 2: Definition of the labels $\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$
    3. 7.3 Step 3: Proof of bijection
    4. 7.4 Step 4: Translation of the statistics
    5. 7.5 Step 5: Computation of the weights
  8. 8 Some final remarks
  9. A J-fraction for the polynomials (4.1)

##  1 Introduction

Our purpose here is to present continued fractions for some multivariate
polynomials that generalize either the Genocchi numbers [36, A110501]111 The
Genocchi numbers appear already in Euler’s book Foundations of Differential
Calculus, with Applications to Finite Analysis and Series, first published in
1755 [16, paragraphs 181 and 182]; this book is E212 in Eneström’s [14]
catalogue. These numbers were revisited by Genocchi [25] in 1852. The
beautiful survey article of Viennot [49] contains a wealth of useful
information. Our notation for the Genocchi and median Genocchi numbers is
nonstandard but, we believe, sensible and logical. Later we will present a
translation dictionary with respect to (the plethora of) previous notations:
see footnotes 6 and 8.

$(g_{n})_{n\geq
0}\;=\;1,1,3,17,155,2073,38227,929569,28820619,1109652905,\ldots$ (1.1)

or the median Genocchi numbers [36, A005439]

$(h_{n})_{n\geq 0}\;=\;1,1,2,8,56,608,9440,198272,5410688,186043904,\ldots\;.$
(1.2)

The present paper can be viewed as a sequel to a recent article by Zeng and
one of us [46] in which we presented Stieltjes-type and Jacobi-type continued
fractions for some “master polynomials” that enumerate permutations, set
partitions or perfect matchings with respect to a large (sometimes infinite)
number of independent statistics. These polynomials systematize what we think
of as the “linear family”: namely, sequences in which the Stieltjes continued-
fraction coefficients $(\alpha_{n})_{n\geq 1}$ grow linearly in $n$. More
precisely, in the simplest case [46, Theorem 2.1] the even and odd
coefficients grow affinely in $n$:

$\alpha_{2k-1}&=x+(k-1)u\\\ \alpha_{2k}=y+(k-1)v$ (1.3)

When $x=y=u=v=1$, these coefficients $\alpha_{2k-1}=\alpha_{2k}=k$ correspond
to Euler’s [17, section 21] continued fraction for the sequence $a_{n}=n!$; so
it is natural to expect that the resulting polynomials $P_{n}(x,y,u,v)$ can be
interpreted as enumerating permutations of $[n]$ with respect to some suitable
statistics. The purpose of [46] was to exhibit explicitly those statistics,
and then to present some generalizations involving more refined statistics.

In the present paper we take one step up in complexity, to consider the
“quadratic family”, in which the $(\alpha_{n})_{n\geq 1}$ grow quadratically
in $n$. For instance, we could consider

$\alpha_{2k-1}&=[x_{1}+(k-1)u_{1}]\,[x_{2}+(k-1)u_{2}]\\\
\alpha_{2k}=[y_{1}+(k-1)v_{1}]\,[y_{2}+(k-1)v_{2}]$ (1.4)

With all parameters set to 1, these coefficients
$\alpha_{2k-1}=\alpha_{2k}=k^{2}$ correspond to the continued fraction [49,
eq. (9.7)] [50, p. V-15] for the median Genocchi numbers; so it is natural to
seek a combinatorial model that is enumerated by the median Genocchi numbers.
Many such models are known. In this paper we shall focus on a class of
permutations of $[2n]$ called D-permutations [33, 32], which are defined by
imposing some constraints concerning the parity (even/odd) of excedances and
anti-excedances. Recall that an index $i$ in a permutation $\sigma$ is called
an excedance in case $i<\sigma(i)$, an anti-excedance in case $i>\sigma(i)$,
and a fixed point in case $i=\sigma(i)$. A permutation is called a
D-permutation in case it contains no even excedances and no odd anti-
excedances. Equivalently, a permutation is a D-permutation in case
$2k-1\leq\sigma(2k-1)$ and $2k\geq\sigma(2k)$ for all $k$. Let us say also
that a permutation is an e-semiderangement (resp. o-semiderangement) in case
in 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).222 In the past,
D-o-semiderangements have been called Genocchi permutations [42, 40, 27] or
excedance-alternating permutations [12]; D-e-semiderangements [5, p. 316,
Corollaire 1] have been called Dumont permutations [33, 32, 38] or Dumont
permutations of the second kind [3, 4]; D-derangements have been called Dumont
derangements [33, 32, 38]. D-permutations that are not semiderangements were
apparently first considered in the recent work of Lazar and Wachs [33, 32].
Note also that the involution of ${\mathfrak{S}}_{2n}$ defined by
$\sigma\mapsto R\circ\sigma\circ R$, where $R(i)=2n+1-i$ is the reversal map,
takes D-permutations into D-permutations and interchanges e-semiderangements
with o-semiderangements; it therefore yields a bijection between D-e-
semiderangements and D-o-semiderangements. Therefore, any result about one of
the two types of D-semiderangements can be expressed equivalently in terms of
the other.  A D-permutation that contains exactly one cycle is called a
D-cycle. Notice that a D-cycle is also a D-derangement. Let
${\mathfrak{D}}_{2n}$ (resp. ${\mathfrak{D}}^{\rm e}_{2n},{\mathfrak{D}}^{\rm
o}_{2n},{\mathfrak{D}}^{\rm eo}_{2n},{\mathfrak{DC}}_{2n}$) denote the set of
all D-permutations (resp. D-e-semiderangements, D-o-semiderangements,
D-derangements, D-cycles) of $[2n]$. For instance,

${\mathfrak{D}}_{2}&=\\{12,\,21^{\rm eo}\\}\\\
{\mathfrak{D}}_{4}=\\{1234,\,1243,\,2134,\,2143^{\rm eo},\,3142^{\rm
eo},\,3241^{\rm o},\,4132^{\rm e},\,4231\\}\\\ {\mathfrak{DC}}_{2}=\\{21\\}\\\
{\mathfrak{DC}}_{4}=\\{3142\\}$ (1.5)

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

> Remark. Three natural variants of this setup lead to nothing new:
>
>   * 1)
>
> In a D-permutation of $[2n+1]$, $2n+1$ must be a fixed point, and the rest
> is a D-permutation of $[2n]$.
>
>   * 2)
>
> Suppose we define an anti-D-permutation to be one in which
> $2k-1\geq\sigma(2k-1)$ and $2k\leq\sigma(2k)$ for all $k$. Then, in an anti-
> D-permutation of $[2n]$, $1$ and $2n$ must be fixed points, and the rest is,
> after renumbering, a D-permutation of $[2n-2]$.
>
>   * 3)
>
> In an anti-D-permutation of $[2n+1]$, $1$ must be a fixed point, and the
> rest is, after renumbering, a D-permutation of $[2n]$.
>
>

>
> So there is no loss of generality in studying only D-permutations of $[2n]$.
> $\blacksquare$
>

It is known [5, 8, 33, 32] — and we will recover as part of our work — that

$|{\mathfrak{D}}_{2n}|&=h_{n+1}\\\ |{\mathfrak{D}}^{\rm
e}_{2n}|\;=\;|{\mathfrak{D}}^{\rm o}_{2n}|=g_{n}\\\ |{\mathfrak{D}}^{\rm
eo}_{2n}|=h_{n}\\\ |{\mathfrak{DC}}_{2n}|=g_{n-1}$ (1.6)

This suggests that we can obtain continued fractions for multivariate
polynomials enumerating D-permutations, D-semiderangements, D-derangements or
D-cycles by generalizing the known continued fractions for the Genocchi and
median Genocchi numbers, analogously to what was done in [46] by generalizing
Euler’s continued fraction for the factorials. That is, indeed, what we shall
do in this paper. These continued fractions will be of Stieltjes and Thron
types; they can also be transformed by contraction into Jacobi type.333 We
call these classical continued fractions, in order to contrast them with the
recently-introduced branched continued fractions [39], which are believed to
apply to certain higher-order generalizations of the Genocchi numbers [39,
Conjecture 16.1].  Our principal results will be:

  * 1)

A Thron-type continued fraction in 12 variables (Theorem 3.3) that enumerates
D-permutations with respect to the parity-refined record-and-cycle
classification (defined in Section 2.7). Specializations of this continued
fraction give Stieltjes-type continued fractions that enumerate
D-semiderangements and D-derangements.

  * 2)

A Thron-type continued fraction in 22 variables (Theorem 3.9) that generalizes
the previous T-fraction by including four pairs of $(p,q)$-variables that
count crossings and nestings and a pair of variables that count pseudo-
nestings of fixed points (defined in Section 2.8).

  * 3)

A Thron-type continued fraction in six infinite families of indeterminates
(Theorem 3.11) that generalizes the preceding two by further refining the
counting of crossings, nestings and pseudo-nestings.

We call these the three versions of our “first T-fraction”. Already the first
version (Theorem 3.3) contains several known continued fractions for the
Genocchi and median Genocchi numbers as special cases. We also have three
variant versions of the first T-fraction (Theorems 3.12 and 3.13) using
slightly different statistics.

We will also have three versions of a “second T-fraction” (Theorems 4.2, 4.7
and 4.10) that includes the counting of cycles, at the expense of partially
renouncing the counting of records; as a corollary we obtain a continued
fraction for D-cycles (Corollary 4.6). The second T-fractions look less
symmetrical than the first ones; this defect seems to be inherent in including
the counting of cycles (just as in [46]). The proofs of both the first and
second T-fractions will be based on bijections from D-permutations to labeled
Schröder paths.

The plan of this paper is as follows: In Section 2 we recall some needed
definitions and facts concerning continued fractions, the Genocchi and median
Genocchi numbers, and permutation statistics. In Section 3 we state the three
versions of the first T-fraction and note some of their corollaries, and in
Section 4 we do the same for the second T-fraction. In Section 5 we recall how
continued fractions can be proven by bijection to labeled Dyck, Motzkin or
Schröder paths. In Section 6 we prove the first T-fraction by a bijection that
combines ideas of Randrianarivony [40] and Foata–Zeilberger [23] together with
some new ingredients. In Section 7 we prove the second T-fraction by a variant
bijection that analogously combines ideas of Randrianarivony [40] and Biane
[2].444 Randrianarivony’s proof [40, Section 6] is already motivated by ideas
of Foata and Zeilberger [23], as Randrianarivony himself points out [40, pp.
78, 88]. By contrast, our work here seems to be the first to apply a Biane-
like [2] bijection to D-permutations, D-semiderangements or D-derangements.
We conclude (Section 8) with some brief remarks on the relation of our work to
[46].

##  2 Preliminaries

In this section we begin by explaining briefly the types of continued
fractions that will be employed (Section 2.1) and recalling some contraction
and transformation formulae (Sections 2.2 and 2.3). We then define the Euler,
Genocchi and median Genocchi numbers and recall their continued fractions
(Sections 2.4–2.6). Finally, we define some permutation statistics that will
play a central role in this paper (Sections 2.7 and 2.8).

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

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

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\cfrac{\alpha_{1}t}{1-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\;,$
(2.1)

and Jacobi-type (J-fractions),

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\gamma_{0}t-\cfrac{\beta_{1}t^{2}}{1-\gamma_{1}t-\cfrac{\beta_{2}t^{2}}{1-\cdots}}}\;\;.$
(2.2)

A less commonly studied type of continued fraction is the Thron-type
(T-fraction):

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\delta_{1}t-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\;.$
(2.3)

(Both sides of all these expressions are to be interpreted as formal power
series in the indeterminate $t$.) This line of investigation goes back at
least to Euler [17, 18], but it gained impetus following Flajolet’s [20]
seminal discovery that any S-fraction (resp. J-fraction) can be interpreted
combinatorially as a generating function for Dyck (resp. Motzkin) paths with
suitable weights for each rise and fall (resp. each rise, fall and level
step). More recently, several authors [24, 37, 29, 45, 13] have found a
similar combinatorial interpretation of the general T-fraction: namely, as a
generating function for Schröder paths with suitable weights for each rise,
fall and long level step. These interpretations will be reviewed in Section
5.1 below.

###  2.2 Contraction formulae

The formulae for even and odd contraction of an S-fraction to an equivalent
J-fraction are well known: see e.g. [11, Lemmas 1 and 2] [7, Lemma 1] for very
simple algebraic proofs, and see [50, pp. V-31–V-32] for enlightening
combinatorial proofs based on grouping pairs of steps in a Dyck path. Here we
will need an extension of these formulae to suitable subclasses of T-fractions
[45]:

######  Proposition 2.1 (Even contraction for T-fractions with
$\delta_{2}=\delta_{4}=\delta_{6}=\ldots=0$).

We have

$\displaystyle\cfrac{1}{1-\delta_{1}t-\cfrac{\alpha_{1}t}{1-\cfrac{\alpha_{2}t}{1-\delta_{3}t-\cfrac{\alpha_{3}t}{1-\cdots}}}}\;\;=\;$
$\displaystyle\cfrac{1}{1-(\alpha_{1}+\delta_{1})t-\cfrac{\alpha_{1}\alpha_{2}t^{2}}{1-(\alpha_{2}+\alpha_{3}+\delta_{3})t-\cfrac{\alpha_{3}\alpha_{4}t^{2}}{1-(\alpha_{4}+\alpha_{5}+\delta_{5})t-\cfrac{\alpha_{5}\alpha_{6}t^{2}}{1-\cdots}}}}\;\;.\qquad$
(2.4)

That is, the T-fraction on the left-hand side of (2.4) equals the J-fraction
with coefficients

$\gamma_{0}&=\alpha_{1}+\delta_{1}\\\
\gamma_{n}=\alpha_{2n}+\alpha_{2n+1}+\delta_{2n+1}\quad\hbox{for $n\geq 1$}\\\
\beta_{n}=\alpha_{2n-1}\alpha_{2n}$ (2.5)

Here (2.4)/(2.5) holds as an identity in
${\mathbb{Z}}[{\bm{\alpha}},{\bm{\delta}}_{\rm odd}][[t]]$, where
${\bm{\delta}}_{\rm odd}=(\delta_{1},0,\delta_{3},0,\ldots)$.

######  Proposition 2.2 (Odd contraction for T-fractions with
$\delta_{1}=\delta_{3}=\delta_{5}=\ldots=0$).

We have

$\displaystyle\cfrac{1}{1-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\cfrac{\alpha_{3}t}{1-\delta_{4}t-\cfrac{\alpha_{4}t}{1-\cdots}}}}}\;\;=\;$
$\displaystyle
1\>+\>\cfrac{\alpha_{1}t}{1-(\alpha_{1}+\alpha_{2}+\delta_{2})t-\cfrac{\alpha_{2}\alpha_{3}t^{2}}{1-(\alpha_{3}+\alpha_{4}+\delta_{4})t-\cfrac{\alpha_{4}\alpha_{5}t^{2}}{1-\cdots}}}\;\;.\qquad$
(2.6)

That is, the T-fraction on the left-hand side of (2.6) equals $1$ plus
$\alpha_{1}t$ times the J-fraction with coefficients

$\gamma_{n}&=\alpha_{2n+1}+\alpha_{2n+2}+\delta_{2n+2}\\\
\beta_{n}=\alpha_{2n}\alpha_{2n+1}$ (2.7)

Here (2.6)/(2.7) holds as an identity in
${\mathbb{Z}}[{\bm{\alpha}},{\bm{\delta}}_{\rm even}][[t]]$, where
${\bm{\delta}}_{\rm even}=(0,\delta_{2},0,\delta_{4},\ldots)$.

Both the algebraic and the combinatorial proofs of the contraction formulae
for S-fractions can be easily generalized [45] to prove Propositions 2.1 and
2.2.

One consequence of Proposition 2.1 is that if two T-fractions with only odd
deltas — say, one with coefficients $({\bm{\alpha}},{\bm{\delta}}_{\rm odd})$
and the other with coefficients
$({\bm{\alpha}}^{\prime},{\bm{\delta}}^{\prime}_{\rm odd})$ — give rise by
contraction to the same J-fraction $({\bm{\beta}},{\bm{\gamma}})$, then they
must be equal. In some cases this principle can be used to transform a
T-fraction into an S-fraction (that is, ${\bm{\delta}}^{\prime}_{\rm
odd}={\bm{0}}$): see, for instance, Corollary 4.3 below.

By combining Propositions 2.1 and 2.2, we obtain:

######  Corollary 2.3 (Combining odd and even contraction).

If

$\sum_{n=0}^{\infty}a_{n}t^{n}\;=\;\cfrac{1}{1-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\cfrac{\alpha_{3}t}{1-\delta_{4}t-\cfrac{\alpha_{4}t}{1-\cdots}}}}}\;,$
(2.8)

then

$\sum_{n=0}^{\infty}a_{n+1}t^{n}\;=\;\cfrac{a_{1}}{1-\delta^{\prime}_{1}t-\cfrac{\alpha^{\prime}_{1}t}{1-\cfrac{\alpha^{\prime}_{2}t}{1-\delta^{\prime}_{3}t-\cfrac{\alpha^{\prime}_{3}t}{1-\cdots}}}}$
(2.9)

whenever

$\alpha_{1}+\alpha_{2}+\delta_{2}&=\alpha^{\prime}_{1}+\delta^{\prime}_{1}\\\
\alpha_{2n+1}+\alpha_{2n+2}+\delta_{2n+2}=\alpha^{\prime}_{2n}+\alpha^{\prime}_{2n+1}+\delta^{\prime}_{2n+1}\quad\hbox{for
$n\geq 1$}\\\
\alpha_{2n}\alpha_{2n+1}=\alpha^{\prime}_{2n-1}\alpha^{\prime}_{2n}$ (2.10)

###  2.3 Transformation formula

We now prove a useful transformation formula for T-fractions. First, a lemma:

######  Lemma 2.4.

Let $R$ be a commutative ring, and let $f(t),g(t)\in R[[t]]$. Then

$1\>+\>{tf(t)\over 1-tf(t)-tg(t)}\;=\;\cfrac{1}{1-\cfrac{tf(t)}{1-tg(t)}}$
(2.11)

as an identity in $R[[t]]$.

Proof. Trivial: both sides equal $\dfrac{1-tg(t)}{1-tf(t)-tg(t)}$. $\square$

######  Proposition 2.5 (Augmentation/restriction of T-fraction).

$1\>+\>\cfrac{\delta_{1}t}{1-\delta_{1}t-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\ldots}}}\;\;=\;\;\cfrac{1}{1-\cfrac{\delta_{1}t}{1-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\ldots}}}}\;\>.\quad$
(2.12)

Proof. Use the lemma with $f(t)=\delta_{1}$ and
$g(t)=\displaystyle\cfrac{\alpha_{1}}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\ldots}}\;\,$.
$\square$

Reading the identity (2.12) from left to right, it says that if the ogf of a
sequence ${\bm{a}}=(a_{0},a_{1},a_{2},\ldots)$ with $a_{0}=1$ is given by a
T-fraction with coefficients ${\bm{\alpha}}$ and ${\bm{\delta}}$, then the ogf
of the “augmented” sequence
${\bm{a}}^{\prime}=(1,\delta_{1}a_{0},\delta_{1}a_{1},\delta_{1}a_{2},\ldots)$
is given by a T-fraction with coefficients ${\bm{\alpha}}^{\prime}$ and
${\bm{\delta}}^{\prime}$, where

$\alpha^{\prime}_{1}&=\delta_{1}\\\
\alpha^{\prime}_{n}=\alpha_{n-1}\quad\hbox{for $n\geq 2$}\\\
\delta^{\prime}_{1}=\delta^{\prime}_{2}=0\\\
\delta^{\prime}_{n}=\delta_{n-1}\quad\hbox{for $n\geq 3$}$ (2.13)

In particular, if $\delta_{2}=\delta_{3}=\ldots=0$, then the T-fraction on the
right-hand side is an S-fraction. Of course, this transformation gives
something interesting only when $\delta_{1}\neq 0$.

Alternatively, reading the identity (2.12) from right to left, it says that if
the ogf of a sequence
${\bm{a}}^{\prime}=(a^{\prime}_{0},a^{\prime}_{1},a^{\prime}_{2},\ldots)$ with
$a^{\prime}_{0}=1$ is given by a T-fraction with coefficients
${\bm{\alpha}}^{\prime}$ and ${\bm{\delta}}^{\prime}$, where
$\delta^{\prime}_{1}=\delta^{\prime}_{2}=0$ (and of course
$\alpha^{\prime}_{1}\neq 0$), then the ogf of the “restricted” sequence
${\bm{a}}=(a_{1}/\alpha^{\prime}_{1},a_{2}/\alpha^{\prime}_{1},\ldots)$ is
given by a T-fraction with coefficients ${\bm{\alpha}}$ and ${\bm{\delta}}$,
where

$\alpha_{n}&=\alpha^{\prime}_{n+1}\\\ \delta_{1}=\alpha^{\prime}_{1}\\\
\delta_{n}=\delta^{\prime}_{n+1}\quad\hbox{for $n\geq 2$}$ (2.14)

###  2.4 Euler numbers and augmented Euler numbers

The Euler numbers [36, A000111]

$(E_{n})_{n\geq
0}\;=\;1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,\ldots$ (2.15)

are positive integers defined by the exponential generating function

$\sec t+\tan t\;=\;\sum_{n=0}^{\infty}E_{n}\,{t^{n}\over n!}\;.$ (2.16)

The $(E_{2n})_{n\geq 0}$ are also called secant numbers [36, A000364], and the
$(E_{2n+1})_{n\geq 0}$ are called tangent numbers [36, A000182]. Their
ordinary generating functions have the S-fraction representations

$\sum_{n=0}^{\infty}E_{2n}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{1^{2}t}{1-\cfrac{2^{2}t}{1-\cfrac{3^{2}t}{1-\cdots}}}}$
(2.17)

with coefficients $\alpha_{n}=n^{2}$, and

$\sum_{n=0}^{\infty}E_{2n+1}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{1\cdot
2t}{1-\cfrac{2\cdot 3t}{1-\cfrac{3\cdot 4t}{1-\cdots}}}}$ (2.18)

with coefficients $\alpha_{n}=n(n+1)$.555 These formulae were found by
Stieltjes [48, p. H9] in 1889 and by Rogers [43, p. 77] in 1907. They were
given beautiful combinatorial proofs by Flajolet [20] in 1980.  See [22, 49,
31, 47, 44] for further information on the Euler numbers, including their
combinatorial interpretations and moment representations.

We define the augmented Euler numbers [36, A065619] by

$E^{\sharp}_{n}\;\stackrel{{\scriptstyle\rm def}}{{=}}\;(n+1)\,E_{n}\;.$
(2.19)

They have the exponential generating function

$t\,(\sec t+\tan
t)\;=\;\sum_{n=0}^{\infty}E^{\sharp}_{n}\,{t^{n+1}\over(n+1)!}\;.$ (2.20)

The $(E^{\sharp}_{2n})_{n\geq 0}$ are the augmented secant numbers [36,
A009843], and the $(E^{\sharp}_{2n+1})_{n\geq 0}$ are the augmented tangent
numbers [36, A009752].

###  2.5 Genocchi numbers

The Genocchi numbers [36, A110501]666 Our $g_{n}$ is usually written by
combinatorialists as $G_{2n+2}$. However, many texts — particularly older
ones, or those in the analysis and special-functions literature — define the
(signed) Genocchi numbers $(G_{n})_{n\geq 0}$ by [35, 24.15.1] ${2t\over
e^{t}+1}\;=\;\sum_{n=1}^{\infty}G_{n}\,{t^{n}\over n!}\;,$ which leads to
$G_{0}=0$, $G_{1}=1$, $G_{n}=0$ for odd $n\geq 3$, and
$G_{2n+2}=(-1)^{n+1}g_{n}$. Warning: Our $g_{n}$ is denoted $g_{n+1}$ by Lazar
and Wachs [33, 32] and Eu, Fu, Lai and Lo [15].

$(g_{n})_{n\geq
0}\;=\;1,1,3,17,155,2073,38227,929569,28820619,1109652905,\ldots$ (2.21)

are odd positive integers [34, 1, 26] [21, pp. 217–218] defined by the
exponential generating function

$t\,\tan(t/2)\;=\;\sum_{n=0}^{\infty}g_{n}\,{t^{2n+2}\over(2n+2)!}\;.$ (2.22)

They are therefore rescaled versions of the augmented tangent numbers:

$g_{n}\;=\;4^{-n}\,(n+1)\,E_{2n+1}\;=\;2^{-(2n+1)}\,E^{\sharp}_{2n+1}\;.$
(2.23)

The ordinary generating function of the Genocchi numbers has a classical
S-fraction expansion [49, eq. (7.5)] [50, p. V-9] [11, eqns. (1.4) and (3.9)]

$\sum_{n=0}^{\infty}g_{n}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{1\cdot
1t}{1-\cfrac{1\cdot 2t}{1-\cfrac{2\cdot 2t}{1-\cfrac{2\cdot 3t}{1-\cdots}}}}}$
(2.24)

with coefficients

$\alpha_{2k-1}\>=\>k^{2}\,,\quad\alpha_{2k}\>=\>k(k+1)\;.$ (2.25)

It then follows from Proposition 2.5 that the once-shifted Genocchi numbers
$(g_{n+1})_{n\geq 0}$ have a T-fraction

$\sum_{n=0}^{\infty}g_{n+1}\,t^{n}\;=\;\cfrac{1}{1-t-\cfrac{1\cdot
2t}{1-\cfrac{2\cdot 2t}{1-\cfrac{2\cdot 3t}{1-\cfrac{3\cdot 3t}{1-\cdots}}}}}$
(2.26)

with coefficients

$\alpha_{2k-1}\>=\>k(k+1)\,,\quad\alpha_{2k}\>=\>(k+1)^{2}\,,\quad\delta_{1}\>=\>1\,,\quad\delta_{n}\>=\>0\;\hbox{for
$n\geq 2$}\;.$ (2.27)

Remark. Some generalizations of (2.24)/(2.25), incorporating additional
parameters, are known in a variety of algebraic or combinatorial models: see
[6, Section 6] [9] [51, eq. (3.3) and Corollaire 8] [41, Théorème 3 and
Proposition 13] [42, Proposition 10] [40, Théorème 1.2] [27, eq. (5) and
Théorème 2]. See also [27, Corollaire 3] for a generalization of the
T-fraction (2.26)/(2.27).777 There is a typographical error in [27, eq. (12)]:
on the left-hand side, $t^{n}$ should be $t^{n-1}$.  $\blacksquare$

###  2.6 Median Genocchi numbers

An alternative way of defining the Genocchi numbers is by the Seidel
recurrence

$s_{n,k}\;=\;\left\\{\\!\\!\begin{array}[]{cl}\sum\limits_{j=0}^{k}s_{n-1,j}&\text{if
$n$ is even}\\\ &\\\\[-5.69054pt] \sum\limits_{j=k}^{\lfloor
n/2\rfloor}s_{n-1,j}&\text{if $n$ is
odd}\end{array}\\!\\!\right\\}\quad\hbox{for $n\geq 1$ and $0\leq k\leq\lfloor
n/2\rfloor$}$ (2.28)

with $s_{0,0}=1$ and $s_{n,k}=0$ for $k>\lfloor n/2\rfloor$. The Seidel
triangle [36, A014781] begins

$n\setminus k$ | 0 | 1 | 2 | 3 | 4 | 5 | Row sums
---|---|---|---|---|---|---|---
0 | 1 |  |  |  |  |  | 1
1 | 1 |  |  |  |  |  | 1
2 | 1 | 1 |  |  |  |  | 2
3 | 2 | 1 |  |  |  |  | 3
4 | 2 | 3 | 3 |  |  |  | 8
5 | 8 | 6 | 3 |  |  |  | 17
6 | 8 | 14 | 17 | 17 |  |  | 56
7 | 56 | 48 | 34 | 17 |  |  | 155
8 | 56 | 104 | 138 | 155 | 155 |  | 608
9 | 608 | 552 | 448 | 310 | 155 |  | 2073
10 | 608 | 1160 | 1608 | 1918 | 2073 | 2073 | 9440
11 | 9440 | 8832 | 7672 | 6064 | 4146 | 2073 | 38227

It can be shown [10] that the Genocchi numbers occur on the “diagonals” and
“subdiagonals” of the Seidel triangle,

$g_{n}\;=\;s_{2n,n}\;=\;s_{2n,n-1}\;=\;s_{2n+1,n}$ (2.29)

(where we set $s_{0,-1}=1$); they are also the odd row sums:

$\sum_{k=0}^{n}s_{2n+1,k}\;=\;g_{n+1}\;.$ (2.30)

The median Genocchi numbers (or Genocchi medians for short) [36, A005439]888
Our $h_{n}$ is usually written by combinatorialists as $H_{2n+1}$. Warning:
Lazar and Wachs’ [33, 32] $h_{n}$ equals our $h_{n+1}$. Pan and Zeng’s [38]
$h_{n}$ is our $h_{n+1}$ divided by $2^{n}$.  are defined by the zeroth column
of the Seidel triangle,

$h_{n}\;\stackrel{{\scriptstyle\rm def}}{{=}}\;s_{2n,0}\;=\;s_{2n-1,0}$ (2.31)

(where we set $s_{-1,0}=1$); they are also the even row sums:

$\sum_{k=0}^{n}s_{2n,k}\;=\;h_{n+1}\;.$ (2.32)

The Genocchi medians can alternatively be defined by [28, p. 63]

$h_{n}\;=\;\sum_{i=0}^{n-1}(-1)^{i}\,\binom{n}{2i+1}\,g_{n-1-i}\;.$ (2.33)

They are also rescaled versions of the 1-binomial transform of the augmented
secant numbers [11, Corollary 3]:

$h_{n}\;=\;4^{-n}\sum_{k=0}^{n}\binom{n}{k}\,(2k+1)E_{2k}\;=\;4^{-n}\sum_{k=0}^{n}\binom{n}{k}\,E^{\sharp}_{2k}$
(2.34)

[compare to (2.23)].

The Genocchi medians

$(h_{n})_{n\geq
0}\;=\;1,1,2,8,56,608,9440,198272,5410688,186043904,7867739648,\ldots$ (2.35)

do not have any known exponential generating function. However, their ordinary
generating function has a nice classical S-fraction expansion [49, eq. (9.7)]
[50, p. V-15] [11, eqns. (1.5) and (3.8)]:

$\sum_{n=0}^{\infty}h_{n}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{1t}{1-\cfrac{1t}{1-\cfrac{4t}{1-\cfrac{4t}{1-\cdots}}}}}$
(2.36)

with coefficients

$\alpha_{2k-1}\>=\>\alpha_{2k}\>=\>k^{2}\;.$ (2.37)

It then follows from Corollary 2.3 that the once-shifted median Genocchi
numbers $(h_{n+1})_{n\geq 0}$ have an S-fraction

$\sum_{n=0}^{\infty}h_{n+1}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{2t}{1-\cfrac{2t}{1-\cfrac{6t}{1-\cfrac{6t}{1-\cdots}}}}}$
(2.38)

with coefficients

$\alpha_{2k-1}\>=\>\alpha_{2k}\>=\>k(k+1)\;.$ (2.39)

Moreover, from Proposition 2.5 they also a T-fraction

$\sum_{n=0}^{\infty}h_{n+1}\,t^{n}\;=\;\cfrac{1}{1-t-\cfrac{1t}{1-\cfrac{4t}{1-\cfrac{4t}{1-\cfrac{9t}{1-\cdots}}}}}$
(2.40)

with coefficients

$\alpha_{2k-1}\>=\>k^{2}\,,\quad\alpha_{2k}\>=\>(k+1)^{2}\,,\quad\delta_{1}\>=\>1\,,\quad\delta_{n}\>=\>0\;\hbox{for
$n\geq 2$}\;.$ (2.41)

Finally, let us define, for future reference, the sequence
$(h^{\flat}_{n+1})_{n\geq 0}$ corresponding to the S-fraction underlying
(2.40):

$\sum_{n=0}^{\infty}h^{\flat}_{n+1}\,t^{n}\;=\;\cfrac{1}{1-\cfrac{1t}{1-\cfrac{4t}{1-\cfrac{4t}{1-\cfrac{9t}{1-\cdots}}}}}$
(2.42)

with coefficients

$\alpha_{2k-1}\>=\>k^{2}\,,\quad\alpha_{2k}\>=\>(k+1)^{2}\;.$ (2.43)

This sequence begins

$(h^{\flat}_{n+1})_{n\geq
0}\;=\;1,1,5,41,493,8161,178469,4998905,174914077,7487810257,\ldots$ (2.44)

and cannot be found, at present, in [36]. In Section 3.2 we will give its
combinatorial interpretation. Using Proposition 2.5, we also get a T-fraction
for the once-shifted sequence $(h^{\flat}_{n+2})_{n\geq 0}$:

$\sum_{n=0}^{\infty}h^{\flat}_{n+2}\,t^{n}\;=\;\cfrac{1}{1-t-\cfrac{4t}{1-\cfrac{4t}{1-\cfrac{9t}{1-\cdots}}}}$
(2.45)

with coefficients

$\alpha_{2k-1}\>=\>(k+1)^{2}\,,\quad\alpha_{2k}\>=\>(k+1)^{2}\,,\quad\delta_{1}\>=\>1\,,\quad\delta_{n}\>=\>0\;\hbox{for
$n\geq 2$}\;.$ (2.46)

Remark. Some generalizations of (2.36)/(2.37) or (2.38)/(2.39), incorporating
additional parameters, are known in a variety of algebraic or combinatorial
models: see [6, Section 6] [9] [51, eq. (3.3) and Corollaire 8] [41, Théorème
3 and Proposition 13] [42, Proposition 10 and Corollary 13] [19, Theorem 0.1]
[38, Corollary 6]. $\blacksquare$

###  2.7 Permutation statistics: The record-and-cycle classification

We now define some permutation statistics that will play a central role in
what follows.

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

  * •

excedance (exc) if $i<\sigma(i)$;

  * •

anti-excedance (aexc) if $i>\sigma(i)$;

  * •

fixed point (fix) if $i=\sigma(i)$.

Clearly every index $i$ belongs to exactly one of these three types; we call
this the excedance classification. We also say that $i$ is a weak excedance if
$i\leq\sigma(i)$, and a weak anti-excedance if $i\geq\sigma(i)$.

A more refined classification is as follows: an index $i\in[N]$ is called a

  * •

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

  * •

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

  * •

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

  * •

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

  * •

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

Clearly every index $i$ belongs to exactly one of these five types; we refer
to this classification as the cycle classification. Obviously, excedance =
cycle valley or cycle double rise, and anti-excedance = cycle peak or cycle
double fall.

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

  * •

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

  * •

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

  * •

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

  * •

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

  * •

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

  * •

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

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

The record and cycle classifications of indices are related as follows:

>   * (a)
>
> Every record is a weak excedance, and every exclusive record is an
> excedance.
>
>   * (b)
>
> Every antirecord is a weak anti-excedance, and every exclusive antirecord is
> an anti-excedance.
>
>   * (c)
>
> Every record-antirecord is a fixed point.
>
>

Therefore, by applying the record and cycle classifications simultaneously, we
obtain 10 disjoint categories [46]:

  * •

ereccval: exclusive records that are also cycle valleys;

  * •

ereccdrise: exclusive records that are also cycle double rises;

  * •

eareccpeak: exclusive antirecords that are also cycle peaks;

  * •

eareccdfall: exclusive antirecords that are also cycle double falls;

  * •

rar: record-antirecords (these are always fixed points);

  * •

nrcpeak: neither-record-antirecords that are also cycle peaks;

  * •

nrcval: neither-record-antirecords that are also cycle valleys;

  * •

nrcdrise: neither-record-antirecords that are also cycle double rises;

  * •

nrcdfall: neither-record-antirecords that are also cycle double falls;

  * •

nrfix: neither-record-antirecords that are also fixed points.

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

Now suppose that $\sigma$ is a D-permutation. Then the cycle classification of
a non-fixed-point index $i$ is equivalent to recording the parities of
$\sigma^{-1}(i)$ and $i$:

$\displaystyle\bullet\;\hbox{{\em cycle peak}\/: $\sigma^{-1}(i)<i>\sigma(i)$
$\implies$ $\sigma^{-1}(i)$ odd, $i$ even}$ (2.47)
$\displaystyle\bullet\;\hbox{{\em cycle valley}\/:
$\sigma^{-1}(i)>i<\sigma(i)$ $\implies$ $\sigma^{-1}(i)$ even, $i$ odd}$
$\displaystyle\bullet\;\hbox{{\em cycle double rise}\/:
$\sigma^{-1}(i)<i<\sigma(i)$ $\implies$ $\sigma^{-1}(i)$ odd, $i$ odd}$
$\displaystyle\bullet\;\hbox{{\em cycle double fall}\/:
$\sigma^{-1}(i)>i>\sigma(i)$ $\implies$ $\sigma^{-1}(i)$ even, $i$ even}\hskip
48.36958pt$

For fixed points, by contrast, we will need to explicitly record the parity of
$i$, by distinguishing even and odd fixed points:

$\displaystyle\bullet\;\hbox{{\em even fixed point}\/ (evenfix):
$\sigma^{-1}(i)=i=\sigma(i)$ is even}$ (2.48)
$\displaystyle\bullet\;\hbox{{\em odd fixed point}\/ (oddfix):
$\sigma^{-1}(i)=i=\sigma(i)$ is odd}\hskip 105.2751pt$

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

  * •

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

  * •

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

  * •

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

  * •

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

This leads to the parity-refined record-and-cycle classification, in which
each index $i$ belongs to exactly one of 12 types. More precisely, each even
index $i$ belongs to exactly one of the 6 types

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

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

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

###  2.8 Permutation statistics: Crossings and nestings

We now define (following [46]) some permutation statistics that count
crossings and nestings.

First we associate to each permutation $\sigma\in{\mathfrak{S}}_{N}$ a
pictorial representation (Figure 1) by placing vertices $1,2,\ldots,N$ along a
horizontal axis and then drawing an arc from $i$ to $\sigma(i)$ above (resp.
below) the horizontal axis in case $\sigma(i)>i$ [resp. $\sigma(i)<i$]; if
$\sigma(i)=i$ we do not draw any arc.

1234567891011121314 Figure 1:  An example of a D-permutation
$\sigma=7\,1\,9\,2\,5\,4\,8\,6\,10\,3\,11\,12\,14\,13\,=(1,7,8,6,4,2)\,(3,9,10)\,(5)\,(11)\,(12)\,(13,14)\in{\mathfrak{D}}_{14}$.

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

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

  * •

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

  * •

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

  * •

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

  * •

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

We also consider some “degenerate” cases with $j=k$, by saying that a triplet
$i<j<l$ forms an

  * •

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

  * •

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

  * •

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

  * •

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

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

${\rm psnest}(\sigma)\;\stackrel{{\scriptstyle\rm def}}{{=}}\;{\rm
upsnest}(\sigma)\;=\;{\rm lpsnest}(\sigma)\;.$ (2.49)

And of course ${\rm ujoin}={\rm cdrise}$ and ${\rm ljoin}={\rm cdfall}$.

$i$$j$$k$$l$Upper crossing$i$$j$$k$$l$Lower crossing

$i$$j$$k$$l$Upper nesting$i$$j$$k$$l$Lower nesting

$i$$j$$l$Upper joining$i$$j$$l$Lower joining

$i$$j$$l$Upper pseudo-nesting$i$$j$$l$Lower pseudo-nesting

Figure 2:  Crossing, nesting, joining and pseudo-nesting.

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

We can further refine the four crossing/nesting categories by examining more
closely the status of the inner index ($j$ or $k$) whose outgoing arc belonged
to the crossing or nesting: we say that a quadruplet $i<j<k<l$ forms an

  * •

upper crossing of type cval (ucrosscval) if $k=\sigma(i)$ and $l=\sigma(j)$
and ${\sigma^{-1}(j)>j}$;

  * •

upper crossing of type cdrise (ucrosscdrise) if $k=\sigma(i)$ and
$l=\sigma(j)$ and ${\sigma^{-1}(j)<j}$;

  * •

lower crossing of type cpeak (lcrosscpeak) if $i=\sigma(k)$ and $j=\sigma(l)$
and ${\sigma^{-1}(k)<k}$;

  * •

lower crossing of type cdfall (lcrosscdfall) if $i=\sigma(k)$ and
$j=\sigma(l)$ and ${\sigma^{-1}(k)>k}$;

  * •

upper nesting of type cval (unestcval) if $l=\sigma(i)$ and $k=\sigma(j)$ and
${\sigma^{-1}(j)>j}$;

  * •

upper nesting of type cdrise (unestcdrise) if $l=\sigma(i)$ and $k=\sigma(j)$
and ${\sigma^{-1}(j)<j}$;

  * •

lower nesting of type cpeak (lnestcpeak) if $i=\sigma(l)$ and $j=\sigma(k)$
and ${\sigma^{-1}(k)<k}$;

  * •

lower nesting of type cdfall (lnestcdfall) if $i=\sigma(l)$ and $j=\sigma(k)$
and ${\sigma^{-1}(k)>k}$.

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

$i$$j$$k$$l$Upper crossing of type cval$i$$j$$k$$l$Upper crossing of type
cdrise

$i$$j$$k$$l$Lower crossing of type cpeak$i$$j$$k$$l$Lower crossing of type
cdfall

$i$$j$$k$$l$Upper nesting of type cval$i$$j$$k$$l$Upper nesting of type cdrise

$i$$j$$k$$l$Lower nesting of type cpeak$i$$j$$k$$l$Lower nesting of type
cdfall

Figure 3:  Refined categories of crossing and nesting.

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

${\rm ucross}(j,\sigma)&=\\#\\{i<j<k<l\colon\>k=\sigma(i)\hbox{ and
}l=\sigma(j)\\}\\\ {\rm
unest}(j,\sigma)=\\#\\{i<j<k<l\colon\>k=\sigma(j)\hbox{ and }l=\sigma(i)\\}\\\
{\rm lcross}(k,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(k)\hbox{ and
}j=\sigma(l)\\}\\\ {\rm
lnest}(k,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(l)\hbox{ and }j=\sigma(k)\\}$
(2.50)

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

When $j$ is a fixed point, we also define the analogous quantity for pseudo-
nestings:

${\rm psnest}(j,\sigma)\;\stackrel{{\scriptstyle\rm
def}}{{=}}\;\\#\\{i<j\colon\>\sigma(i)>j\\}\;=\;\\#\\{i>j\colon\>\sigma(i)<j\\}\;.$
(2.51)

(Here the two expressions are equal because $\sigma$ is a bijection from
$[1,j)\cup(j,n]$ to itself.) In [46, eq. (2.20)] this quantity was called the
level of the fixed point $j$ and was denoted ${\rm lev}(j,\sigma)$.

For some purposes we will also require a variant of (2.50) in which the roles
of second and third position are interchanged:

${\rm ucross}^{\prime}(k,\sigma)&=\\#\\{i<j<k<l\colon\>k=\sigma(i)\hbox{ and
}l=\sigma(j)\\}\\\ {\rm
unest}^{\prime}(k,\sigma)=\\#\\{i<j<k<l\colon\>k=\sigma(j)\hbox{ and
}l=\sigma(i)\\}\\\ {\rm
lcross}^{\prime}(j,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(k)\hbox{ and
}j=\sigma(l)\\}\\\ {\rm
lnest}^{\prime}(j,\sigma)=\\#\\{i<j<k<l\colon\>i=\sigma(l)\hbox{ and
}j=\sigma(k)\\}$ (2.52)

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

${\rm unest}^{\prime}(k,\sigma)&={\rm unest}(\sigma^{-1}(k),\sigma)\\\ {\rm
lnest}^{\prime}(j,\sigma)={\rm lnest}(\sigma^{-1}(j),\sigma)$ (2.53)

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

##  3 First T-fraction and its generalizations

In this section we state our first T-fraction for D-permutations, in three
increasingly more general versions. The first and most basic version (Theorem
3.3) is a T-fraction in 12 variables that enumerates D-permutations with
respect to the parity-refined record-and-cycle classification; it includes
many previously known results as special cases. The second version (Theorem
3.9) is a $(p,q)$-generalization of the first one: it is a T-fraction in 22
variables that enumerates D-permutations with respect to the parity-refined
record-and-cycle classification together with four pairs of $(p,q)$-variables
counting the refined categories of crossing and nesting (Figure 3) as well as
two variables corresponding to pseudo-nestings of fixed points. Finally, our
third version — what we call the “first master T-fraction” (Theorem 3.11) — is
a T-fraction in six infinite families of indeterminates that generalizes the
preceding two by employing the index-refined crossing and nesting statistics
defined in (2.50).

The plan of this section is as follows: We begin (Section 3.1) by establishing
some easy but important preliminary results concerning record-antirecord fixed
points. Then, in Sections 3.2–3.4 we state the three versions of our first
T-fraction and note some of their corollaries. Finally, in Section 3.5 we
state variant forms of the three T-fractions. All these results will be proven
in Section 6.

###  3.1 Preliminaries on record-antirecords

An important role in our study of D-permutations will be played by record-
antirecords, i.e. indices $i$ that are both a record and an antirecord. It is
easy to see that, in any permutation, a record-antirecord must be a fixed
point. More precisely:

######  Lemma 3.1.

Consider a permutation $\sigma\in{\mathfrak{S}}_{N}$. An index $i\in[N]$ is a
record-antirecord if and only if $\sigma$ maps each of the sets
$\\{1,\ldots,i-1\\}$, $\\{i\\}$ and $\\{i+1,\ldots,N\\}$ onto itself.

Proof. If $i$ is a record, then $\sigma$ maps $\\{1,\ldots,i-1\\}$ injectively
into $\\{1,\ldots,\sigma(i)-1\\}$, so that $\sigma(i)\geq i$. If $i$ is an
antirecord, then $\sigma$ maps $\\{i+1,\ldots,N\\}$ injectively into
$\\{\sigma(i)+1,\ldots,N\\}$, so that $\sigma(i)\leq i$. So if $i$ is a
record-antirecord, then $i$ must be a fixed point and $\sigma$ must map both
$\\{1,\ldots,i-1\\}$ and $\\{i+1,\ldots,N\\}$ bijectively onto themselves.

The converse is obvious. $\square$

For D-permutations, record-antirecords can occur only in pairs:

######  Lemma 3.2.

Let $\sigma\in{\mathfrak{D}}_{2n}$ and let $i\in[n]$. Then the following are
equivalent:

  * (a)

$2i-1$ is a record-antirecord.

  * (b)

$2i$ is a record-antirecord.

  * (c)

$\sigma$ maps each of the sets $\\{1,\ldots,2i-1\\}$ and $\\{2i,\ldots,2n\\}$
onto itself.

  * (d)

$\sigma$ maps each of the sets $\\{1,\ldots,2i-2\\}$, $\\{2i-1\\}$, $\\{2i\\}$
and $\\{2i+1,\ldots,2n\\}$ onto itself.

Proof. By Lemma 3.1, (d)$\iff$“(a) and (b)”, and “(a) or (b)”$\implies$(c). On
the other hand, if $\sigma$ is a D-permutation, then $\sigma(2i-1)\geq 2i-1$
and $\sigma(2i)\leq 2i$, so (c)$\implies$(d). $\square$

Let us say that a permutation is pure if it has no record-antirecords. We
write ${\mathfrak{D}}^{\rm pure}_{2n}$ for the set of pure D-permutations of
$[2n]$. From Lemma 3.1 we have

$\begin{array}[]{rcccl}&&{\mathfrak{D}}^{\rm e}_{2n}&&\\\
&\rotatebox[origin={c}]{45.0}{$\subseteq$}&&\rotatebox[origin={c}]{-45.0}{$\subseteq$}&\\\
{\mathfrak{DC}}_{2n}\;\subseteq\;{\mathfrak{D}}^{\rm
eo}_{2n}={\mathfrak{D}}^{\rm e}_{2n}\cap{\mathfrak{D}}^{\rm
o}_{2n}&&&&{\mathfrak{D}}^{\rm e}_{2n}\cup{\mathfrak{D}}^{\rm o}_{2n}\\\
&\rotatebox[origin={c}]{-45.0}{$\subseteq$}&&\rotatebox[origin={c}]{45.0}{$\subseteq$}&\\\
&&{\mathfrak{D}}^{\rm o}_{2n}&&\end{array}\;\subseteq\;{\mathfrak{D}}^{\rm
pure}_{2n}\;\subseteq\;{\mathfrak{D}}_{2n}\;.$ (3.1)

These inclusions are strict for $n\geq 2$:

| ${\mathfrak{DC}}_{2n}$ | ${\mathfrak{D}}^{\rm eo}_{2n}$ | ${\mathfrak{D}}^{\rm e/o}_{2n}$ | ${\mathfrak{D}}^{\rm e}_{2n}\cup{\mathfrak{D}}^{\rm o}_{2n}$ | ${\mathfrak{D}}^{\rm pure}_{2n}$ | ${\mathfrak{D}}_{2n}$
---|---|---|---|---|---|---
$n$ | $g_{n-1}$ | $h_{n}$ | $g_{n}$ | $2g_{n}-h_{n}$ | $h_{n+1}^{\flat}$ | $h_{n+1}$
0 | 0 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1 | 1 | 2
2 | 1 | 2 | 3 | 4 | 5 | 8
3 | 3 | 8 | 17 | 26 | 41 | 56
4 | 17 | 56 | 155 | 254 | 493 | 608
5 | 155 | 608 | 2073 | 3538 | 8161 | 9440
6 | 2073 | 9440 | 38227 | 67014 | 178469 | 198272

For instance, the permutation 4231 belongs to ${\mathfrak{D}}^{\rm
pure}_{4}\setminus({\mathfrak{D}}^{\rm e}_{4}\cup{\mathfrak{D}}^{\rm o}_{4})$:
it has both even and odd fixed points, but they are not record-antirecords.
Likewise, the permutation 513462 belongs to ${\mathfrak{D}}^{\rm
pure}_{6}\setminus({\mathfrak{D}}^{\rm e}_{6}\cup{\mathfrak{D}}^{\rm o}_{6})$:
it has an odd-even pair of fixed points 34, but they are not record-
antirecords. We will show later that $|{\mathfrak{D}}^{\rm
pure}_{2n}|=h_{n+1}^{\flat}$; we recall that these numbers were defined by the
S-fraction (2.42)/(2.43).

###  3.2 First T-fraction

####  3.2.1 Main theorem and its corollaries

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

$\displaystyle P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\;.$ (3.2)

Thus, the variables $x_{1}$ and $u_{1}$ are associated to cycle peaks, $y_{1}$
and $v_{1}$ to cycle valleys, $x_{2}$ and $u_{2}$ to cycle double falls,
$y_{2}$ and $v_{2}$ to cycle double rises, $w_{\rm e}$ and $w_{\rm o}$ to
neither-record-antirecord fixed points, and $z_{\rm e}$ and $z_{\rm o}$ to
record-antirecord fixed points. We remark that (3.2) is the same as the
polynomial introduced in [46, eq. (2.19)], but restricted to D-permutations
and refined to record the parity of fixed points. Since in a D-permutation
each even (resp. odd) index $i\in[2n]$ belongs to exactly one of the 6 types
mentioned at the end of Section 2.7, it follows that the polynomial $P_{n}$ is
homogeneous of degree $n$ in $x_{1},x_{2},u_{1},u_{2},w_{\rm e},z_{\rm e}$ and
also homogeneous of degree $n$ in $y_{1},y_{2},v_{1},v_{2},w_{\rm o},z_{\rm
o}$.

The polynomials (3.2) have a beautiful T-fraction:

######  Theorem 3.3 (First T-fraction for D-permutations).

The ordinary generating function of the polynomials (3.2) has the T-type
continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-z_{\rm e}z_{\rm
o}\,t-\cfrac{x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})(y_{1}\\!+\\!v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!v_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})(y_{1}\\!+\\!2v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!2v_{2}\\!+\\!w_{\rm o})\,t}{1-\cdots}}}}}}}$ (3.3)

with coefficients

$\alpha_{2k-1}&=[x_{1}+(k-1)u_{1}]\>[y_{1}+(k-1)v_{1}]\\\
\alpha_{2k}=[x_{2}+(k-1)u_{2}+w_{\rm e}]\>[y_{2}+(k-1)v_{2}+w_{\rm o}]\\\
\delta_{1}=z_{\rm e}z_{\rm o}\\\ \delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (3.4)

We will prove Theorem 3.3 in Section 6.

Note that each of the coefficients $\alpha_{i}$ and $\delta_{i}$ is
homogeneous of degree $1$ in $x_{1},x_{2},$ $u_{1},u_{2},w_{\rm e},z_{\rm e}$
and also homogeneous of degree $1$ in $y_{1},y_{2},v_{1},v_{2},w_{\rm
o},z_{\rm o}$. This reflects the homogeneities of the $P_{n}$.

Note also that the involution of ${\mathfrak{D}}_{2n}$ defined by
$\sigma\mapsto R\circ\sigma\circ R$ where $R(i)=2n+1-i$ is the reversal map,
interchanges $x_{1}\leftrightarrow y_{1}$, $x_{2}\leftrightarrow y_{2}$,
$u_{1}\leftrightarrow v_{1}$, $u_{2}\leftrightarrow v_{2}$, $z_{\rm
e}\leftrightarrow z_{\rm o}$, $w_{\rm e}\leftrightarrow w_{\rm o}$. The
T-fraction (3.3)/(3.4) is invariant under these simultaneous interchanges.

The T-fraction (3.3)/(3.4) has numerous interesting specializations:

1) With all variables equal to 1, it gives the T-fraction (2.40)/(2.41) for
the once-shifted median Genocchi numbers, and confirms that
$|{\mathfrak{D}}_{2n}|=h_{n+1}$.

2) With $z_{\rm e}=0$ and/or $z_{\rm o}=0$ and all other variables equal to 1,
it gives the S-fraction (2.42)/(2.43) and shows that $|{\mathfrak{D}}^{\rm
pure}_{2n}|=h_{n+1}^{\flat}$. More generally, with $z_{\rm e}=0$ and/or
$z_{\rm o}=0$ and the other variables retained, it gives an S-fraction for
pure D-permutations according to the parity-refined record-and-cycle
classification. Note that since record-antirecords occur in pairs by Lemma
3.2, setting either $z_{\rm e}=0$ or $z_{\rm o}=0$ suffices to suppress them;
this explains why these variables occur in the T-fraction only as a product
$z_{\rm e}z_{\rm o}$.

3) With $z_{\rm e}=w_{\rm e}=0$ (resp. $z_{\rm o}=w_{\rm o}=0$) and all other
variables equal to 1, it gives the S-fraction (2.24)/(2.25) for the Genocchi
numbers, and confirms that $|{\mathfrak{D}}^{\rm e}_{2n}|=|{\mathfrak{D}}^{\rm
o}_{2n}|=g_{n}$. More generally, with $z_{\rm e}=w_{\rm e}=0$ (resp. $z_{\rm
o}=w_{\rm o}=0$) and the other variables retained, it gives an S-fraction for
D-e-semiderangements (resp. D-o-semiderangements) according to the parity-
refined record-and-cycle classification.

4) With $z_{\rm e}=z_{\rm o}=w_{\rm e}=w_{\rm o}=0$ and all other variables
equal to 1, it gives the S-fraction (2.36)/(2.37) for the median Genocchi
numbers, and confirms that $|{\mathfrak{D}}^{\rm eo}_{2n}|=h_{n}$. More
generally, with $z_{\rm e}=z_{\rm o}=w_{\rm e}=w_{\rm o}=0$ and the other
variables retained, it gives an S-fraction for D-derangements according to the
parity-refined record-and-cycle classification; this S-fraction is of
precisely the form (1.4) that was proposed in the Introduction.

5) If we specialize to $x_{1}=u_{1}$, $y_{1}=v_{1}$, $x_{2}=u_{2}$,
$y_{2}=v_{2}$ — that is, renounce the counting of records — then the
coefficients (3.4a,b) simplify to

$\alpha_{2k-1}&=k^{2}\,x_{1}y_{1}\\\ \alpha_{2k}=(kx_{2}+w_{\rm
e})\,(ky_{2}+w_{\rm o})$ (3.5)

Using Proposition 2.5, we can alternatively rewrite the T-fraction (3.3) as an
S-fraction for the ogf of an “augmented” sequence:

######  Corollary 3.4 (First S-fraction for augmented D-permutations).

The ordinary generating function of the “augmented” sequence of polynomials
(3.2) has the S-type continued fraction

$\displaystyle 1\>+\>z_{\rm e}z_{\rm
o}t\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-\cfrac{z_{\rm e}z_{\rm
o}\,t}{1-\cfrac{x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})(y_{1}\\!+\\!v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!v_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})(y_{1}\\!+\\!2v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!2v_{2}\\!+\\!w_{\rm o})\,t}{1-\cdots}}}}}}}}$ (3.6)

with coefficients

$\alpha_{1}&=z_{\rm e}z_{\rm o}\\\ \alpha_{2k-1}=[x_{2}+(k-2)u_{2}+w_{\rm
e}]\>[y_{2}+(k-2)v_{2}+w_{\rm o}]\quad\hbox{for $k\geq 2$}\\\
\alpha_{2k}=[x_{1}+(k-1)u_{1}]\>[y_{1}+(k-1)v_{1}]$ (3.7)

With all variables equal to 1, this gives (since
$|{\mathfrak{D}}_{2n}|=h_{n+1}$) the the S-fraction (2.36)/(2.37) for the
sequence $(h_{n})_{n\geq 0}$.

Also, using Proposition 2.5 in the other direction, we can rewrite the
T-fraction (3.3) specialized to $z_{\rm e}=0$ and/or $z_{\rm o}=0$ as a
T-fraction for the ogf of the “restricted” sequence:

######  Corollary 3.5 (First T-fraction for restricted pure D-permutations).

The ordinary generating function of the “restricted” sequence of polynomials
(3.2) specialized to $z_{\rm e}=0$ and/or $z_{\rm o}=0$ has the T-type
continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n+1}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},0,z_{\rm o})\>t^{n}\;=\;$
$\displaystyle\sum_{n=0}^{\infty}P_{n+1}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},0)\>t^{n}\;=\;$
$\displaystyle\cfrac{x_{1}y_{1}}{1-x_{1}y_{1}\,t-\cfrac{(x_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})(y_{1}\\!+\\!v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!v_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})(y_{1}\\!+\\!2v_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!2v_{2}\\!+\\!w_{\rm o})\,t}{1-\cdots}}}}}}$ (3.8)

with coefficients

$\alpha_{2k-1}&=[x_{2}+(k-1)u_{2}+w_{\rm e}]\>[y_{2}+(k-1)v_{2}+w_{\rm o}]\\\
\alpha_{2k}=[x_{1}+k\,u_{1}]\>[y_{1}+k\,v_{1}]\\\ \delta_{1}=x_{1}y_{1}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (3.9)

With all variables equal to 1, this gives (since $|{\mathfrak{D}}^{\rm
pure}_{2n}|=h^{\flat}_{n+1}$) the T-fraction (2.45)/(2.46) for the sequence
$(h^{\flat}_{n+2})_{n\geq 0}$. With $w_{\rm e}=0$ (or $w_{\rm o}=0$) and all
other variables equal to 1, this gives the T-fraction (2.26)/(2.27) for the
once-shifted Genocchi numbers. And finally, with $w_{\rm e}=w_{\rm o}=0$ and
all other variables equal to 1, this gives the T-fraction (2.40)/(2.41) for
the once-shifted median Genocchi numbers.

####  3.2.2 Alternative T-fraction, and specializations leading to S-fraction

T-fractions — unlike S-fractions and J-fractions — are not unique; indeed, any
formal power series can be expressed as a T-fraction in uncountably many
different ways.999 See footnote 11 below.  Of course, most of these
T-fractions will be too complicated to be of any use; but sometimes they can
be of interest. We would now like to exhibit, for the ordinary generating
function of the polynomials (3.2), a T-fraction that is alternative to the one
shown in Theorem 3.3:

######  Proposition 3.6 (Alternative T-fraction for D-permutations).

The ordinary generating function of the polynomials (3.2) has the alternative
T-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\>t^{n}\;=\;$ (3.10)

with coefficients

$\alpha^{\prime}_{2k-1}&=[x_{2}+ (k-1)u_{2}+w_{\rm e}]\,[y_{1}+(k-1)v_{1}]\\\
\alpha^{\prime}_{2k}=[x_{1}+(k-1)u_{1}]\,[y_{2}+(k-1)v_{2}+w_{\rm o}]\\\
\delta^{\prime}_{1}=(x_{1}-x_{2}-w_{\rm e})y_{1}\,+\,z_{\rm e}z_{\rm o}\\\
\delta^{\prime}_{2k+1}=(x_{1}-x_{2}-w_{\rm
e})\,[y_{1}-y_{2}+kv_{1}-(k-1)v_{2}-w_{\rm o}]\;+\\\
\quad(u_{1}-u_{2})\,[ky_{1}-(k-1)y_{2}+k^{2}v_{1}-(k-1)^{2}v_{2}-(k-1)w_{\rm
o}]\quad\hbox{for $k\geq 1$}\\\ \\\ \delta^{\prime}_{2k}=0$ (3.11)

Proof. It suffices to verify that the T-fractions (3.3)/(3.4) and
(3.10)/(3.11) contract by Proposition 2.1 to the same J-fraction. Note that
the products forming $\alpha_{2k-1}$ and $\alpha_{2k}$ in (3.4) have been
interchanged in (3.11): this guarantees that
$\alpha_{2k-1}\alpha_{2k}=\alpha^{\prime}_{2k-1}\alpha^{\prime}_{2k}$. It is
then straightforward to verify that the coefficients ${\bm{\delta}}^{\prime}$
have been chosen so that
$\alpha_{1}+\delta_{1}=\alpha^{\prime}_{1}+\delta^{\prime}_{1}$ and
$\alpha_{2k}+\alpha_{2k+1}=\alpha^{\prime}_{2k}+\alpha^{\prime}_{2k+1}+\delta^{\prime}_{2k+1}$
for all $k\geq 1$. $\square$

Remark. There is also an analogous T-fraction in which the roles of odd and
even indices are reversed. $\blacksquare$

Of course, the T-fraction (3.10)/(3.11) is rather ugly, because of the very
complicated expression for $\delta_{2k+1}$. But it simplifies greatly if we
specialize to $y_{1}=y_{2}=v_{1}=v_{2}=w_{\rm o}=z_{\rm o}$: that is, all the
weights associated to odd indices are equal, and hence might as well be set to
1. In this case we have:

######  Corollary 3.7 (Alternative T-fraction for D-permutations,
specialized).

The ordinary generating function of the polynomials (3.2) specialized to
$y_{1}=y_{2}=v_{1}=v_{2}=w_{\rm o}=z_{\rm o}=1$ has the alternative T-type
continued fraction

$\displaystyle\sum_{n=0}^{\infty}P_{n}(x_{1},x_{2},1,1,u_{1},u_{2},1,1,w_{\rm
e},1,z_{\rm e},1)\>t^{n}\;=\;$ $\displaystyle\cfrac{1}{1-(x_{1}-x_{2}+z_{\rm
e}-w_{\rm e})t-\cfrac{(x_{2}+w_{\rm
e})t}{1-\cfrac{2x_{1}t}{1-2(u_{1}-u_{2})t-\cfrac{2(x_{2}+u_{2}+w_{\rm
e})t}{1-\cfrac{3(x_{1}+u_{1})t}{1-\cdots}}}}}\qquad$ (3.12)

with coefficients

$\alpha^{\prime}_{2k-1}&=k\,[x_{2}+ (k-1)u_{2}+w_{\rm e}]\\\
\alpha^{\prime}_{2k}=(k+1)\,[x_{1}+(k-1)u_{1}]\\\
\delta^{\prime}_{1}=(x_{1}-x_{2})\,+\,(z_{\rm e}-w_{\rm e})\\\
\delta^{\prime}_{2k+1}=(k+1)(u_{1}-u_{2})\quad\hbox{for $k\geq 1$}\\\
\delta^{\prime}_{2k}=0$ (3.13)

And if we further specialize to $x_{1}=x_{2}$, $u_{1}=u_{2}$, $z_{\rm
e}=w_{\rm e}$, we obtain an S-fraction:

######  Corollary 3.8 (S-fraction for specialized D-permutations).

The ordinary generating function of the polynomials $P^{\star}_{n}(x,u,w_{\rm
e})$ defined by

$P^{\star}_{n}(x,u,w_{\rm e})\;=\;\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
earec}(\sigma)}u^{{\rm nrcpeak}(\sigma)+{\rm nrcdfall}(\sigma)}w_{\rm e}^{{\rm
evenfix}(\sigma)}$ (3.14)

has the S-type continued fraction

$\sum_{n=0}^{\infty}P^{\star}_{n}(x,u,w_{\rm
e})\>t^{n}\;=\;\cfrac{1}{1-\cfrac{(x+w_{\rm
e})t}{1-\cfrac{2xt}{1-\cfrac{2(x+u+w_{\rm
e})t}{1-\cfrac{3(x+u)t}{1-\cdots}}}}}$ (3.15)

with coefficients

$\alpha_{2k-1}&=k\,[x+ (k-1)u+w_{\rm e}]\\\ \alpha_{2k}=(k+1)\,[x+(k-1)u]$
(3.16)

Remarks. 1\. Specializing to $x=u=w_{\rm e}=1$ gives the S-fraction
(2.38)/(2.39) for the once-shifted median Genocchi numbers.

2\. Specializing to $x=u=1$, $w_{\rm e}=0$ gives the S-fraction (2.24)/(2.25)
for the Genocchi numbers.

3\. There is also a slightly weaker specialization of Corollary 3.7 that leads
to an S-fraction, namely, $x_{2}=x_{1}+z_{\rm e}-w_{\rm e}$ and $u_{1}=u_{2}$:
it leads to the S-fraction with $\alpha_{2k-1}={k\,[x_{1}+ (k-1)u_{1}+z_{\rm
e}]}$, $\alpha_{2k}={(k+1)\,[x_{1}+(k-1)u_{1}]}$. Curiously this is
independent of $w_{\rm e}$: the direct dependence on $w_{\rm e}$ and the
dependence via $x_{2}$ apparently cancel.

4\. See also the generalization in Corollary 4.3, as well as Open Problem 4.4.
$\blacksquare$

###  3.3 $\bm{p,q}$-generalizations of the first T-fraction

We can extend Theorem 3.3 by introducing a $p,q$-generalization. Recall that
for integer $n\geq 0$ we define

$[n]_{p,q}\;=\;{p^{n}-q^{n}\over
p-q}\;=\;\sum\limits_{j=0}^{n-1}p^{j}q^{n-1-j}$ (3.17)

where $p$ and $q$ are indeterminates; it is a homogeneous polynomial of degree
$n-1$ in $p$ and $q$, which is symmetric in $p$ and $q$. In particular,
$[0]_{p,q}=0$ and $[1]_{p,q}=1$; and for $n\geq 1$ we have the recurrence

$[n]_{p,q}\;=\;p\,[n-1]_{p,q}\,+\,q^{n-1}\;=\;q\,[n-1]_{p,q}\,+\,p^{n-1}\;.$
(3.18)

If $p=1$, then $[n]_{1,q}$ is the well-known $q$-integer

$[n]_{q}\;=\;[n]_{1,q}\;=\;{1-q^{n}\over 1-q}\;=\;\begin{cases}0&\textrm{if
$n=0$}\\\ 1+q+q^{2}+\ldots+q^{n-1}&\textrm{if $n\geq 1$}\end{cases}$ (3.19)

If $p=0$, then

$[n]_{0,q}\;=\;\begin{cases}0&\textrm{if $n=0$}\\\ q^{n-1}&\textrm{if $n\geq
1$}\end{cases}$ (3.20)

The statistics on permutations corresponding to the variables $p$ and $q$ will
be crossings and nestings, as defined in Section 2.8. More precisely, we
define the following polynomial in 22 variables that generalizes (3.2) by
including four pairs of $(p,q)$-variables corresponding to the four refined
types of crossings and nestings illustrated in Figure 3, as well as two
variables corresponding to pseudo-nestings of fixed points:

$\displaystyle P_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm
o},p_{-1},p_{-2},p_{+1},p_{+2},q_{-1},q_{-2},q_{+1},q_{+2},s_{\rm e},s_{\rm
o})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>p_{-1}^{{\rm
lcrosscpeak}(\sigma)}p_{-2}^{{\rm lcrosscdfall}(\sigma)}p_{+1}^{{\rm
ucrosscval}(\sigma)}p_{+2}^{{\rm ucrosscdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>q_{-1}^{{\rm
lnestcpeak}(\sigma)}q_{-2}^{{\rm lnestcdfall}(\sigma)}q_{+1}^{{\rm
unestcval}(\sigma)}q_{+2}^{{\rm unestcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>s_{\rm e}^{{\rm epsnest}(\sigma)}s_{\rm
o}^{{\rm opsnest}(\sigma)}$ (3.21)

where

${\rm epsnest}(\sigma)\;=\;\sum_{i\in{\rm Evenfix}}{\rm
psnest}(i,\sigma)\;,\qquad{\rm opsnest}(\sigma)\;=\;\sum_{i\in{\rm
Oddfix}}{\rm psnest}(i,\sigma)\;.$ (3.22)

We remark that (3.21) is essentially the same as the polynomial introduced in
[46, eq. (2.51)], but restricted to D-permutations and refined to record the
parity of fixed points.101010 The polynomial in [46, eq. (2.51)] also included
a more refined stratification of fixed points by level (= psnest) as defined
in (2.51) above. That refined stratification is omitted here for simplicity —
instead we include only the simple factors $s^{\rm psnest}$ — but it is
included in (3.30) below.

We then have the following $p,q$-generalization of Theorem 3.3:

######  Theorem 3.9 (First T-fraction for D-permutations,
$p,q$-generalization).

The ordinary generating function of the polynomials (3.21) has the T-type
continued fraction

(3.23)

with coefficients

$\alpha_{2k-1}&=\bigl{(}p_{-1}^{k-1}x_{1}+q_{-1}[k-1]_{p_{-1},q_{-1}}u_{1}\bigr{)}\>\bigl{(}p_{+1}^{k-1}y_{1}+q_{+1}[k-1]_{p_{+1},q_{+1}}v_{1}\bigr{)}\\\
\alpha_{2k}=\bigl{(}p_{-2}^{k-1}x_{2}+q_{-2}[k-1]_{p_{-2},q_{-2}}u_{2}+s_{\rm
e}^{k}w_{\rm
e}\bigr{)}\>\bigl{(}p_{+2}^{k-1}y_{2}+q_{+2}[k-1]_{p_{+2},q_{+2}}v_{2}+s_{\rm
o}^{k}w_{\rm o}\bigr{)}\\\ \\\ \delta_{1}=z_{\rm e}z_{\rm o}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (3.24)

We will prove Theorem 3.9 in Section 6. Of course we reobtain Theorem 3.3 by
making the specialization
$p_{-1}=p_{-2}=p_{+1}=p_{+2}=q_{-1}=q_{-2}=q_{+1}=q_{+2}=s_{\rm e}=s_{\rm
o}=1$.

Remarks. 1\. If we specialize to $x_{1}=u_{1}$, $y_{1}=v_{1}$, $x_{2}=u_{2}$,
$y_{2}=v_{2}$ — that is, renounce the counting of records — then the
coefficients (3.24) simplify to

$\alpha_{2k-1}&=[k]_{p_{-1},q_{-1}}\,[k]_{p_{+1},q_{+1}}\,x_{1}y_{1}\\\
\alpha_{2k}=\bigl{(}[k]_{p_{-2},q_{-2}}x_{2}+s_{\rm e}^{k}w_{\rm
e}\bigr{)}\>\bigl{(}[k]_{p_{+2},q_{+2}}y_{2}+s_{\rm o}^{k}w_{\rm o}\bigr{)}\\\
\delta_{1}=z_{\rm e}z_{\rm o}\\\ \delta_{n}=0\qquad\hbox{for $n\geq 2$}$
(3.25)

2\. If we further specialize to $x_{1}=1$, $x_{2}=y_{1}=y_{2}=q$,
$p_{-1}=p_{-2}=p_{+1}=p_{+2}=q$ and $q_{-1}=q_{-2}=q_{+1}=q_{+2}=s_{\rm
e}=s_{\rm o}=q^{2}$ and recall [46, Proposition 2.24] that the number of
inversions (${\rm inv}$) of a permutation satisfies

${\rm inv}\;=\;{\rm cval}+{\rm cdrise}+{\rm cdfall}+{\rm ucross}+{\rm
lcross}+2({\rm unest}+{\rm lnest}+{\rm psnest})\;,$ (3.26)

we obtain a T-fraction for D-permutations according to the number of even and
odd fixed points and number of inversions, with coefficients
$\alpha_{2k-1}=q^{2k-1}[k]_{q}^{2}$, $\alpha_{2k}=q^{2k}([k]_{q}+q^{k}w_{\rm
e})([k]_{q}+q^{k}w_{\rm o})$, $\delta_{1}=z_{\rm e}z_{\rm o}$.

3\. And if we further specialize to $w_{\rm o}=z_{\rm o}=0$, we reobtain the
S-fraction for D-o-semiderangements according to the number of fixed points
and number of inversions [40, Théorème 1.2], with coefficients
$\alpha_{2k-1}=q^{2k-1}[k]_{q}^{2}$,
$\alpha_{2k}=q^{2k}[k]_{q}([k]_{q}+q^{k}w_{\rm e})$. $\blacksquare$

We refrain from pursuing the $p,q$-generalizations of Proposition 3.6 and
Corollary 3.7, and limit ourselves to giving the $p,q$-generalization of
Corollary 3.8. We need to make the specializations
$y_{1}=y_{2}=v_{1}=v_{2}=w_{\rm o}=z_{\rm
o}=p_{+1}=p_{+2}=q_{+1}=q_{+2}=s_{\rm o}=1$ — that is, set all the weights
associated to odd indices to 1 — and also specialize $x_{1}=x_{2}$,
$u_{1}=u_{2}$, $z_{\rm e}=w_{\rm e}$, $p_{-1}=p_{-2}$, $q_{-1}=q_{-2}$ and
$s_{\rm e}=1$:

######  Corollary 3.10 (S-fraction for specialized D-permutations,
$p,q$-generalization).

The ordinary generating function of the polynomials $P^{\star}_{n}(x,u,w_{\rm
e},p_{-},q_{-})$ defined by

$P^{\star}_{n}(x,u,w_{\rm
e},p_{-},q_{-})\;=\;\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
earec}(\sigma)}u^{{\rm nrcpeak}(\sigma)+{\rm nrcdfall}(\sigma)}w_{\rm e}^{{\rm
evenfix}(\sigma)}p_{-}^{{\rm lcross}(\sigma)}q_{-}^{{\rm lnest}(\sigma)}$
(3.27)

has the S-type continued fraction

$\sum_{n=0}^{\infty}P^{\star}_{n}(x,u,w_{\rm
e})\>t^{n}\;=\;\cfrac{1}{1-\cfrac{(x+w_{\rm
e})t}{1-\cfrac{2xt}{1-\cfrac{2(p_{-}x+q_{-}u+w_{\rm
e})t}{1-\cfrac{3(p_{-}x+q_{-}u)t}{1-\cdots}}}}}$ (3.28)

with coefficients

$\alpha_{2k-1}&=k\,\bigl{(}p_{-}^{k-1}x+q_{-}[k-1]_{p_{-},q_{-}}u+w_{\rm
e}\bigr{)}\\\
\alpha_{2k}=(k+1)\,\bigl{(}p_{-}^{k-1}x+q_{-}[k-1]_{p_{-},q_{-}}u\bigr{)}$
(3.29)

Proof. It suffices to verify that the T-fraction (3.23)/(3.24) with the given
specializations and the S-fraction (3.28)/(3.29) contract by Proposition 2.1
to the same J-fraction. $\square$

###  3.4 First master T-fraction

In fact, we can go farther, and introduce a polynomial in six infinite
families of indeterminates ${\mbox{{{a}}}}=({{\sf
a}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{b}}}}=({{\sf
b}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{c}}}}=({{\sf
c}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{d}}}}=({{\sf
d}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{e}}}}=({{\sf
e}}_{\ell})_{\ell\geq 0}$, ${\mbox{{{f}}}}=({{\sf f}}_{\ell})_{\ell\geq 0}$
that will have a nice T-fraction and that will include the polynomials (3.2)
and (3.21) as specializations.

Using the index-refined crossing and nesting statistics defined in (2.50), we
define the polynomial
$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})$
by

$\displaystyle
Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\;=\;$
$\displaystyle\sum_{\sigma\in{\mathfrak{D}}_{2n}}\;\>\prod\limits_{i\in{\rm
Cval}(\sigma)}\\!{{\sf a}}_{{\rm ucross}(i,\sigma),\,{\rm
unest}(i,\sigma)}\prod\limits_{i\in{\rm Cpeak}(\sigma)}\\!\\!{{\sf b}}_{{\rm
lcross}(i,\sigma),\,{\rm lnest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\;\;\,\prod\limits_{i\in{\rm Cdfall}(\sigma)}\\!\\!{{\sf
c}}_{{\rm lcross}(i,\sigma),\,{\rm lnest}(i,\sigma)}\;\prod\limits_{i\in{\rm
Cdrise}(\sigma)}\\!\\!{{\sf d}}_{{\rm ucross}(i,\sigma),\,{\rm
unest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\;\>\prod\limits_{i\in{\rm Evenfix}(\sigma)}\\!\\!\\!{{\sf
e}}_{{\rm psnest}(i,\sigma)}\;\prod\limits_{i\in{\rm
Oddfix}(\sigma)}\\!\\!\\!{{\sf f}}_{{\rm psnest}(i,\sigma)}\;.\quad$ (3.30)

where ${\rm Cval}(\sigma)=\\{i\colon\sigma^{-1}(i)>i<\sigma(i)\\}$ and
likewise for the others. We remark that (3.30) is the same as the polynomial
introduced in [46, eq. (2.77)], but restricted to D-permutations and refined
to record the parity of fixed points.

The polynomials (3.30) then have a beautiful T-fraction:

######  Theorem 3.11 (First master T-fraction for D-permutations).

The ordinary generating function of the polynomials
$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})$
has the T-type continued fraction

$\sum_{n=0}^{\infty}Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\>t^{n}\;=\;\scalebox{0.95}{$\cfrac{1}{1-{{\sf
e}}_{0}{{\sf f}}_{0}t-\cfrac{{{\sf a}}_{00}{{\sf b}}_{00}t}{1-\cfrac{({{\sf
c}}_{00}+{{\sf e}}_{1})({{\sf d}}_{00}+{{\sf f}}_{1})t}{1-\cfrac{({{\sf
a}}_{01}+{{\sf a}}_{10})({{\sf b}}_{01}+{{\sf b}}_{10})t}{1-\cfrac{({{\sf
c}}_{01}+{{\sf c}}_{10}+{{\sf e}}_{2})({{\sf d}}_{01}+{{\sf d}}_{10}+{{\sf
f}}_{2})t}{1-\cdots}}}}}$}$ (3.31)

with coefficients

$\alpha_{2k-1}&=\biggl{(}\sum_{\xi=0}^{k-1}{{\sf
a}}_{k-1-\xi,\xi}\biggr{)}\biggl{(}\sum_{\xi=0}^{k-1}{{\sf
b}}_{k-1-\xi,\xi}\biggr{)}\\\ \alpha_{2k}=\biggl{(}{{\sf
e}}_{k}\,+\,\sum_{\xi=0}^{k-1}{{\sf c}}_{k-1-\xi,\xi}\biggr{)}\biggl{(}{{\sf
f}}_{k}\,+\,\sum_{\xi=0}^{k-1}{{\sf d}}_{k-1-\xi,\xi}\biggr{)}\\\
\delta_{1}={{\sf e}}_{0}{{\sf f}}_{0}\\\ \delta_{n}=0\qquad\hbox{for $n\geq
2$}$ (3.32)

We will prove this theorem in Section 6; it is our “master” version of the
first T-fraction. It implies Theorems 3.3 and 3.9 by straightforward
specializations.

###  3.5 Variant forms of the first T-fractions

Our first T-fractions (Theorems 3.3, 3.9 and 3.11) have variant forms in which
we use the variant index-refined crossing and nesting statistics (2.52) in
place of the original index-refined crossing and nesting statistics (2.50).

It is convenient to start with the master T-fraction. Introducing
indeterminates
${\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}}$
as before, we define the variant polynomial
$Q^{\prime}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})$
by

$\displaystyle
Q^{\prime}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\;=\;$
$\displaystyle\sum_{\sigma\in{\mathfrak{D}}_{2n}}\;\>\prod\limits_{i\in{\rm
Cval}(\sigma)}\\!{{\sf a}}_{{\rm lcross}^{\prime}(i,\sigma),\,{\rm
lnest}^{\prime}(i,\sigma)}\prod\limits_{i\in{\rm Cpeak}(\sigma)}\\!\\!{{\sf
b}}_{{\rm ucross}^{\prime}(i,\sigma),\,{\rm
unest}^{\prime}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\;\;\,\prod\limits_{i\in{\rm Cdfall}(\sigma)}\\!\\!{{\sf
c}}_{{\rm lcross}^{\prime}(i,\sigma),\,{\rm
lnest}^{\prime}(i,\sigma)}\;\prod\limits_{i\in{\rm Cdrise}(\sigma)}\\!\\!{{\sf
d}}_{{\rm ucross}^{\prime}(i,\sigma),\,{\rm
unest}^{\prime}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\;\>\prod\limits_{i\in{\rm Evenfix}(\sigma)}\\!\\!\\!{{\sf
e}}_{{\rm psnest}(i,\sigma)}\;\prod\limits_{i\in{\rm
Oddfix}(\sigma)}\\!\\!\\!{{\sf f}}_{{\rm psnest}(i,\sigma)}\;.\quad$ (3.33)

Note that for cycle valleys and cycle peaks, the “u” and “l” have here been
interchanged relative to (3.30); this is in accordance with the explanation
after (2.52) about which types of indices can have nonzero values for the
primed crossing and nesting statistics.

We then have the following variant of Theorem 3.11:

######  Theorem 3.12 (Variant first master T-fraction for D-permutations).

The ordinary generating function of the polynomials
$Q^{\prime}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})$
has the same T-type continued fraction (3.31)/(3.32) as the polynomials
$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})$.
Therefore

$Q_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\;=\;Q^{\prime}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\;.$
(3.34)

We will prove this theorem in Section 6.5.

Next we define the variant $p,q$-generalized polynomials $P^{\prime}_{n}$:

$\displaystyle
P^{\prime}_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm
o},p_{-1},p_{-2},p_{+1},p_{+2},q_{-1},q_{-2},q_{+1},q_{+2},s_{\rm e},s_{\rm
o})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
ereccpeak}^{\prime}(\sigma)}x_{2}^{{\rm
eareccdfall}^{\prime}(\sigma)}y_{1}^{{\rm
eareccval}^{\prime}(\sigma)}y_{2}^{{\rm
ereccdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm
nrcpeak}^{\prime}(\sigma)}u_{2}^{{\rm nrcdfall}^{\prime}(\sigma)}v_{1}^{{\rm
nrcval}^{\prime}(\sigma)}v_{2}^{{\rm
nrcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>p_{-1}^{{\rm
ucrosscpeak}^{\prime}(\sigma)}p_{-2}^{{\rm
lcrosscdfall}^{\prime}(\sigma)}p_{+1}^{{\rm
lcrosscval}^{\prime}(\sigma)}p_{+2}^{{\rm
ucrosscdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>q_{-1}^{{\rm
unestcpeak}^{\prime}(\sigma)}q_{-2}^{{\rm
lnestcdfall}^{\prime}(\sigma)}q_{+1}^{{\rm
lnestcval}^{\prime}(\sigma)}q_{+2}^{{\rm
unestcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>s_{\rm e}^{{\rm epsnest}(\sigma)}s_{\rm
o}^{{\rm opsnest}(\sigma)}$ (3.35)

where, for example, the statistics ${\rm ereccpeak}^{\prime}$ and ${\rm
nrcpeak}^{\prime}$ measure whether a cycle peak $i$ is a record value, i.e.
whether $\sigma^{-1}(i)$ is a record position. That is, we define

${\rm
ereccpeak}^{\prime}(\sigma)&=\\#\\{i\colon\>\sigma^{-1}(i)<i>\sigma(i)\hbox{
and }\sigma^{-1}(i)\hbox{ is a record}\\}\\\ {\rm
nrcpeak}^{\prime}(\sigma)=\\#\\{i\colon\>\sigma^{-1}(i)<i>\sigma(i)\hbox{ and
}\sigma^{-1}(i)\hbox{ is not a record}\\}\qquad$ (3.36)

and likewise for the others. (Since a record position is necessarily a weak
excedance, which here means $\sigma^{-1}(i)\leq i$, erec here corresponds to
cpeak and cdrise; likewise earec corresponds to cval and cdfall.) Similarly,
we define

${\rm ucrosscpeak}^{\prime}(\sigma)&=\sum_{k\in{\rm Cpeak}(\sigma)}{\rm
ucross}^{\prime}(k,\sigma)\\\ {\rm unestcpeak}^{\prime}(\sigma)=\sum_{k\in{\rm
Cpeak}(\sigma)}{\rm unest}^{\prime}(k,\sigma)$ (3.37)

where ${\rm ucross}^{\prime}$ and ${\rm unest}^{\prime}$ have been defined in
(2.52a,b), and likewise for the others.

We then have the following variant of Theorem 3.9:

######  Theorem 3.13 (Variant first T-fraction for D-permutations,
$p,q$-generalization).

The ordinary generating function of the polynomials $P^{\prime}_{n}$ has the
same T-type continued fraction (3.23)/(3.24) as the polynomials $P_{n}$.
Therefore

And finally, we can define variant polynomials
$P^{\prime}_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},$ $z_{\rm e},z_{\rm o})$ by specializing
$p_{-1}=p_{-2}=p_{+1}=p_{+2}=q_{-1}=q_{-2}=q_{+1}=q_{+2}=s_{\rm e}=s_{\rm
o}=1$, and thereby obtain a variant version of Theorem 3.3. We leave the
details to the reader.

Remark. A four-variable special case of Theorem 3.13 was found by
Randrianarivony and Zeng [42, Proposition 10] for D-o-semiderangements. Note
first that for a D-o-semiderangement, each fixed point (which is necessarily
even) must be a neither-record-antirecord: for if a fixed point $i$ were a
record or antirecord, then it would be both; but by Lemma 3.2, $i\\!-\\!1$
would then also be a record-antirecord fixed point, which is impossible since
$\sigma$ is a D-o-semiderangement.

Let us now look at the statistics defined by Randrianarivony and Zeng [42, p.
2]. Their statistic “lema” is a left-to-right maximum (i.e. a record) whose
value is even: thus we can say that $\sigma^{-1}(i)$ is a record position and
that $i$ is even. But a record is always a weak excedance, hence
$\sigma^{-1}(i)\leq i$; and $i$ is even, hence $i\geq\sigma(i)$. Since $i$ is
a record, it cannot be a fixed point, so it must be a cycle peak, and we have
${\rm lema}={\rm ereccpeak}^{\prime}$. Similarly, their statistic “remi”
(resp. “romi”) is a right-to-left minimum (i.e. an antirecord) whose value is
even (resp. odd); by similar reasoning we obtain ${\rm remi}={\rm
eareccdfall}^{\prime}$ and ${\rm romi}={\rm eareccval}^{\prime}$. Their
polynomial [42, eq. (3.3)]

$R_{n}(x,y,\bar{x},\bar{y})\;=\;\sum_{\sigma\in{\mathfrak{D}}^{\rm
o}_{2n}}x^{{\rm lema}(\sigma)}y^{{\rm romi}(\sigma)}\bar{x}^{{\rm
fix}(\sigma)}\bar{y}^{{\rm remi}(\sigma)}$ (3.39)

thus corresponds to our $P^{\prime}_{n}$ specialized to $x_{1}=x$, $y_{1}=y$,
$w_{\rm e}=\bar{x}$, $x_{2}=\bar{y}$, $w_{\rm o}=z_{\rm o}=0$, and all other
variables equal to 1. Their S-fraction [42, Proposition 10] is then a special
case of Theorem 3.13. $\blacksquare$

##  4 Second T-fraction and its generalizations

It is natural to want to refine the foregoing polynomials by keeping track
also of the number of cycles (cyc). Unfortunately, ${\rm cyc}$ does not seem
to mesh well with the record classification: even the three-variable
polynomials

$P_{n}(x,y,\lambda)\;=\;\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
arec}(\sigma)}y^{{\rm erec}(\sigma)}\lambda^{{\rm cyc}(\sigma)}$ (4.1)

do not have a J-fraction with polynomial coefficients (see Appendix A). Using
the contraction formula (Proposition 2.1), it follows from this that
$P_{n}(x,y,\lambda)$ also cannot have a T-fraction with polynomial
coefficients and $\delta_{2}=\delta_{4}=\ldots=0$.111111 This does not exclude
that $P_{n}(x,y,\lambda)$ might have a general T-fraction with polynomial
coefficients. Indeed, it is easy to see [45] that, for any sequence
${\bm{a}}=(a_{n})_{n\geq 0}$ with $a_{0}=1$ in a commutative ring $R$, and any
sequence ${\bm{\alpha}}=(\alpha_{n})_{n\geq 1}$ of invertible elements of $R$,
there exists a unique sequence ${\bm{\delta}}=(\delta_{n})_{n\geq 1}$ in $R$
such that the ordinary generating function $\sum_{n=0}^{\infty}a_{n}t^{n}$ is
represented by the T-fraction with coefficients ${\bm{\alpha}}$ and
${\bm{\delta}}$. So the polynomials $P_{n}(x,y,\lambda)$ are in fact
represented by uncountably many different T-fractions with coefficients
$\alpha_{n}\in{\mathbb{Z}}\setminus\\{0\\}$ (or even $\alpha_{n}\in\\{1,2\\}$)
and $\delta_{n}\in{\mathbb{Q}}[x,y,\lambda]$. Furthermore, such T-fractions
might exist also for certain noninvertible ${\bm{\alpha}}$, subject to
suitable divisibility conditions. But it is far from clear whether any of
these T-fractions are simple enough to be found explicitly.

Nevertheless, it turns out that cyc almost meshes with the complete parity-
refined record-and-cycle classification: it suffices to make one
(conjecturally) or two (provably) specializations in which we partially
renounce recording the record status. We explain this in the next subsection.

###  4.1 Second T-fraction

####  4.1.1 Conjectured T-fraction and main theorem

We begin by introducing a polynomial in 13 variables that generalizes (3.2) by
keeping track also of the number of cycles (cyc):

$\displaystyle\scalebox{0.97}{$\widehat{P}_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},\lambda)$}\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\,\lambda^{{\rm cyc}(\sigma)}\;.$ (4.2)

Of course there is no hope that $\widehat{P}_{n}$ has a J-fraction (or a
T-fraction with $\delta_{2}=\delta_{4}=\ldots=0$) with polynomial
coefficients, because even the specialization (4.1) does not have one.
Nevertheless, we find empirically that we need to make only one specialization
— either $u_{1}=x_{1}$ or $v_{1}=y_{1}$ — to obtain a good T-fraction. In
other words, it suffices to renounce distinguishing either the antirecord
status of cycle peaks or the record status of cycle valleys. For concreteness
we show the second of these conjectures:

######  Conjecture 4.1.

The ordinary generating function of the polynomials (4.2) specialized to
$v_{1}=y_{1}$ has the T-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}\widehat{P}_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},y_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},\lambda)\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-\lambda^{2}z_{\rm e}z_{\rm o}\,t-\cfrac{\lambda
x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!\lambda w_{\rm e})(y_{2}\\!+\\!\lambda
w_{\rm
o})\,t}{1-\cfrac{(\lambda+1)(x_{1}\\!+\\!u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!\lambda
w_{\rm e})(y_{2}\\!+\\!v_{2}\\!+\\!\lambda w_{\rm
o})\,t}{1-\cfrac{(\lambda+2)(x_{1}\\!+\\!2u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!\lambda
w_{\rm e})(y_{2}\\!+\\!2v_{2}\\!+\\!\lambda w_{\rm o})\,t}{1-\cdots}}}}}}}$
(4.3)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1)\>[x_{1}+(k-1)u_{1}]\>y_{1}\\\
\alpha_{2k}=[x_{2}+(k-1)u_{2}+\lambda w_{\rm e}]\>[y_{2}+(k-1)v_{2}+\lambda
w_{\rm o}]\\\ \delta_{1}=\lambda^{2}z_{\rm e}z_{\rm o}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (4.4)

We have tested this conjecture through $n=6$.

Alas, we are unable at present to prove Conjecture 4.1; we are only able to
prove the weaker version in which we make the two specializations
$v_{1}=y_{1}$ and $v_{2}=y_{2}$, i.e. we renounce distinguishing the record
status of cycle valleys and cycle double rises. However, we can do better than
this: namely, we replace the pair $y_{2},v_{2}$ by a pair of new variables
${\widehat{y}}_{2},{\widehat{v}}_{2}$ that measure, not whether a cycle double
rise $i$ is a record position, but rather whether it is a record value, i.e.
whether $\sigma^{-1}(i)$ is a record. That is, we define

${\rm
ereccdrise}^{\prime}(\sigma)&=\\#\\{i\colon\>\sigma^{-1}(i)<i<\sigma(i)\hbox{
and }\sigma^{-1}(i)\hbox{ is a record}\\}\\\ {\rm
nrcdrise}^{\prime}(\sigma)=\\#\\{i\colon\>\sigma^{-1}(i)<i<\sigma(i)\hbox{ and
}\sigma^{-1}(i)\hbox{ is not a record}\\}\qquad$ (4.5)

[These statistics have already been used in (3.35).] We then define the
modified polynomials

$\displaystyle\widehat{\widehat{P}}_{n}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},v_{1},{\widehat{v}}_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},\lambda)\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}{\widehat{y}}_{2}^{{\rm
ereccdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}{\widehat{v}}_{2}^{{\rm
nrcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\,\lambda^{{\rm cyc}(\sigma)}\;.$ (4.6)

We are then able to prove:

######  Theorem 4.2 (Second T-fraction for D-permutations).

The ordinary generating function of the polynomials (4.6) specialized to
$v_{1}=y_{1}$ has the T-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}\widehat{\widehat{P}}_{n}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},y_{1},{\widehat{v}}_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o},\lambda)\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-\lambda^{2}z_{\rm e}z_{\rm o}\,t-\cfrac{\lambda
x_{1}y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!\lambda w_{\rm
e})({\widehat{y}}_{2}\\!+\\!\lambda w_{\rm
o})\,t}{1-\cfrac{(\lambda+1)(x_{1}\\!+\\!u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!\lambda
w_{\rm e})({\widehat{y}}_{2}\\!+\\!{\widehat{v}}_{2}\\!+\\!\lambda w_{\rm
o})\,t}{1-\cfrac{(\lambda+2)(x_{1}\\!+\\!2u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!\lambda
w_{\rm e})({\widehat{y}}_{2}\\!+\\!2{\widehat{v}}_{2}\\!+\\!\lambda w_{\rm
o})\,t}{1-\cdots}}}}}}}$ (4.7)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1)\>[x_{1}+(k-1)u_{1}]\>y_{1}\\\
\alpha_{2k}=[x_{2}+(k-1)u_{2}+\lambda w_{\rm
e}]\>[{\widehat{y}}_{2}+(k-1){\widehat{v}}_{2}+\lambda w_{\rm o}]\\\
\delta_{1}=\lambda^{2}z_{\rm e}z_{\rm o}\\\ \delta_{n}=0\qquad\hbox{for $n\geq
2$}$ (4.8)

This continued fraction has exactly the same form as Conjecture 4.1, except
that $y_{2},v_{2}$ are replaced by ${\widehat{y}}_{2},{\widehat{v}}_{2}$. We
will prove Theorem 4.2 in Section 7.

Note that each of the coefficients $\alpha_{i}$ and $\delta_{i}$ in (4.8) is
homogeneous of degree $1$ in $x_{1},x_{2},$ $u_{1},u_{2},w_{\rm e},z_{\rm e}$
and also homogeneous of degree $1$ in
$y_{1},{\widehat{y}}_{2},{\widehat{v}}_{2},w_{\rm o},z_{\rm o}$. As before,
this reflects the homogeneities of the $\widehat{\widehat{P}}_{n}$.

Remark. Specializing Theorem 4.2 to $w_{\rm e}=w_{\rm o}=z_{\rm e}=z_{\rm
o}=0$ and all other variables except $\lambda$ to 1, we obtain an S-fraction
with $\alpha_{2k-1}=k(\lambda+k-1)$, $\alpha_{2k}=k^{2}$ for counting
D-derangements by number of cycles [38, eq. (4.4)]. $\blacksquare$

It is perhaps worth observing that, in view of Theorem 4.2, Conjecture 4.1 is
equivalent to the following assertion about the equidistribution of
statistics:

######  Conjecture 4.1.

′ There exists a bijection
$\psi_{n}\colon{\mathfrak{D}}_{2n}\to{\mathfrak{D}}_{2n}$ that maps the
12-tuple

$\displaystyle({\rm eareccpeak},{\rm eareccdfall},{\rm cval},{\rm
ereccdrise},{\rm nrcpeak},{\rm nrcdfall},{\rm nrcdrise},\qquad$
$\displaystyle\;\,{\rm evennrfix},{\rm oddnrfix},{\rm evenrar},{\rm
oddrar},{\rm cyc})$

onto

$\displaystyle({\rm eareccpeak},{\rm eareccdfall},{\rm cval},{\rm
ereccdrise}^{\prime},{\rm nrcpeak},{\rm nrcdfall},{\rm
nrcdrise}^{\prime},\qquad$ $\displaystyle\;\,{\rm evennrfix},{\rm
oddnrfix},{\rm evenrar},{\rm oddrar},{\rm cyc})\;.$

####  4.1.2 Specialization leading to S-fraction

We refrain from pursuing the cycle-counting generalizations of Proposition 3.6
and Corollary 3.7, and limit ourselves to giving the cycle-counting
generalization of Corollary 3.8. If in the T-fraction (4.7)/(4.8) we
specialize $y_{1}={\widehat{y}}_{2}={\widehat{v}}_{2}=1=z_{\rm o}=w_{\rm o}=1$
— that is, all the weights associated to odd indices are set to 1 — and also
specialize $z_{\rm e}=w_{\rm e}$, $x_{1}=x_{2}$ and $u_{1}=u_{2}$, the
resulting T-fraction can be rewritten as an S-fraction by noticing that both
of them contract (Proposition 2.1) to the same J-fraction, and we obtain a
generalization of Corollary 3.8 that includes counting the number of cycles:

######  Corollary 4.3 (S-fraction for specialized D-permutations, counting
number of cycles).

The ordinary generating function of the polynomials $P^{\star}_{n}(x,u,w_{\rm
e},\lambda)$ defined by

$P^{\star}_{n}(x,u,w_{\rm
e},\lambda)\;=\;\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
earec}(\sigma)}u^{{\rm nrcpeak}(\sigma)+{\rm nrcdfall}(\sigma)}w_{\rm e}^{{\rm
evenfix}(\sigma)}\lambda^{{\rm cyc}(\sigma)}$ (4.9)

has the S-type continued fraction

$\sum_{n=0}^{\infty}P^{\star}_{n}(x,u,w_{\rm
e},\lambda)\>t^{n}\;=\;\cfrac{1}{1-\cfrac{\lambda(x+\lambda w_{\rm
e})t}{1-\cfrac{(\lambda+1)xt}{1-\cfrac{(\lambda+1)(x+u+\lambda w_{\rm
e})t}{1-\cfrac{(\lambda+2)(x+u)t}{1-\cdots}}}}}$ (4.10)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1)\,[x+ (k-1)u+\lambda w_{\rm e}]\\\
\alpha_{2k}=(\lambda+k)\,[x+(k-1)u]$ (4.11)

Of course there is also an analogous S-fraction in which the roles of odd and
even indices are reversed.

Remarks. 1\. Setting $x=u=1$ and $w_{\rm e}=0$ in (4.10)/(4.11), we obtain the
S-fraction for D-semiderangements enumerated by number of cycles, with
coefficients $\alpha_{2k-1}=k(\lambda+k-1)$ and $\alpha_{2k}=k(\lambda+k)$,
which was found a quarter-century ago by Randrianarivony and Zeng [42,
Corollary 13].

2\. Setting $x=u=w_{\rm e}=1$ in (4.10)/(4.11), we obtain an S-fraction for
D-permutations enumerated by number of cycles, with coefficients
$\alpha_{2k-1}=\alpha_{2k}=k(\lambda+k)$. This S-fraction appeared in [27, eq.
(14)] (in fact in a $q$-generalization), but with a different combinatorial
interpretation. Further specializing to $\lambda=1$, we obtain the S-fraction
(2.38)/(2.39) for the once-shifted Genocchi medians $h_{n+1}$. $\blacksquare$

Since the once-shifted Genocchi medians $h_{n+1}$ count D-permutations of
$[2n]$, the preceding remark suggests that one should try to find an
S-fraction for D-permutations that generalizes (2.38)/(2.39):

######  Open Problem 4.4.

Find the statistics on D-permutations that would lead to a more general
S-fraction of the form

$\alpha_{2k-1}&=[x_{1}+(k-1)u_{1}]\,[x_{2}+ku_{2}]\\\
\alpha_{2k}=[y_{1}+(k-1)v_{1}]\,[y_{2}+kv_{2}]$ (4.12)

or

$\alpha_{2k-1}&=[x_{1}+(k-1)u_{1}]\,[x_{2}+(k-1)u_{2}+w]\\\
\alpha_{2k}=[y_{1}+(k-1)v_{1}]\,[y_{2}+(k-1)v_{2}+w^{\prime}]$ (4.13)

$\blacksquare$

####  4.1.3 Reformulation using cycle valley minima

We can rephrase Conjecture 4.1 and Theorem 4.2 in a more suggestive form by
observing that each 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 therefore define four new statistics:

  * •

cycle peak maximum (${{\rm maxpeak}}$): cycle peak that is the largest in its
cycle;

  * •

cycle peak non-maximum (${\rm nmaxpeak}$): cycle peak that is not the largest
in its cycle;

  * •

cycle valley minimum (${{\rm minval}}$): cycle valley that is the smallest in
its cycle;

  * •

cycle valley non-minimum (${\rm nminval}$): cycle valley that is not the
smallest in its cycle.

We now introduce a polynomial that is similar to (3.2) except that the
classification of cycle valleys as records or non-records — which we have
already renounced in Conjecture 4.1 — is replaced by the classification of
cycle valleys as minima or non-minima:

$\displaystyle\widetilde{P}_{n}(x_{1},x_{2},{\widetilde{y}}_{1},y_{2},u_{1},u_{2},{\widetilde{v}}_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}{\widetilde{y}}_{1}^{{\rm
minval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}{\widetilde{v}}_{1}^{{\rm nminval}(\sigma)}v_{2}^{{\rm
nrcdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\>w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\;.$ (4.14)

Then the factor $(\lambda+k-1)y_{1}$ in Conjecture 4.1 and Theorem 4.2 is
replaced by ${\widetilde{y}}_{1}+(k-1){\widetilde{v}}_{1}$, and Conjecture 4.1
can be rewritten as:

######  Conjecture 4.2.

′′ The ordinary generating function of the polynomials (4.14) has the T-type
continued fraction

$\displaystyle\sum_{n=0}^{\infty}\widetilde{P}_{n}(x_{1},x_{2},{\widetilde{y}}_{1},y_{2},u_{1},u_{2},{\widetilde{v}}_{1},v_{2},w_{\rm
e},w_{\rm o},z_{\rm e},z_{\rm o})\>t^{n}\;=\;$
$\displaystyle\cfrac{1}{1-z_{\rm e}z_{\rm
o}\,t-\cfrac{x_{1}{\widetilde{y}}_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})({\widetilde{y}}_{1}+{\widetilde{v}}_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!v_{2}\\!+\\!w_{\rm
o})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})({\widetilde{y}}_{1}+2{\widetilde{v}}_{1})\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2}\\!+\\!w_{\rm
e})(y_{2}\\!+\\!2v_{2}\\!+\\!w_{\rm o})\,t}{1-\cdots}}}}}}}$ (4.15)

with coefficients

$\alpha_{2k-1}&=[x_{1}+(k-1)u_{1}]\>[{\widetilde{y}}_{1}+(k-1){\widetilde{v}}_{1}]\\\
\alpha_{2k}=[x_{2}+(k-1)u_{2}+w_{\rm e}]\>[y_{2}+(k-1)v_{2}+w_{\rm o}]\\\
\delta_{1}=z_{\rm e}z_{\rm o}\\\ \delta_{n}=0\qquad\hbox{for $n\geq 2$}$
(4.16)

Note that the factors of $\lambda$ multiplying $w_{\rm e},w_{\rm o},z_{\rm
e},z_{\rm o}$ in Conjecture 4.1 have now disappeared because we are no longer
giving such factors to singleton cycles. Even more strikingly, Conjecture 4.1′
now looks identical to Theorem 3.3 except that $y_{1},v_{1}$ have been
replaced by ${\widetilde{y}}_{1},{\widetilde{v}}_{1}$. Moreover, Theorem 4.2
can be rewritten in a similar way, replacing $y_{1},v_{1}$ by
${\widetilde{y}}_{1},{\widetilde{v}}_{1}$ as in (4.14) and replacing
$y_{2},v_{2}$ by ${\widehat{y}}_{2},{\widehat{v}}_{2}$ as in (4.6); for
brevity we leave this reformulation to the reader.

####  4.1.4 S-fraction for D-cycles

We can also enumerate D-cycles by extracting the coefficient of $\lambda^{1}$
in Conjecture 4.1 and Theorem 4.2. We begin by defining the polynomials
analogous to (3.2) but restricted to D-cycles (which we recall have no fixed
points):

$\displaystyle
P^{{\mathfrak{DC}}}_{n}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},v_{1},v_{2})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{DC}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}y_{2}^{{\rm ereccdrise}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\quad\\!u_{1}^{{\rm
nrcpeak}(\sigma)}u_{2}^{{\rm nrcdfall}(\sigma)}v_{1}^{{\rm
nrcval}(\sigma)}v_{2}^{{\rm nrcdrise}(\sigma)}\;.$ (4.17)

Conjecture 4.1 then implies the following:

######  Conjecture 4.5 (Conjectured S-fraction for D-cycles).

The ordinary generating function of the polynomials (4.17) specialized to
$v_{1}=y_{1}$ has the S-type continued fraction

$\\!\\!\\!\sum_{n=0}^{\infty}P^{{\mathfrak{DC}}}_{n+1}(x_{1},x_{2},y_{1},y_{2},u_{1},u_{2},y_{1},v_{2})\>t^{n}\;=\;\cfrac{x_{1}y_{1}}{1-\cfrac{x_{2}y_{2}\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2}\\!)(y_{2}\\!+\\!v_{2})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})2y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2})(y_{2}\\!+\\!2v_{2})\,t}{1-\cdots}}}}}}$
(4.18)

with coefficients

$\alpha_{2k-1}&=[x_{2}+(k-1)u_{2}]\>[y_{2}+(k-1)v_{2}]\\\
\alpha_{2k}=[x_{1}+ku_{1}]\>ky_{1}$ (4.19)

We have tested this conjecture through $n=5$.

Similarly, we can define the polynomials analogous to (4.6) but restricted to
D-cycles:

$\displaystyle\widehat{\widehat{P}}{}^{{\mathfrak{DC}}}_{n}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},v_{1},{\widehat{v}}_{2})\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{DC}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}{\widehat{y}}_{2}^{{\rm
ereccdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\quad\\!u_{1}^{{\rm
nrcpeak}(\sigma)}u_{2}^{{\rm nrcdfall}(\sigma)}v_{1}^{{\rm
nrcval}(\sigma)}{\widehat{v}}_{2}^{{\rm nrcdrise}^{\prime}(\sigma)}\;.$ (4.20)

Theorem 4.2 implies the following:

######  Corollary 4.6 (S-fraction for D-cycles).

The ordinary generating function of the polynomials (4.20) specialized to
$v_{1}=y_{1}$ has the S-type continued fraction

$\\!\\!\\!\sum_{n=0}^{\infty}\widehat{\widehat{P}}{}^{{\mathfrak{DC}}}_{n+1}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},y_{1},{\widehat{v}}_{2})\>t^{n}\;=\;\cfrac{x_{1}y_{1}}{1-\cfrac{x_{2}{\widehat{y}}_{2}\,t}{1-\cfrac{(x_{1}\\!+\\!u_{1})y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!u_{2})({\widehat{y}}_{2}\\!+\\!{\widehat{v}}_{2})\,t}{1-\cfrac{(x_{1}\\!+\\!2u_{1})2y_{1}\,t}{1-\cfrac{(x_{2}\\!+\\!2u_{2})({\widehat{y}}_{2}\\!+\\!2{\widehat{v}}_{2})\,t}{1-\cdots}}}}}}$
(4.21)

with coefficients

$\alpha_{2k-1}&=[x_{2}+(k-1)u_{2}]\>[{\widehat{y}}_{2}+(k-1){\widehat{v}}_{2}]\\\
\alpha_{2k}=[x_{1}+ku_{1}]\>ky_{1}$ (4.22)

Specializing Corollary 4.6 by setting all variables equal to 1, we obtain an
S-fraction with $\alpha_{2k-1}=k^{2}$ and $\alpha_{2k}=k(k+1)$, which we
recognize as the S-fraction (2.24)/(2.25) for the Genocchi numbers $g_{n}$. We
have therefore recovered the known fact [32, 33] that
$|{\mathfrak{DC}}_{2n+2}|=g_{n}$, or equivalently that
$|{\mathfrak{DC}}_{2n}|=g_{n-1}$.

###  4.2 $\bm{p,q}$-generalizations of the second T-fraction

We can also make a $p,q$-generalization of the second T-fraction in Theorem
4.2. Let us define the polynomial in 23 variables that generalizes (4.6) by
including four pairs of $(p,q)$-variables corresponding to the four refined
types of crossings and nestings illustrated in Figure 3, as well as two
variables corresponding to pseudo-nestings of fixed points:

$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}{\widehat{y}}_{2}^{{\rm
ereccdrise}^{\prime}(\sigma)}\>\times\qquad\qquad\>$
$\displaystyle\qquad\qquad\qquad\;\,u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}{\widehat{v}}_{2}^{{\rm
nrcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad\;$
$\displaystyle\qquad\qquad\qquad\;\,w_{\rm e}^{{\rm evennrfix}(\sigma)}w_{\rm
o}^{{\rm oddnrfix}(\sigma)}z_{\rm e}^{{\rm evenrar}(\sigma)}z_{\rm o}^{{\rm
oddrar}(\sigma)}\>\times\qquad\qquad\;$
$\displaystyle\qquad\qquad\qquad\;\,p_{-1}^{{\rm
lcrosscpeak}(\sigma)}p_{-2}^{{\rm lcrosscdfall}(\sigma)}p_{+1}^{{\rm
ucrosscval}(\sigma)}{\widehat{p}}_{+2}^{{\rm
ucrosscdrise}^{\prime}(\sigma)}\>\times\qquad\qquad\;$
$\displaystyle\qquad\qquad\qquad\;\,q_{-1}^{{\rm
lnestcpeak}(\sigma)}q_{-2}^{{\rm lnestcdfall}(\sigma)}q_{+1}^{{\rm
unestcval}(\sigma)}{\widehat{q}}_{+2}^{{\rm
unestcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\;\,s_{\rm e}^{{\rm epsnest}(\sigma)}s_{\rm
o}^{{\rm opsnest}(\sigma)}\,\lambda^{{\rm cyc}(\sigma)}\;.$ (4.23)

This is the same as (3.21), except for the inclusion of the factor
$\lambda^{{\rm cyc}(\sigma)}$ and the replacement of $y_{2}^{{\rm
ereccdrise}(\sigma)},v_{2}^{{\rm nrcdrise}(\sigma)},p_{+2}^{{\rm
ucrosscdrise}(\sigma)},q_{+2}^{{\rm unestcdrise}(\sigma)}$ by
${\widehat{y}}_{2}^{{\rm ereccdrise}^{\prime}(\sigma)},{\widehat{v}}_{2}^{{\rm
nrcdrise}^{\prime}(\sigma)}$, ${\widehat{p}}_{+2}^{{\rm
ucrosscdrise}^{\prime}(\sigma)},{\widehat{q}}_{+2}^{{\rm
unestcdrise}^{\prime}(\sigma)}$, respectively, where the statistics ${\rm
ucrosscdrise}^{\prime}$ and ${\rm unestcdrise}^{\prime}$ are defined as

${\rm ucrosscdrise}^{\prime}(\sigma)&=\sum_{k\in{\rm Cdrise}(\sigma)}{\rm
ucross}^{\prime}(k,\sigma)\\\ {\rm
unestcdrise}^{\prime}(\sigma)=\sum_{k\in{\rm Cdrise}(\sigma)}{\rm
unest}^{\prime}(k,\sigma)$ (4.24)

[These statistics have already been used in (3.35).]

We refrain from attempting to generalize Conjecture 4.1 and simply limit
ourselves to stating the $p,q$-generalization of Theorem 4.2 that we are able
to prove. It turns out that we need to make the specializations $v_{1}=y_{1}$
and $q_{+1}=p_{+1}$. The result is then the following:

######  Theorem 4.7 (Second T-fraction for D-permutations,
$p,q$-generalization).

The ordinary generating function of the polynomials (4.23) specialized to
$v_{1}=y_{1}$ and $q_{+1}=p_{+1}$ has the T-type continued fraction

(4.25)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1)\>p_{+1}^{k}y_{1}\>\bigl{(}p_{-1}^{k-1}x_{1}+q_{-1}[k-1]_{p_{-1},q_{-1}}u_{1}\bigr{)}\>\\\
\alpha_{2k}=\bigl{(}p_{-2}^{k-1}x_{2}+q_{-2}[k-1]_{p_{-2},q_{-2}}u_{2}+\lambda
s_{\rm e}^{k}w_{\rm
e}\bigr{)}\>\bigl{(}{\widehat{p}}_{+2}^{k-1}{\widehat{y}}_{2}+{\widehat{q}}_{+2}[k-1]_{{\widehat{p}}_{+2},{\widehat{q}}_{+2}}{\widehat{v}}_{2}+\lambda
s_{\rm o}^{k}w_{\rm o}\bigr{)}\\\ \\\ \delta_{1}=\lambda^{2}z_{\rm e}z_{\rm
o}\\\ \delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (4.26)

We will prove Theorem 4.7 in Section 7. Of course we reobtain Theorem 4.2 by
making the specialization
$p_{-1}=p_{-2}=p_{+1}={\widehat{p}}_{+2}=q_{-1}=q_{-2}={\widehat{q}}_{+2}=s_{\rm
e}=s_{\rm o}=1$.

Remark. If we specialize to $x_{1}=u_{1}$, $x_{2}=u_{2}$,
${\widehat{y}}_{2}={\widehat{v}}_{2}$ — that is, renounce the counting of
records — then the coefficients (4.26) simplify to

$\alpha_{2k-1}&=(\lambda+k-1)\>p_{+1}^{k}y_{1}\>[k]_{p_{-1},q_{-1}}x_{1}\\\
\alpha_{2k}=\bigl{(}[k]_{p_{-2},q_{-2}}x_{2}+\lambda s_{\rm e}^{k}w_{\rm
e}\bigr{)}\>\bigl{(}[k]_{{\widehat{p}}_{+2},{\widehat{q}}_{+2}}{\widehat{y}}_{2}+\lambda
s_{\rm o}^{k}w_{\rm o}\bigr{)}\\\ \delta_{1}=z_{\rm e}z_{\rm o}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (4.27)

$\blacksquare$

We can also obtain a $p,q$-generalization of Corollary 4.3, or equivalently a
cycle-counting generalization of Corollary 3.10. If in the T-fraction
(4.25)/(4.26) we specialize $z_{\rm o}=w_{\rm
o}=y_{1}={\widehat{y}}_{2}={\widehat{v}}_{2}=p_{+1}={\widehat{p}}_{+2}={\widehat{q}}_{+2}=s_{\rm
o}=1$ — that is, all the weights associated to odd indices are set to 1 — and
also specialize $z_{\rm e}=w_{\rm e}$, $x_{1}=x_{2}$, $u_{1}=u_{2}$,
$p_{-1}=p_{-2}$, $q_{-1}=q_{-2}$ and $s_{\rm e}=1$, the resulting T-fraction
can be rewritten as an S-fraction by noticing that they contract (Proposition
2.1) to the same J-fraction:

######  Corollary 4.8 (S-fraction for D-permutations counting number of
cycles, $p,q$-generalization).

The ordinary generating function of the polynomials $P^{\star}_{n}(x,u,w_{\rm
e},p_{-},q_{-},\lambda)$ defined by

$\displaystyle P^{\star}_{n}(x,u,w_{\rm e},p_{-},q_{-},\lambda)\;=\;$
$\displaystyle\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x^{{\rm
earec}(\sigma)}u^{{\rm nrcpeak}(\sigma)+{\rm nrcdfall}(\sigma)}w_{\rm e}^{{\rm
evenfix}(\sigma)}p_{-}^{{\rm lcross}(\sigma)}q_{-}^{{\rm
lnest}(\sigma)}\,\lambda^{{\rm cyc}(\sigma)}\qquad\qquad$ (4.28)

has the S-type continued fraction

$\sum_{n=0}^{\infty}P^{\star}_{n}(x,u,w_{\rm
e},p_{-},q_{-},\lambda)\>t^{n}\;=\;\cfrac{1}{1-\cfrac{\lambda(x+\lambda w_{\rm
e})t}{1-\cfrac{(\lambda+1)xt}{1-\cfrac{(\lambda+1)(p_{-}x+q_{-}u+\lambda
w_{\rm e})t}{1-\cfrac{(\lambda+2)(p_{-}x+q_{-}u)t}{1-\cdots}}}}}$ (4.29)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1)\,\bigl{(}p_{-}^{k-1}x+q_{-}[k-1]_{p_{-},q_{-}}u+\lambda
w_{\rm e}\bigr{)}\\\
\alpha_{2k}=(\lambda+k)\,\bigl{(}p_{-}^{k-1}x+q_{-}[k-1]_{p_{-},q_{-}}u\bigr{)}$
(4.30)

Finally, we can enumerate D-cycles by extracting the coefficient of
$\lambda^{1}$ in Theorem 4.7. We begin by defining the polynomials analogous
to (4.23) but restricted to D-cycles (which we recall have no fixed points):

$\displaystyle\widehat{\widehat{P}}{}^{{\mathfrak{DC}}}_{n}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},v_{1},{\widehat{v}}_{2},p_{-1},p_{-2},p_{+1},{\widehat{p}}_{+2},q_{-1},q_{-2},q_{+1},{\widehat{q}}_{+2},\lambda)\;=\;$
$\displaystyle\qquad\qquad\sum_{\sigma\in{\mathfrak{D}}_{2n}}x_{1}^{{\rm
eareccpeak}(\sigma)}x_{2}^{{\rm eareccdfall}(\sigma)}y_{1}^{{\rm
ereccval}(\sigma)}{\widehat{y}}_{2}^{{\rm
ereccdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\;\,u_{1}^{{\rm nrcpeak}(\sigma)}u_{2}^{{\rm
nrcdfall}(\sigma)}v_{1}^{{\rm nrcval}(\sigma)}{\widehat{v}}_{2}^{{\rm
nrcdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\;\,p_{-1}^{{\rm
lcrosscpeak}(\sigma)}p_{-2}^{{\rm lcrosscdfall}(\sigma)}p_{+1}^{{\rm
ucrosscval}(\sigma)}{\widehat{p}}_{+2}^{{\rm
ucrosscdrise}^{\prime}(\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\;\,q_{-1}^{{\rm
lnestcpeak}(\sigma)}q_{-2}^{{\rm lnestcdfall}(\sigma)}q_{+1}^{{\rm
unestcval}(\sigma)}{\widehat{q}}_{+2}^{{\rm
unestcdrise}^{\prime}(\sigma)}\,\lambda^{{\rm cyc}(\sigma)}\;.$ (4.31)

Theorem 4.7 then implies the following generalization of Corollary 4.6:

######  Corollary 4.9 (S-fraction for D-cycles, $p,q$-generalization).

The ordinary generating function of the polynomials (4.31) specialized to
$v_{1}=y_{1}$ and $q_{+1}=p_{+1}$ has the S-type continued fraction

$\displaystyle\sum_{n=0}^{\infty}\widehat{\widehat{P}}{}^{{\mathfrak{DC}}}_{n+1}(x_{1},x_{2},y_{1},{\widehat{y}}_{2},u_{1},u_{2},y_{1},{\widehat{v}}_{2},p_{-1},p_{-2},p_{+1},{\widehat{p}}_{+2},q_{-1},q_{-2},p_{+1},{\widehat{q}}_{+2})\>t^{n}\;=\;$
$\displaystyle\cfrac{p_{+1}x_{1}y_{1}}{1-\cfrac{x_{2}{\widehat{y}}_{2}\,t}{1-\cfrac{p_{+1}^{2}(p_{-1}x_{1}\\!+\\!q_{-1}u_{1})y_{1}\,t}{1-\cfrac{(p_{-2}x_{2}\\!+\\!q_{-2}u_{2})({\widehat{p}}_{+2}{\widehat{y}}_{2}\\!+\\!{\widehat{q}}_{+2}{\widehat{v}}_{2})\,t}{1-\cfrac{(p_{-1}^{2}x_{1}\\!+\\!q_{-1}[2]_{p_{-1},q_{-1}}u_{1})2p_{+1}^{3}y_{1}\,t}{1-\cfrac{(p_{-2}^{2}x_{2}\\!+\\!q_{-2}[2]_{p_{-2},q_{-2}}u_{2})(p_{+2}^{2}{\widehat{y}}_{2}\\!+\\!q_{+2}[2]_{p_{+2},q_{+2}}{\widehat{v}}_{2})\,t}{1-\cdots}}}}}}\qquad\qquad$
(4.32)

with coefficients

$\alpha_{2k-1}&=\bigl{(}p_{-2}^{k-1}x_{2}+q_{-2}[k-1]_{p_{-2},q_{-2}}u_{2}\bigr{)}\>\bigl{(}{\widehat{p}}_{+2}^{k-1}{\widehat{y}}_{2}+{\widehat{q}}_{+2}[k-1]_{{\widehat{p}}_{+2},{\widehat{q}}_{+2}}{\widehat{v}}_{2}\bigr{)}\qquad\\\
\alpha_{2k}=\bigl{(}p_{-1}^{k}x_{1}+q_{-1}[k]_{p_{-1},q_{-1}}u_{1}\bigr{)}\>k\,p_{+1}^{k+1}y_{1}\>$
(4.33)

###  4.3 Second master T-fraction

As with the first T-fraction, we can go much farther, and obtain a T-fraction
in six infinite families of indeterminates: ${\mbox{{{a}}}}=({{\sf
a}}_{\ell})_{\ell\geq 0}$, ${\mbox{{{b}}}}=({{\sf
b}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{c}}}}=({{\sf
c}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{d}}}}=({{\sf
d}}_{\ell,\ell^{\prime}})_{\ell,\ell^{\prime}\geq 0}$, ${\mbox{{{e}}}}=({{\sf
e}}_{\ell})_{\ell\geq 0}$, ${\mbox{{{f}}}}=({{\sf f}}_{\ell})_{\ell\geq 0}$;
please note that a now has one index rather than two. We now define a sequence
of polynomials that will include the polynomials (4.6) and (4.23) as
specializations:

$\displaystyle\widehat{\widehat{Q}}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},\lambda)\;=\;$
$\displaystyle\sum_{\sigma\in{\mathfrak{D}}_{2n}}\;\>\lambda^{{\rm
cyc}(\sigma)}\prod\limits_{i\in{\rm Cval}(\sigma)}\\!{{\sf a}}_{{\rm
ucross}(i,\sigma)+{\rm unest}(i,\sigma)}\prod\limits_{i\in{\rm
Cpeak}(\sigma)}\\!\\!{{\sf b}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\quad\;\;\prod\limits_{i\in{\rm
Cdfall}(\sigma)}\\!\\!{{\sf c}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}\;\prod\limits_{i\in{\rm Cdrise}(\sigma)}\\!\\!{{\sf
d}}_{{\rm ucross}^{\prime}(i,\sigma),\,{\rm
unest}^{\prime}(i,\sigma)}\>\times\qquad\qquad$
$\displaystyle\qquad\qquad\quad\;\prod\limits_{i\in{\rm
Evenfix}(\sigma)}\\!\\!\\!{{\sf e}}_{{\rm
psnest}(i,\sigma)}\;\prod\limits_{i\in{\rm Oddfix}(\sigma)}\\!\\!\\!{{\sf
f}}_{{\rm psnest}(i,\sigma)}\;.\quad$ (4.34)

We remark that (4.34) is almost the same as the polynomial introduced in [46,
eq. (2.100)], but restricted to D-permutations and refined to record the
parity of fixed points; the main difference is that the treatment of ${{\sf
d}}$ is a bit nicer here, using the statistics ${\rm ucross}^{\prime}$ and
${\rm unest}^{\prime}$.

Note that here, in contrast to the first master T-fraction,
$\widehat{\widehat{Q}}_{n}$ depends on ${\rm ucross}(i,\sigma)$ and ${\rm
unest}(i,\sigma)$ only via their sum: that is the price we have to pay in
order to include the statistic ${\rm cyc}$. Furthermore, the indices of ${{\sf
d}}$ involve ${\rm ucross}^{\prime}$ and ${\rm unest}^{\prime}$ instead of
${\rm ucross}$ and ${\rm unest}$.

The polynomials (4.34) then have a nice T-fraction:

######  Theorem 4.10 (Second master T-fraction for D-permutations).

The ordinary generating function of the polynomials
$\widehat{\widehat{Q}}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}},\lambda)$
has the T-type continued fraction

$\sum_{n=0}^{\infty}\widehat{\widehat{Q}}_{n}({\mbox{{{a}}}},{\mbox{{{b}}}},{\mbox{{{c}}}},{\mbox{{{d}}}},{\mbox{{{e}}}},{\mbox{{{f}}}})\>t^{n}\;=\;\scalebox{0.95}{$\cfrac{1}{1-\lambda^{2}{{\sf
e}}_{0}{{\sf f}}_{0}t-\cfrac{\lambda{{\sf a}}_{0}{{\sf
b}}_{00}t}{1-\cfrac{({{\sf c}}_{00}+\lambda{{\sf e}}_{1})({{\sf
d}}_{00}+\lambda{{\sf f}}_{1})t}{1-\cfrac{(\lambda+1){{\sf a}}_{1}({{\sf
b}}_{01}+{{\sf b}}_{10})t}{1-\cfrac{({{\sf c}}_{01}+{{\sf
c}}_{10}+\lambda{{\sf e}}_{2})({{\sf d}}_{01}+{{\sf d}}_{10}+\lambda{{\sf
f}}_{2})t}{1-\cdots}}}}}$}$ (4.35)

with coefficients

$\alpha_{2k-1}&=(\lambda+k-1){{\sf a}}_{k-1}\biggl{(}\sum_{\xi=0}^{k-1}{{\sf
b}}_{k-1-\xi,\xi}\biggr{)}\\\ \alpha_{2k}=\biggl{(}\lambda{{\sf
e}}_{k}\,+\,\sum_{\xi=0}^{k-1}{{\sf
c}}_{k-1-\xi,\xi}\biggr{)}\biggl{(}\lambda{{\sf
f}}_{k}\,+\,\sum_{\xi=0}^{k-1}{{\sf d}}_{k-1-\xi,\xi}\biggr{)}\\\
\delta_{1}=\lambda^{2}{{\sf e}}_{0}{{\sf f}}_{0}\\\
\delta_{n}=0\qquad\hbox{for $n\geq 2$}$ (4.36)

We will prove this theorem in Section 7. It implies Theorems 4.2 and 4.7 by
straightforward specializations.

##  5 Preliminaries for the proofs

Our proofs are based on Flajolet’s [20] combinatorial interpretation of
continued fractions in terms of Dyck and Motzkin paths and its generalization
[24, 37, 29, 45, 13] to Schröder paths, together with some bijections mapping
combinatorial objects (in particular, D-permutations) to labeled Dyck, Motzkin
or Schröder paths. We begin by reviewing briefly these two ingredients.

###  5.1 Combinatorial interpretation of continued fractions

Recall that a Motzkin path of length $n\geq 0$ is a path
$\omega=(\omega_{0},\ldots,\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
${\mathcal{M}}_{n}$ for the set of Motzkin paths of length $n$, and
${\mathcal{M}}=\bigcup_{n=0}^{\infty}{\mathcal{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 ${\mathcal{D}}_{2n}$ for the set of Dyck paths of length
$2n$, and ${\mathcal{D}}=\bigcup_{n=0}^{\infty}{\mathcal{D}}_{2n}$.

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

######  Theorem 5.1 (Flajolet’s master theorem).

We have

$\sum_{\omega\in{\mathcal{M}}}W(\omega)\;=\;\cfrac{1}{1-c_{0}-\cfrac{a_{0}b_{1}}{1-c_{1}-\cfrac{a_{1}b_{2}}{1-c_{2}-\cfrac{a_{2}b_{3}}{1-\cdots}}}}$
(5.1)

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

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

$\sum_{n=0}^{\infty}t^{n}\sum_{\omega\in{\mathcal{M}}_{n}}W(\omega)\;=\;\cfrac{1}{1-\gamma_{0}t-\cfrac{\beta_{1}t^{2}}{1-\gamma_{1}t-\cfrac{\beta_{2}t^{2}}{1-\cdots}}}\;\,,$
(5.2)

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

$\sum_{n=0}^{\infty}t^{n}\sum_{\omega\in{\mathcal{D}}_{2n}}W(\omega)\;=\;\cfrac{1}{1-\cfrac{\alpha_{1}t}{1-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\,,$
(5.3)

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

Let us now show how to handle Schröder paths within this framework. A Schröder
path of length $2n$ ($n\geq 0$) is a path
$\omega=(\omega_{0},\ldots,\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 ${\mathcal{S}}_{2n}$ for the set of Schröder
paths of length $2n$, and
${\mathcal{S}}=\bigcup_{n=0}^{\infty}{\mathcal{S}}_{2n}$.

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

$\sum_{n=0}^{\infty}t^{n}\sum_{\omega\in{\mathcal{S}}_{2n}}W(\omega)\;=\;\cfrac{1}{1-\delta_{1}t-\cfrac{\alpha_{1}t}{1-\delta_{2}t-\cfrac{\alpha_{2}t}{1-\cdots}}}\;\,,$
(5.4)

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

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

Let ${\bm{\mathcal{A}}}=({\mathcal{A}}_{h})_{h\geq 0}$,
${\bm{\mathcal{B}}}=({\mathcal{B}}_{h})_{h\geq 1}$ and
${\bm{\mathcal{C}}}=({\mathcal{C}}_{h})_{h\geq 0}$ be sequences of finite
sets. An $({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled
Motzkin path of length $\bm{n}$ is a pair $(\omega,\xi)$ where
$\omega=(\omega_{0},\ldots,\omega_{n})$ is a Motzkin path of length $n$, and
$\xi=(\xi_{1},\ldots,\xi_{n})$ is a sequence satisfying

$\xi_{i}\>\in\>\begin{cases}{\mathcal{A}}(h_{i-1})&\textrm{if step $i$ is a
rise (i.e.\ $h_{i}=h_{i-1}+1$)}\\\\[2.84526pt]
{\mathcal{B}}(h_{i-1})&\textrm{if step $i$ is a fall (i.e.\
$h_{i}=h_{i-1}-1$)}\\\\[2.84526pt] {\mathcal{C}}(h_{i-1})&\textrm{if step $i$
is a level step (i.e.\ $h_{i}=h_{i-1}$)}\end{cases}$ (5.5)

where $h_{i-1}$ (resp. $h_{i}$) is the height of the Motzkin path before
(resp. after) step $i$. [For typographical clarity we have here written
${\mathcal{A}}(h)$ as a synonym for ${\mathcal{A}}_{h}$, etc.] We call
$\xi_{i}$ the label associated to step $i$. We call the pair $(\omega,\xi)$ an
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}})$-labeled Dyck path if $\omega$ is a
Dyck path (in this case ${\bm{\mathcal{C}}}$ plays no role). We denote by
${\mathcal{M}}_{n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$
the set of
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled Motzkin
paths of length $n$, and by
${\mathcal{D}}_{2n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}})$ the set of
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}})$-labeled Dyck paths of length $2n$.

We define a
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled Schröder
path in an analogous way; now the sets ${\mathcal{C}}_{h}$ refer to long level
steps. We denote by
${\mathcal{S}}_{2n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$
the set of
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled Schröder
paths of length $2n$.

Let us stress that the sets ${\mathcal{A}}_{h}$, ${\mathcal{B}}_{h}$ and
${\mathcal{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.

Remark. What we have called an
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled Motzkin
path is (up to small changes in notation) called a path diagramme by Flajolet
[20, p. 136] and a history by Viennot [50, p. II-9]. Often the label sets
${\mathcal{A}}_{h},{\mathcal{B}}_{h},{\mathcal{C}}_{h}$ are intervals of
integers, e.g. ${\mathcal{A}}_{h}=\\{1,\ldots,A_{h}\\}$ or
$\\{0,\ldots,A_{h}\\}$; in this case the triplet $({\bf A},{\bf B},{\bf C})$
of sequences of maximum values is called a possibility function. On the other
hand, it is sometimes useful to employ labels that are pairs of integers (e.g.
[46, Section 6.2] and Section 7 below). It therefore seems preferable to state
the general theory without any specific assumption about the nature of the
label sets. $\blacksquare$

Following Flajolet [20, Proposition 7A], we can state a “master J-fraction”
for $({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled
Motzkin paths. Let ${\bf a}=(a_{h,\xi})_{h\geq 0,\;\xi\in{\mathcal{A}}(h)}$,
${\bf b}=(b_{h,\xi})_{h\geq 1,\;\xi\in{\mathcal{B}}(h)}$ and ${\bf
c}=(c_{h,\xi})_{h\geq 0,\;\xi\in{\mathcal{C}}(h)}$ be indeterminates; we give
an $({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled
Motzkin path $(\omega,\xi)$ a weight $W(\omega,\xi)$ that is the product of
the weights for the individual steps, where a rise starting at height $h$ with
label $\xi$ gets weight $a_{h,\xi}$, a fall starting at height $h$ with label
$\xi$ gets weight $b_{h,\xi}$, and a level step at height $h$ with label $\xi$
gets weight $c_{h,\xi}$. Then:

######  Theorem 5.2 (Flajolet’s master theorem for labeled Motzkin paths).

We have

$\sum_{n=0}^{\infty}t^{n}\\!\\!\sum_{(\omega,\xi)\in{\mathcal{M}}_{n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})}\\!\\!\\!W(\omega,\xi)\;=\;\cfrac{1}{1-c_{0}t-\cfrac{a_{0}b_{1}t^{2}}{1-c_{1}t-\cfrac{a_{1}b_{2}t^{2}}{1-c_{2}t-\cfrac{a_{2}b_{3}t^{2}}{1-\cdots}}}}$
(5.6)

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

$a_{h}\;=\;\sum_{\xi\in{\mathcal{A}}(h)}a_{h,\xi}\;,\qquad
b_{h}\;=\;\sum_{\xi\in{\mathcal{B}}(h)}b_{h,\xi}\;,\qquad
c_{h}\;=\;\sum_{\xi\in{\mathcal{C}}(h)}c_{h,\xi}\;.$ (5.7)

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

By specializing to ${\bf c}={\bm{0}}$ and replacing $t^{2}$ by $t$, we obtain
the corresponding theorem for
$({\bm{\mathcal{A}}},{\bm{\mathcal{B}}})$-labeled Dyck paths:

######  Corollary 5.3 (Flajolet’s master theorem for labeled Dyck paths).

We have

$\sum_{n=0}^{\infty}t^{n}\\!\\!\sum_{(\omega,\xi)\in{\mathcal{D}}_{2n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}})}\\!\\!\\!W(\omega,\xi)\;=\;\cfrac{1}{1-\cfrac{a_{0}b_{1}t}{1-\cfrac{a_{1}b_{2}t}{1-\cfrac{a_{2}b_{3}t}{1-\cdots}}}}$
(5.8)

as an identity in ${\mathbb{Z}}[{\bf a},{\bf b}][[t]]$, where $a_{h}$ and
$b_{h}$ are defined by (5.7).

Similarly, for labeled Schröder paths we have:

######  Theorem 5.4 (Flajolet’s master theorem for labeled Schröder paths).

We have

$\sum_{n=0}^{\infty}t^{n}\\!\\!\sum_{(\omega,\xi)\in{\mathcal{S}}_{2n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})}\\!\\!\\!W(\omega,\xi)\;=\;\cfrac{1}{1-c_{0}t-\cfrac{a_{0}b_{1}t}{1-c_{1}t-\cfrac{a_{1}b_{2}t}{1-c_{2}t-\cfrac{a_{2}b_{3}t}{1-\cdots}}}}$
(5.9)

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

##  6 First T-fraction: Proof of Theorems 3.3, 3.9, 3.11, 3.12 and 3.13

In this section we prove the first master T-fraction (Theorem 3.11) by a
bijection from D-permutations to labeled Schröder paths. Our construction
combines ideas of Randrianarivony [40] with a variant [46, Section 6.1] of
Foata–Zeilberger [23], together with some new ingredients. After proving
Theorem 3.11, we deduce Theorems 3.3 and 3.9 by specialization. Then, in
Section 6.5, we prove the variant T-fractions of Theorems 3.12 and 3.13.

Let us define an almost-Dyck path of length $2n$ to be a path
$\omega=(\omega_{0},\ldots,\omega_{2n})$ in the right half-plane
${\mathbb{N}}\times{\mathbb{Z}}$, starting at $\omega_{0}=(0,0)$ and ending at
$\omega_{2n}=(2n,0)$, using the steps $(1,1)$ and $(1,-1)$, that stays always
at height $\geq-1$. Thus, an almost-Dyck path is like a Dyck path except that
a down step from height 0 to height $-1$ is allowed; note, however, that it
must be immediately followed by an up step back to height 0. Each non-Dyck
part of the path is therefore of the form
$(h_{2i-2},h_{2i-1},h_{2i})=(0,-1,0)$. We write ${\mathcal{D}}^{\sharp}_{2n}$
for the set of almost-Dyck paths of length $2n$.

Next let us define a 0-Schröder path to be a Schröder path in which long level
steps, if any, occur only at height 0. We write ${\mathcal{S}}^{0}_{2n}$ for
the set of 0-Schröder paths of length $2n$. There is an obvious bijection
$\psi\colon{\mathcal{D}}^{\sharp}_{2n}\to{\mathcal{S}}^{0}_{2n}$ from almost-
Dyck paths to 0-Schröder paths: namely, we replace each down-up pair starting
and ending at height 0 with a long level step at height 0.

In this section we will construct a bijection from D-permutations of $[2n]$
onto labeled 0-Schröder paths of length $2n$, as follows: We first define the
path by constructing an almost-Dyck path $\omega$ and then transforming it
into a 0-Schröder path ${\widehat{\omega}}=\psi(\omega)$. Then we define the
labels $\xi_{i}$, which will lie in the sets

${\mathcal{A}}_{h}&=\\{0,\ldots,\lceil h/2\rceil\\}\qquad\quad\;\;\hbox{for
$h\geq 0$}\\\
{\mathcal{B}}_{h}=\\{0,\ldots,\lceil(h-1)/2\rceil\\}\quad\hbox{for $h\geq
1$}\\\ {\mathcal{C}}_{0}=\\{0\\}\\\
{\mathcal{C}}_{h}=\varnothing\qquad\qquad\qquad\qquad\quad\hbox{for $h\geq
1$}$ (6.1)

We also interpret our crossing, nesting and record statistics in terms of the
heights and labels. Next we prove that the map
$\sigma\mapsto({\widehat{\omega}},\xi)$ really is a bijection from the set
${\mathfrak{D}}_{2n}$ of D-permutations of $[2n]$ onto the set
${\mathcal{S}}_{2n}({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$
of $({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})$-labeled
Schröder paths of length $2n$. Finally, we sum over the labels $\xi$ to obtain
the weight $W({\widehat{\omega}})$ associated to a Schröder path
${\widehat{\omega}}$, which upon applying (5.4) will yield Theorem 3.11.

###  6.1 Step 1: Definition of the almost-Dyck path

Given a D-permutation $\sigma\in{\mathfrak{D}}_{2n}$, we define a path
$\omega=(\omega_{0},\ldots,\omega_{2n})$ starting at $\omega_{0}=(0,0)$, with
steps $s_{1},\ldots,s_{2n}$ as follows:

  * •

If $\sigma^{-1}(i)$ is even, then $s_{i}$ is a rise. (Note that in this case
we must have $\sigma^{-1}(i)\geq i$, by definition of D-permutation.)

  * •

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

(See Figure 4 for an example.) An alternative way of saying this is:

  * •

If $\sigma^{-1}(i)>i$, then $s_{i}$ is a rise. (In this case $\sigma^{-1}(i)$
must be even.)

  * •

If $\sigma^{-1}(i)<i$, then $s_{i}$ is a fall. (In this case $\sigma^{-1}(i)$
must be odd.)

  * •

If $i$ is a fixed point, then $s_{i}$ is a rise if $i$ is even, and a fall if
$i$ is odd.

Yet another alternative way of saying this is:

  * •

If $i$ is a cycle valley, cycle double fall or even fixed point, then $s_{i}$
is a rise.

  * •

If $i$ is a cycle peak, cycle double rise or odd fixed point, then $s_{i}$ is
a fall.

Of course we need to prove that this $\omega$ is indeed an almost-Dyck path,
i.e. that all the heights $h_{i}$ are $\geq-1$ and that $h_{2n}=0$. We will do
this by obtaining a precise interpretation of the heights $h_{i}$.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$0$$1$$2$$3$$4$ Figure 4: