Almost-Dyck path $\omega$ corresponding to the 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)$.
This is the same D-permutation that was illustrated in Figure 1.
$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$1^{\prime}$$2^{\prime}$$3^{\prime}$$4^{\prime}$$5^{\prime}$$6^{\prime}$$7^{\prime}$$8^{\prime}$$9^{\prime}$$10^{\prime}$$11^{\prime}$$12^{\prime}$$13^{\prime}$$14^{\prime}$
Figure 5:  Bipartite digraph representing the 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)$.
Arrows run from the top row to the bottom row and are suppressed for clarity.

In what follows, it will be convenient to represent a permutation
$\sigma\in{\mathfrak{S}}_{N}$ by a bipartite digraph $\Gamma=\Gamma(\sigma)$
in which the top row of vertices is labeled $1,\ldots,N$ and the bottom row
$1^{\prime},\ldots,N^{\prime}$, and we draw an arrow from $i$ to $j^{\prime}$
in case $\sigma(i)=j$ (see Figure 5). For $k\in[N]$, we denote by $\Gamma_{k}$
the induced subgraph of $\Gamma$ on the vertex set
$\\{1,\ldots,k\\}\cup\\{1^{\prime},\ldots,k^{\prime}\\}$. Thus, the edges of
$\Gamma_{k}$ are arrows $i\to j^{\prime}$ drawn whenever $\sigma(i)=j$ and
$i\leq k$ and $j\leq k$. We say that a vertex of $\Gamma_{k}$ is free if no
arrow is incident on it. We write

$f_{k}&\stackrel{{\scriptstyle\rm def}}{{=}}\hbox{\\# of free vertices in the
top row of $\Gamma_{k}$}\\\ =\\#\\{i\leq k\colon\>\sigma(i)>k\\}\;.$ (6.2)

Of course, we also have

$f_{k}&=\hbox{\\# of free vertices in the bottom row of $\Gamma_{k}$}\\\
=\\#\\{j\leq k\colon\>\sigma^{-1}(j)>k\\}\;.$ (6.3)

The total number of free vertices in $\Gamma_{k}$ is therefore $2f_{k}$. Note
that $f_{k}=0$ if and only if $\sigma$ maps $\\{1,\ldots,k\\}$ onto itself.
Note also that

$f_{k}-f_{k-1}\;=\;\begin{cases}+1&\textrm{if $k$ is a cycle valley}\\\
-1&\textrm{if $k$ is a cycle peak}\\\ 0&\textrm{if $k$ is a cycle double rise,
cycle double fall, or fixed point}\end{cases}$ (6.4)

Remark. The sequence $(f_{0},\ldots,f_{2n})$ is a Motzkin path; in fact, it is
precisely the Motzkin path associated to the permutation $\sigma$ by the
Foata–Zeilberger (or Biane) bijection. To see this, compare (6.2)/(6.3) with
[46, eq. (6.4)]; or equivalently, compare (6.4) with [46, definition of steps
$s_{i}$ preceding (6.2)]. $\blacksquare$

We can now give the promised interpretation of the heights:

######  Lemma 6.1 (Interpretation of the heights).

For $k\in[2n]$ we have

$h_{k}\;=\;\begin{cases}2f_{k}-1&\textrm{if $k$ is odd}\\\ 2f_{k}&\textrm{if
$k$ is even}\end{cases}$ (6.5)

In particular, $h_{k}\geq-1$ and $h_{2n}=0$, so that $\omega$ is an almost-
Dyck path.

Furthermore, we have $(h_{2i-2},h_{2i-1},h_{2i})=(0,-1,0)$ if and only if
$2i-1$ and $2i$ are record-antirecords.

Please note that, by (6.5), the parity of $h_{k}$ equals the parity of $k$;
this reflects the fact that $\omega$ is an almost-Dyck path. Note also that
(6.5) can be rewritten as

$f_{k}\;=\;\left\lceil\dfrac{h_{k}}{2}\right\rceil\;=\;\begin{cases}(h_{k}+1)/2&\textrm{if
$k$ is odd}\\\\[2.84526pt] h_{k}/2&\textrm{if $k$ is even}\end{cases}$ (6.6)

And recall, finally, from Lemma 3.2 that record-antirecords come in pairs:
$2i-1$ is a record-antirecord if and only if $2i$ is a record-antirecord.

Proof of Lemma 6.1.  We have

$h_{k}&=\\#\\{j\leq k\colon\>\sigma^{-1}(j)\text{ is even}\\}\>-\>\\#\\{j\leq
k\colon\>\sigma^{-1}(j)\text{ is odd}\\}\\\ =2\,\\#\\{j\leq
k\colon\>\sigma^{-1}(j)\text{ is even}\\}\>-\>k\\\ =2\,\bigl{[}\\#\\{j\leq
k\colon\>\sigma^{-1}(j)>k\\}\>+\>\\#\\{j\leq
k\colon\>k\geq\sigma^{-1}(j)>j\\}\\\ \qquad+\>\\#\\{j\leq
k\colon\>\sigma^{-1}(j)=j\text{ is even}\\}\bigr{]}\;-\;k\\\
=2\,\bigl{[}\\#\\{j\leq k:\sigma^{-1}(j)>k\\}\>+\>\\#\\{i\leq
k\colon\>i>\sigma(i)\\}\\\ \qquad+\>\\#\\{i\leq k\colon\>\sigma(i)=i\text{ is
even}\\}\bigr{]}\;-\;k\\\ =2\,\bigl{[}\\#\\{j\leq
k\colon\>\sigma^{-1}(j)>k\\}\>+\>\\#\\{i\leq k\colon\>i\text{ is
even}\\}\bigr{]}\;-\;k\\\
=2f_{k}\>+\>2\left\lceil\frac{k-1}{2}\right\rceil\>-\>k\;,$ (6.7)

which is (6.5).

Furthermore, $h_{k}=-1$ occurs when and only when $k$ is odd (say, $k=2i-1$)
and $f_{k}=0$. The latter statement means that $\sigma$ maps
$\\{1,\ldots,2i-1\\}$ onto itself. By Lemma 3.2(c)$\implies$(a,b) this means
that $2i-1$ and $2i$ are record-antirecords. Conversely, if $2i-1$ is a
record-antirecord, then by Lemma 3.2(a)$\implies$(d) we have
$f_{2i-2}=f_{2i-1}=f_{2i}=0$, so that $(h_{2i-2},h_{2i-1},h_{2i})=(0,-1,0)$.
$\square$

Remarks. 1\. Randrianarivony [40, Section 6] considered the special case of
this construction in which $\sigma$ is a D-o-semiderangement (in his
terminology, a “Genocchi permutation”); in this case $\omega$ is a Dyck path.
Our proof of Lemma 6.1 is a very slight modification of his, designed to allow
for fixed points of both parities. See also Han and Zeng [27, pp. 126–127] for
the interpretation in terms of bipartite graphs and free vertices.

2\. The number of almost-Dyck paths of length $2n$ is $C_{n+1}$, where
$C_{n}=\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number: it suffices to
observe that an almost-Dyck path of semilength $n$ can be converted to a Dyck
path of semilength $n+1$ by adding a rise at the beginning and a fall at the
end, and conversely. Equivalently, the number of 0-Schröder paths of length
$2n$ is $C_{n+1}$: this follows from (5.4) with $\delta_{1}=1$, $\delta_{n}=0$
for $n\geq 2$, and $\alpha_{n}=1$ for $n\geq 1$ together with the identity

${1\over 1-t-tC(t)}\;=\;{C(t)-1\over t}$ (6.8)

for the Catalan generating function
$C(t)=\sum\limits_{n=0}^{\infty}C_{n}\,t^{n}=(1-\sqrt{1-4t})/(2t)$.
$\blacksquare$

###  6.2 Step 2: Definition of the labels $\bm{\xi_{i}}$

We now define

$\xi_{i}\;=\;\begin{cases}\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq
i<j\\}&\textrm{if $i$ is even}\\\\[5.69054pt]
\\#\\{j\colon\>j<i\leq\sigma(i)<\sigma(j)\\}&\textrm{if $i$ is
odd}\end{cases}$ (6.9)

Note that the middle inequalities in this definition hold automatically: a
D-permutation always has $\sigma(i)\leq i$ if $i$ is even, and
$i\leq\sigma(i)$ if $i$ is odd. The definition (6.9) can be written
equivalently as

$\xi_{i}\;=\;\begin{cases}\\#\\{2l>2k\colon\>\sigma(2l)<\sigma(2k)\\}&\textrm{if
$i=2k$}\\\\[5.69054pt]
\\#\\{2l-1<2k-1\colon\>\sigma(2l-1)>\sigma(2k-1)\\}&\textrm{if
$i=2k-1$}\end{cases}$ (6.10)

since $\sigma(j)<j$ implies that $j$ is even, and $j<\sigma(j)$ implies that
$j$ is odd.

It is worth remarking that the labels $\xi_{i}$ defined in (6.9) are the same
as those in the variant Foata–Zeilberger bijection [46, eq. (6.5)] whenever
$i$ is not a fixed point.121212 With the only difference that in [46] the
labels were defined to start at 1, whereas here they start at 0.

The label $\xi_{i}$ has a simple interpretation in terms of the index-refined
nesting statistics defined in (2.50)/(2.51):

$\sigma(j)$$\sigma(i)$$i$$j$When $i$ is even and $\neq\sigma(i)$

$j$$i$$\sigma(i)$$\sigma(j)$When $i$ is odd and $\neq\sigma(i)$

Figure 6:  Nestings involved in the definition of the label $\xi_{i}$.

######  Lemma 6.2 (Nesting statistics).

We have

$\xi_{i}\;=\;\begin{cases}{\rm lnest}(i,\sigma)&\hbox{\rm if $i$ is even and
$\neq\sigma(i)$}\;\,\hbox{\rm[equivalently, $i>\sigma(i)$]}\\\\[1.42262pt]
{\rm unest}(i,\sigma)&\hbox{\rm if $i$ is odd and
$\neq\sigma(i)$}\;\,\hbox{\rm[equivalently, $i<\sigma(i)$]}\\\\[1.42262pt]
{\rm psnest}(i,\sigma)&\hbox{\rm if $i=\sigma(i)$ (that is, $i$ is a fixed
point)}\end{cases}$ (6.11)

See Figure 6. Note also that if $i$ is a fixed point, we have

$\xi_{i}\;=\;f_{i}\;=\;\left\lceil\dfrac{h_{i}}{2}\right\rceil\;=\;\begin{cases}h_{i}/2&\textrm{if
$i$ is even}\\\\[2.84526pt] (h_{i}+1)/2&\textrm{if $i$ is odd}\end{cases}$
(6.12)

Now we shall show, as required by (6.1), that the following inequalities hold
true:

######  Lemma 6.3 (Inequalities satisfied by the labels).

We have

$&0\;\leq\;\xi_{i}\;\leq\;\left\lceil\dfrac{h_{i}-1}{2}\right\rceil\;=\;\left\lceil\dfrac{h_{i-1}}{2}\right\rceil\textrm{if
$\sigma^{-1}(i)$ is even (i.e., $s_{i}$ is a rise)}\qquad{}\\\
0\;\leq\;\xi_{i}\;\leq\;\left\lceil\dfrac{h_{i}}{2}\right\rceil\;=\;\left\lceil\dfrac{h_{i-1}-1}{2}\right\rceil\textrm{if
$\sigma^{-1}(i)$ is odd (i.e., $s_{i}$ is a fall)}{}$ (6.13)

We remark that a fall starting at height $h_{i-1}=0$, or a rise starting at
height $h_{i-1}=-1$, always gets the label $\xi_{i}=0$. When we pass from the
almost-Dyck path $\omega$ to the 0-Schröder path
${\widehat{\omega}}=\psi(\omega)$, these labels become the label $\xi=0$ for
the long level step at height 0.

To prove the inequalities (6.13), we will interpret
$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}$ when $s_{i}$ is a rise,
and $\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}$ when $s_{i}$ is a fall,
in terms of crossing statistics, as follows:

######  Lemma 6.4 (Crossing statistics).

  * (a)

If $s_{i}$ a rise and $i$ (hence also $h_{i}$) is odd, then

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}\;=\;{\rm
ucross}(i,\sigma)\;.$ (6.14)

  * (b)

If $s_{i}$ a rise and $i$ (hence also $h_{i}$) is even, then

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}&={\rm
lcross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\\\ ={\rm
lcross}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle double fall}]\;.$ (6.15)

  * (c)

If $s_{i}$ a fall and $i$ (hence also $h_{i}$) is odd, then

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}&={\rm
ucross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\\\ ={\rm
ucross}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle double rise}]\;.$ (6.16)

  * (d)

If $s_{i}$ a fall and $i$ (hence also $h_{i}$) is even, then

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}\;=\;{\rm
lcross}(i,\sigma)\;.$ (6.17)

(Here ${\rm I}[\hbox{\sl proposition}]=1$ if proposition is true, and 0 if it
is false.)

Since the right-hand sides of (6.14)–(6.17) are manifestly nonnegative, Lemma
6.3 is an immediate consequence of Lemma 6.4.

$\sigma(i)$$\sigma(j)$$i$$j$(b,d) When $i$ is even and $\neq\sigma(i)$

$j$$i$$\sigma(j)$$\sigma(i)$(a,c) When $i$ is odd and $\neq\sigma(i)$

Figure 7:  Crossings involved in the identities for the label $\xi_{i}$.

Proof of Lemma 6.4.  (a,b) If $s_{i}$ is a rise, then $\sigma^{-1}(i)$ is even
and $i\leq\sigma^{-1}(i)$. We now consider separately the cases of $i$ odd and
$i$ even.

(a) If $i$ is odd, then $h_{i}$ is odd; moreover, since $\sigma^{-1}(i)$ is
even, $i$ cannot be a fixed point, and we have the strict inequalities
$i<\sigma^{-1}(i)$ and $i<\sigma(i)$. Then

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}&=\dfrac{h_{i}-1}{2}\,-\,\xi_{i}\\\
=f_{i}\,-\,1\,-\,\xi_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma(j)>i\\}\,-\,1\,-\,\\#\\{j\colon\>j<i\leq\sigma(i)<\sigma(j)\\}\qquad\qquad\\\
=\\#\\{j<i\colon\>\sigma(j)>i\\}\,-\,\\#\\{j\colon\>j<i<\sigma(i)<\sigma(j)\\}\qquad\qquad\\\
=\\#\\{j\colon\>j<i<\sigma(j)<\sigma(i)\\}\qquad\qquad\\\ ={\rm
ucross}(i,\sigma)\;.$ (6.18)

See Figure 7(a,c).

(b) If $i$ is even, then $h_{i}$ is even, and $\sigma(i)\leq i$. So either $i$
is a fixed point (hence $\sigma(i)=i=\sigma^{-1}(i)$) or else
$\sigma(i)<i<\sigma^{-1}(i)$. Then

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}&=\dfrac{h_{i}}{2}\,-\,\xi_{i}\\\
=f_{i}\,-\,\xi_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma^{-1}(j)>i\\}\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq
i<j\\}\qquad\qquad\\\ =\\#\\{j<i\colon\>\sigma^{-1}(j)>i\\}\,+\,{\rm
I}[\sigma^{-1}(i)>i]\\\ \hskip
113.81102pt\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq i<j\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma(j)<i<j\\}\,+\,{\rm I}[\sigma(i)\neq i]\\\ \hskip
105.2751pt\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq i<j\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma(i)<\sigma(j)<i<j\\}\,+\,{\rm I}[\sigma(i)\neq
i]\qquad\qquad\\\ ={\rm lcross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;.$
(6.19)

See Figure 7(b,d). Note that the identity (6.19) holds also when $h_{i}=0$,
i.e. when the step $s_{i}$ is a rise from height $h_{i-1}=-1$: in this case
$i$ is a record-antirecord fixed point and we have $f_{i}=\xi_{i}=0$, so that
both sides of (6.19) are zero.

(c,d) If $s_{i}$ is a fall, then $\sigma^{-1}(i)$ is odd and
$\sigma^{-1}(i)\leq i$. We again consider separately the cases of $i$ odd and
$i$ even.

(c) If $i$ is odd, then $h_{i}$ is odd, and $i\leq\sigma(i)$. So either $i$ is
a fixed point (hence $\sigma^{-1}(i)=i=\sigma(i)$) or else
$\sigma^{-1}(i)<i<\sigma(i)$. Then

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}&=\dfrac{h_{i}+1}{2}\,-\,\xi_{i}\\\
=f_{i}\,-\,\xi_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma(j)>i\\}\,-\,\\#\\{j\colon\>j<i\leq\sigma(i)<\sigma(j)\\}\qquad\qquad\\\
=\\#\\{j<i\colon\>\sigma(j)>i\\}\,+\,{\rm I}[\sigma(i)\neq i]\\\ \hskip
102.43008pt\,-\,\\#\\{j\colon\>j<i<\sigma(i)<\sigma(j)\\}\qquad\qquad\\\
=\\#\\{j\colon\>j<i<\sigma(j)<\sigma(i)\\}\,+\,{\rm I}[\sigma(i)\neq i]\\\
={\rm ucross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;.$ (6.20)

See again Figure 7(a,c). Note that the identity (6.20) holds also when
$h_{i}=-1$, i.e. when the step $s_{i}$ is a fall from height $h_{i-1}=0$; in
this case $i$ is a record-antirecord fixed point and we have
$f_{i}=\xi_{i}=0$, so that both sides of (6.20) are zero.

(d) If $i$ is even, then $h_{i}$ is even; moreover, since $\sigma^{-1}(i)$ is
odd, $i$ cannot be a fixed point, and we have the strict inequalities
$\sigma^{-1}(i)<i$ and $\sigma(i)<i$. Then

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}&=\dfrac{h_{i}}{2}\,-\,\xi_{i}\\\
=f_{i}\,-\,\xi_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma^{-1}(j)>i\\}\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq
i<j\\}\qquad\qquad\\\
=\\#\\{j<i\colon\>\sigma^{-1}(j)>i\\}\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)<i<j\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma(j)<i<j\\}\,-\,\\#\\{j\colon\>\sigma(j)<\sigma(i)<i<j\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma(i)<\sigma(j)<i<j\\}\qquad\qquad\\\ ={\rm
lcross}(i,\sigma)\;.$ (6.21)

See again Figure 7(b,d). $\square$

We now consider the four possible combinations of $s_{i}$ (rise or fall) and
parity of $h_{i}$ (odd or even), and determine in each case the cycle
classification of the index $i$. By definition $s_{i}$ tells us the parity of
$\sigma^{-1}(i)$, while the parity of $h_{i}$ equals the parity of $i$. So
these two pieces of information tell us what was recorded in (2.47)/(2.48):

  * •

$\sigma^{-1}(i)$ even and $i$ odd $\iff$ $i$ is a cycle valley

  * •

$\sigma^{-1}(i)$ even and $i$ even $\iff$ $i$ is either a cycle double fall or
an even fixed point

  * •

$\sigma^{-1}(i)$ odd and $i$ odd $\iff$ $i$ is either a cycle double rise or
an odd fixed point

  * •

$\sigma^{-1}(i)$ odd and $i$ even $\iff$ $i$ is a cycle peak

So we need only disambiguate the fixed points from the cycle double
falls/rises in the middle two cases; we will see that in these cases $i$ is a
fixed point if and only if $\xi_{i}$ takes its maximum allowed value. More
precisely:

######  Lemma 6.5 (Cycle classification).

  * (a)

If $s_{i}$ a rise and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is a
cycle valley.

  * (b)

If $s_{i}$ a rise and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is an
even fixed point in case $\xi_{i}=\left\lceil\dfrac{h_{i}-1}{2}\right\rceil$
($=h_{i}/2=f_{i})$; otherwise it is a cycle double fall.

  * (c)

If $s_{i}$ is a fall and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is
an odd fixed point in case $\xi_{i}=\left\lceil\dfrac{h_{i}}{2}\right\rceil$
($=(h_{i}+1)/2=f_{i}$); otherwise it is a cycle double rise.

  * (d)

If $s_{i}$ is a fall and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is
a cycle peak.

Proof. (a,d) follow immediately from (2.47)/(2.48).

(b) If $s_{i}$ a rise and $h_{i}$ is even (hence $i$ is even), then by (6.15)
we have

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\xi_{i}\;=\;{\rm
lcross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;,$ (6.22)

so $i$ is a fixed point if and only if
$\xi_{i}=\left\lceil\dfrac{h_{i}-1}{2}\right\rceil$. Otherwise $i$ is a cycle
double fall.

(c) If $s_{i}$ is a fall and $h_{i}$ is odd (hence $i$ is odd), by (6.16) we
have

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\xi_{i}\;=\;{\rm
ucross}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;,$ (6.23)

so $i$ is a fixed point if and only if
$\xi_{i}=\left\lceil\dfrac{h_{i}}{2}\right\rceil$. Otherwise $i$ is a cycle
double rise. $\square$

Remark. We already saw in (6.12) that if $i$ is a fixed point, then $\xi_{i}$
takes the value specified in (b) or (c), which is also the maximum allowed
value according to (6.13). Now we see the converse. $\blacksquare$

At the other extreme, it is easy to see that the index $i$ is a record or
antirecord if and only if $\xi_{i}$ takes its minimum allowed value (namely,
zero):

######  Lemma 6.6 (Record statistics).

  * (a)

If $i$ is odd, then the index $i$ is a record if and only if $\xi_{i}=0$.

  * (b)

If $i$ is odd, then the index $i$ is an antirecord if and only if $h_{i}=-1$
and $\xi_{i}=0$, in which case $i$ is a record-antirecord fixed point.

  * (c)

If $i$ is even, then the index $i$ is an antirecord if and only if
$\xi_{i}=0$.

  * (d)

If $i$ is even, then the index $i$ is a record if and only if $h_{i}=0$ and
$\xi_{i}=0$, in which case $i$ is a record-antirecord fixed point.

Proof. (a,c) This is an immediate consequence of the definition (6.9).

(b) Every antirecord is a weak anti-excedance, so an odd index in a
D-permutation can be an antirecord only if it is a fixed point, in which case
it is a record-antirecord fixed point. This happens if and only if $h_{i}=-1$
and $\xi_{i}=0$.

(d) Similar to (b), using the fact that every record is a weak excedance.
$\square$

###  6.3 Step 3: Proof of bijection

We prove that the map $\sigma\mapsto(\omega,\xi)$ is a bijection by explicitly
describing the inverse map. That is, we let $\omega$ be any almost-Dyck path
of length $2n$ and let $\xi$ be any set of labels satisfying the inequalities
(6.13), and we show how to reconstruct the unique D-permutation $\sigma$ that
gives rise to $(\omega,\xi)$ by the foregoing construction.

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

$F&=\\{2,4,\ldots,2n\\}\;=\;\hbox{even positions}\\\
F^{\prime}=\\{i\colon\sigma^{-1}(i)\text{ is
even}\\}\;=\;\\{\sigma(2),\sigma(4),\ldots,\sigma(2n)\\}\\\
G=\\{1,3,\ldots,2n-1\\}\;=\;\hbox{odd positions}\\\
G^{\prime}=\\{i\colon\sigma^{-1}(i)\text{ is
odd}\\}\;=\;\\{\sigma(1),\sigma(3),\ldots,\sigma(2n-1)\\}$ (6.24)

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

Let us observe that

$F\cap F^{\prime}&=\hbox{cycle double falls and even fixed points}\\\ G\cap
G^{\prime}=\hbox{cycle double rises and odd fixed points}\\\ F\cap
G^{\prime}=\hbox{cycle peaks}\\\ F^{\prime}\cap G=\hbox{cycle valleys}\\\
F\cap G=\varnothing\\\ F^{\prime}\cap G^{\prime}=\varnothing$ (6.25)

Let us also recall the notion of an inversion table: Let $S$ be a totally
ordered set of cardinality $k$, and let $\bm{x}=(x_{1},\ldots,x_{k})$ be a
permutation of $S$ (i.e., a word in which each element of $S$ occurs exactly
once); then the (left-to-right) inversion table corresponding to $\bm{x}$ is
the sequence $\bm{p}=(p_{1},\ldots,p_{k})$ of nonnegative integers defined by
$p_{\alpha}=\\#\\{\beta<\alpha\colon\>x_{\beta}>x_{\alpha}\\}$. Note that
$0\leq p_{\alpha}\leq\alpha-1$ for all $\alpha\in[k]$, so there are exactly
$k!$ possible inversion tables. Given the inversion table $\bm{p}$, we can
reconstruct the sequence $\bm{x}$ by working from right to left, as follows:
There are $p_{k}$ elements of $S$ larger than $x_{k}$, so $x_{k}$ must be the
$(p_{k}+1)$th largest element of $S$. Then there are $p_{k-1}$ elements of
$S\setminus\\{x_{k}\\}$ larger than $x_{k-1}$, so $x_{k-1}$ must be the
$(p_{k-1}+1)$th largest element of $S\setminus\\{x_{k}\\}$. And so forth.
[Analogously, the right-to-left inversion table corresponding to $\bm{x}$ is
the sequence $\bm{q}=(q_{1},\ldots,q_{k})$ of nonnegative integers defined by
$q_{\alpha}=\\#\\{\beta>\alpha\colon\>x_{\beta}<x_{\alpha}\\}$.]

With these preliminaries out of the way, we can now describe the map
$(\omega,\xi)\mapsto\sigma$. Given the almost-Dyck path $\omega$, we can
immediately reconstruct the sets $F,F^{\prime},G,G^{\prime}$. We now use the
labels $\xi$ to reconstruct the maps $\sigma\upharpoonright F\colon\>F\to
F^{\prime}$ and $\sigma\upharpoonright G\colon\>G\to G^{\prime}$ as follows:
The even subword $\sigma(2)\sigma(4)\cdots\sigma(2n)$ is a listing of
$F^{\prime}$ whose right-to-left inversion table is given by
$q_{\alpha}=\xi_{2\alpha}$; this is the content of (6.10a). Similarly, the odd
subword $\sigma(1)\sigma(3)\cdots\sigma(2n-1)$ is a listing of $G^{\prime}$
whose left-to-right inversion table is given by $p_{\alpha}=\xi_{2\alpha-1}$;
this is the content of (6.10b). See Figure 8 for an example.

$\begin{array}[]{r}F=\\{2i\;|\;1\leq i\leq 7\\}\\\\[8.53581pt]
F^{\prime}=\\{\sigma(2i)\;|\;1\leq i\leq 7\\}\\\\[8.53581pt] \text{Right-to-
left inversion table:}\;\xi_{2i}\\\
\end{array}\;\begin{pmatrix}\;2&4&6&8&10&12&14\;\\\\[8.53581pt]
\;1&2&4&6&3&12&13\;\\\\[8.53581pt] \;0&0&1&1&0&0&0\;\end{pmatrix}$

$\begin{array}[]{r}G=\\{2i-1\;|\;1\leq i\leq 7\\}\\\\[8.53581pt]
G^{\prime}=\\{\sigma(2i-1)\;|\;1\leq i\leq 7\\}\\\\[8.53581pt] \text{Left-to-
right inversion table:}\;\xi_{2i-1}\\\
\end{array}\;\begin{pmatrix}\;1&3&5&7&9&11&13\;\\\\[8.53581pt]
\;7&9&5&8&10&11&14\;\\\\[8.53581pt] \;0&0&2&1&0&0&0\;\end{pmatrix}$

$2i$ | $\xi_{2i}$ | $F^{\prime}\backslash\\{\sigma(2),\ldots,\sigma(2i-2)\\}$ | $\sigma(2i)$
---|---|---|---
$2$ | $0$ | $\\{\underline{1},2,3,4,6,12,13\\}$ | $1$
$4$ | $0$ | $\\{\underline{2},3,4,6,12,13\\}$ | $2$
$6$ | $1$ | $\\{3,\underline{4},6,12,13\\}$ | $4$
$8$ | $1$ | $\\{3,\underline{6},12,13\\}$ | $6$
$10$ | $0$ | $\\{\underline{3},12,13\\}$ | $3$
$12$ | $0$ | $\\{\underline{12},13\\}$ | $12$
$14$ | $0$ | $\\{\underline{13}\\}$ | $13$

$2i-1$ | $\xi_{2i-1}$ | $G^{\prime}\backslash\\{\sigma(13),\ldots,\sigma(2i+1)\\}$ | $\sigma(2i-1)$
---|---|---|---
$13$ | $0$ | $\\{5,7,8,9,10,11,\underline{14}\\}$ | $14$
$11$ | $0$ | $\\{5,7,8,9,10,\underline{11}\\}$ | $11$
$9$ | $0$ | $\\{5,7,8,9,\underline{10}\\}$ | $10$
$7$ | $1$ | $\\{5,7,\underline{8},9\\}$ | $8$
$5$ | $2$ | $\\{\underline{5},7,9\\}$ | $5$
$3$ | $0$ | $\\{7,\underline{9}\\}$ | $9$
$1$ | $0$ | $\\{\underline{7}\\}$ | $7$

Figure 8:  Reconstruction of the 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)$
from its almost-Dyck path $\omega$ and labels $\xi$. The value $\sigma(2i)$ is
chosen so that it has $\xi_{2i}$ entries to its left in the remaining subset
of $F^{\prime}$ in increasing order; the value $\sigma(2i-1)$ is chosen so
that it has $\xi_{2i-1}$ entries to its right in the remaining subset of
$G^{\prime}$ in increasing order.

The only thing that remains to be shown is that the $\sigma$ thus constructed
is indeed a D-permutation. For this, we need to show that the following
inequalities hold:

$\sigma(2k)&\leq 2k\\\ \sigma(2k-1)\geq 2k-1$ (6.26)

Let us do a double counting of the number of rises occuring after the step
$s_{2k}$. As $2n-2k$ is the total number of steps after $2k$, the number of
rises after $s_{2k}$ is $(n-k)-h_{2k}/2$. Thus, we have that

$(n-k)\,-\,\frac{h_{2k}}{2}&=\\#\\{i>2k\colon\,\sigma^{-1}(i)\hbox{ is
even}\\}\\\ \geq\\#\\{i>2k\colon\,\sigma^{-1}(i)>2k\text{ and
}\sigma^{-1}(i)\hbox{ is even}\\}\\\ =\\#\\{2l>2k\colon\,\sigma(2l)>2k\\}\\\
=(n-k)\,-\,\\#\\{2l>2k\colon\,\sigma(2l)\leq 2k\\}$ (6.27)

and hence,

$\frac{h_{2k}}{2}\;\>\leq\;\>\\#\\{2l>2k\colon\,\sigma(2l)\leq 2k\\}\;.$
(6.28)

If $k$ is such that $\sigma(2k)>2k$, then (6.28) becomes strict [because
$i=\sigma(2k)$ contributes to (6.27a) but not to (6.27b)]. Furthermore, if
$\sigma(2k)>2k$, we also have

$\\#\\{2l>2k\colon\,\sigma(2l)\leq
2k\\}\;\>\leq\;\>\\#\\{2l>2k\colon\,\sigma(2l)<\sigma(2k)\\}\;\>=\;\>\xi_{2k}$
(6.29)

by (6.10). In this situation, equations (6.28) and (6.29) together give

$\xi_{2k}\;>\;\frac{h_{2k}}{2}\;=\;\left\lceil\frac{h_{2k}}{2}\right\rceil\;=\;\left\lceil\frac{h_{2k}-1}{2}\right\rceil\;,$
(6.30)

where the equalities occur because $h_{2k}$ is even. This contradicts
(6.13a,b), and proves that $\sigma(2k)\leq 2k$.

The proof that $\sigma(2k-1)\geq 2k-1$ uses a similar double-counting argument
for the number of falls before $s_{2k-1}$. $\square$

###  6.4 Step 4: Computation of the weights

We can now compute the weights associated to the 0-Schröder path
${\widehat{\omega}}$ in Theorem 5.4, which we recall are $a_{h,\xi}$ for a
rise starting at height $h$ with label $\xi$, $b_{h,\xi}$ for a fall starting
at height $h$ with label $\xi$, and $c_{h,\xi}$ for a long level step at
height $h$ with label $\xi$. (Of course, in the present case we have long
level steps only at height 0.) We do this by putting together the information
collected in Lemmas 6.2–6.6:

  * (a)

Rise from height $h_{i-1}=2k$ to height $h_{i}=2k+1$ (hence $i$ odd):

    * –

By Lemma 6.3, the label satisfies $0\leq\xi_{i}\leq k$.

    * –

By Lemma 6.5(a), this is a cycle valley.

    * –

By Lemma 6.2, ${\rm unest}(i,\sigma)=\xi_{i}$.

    * –

By Lemma 6.4(a), ${\rm ucross}(i,\sigma)=k-\xi_{i}$.

Therefore, from (3.30), the weight for this step is

$a_{2k,\xi}\;=\;{{\sf a}}_{k-\xi,\xi}\;.$ (6.31)

  * (b)

Rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$ (hence $i$ even):

    * –

By Lemma 6.3, the label satisfies $0\leq\xi_{i}\leq k$.

    * –

By Lemma 6.5(b), this is a cycle double fall if $0\leq\xi_{i}<k$, and a fixed
point if $\xi_{i}=k$.

    * –

By Lemma 6.2, $\xi_{i}=\displaystyle\begin{cases}{\rm
lnest}(i,\sigma)&\textrm{if $i$ is not a fixed point}\\\ {\rm
psnest}(i,\sigma)&\textrm{if $i$ is a fixed point}\end{cases}$

    * –

By Lemma 6.4(b), ${\rm lcross}(i,\sigma)=k-1-\xi_{i}$ when $i$ is not a fixed
point.

Therefore, from (3.30), the weight for this step is

$a_{2k-1,\xi}\;=\;\begin{cases}{{\sf c}}_{k-1-\xi,\xi}&\textrm{if
$0\leq\xi<k$}\\\\[2.84526pt] {{\sf e}}_{k}&\textrm{if $\xi=k$}\end{cases}$
(6.32)

  * (c)

Fall from height $h_{i-1}=2k$ to height $h_{i}=2k-1$ (hence $i$ odd):

    * –

By Lemma 6.3, the label satisfies $0\leq\xi_{i}\leq k$.

    * –

By Lemma 6.5(c), this is a cycle double rise if $0\leq\xi_{i}<k$, and a fixed
point if $\xi_{i}=k$.

    * –

By Lemma 6.2, $\xi_{i}=\displaystyle\begin{cases}{\rm
unest}(i,\sigma)&\textrm{if $i$ is not a fixed point}\\\ {\rm
psnest}(i,\sigma)&\textrm{if $i$ is a fixed point}\end{cases}$

    * –

By Lemma 6.4(c), ${\rm ucross}(i,\sigma)=k-1-\xi_{i}$ when $i$ is not a fixed
point.

Therefore, from (3.30), the weight for this step is

$b_{2k,\xi}\;=\;\begin{cases}{{\sf d}}_{k-1-\xi,\xi}&\textrm{if
$0\leq\xi<k$}\\\\[2.84526pt] {{\sf f}}_{k}&\textrm{if $\xi=k$}\end{cases}$
(6.33)

  * (d)

Fall from height $h_{i-1}=2k+1$ to height $h_{i}=2k$ (hence $i$ even):

    * –

By Lemma 6.3, the label satisfies $0\leq\xi_{i}\leq k$.

    * –

By Lemma 6.5(d), this is a cycle peak.

    * –

By Lemma 6.2, ${\rm lnest}(i,\sigma)=\xi_{i}$.

    * –

By Lemma 6.4(d), ${\rm lcross}(i,\sigma)=k-\xi_{i}$.

Therefore, from (3.30), the weight for this step is

$b_{2k+1,\xi}\;=\;{{\sf b}}_{k-\xi,\xi}\;.$ (6.34)

  * (e)

Long level step at height $0$:
This corresponds in the almost-Dyck path $\omega$ to a fall from height $0$ to
height $-1$, followed by a rise from height $-1$ to height $0$. Applying case
(d) with $k=0$ and $\xi=0$, followed by case (b) with $k=0$ and $\xi=0$, we
obtain a weight

$c_{0,0}\;=\;{{\sf e}}_{0}{{\sf f}}_{0}\;.$ (6.35)

Putting this all together in Theorem 5.4, we obtain a T-fraction with

$\displaystyle\alpha_{2k-1}$ $\displaystyle=$ $\displaystyle(\hbox{rise from
$2k-2$ to $2k-1$})\,\times\,(\hbox{fall from $2k-1$ to $2k-2$})$ (6.36)
$\displaystyle=$ $\displaystyle\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{)}$ $\displaystyle\alpha_{2k}$ $\displaystyle=$
$\displaystyle(\hbox{rise from $2k-1$ to $2k$})\,\times\,(\hbox{fall from $2k$
to $2k-1$})$ (6.37) $\displaystyle=$ $\displaystyle\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{)}$
$\displaystyle\delta_{1}$ $\displaystyle=$ $\displaystyle{{\sf e}}_{0}{{\sf
f}}_{0}$ (6.38) $\displaystyle\delta_{n}$ $\displaystyle=$ $\displaystyle
0\qquad\hbox{for $n\geq 2$}$ (6.39)

This completes the proof of Theorem 3.11. $\square$

We can now deduce Theorem 3.9 as a corollary:

Proof of Theorem 3.9.  Comparing (3.21) with (3.30) and using Lemma 6.6, we
see that the needed weights in (3.30) are

$\displaystyle{{\sf a}}_{k-1-\xi,\xi}$ $\displaystyle=$ $\displaystyle
p_{+1}^{k-1-\xi}q_{+1}^{\xi}\,\times\,\begin{cases}y_{1}&\textrm{if
$\xi=0$}\\\ v_{1}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (6.40)
$\displaystyle{{\sf b}}_{k-1-\xi,\xi}$ $\displaystyle=$ $\displaystyle
p_{-1}^{k-1-\xi}q_{-1}^{\xi}\,\times\,\begin{cases}x_{1}&\textrm{if
$\xi=0$}\\\ u_{1}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (6.41)
$\displaystyle{{\sf c}}_{k-1-\xi,\xi}$ $\displaystyle=$ $\displaystyle
p_{-2}^{k-1-\xi}q_{-2}^{\xi}\,\times\,\begin{cases}x_{2}&\textrm{if
$\xi=0$}\\\ u_{2}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (6.42)
$\displaystyle{{\sf d}}_{k-1-\xi,\xi}$ $\displaystyle=$ $\displaystyle
p_{+2}^{k-1-\xi}q_{+2}^{\xi}\,\times\,\begin{cases}y_{2}&\textrm{if
$\xi=0$}\\\ v_{2}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (6.43)
$\displaystyle{{\sf e}}_{k}$ $\displaystyle=$
$\displaystyle\begin{cases}z_{\rm e}&\textrm{if $k=0$}\\\\[2.84526pt] s_{\rm
e}^{k}w_{\rm e}&\textrm{if $k\geq 1$}\end{cases}$ (6.44) $\displaystyle{{\sf
f}}_{k}$ $\displaystyle=$ $\displaystyle\begin{cases}z_{\rm o}&\textrm{if
$k=0$}\\\\[2.84526pt] s_{\rm o}^{k}w_{\rm o}&\textrm{if $k\geq 1$}\end{cases}$
(6.45)

Inserting these into (6.36)–(6.39) yields the continued-fraction coefficients
(3.24). $\square$

Proof of Theorem 3.3.  Specialize Theorem 3.9 to
$p_{-1}=p_{-2}=p_{+1}=p_{+2}=q_{-1}=q_{-2}=q_{+1}=q_{+2}=s_{\rm e}=s_{\rm
o}=1$. $\square$

###  6.5 An alternative label $\bm{\widehat{\xi}_{i}}$: Proof of Theorems 3.12
and 3.13

As mentioned earlier, Randrianarivony [40, Section 6] employed a very similar
construction in the special case where $\sigma$ is a D-o-semiderangement. Our
definition of the almost-Dyck path $\omega$ is essentially the same as his
Dyck path, modified slightly to allow for fixed points of both parities.
However, he used a very different definition of the labels, namely [40, eq.
(6.2)]

$\widehat{\xi}_{i}&=\begin{cases}\\#\\{2l>2k\colon\>\sigma(2l)<\sigma(2k)\\}&\textrm{if
$i=\sigma(2k)$}\\\\[5.69054pt]
\\#\\{2l-1<2k-1\colon\>\sigma(2l-1)>\sigma(2k-1)\\}&\textrm{if
$i=\sigma(2k-1)$}\end{cases}\qquad{}\\\
=\begin{cases}\\#\\{j\colon\>j<i\leq\sigma^{-1}(i)<\sigma^{-1}(j)\\}&\textrm{if
$\sigma^{-1}(i)$ is even}\\\\[5.69054pt]
\\#\\{j\colon\>\sigma^{-1}(j)<\sigma^{-1}(i)\leq i<j\\}&\textrm{if
$\sigma^{-1}(i)$ is odd}\end{cases}{}$ (6.46)

We would now like to show how the alternative label $\widehat{\xi}_{i}$ can be
use to prove the variant forms of our T-fractions (Theorems 3.12 and 3.13).

Just as the labels $\xi_{i}$ are related to the index-refined crossing and
nesting statistics (2.50), so the alternative labels $\widehat{\xi}_{i}$ are
related to the variant index-refined crossing and nesting statistics (2.52).
For the nesting statistics this is immediate from the definition
(LABEL:def.xi.b):

######  Lemma 6.7 (Nesting statistics for the alternative labels).

We have

$\widehat{\xi}_{i}\;=\;\begin{cases}{\rm lnest}^{\prime}(i,\sigma)&\hbox{\rm
if $\sigma^{-1}(i)$ is even (i.e., $s_{i}$ is a rise) and $\neq
i$}\\\\[2.84526pt] {\rm unest}^{\prime}(i,\sigma)&\hbox{\rm if
$\sigma^{-1}(i)$ is odd (i.e., $s_{i}$ is a fall) and $\neq i$}\\\\[2.84526pt]
{\rm psnest}(i,\sigma)&\hbox{\rm if $\sigma^{-1}(i)=i$ (i.e., $i$ is a fixed
point)}\end{cases}$ (6.47)

Remarks. 1\. By comparing (LABEL:def.xi.b) with (6.9), we see that

$\widehat{\xi}_{i}\;=\;\xi_{\sigma^{-1}(i)}\;.$ (6.48)

This explains (6.47): combine (6.11) with (2.53).

2\. The distinction between $\xi_{i}$ and $\widehat{\xi}_{i}$ is also related
to the distinction between two different notions of “inversion table”. In the
approach used here and in [46, Section 6.1, Step 3], the label $\xi_{i}$ is
the number of inversions associated to the position $i$. By contrast, in [40,
p. 88] and [23, p. 51], the label $\widehat{\xi}_{i}$ is the number of
inversions associated to the value $i$, i.e. to the position $\sigma^{-1}(i)$.
Thus, whenever $i$ is not a fixed point, $\widehat{\xi}_{i}$ corresponds to
the original Foata–Zeilberger [23] labels, while $\xi_{i}$ corresponds to the
modified labels used in [46, Section 6.1]. $\blacksquare$

The alternative labels $\widehat{\xi}_{i}$ satisfy the same inequalities as
the original labels $\xi_{i}$:

######  Lemma 6.8 (Inequalities satisfied by the alternative labels).

We have

$&0\;\leq\;\widehat{\xi}_{i}\;\leq\;\left\lceil\dfrac{h_{i}-1}{2}\right\rceil\;=\;\left\lceil\dfrac{h_{i-1}}{2}\right\rceil\textrm{if
$\sigma^{-1}(i)$ is even (i.e., $s_{i}$ is a rise)}\qquad{}\\\
0\;\leq\;\widehat{\xi}_{i}\;\leq\;\left\lceil\dfrac{h_{i}}{2}\right\rceil\;=\;\left\lceil\dfrac{h_{i-1}-1}{2}\right\rceil\textrm{if
$\sigma^{-1}(i)$ is odd (i.e., $s_{i}$ is a fall)}{}$ (6.49)

Lemma 6.8 will be an immediate consequence of the following identities:

######  Lemma 6.9 (Crossing statistics for the alternative labels).

  * (a)

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

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\widehat{\xi}_{i}&={\rm
lcross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is even and }\sigma(i)\neq
i]\\\ ={\rm lcross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle
double fall}]\;.$ (6.50)

  * (b)

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

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\widehat{\xi}_{i}&={\rm
ucross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is odd and }\sigma(i)\neq
i]\\\ ={\rm ucross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle
double rise}]\;.$ (6.51)

$j$$i=\sigma(2k)$$\sigma^{-1}(j)$$\sigma^{-1}(i)=2k$When $\sigma^{-1}(i)$ is
even

$\sigma^{-1}(i)=2k\\!-\\!1$$j$$i=\sigma(2k\\!-\\!1)$$\sigma(j)$When
$\sigma^{-1}(i)$ is odd

Figure 9:  Crossings involved in the inequalities for the label
$\widehat{\xi}_{i}$.

Proof. (a) If $s_{i}$ is a rise, then $\sigma^{-1}(i)$ is even, and
$i\leq\sigma^{-1}(i)$. We now consider separately the cases of $i$ odd and $i$
even.

  * (i)

If $i$ is odd, then $h_{i}$ is odd; moreover, we have the strict inequality
$i<\sigma^{-1}(i)$ (hence $i$ is not a fixed point). Then

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\widehat{\xi}_{i}&=\dfrac{h_{i}-1}{2}\,-\,\widehat{\xi}_{i}\\\
=f_{i}\,-\,1\,-\,\widehat{\xi}_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma^{-1}(j)>i\\}\,-\,1\\\ \hskip
113.81102pt\,-\,\\#\\{j<i\colon\>\sigma^{-1}(j)>\sigma^{-1}(i)\\}\qquad\qquad\\\
=\\#\\{j<i\colon\>\sigma^{-1}(j)>i\\}\,-\,\\#\\{j<i\colon\>\sigma^{-1}(j)>\sigma^{-1}(i)\\}\qquad\qquad\\\
=\\#\\{j\colon\>j<i<\sigma^{-1}(j)\leq\sigma^{-1}(i)\\}\\\
=\\#\\{j\colon\>j<i<\sigma^{-1}(j)<\sigma^{-1}(i)\\}\\\
\qquad\qquad\hbox{since $j\neq i$ implies
$\sigma^{-1}(j)\neq\sigma^{-1}(i)$}\\\ ={\rm lcross}^{\prime}(i,\sigma)\;.$
(6.52)

See Figure 9(a).

  * (ii)

If $i$ is even, then $h_{i}$ is even, and

$\left\lceil\dfrac{h_{i}-1}{2}\right\rceil-\widehat{\xi}_{i}&=\dfrac{h_{i}}{2}\,-\,\widehat{\xi}_{i}\\\
=f_{i}\,-\,\widehat{\xi}_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma^{-1}(j)>i\\}\,-\,\\#\\{j<i\colon\>\sigma^{-1}(j)>\sigma^{-1}(i)\\}\qquad\qquad\\\
=\\#\\{j<i\colon\>\sigma^{-1}(j)>i\\}\,+\,{\rm I}[\sigma(i)\neq i]\\\ \hskip
113.81102pt\,-\,\\#\\{j<i\colon\>\sigma^{-1}(j)>\sigma^{-1}(i)\\}\\\
=\\#\\{j\colon\>j<i<\sigma^{-1}(j)\leq\sigma^{-1}(i)\\}\,+\,{\rm
I}[\sigma(i)\neq i]\qquad\qquad\\\
=\\#\\{j\colon\>j<i<\sigma^{-1}(j)<\sigma^{-1}(i)\\}\,+\,{\rm I}[\sigma(i)\neq
i]\\\ \qquad\qquad\hbox{since $j\neq i$ implies
$\sigma^{-1}(j)\neq\sigma^{-1}(i)$}\qquad\\\ ={\rm
lcross}^{\prime}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;.$ (6.53)

See again Figure 9(a). Note that the identity (6.53) holds also when
$h_{i}=0$, i.e. when the step $s_{i}$ is a rise from height $h_{i-1}=-1$; in
this case $i$ is a record-antirecord fixed point and we have
$\widehat{\xi}_{i}=0$, so that both sides of (6.53) are zero.

Combining (6.52) and (6.53) yields (6.50).

(b) If $s_{i}$ is a fall, then $\sigma^{-1}(i)$ is odd, and
$\sigma^{-1}(i)\leq i$. We again consider separately the cases of $i$ odd and
$i$ even.

  * (i)

If $i$ is odd, then $h_{i}$ is odd, and

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\widehat{\xi}_{i}&=\dfrac{h_{i}+1}{2}\,-\,\widehat{\xi}_{i}\\\
=f_{i}\,-\,\widehat{\xi}_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma(j)>i\\}\,-\,\\#\\{j\colon\>\sigma^{-1}(j)<\sigma^{-1}(i)\leq
i<j\\}\\\ =\\#\\{j\leq
i\colon\>\sigma(j)>i\\}\,-\,\\#\\{j<\sigma^{-1}(i)\colon\>\sigma(j)>i\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma^{-1}(i)\leq j\leq i<\sigma(j)\\}\\\
=\\#\\{j\colon\>\sigma^{-1}(i)<j\leq i<\sigma(j)\\}\\\ \qquad\hbox{since
$i\neq\sigma(j)$ implies $j\neq\sigma^{-1}(i)$}\\\
=\\#\\{j\colon\>\sigma^{-1}(i)<j<i<\sigma(j)\\}\,+\,{\rm
I}[\sigma^{-1}(i)<i<\sigma(i)]\qquad\qquad\\\ ={\rm
ucross}^{\prime}(i,\sigma)\,+\,{\rm I}[\sigma(i)\neq i]\;.$ (6.54)

See Figure 9(b). Note that the identity (6.54) holds also when $h_{i}=-1$,
i.e. when the step $s_{i}$ is a fall from height $h_{i-1}=0$; in this case $i$
is a record-antirecord fixed point and we have $\widehat{\xi}_{i}=0$, so that
both sides of (6.54) are zero.

  * (ii)

If $i$ is even, then $h_{i}$ is even; moreover, we have the strict inequality
$\sigma^{-1}(i)<i$ (hence $i$ is not a fixed point). Then

$\left\lceil\dfrac{h_{i}}{2}\right\rceil-\widehat{\xi}_{i}&=\dfrac{h_{i}}{2}\,-\,\widehat{\xi}_{i}\\\
=f_{i}\,-\,\widehat{\xi}_{i}\\\ =\\#\\{j\leq
i\colon\>\sigma(j)>i\\}\,-\,\\#\\{j<\sigma^{-1}(i)\colon\>\sigma(j)>i\\}\qquad\qquad\\\
=\\#\\{j\colon\>\sigma^{-1}(i)\leq j\leq i<\sigma(j)\\}\\\
=\\#\\{j\colon\>\sigma^{-1}(i)<j\leq i<\sigma(j)\\}\\\ \qquad\hbox{since
$i\neq\sigma(j)$ implies $j\neq\sigma^{-1}(i)=\sigma^{-1}(i)$}\\\
=\\#\\{j\colon\>\sigma^{-1}(i)<j<i<\sigma(j)\\}\quad\hbox{since
$i\geq\sigma(i)$}\qquad\qquad\\\ ={\rm ucross}^{\prime}(i,\sigma)\;.$ (6.55)

See again Figure 9(b).

Combining (6.54) and (6.55) yields (6.51). $\square$

######  Lemma 6.10 (Cycle classification for the alternative labels).

  * (a)

If $s_{i}$ a rise and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is a
cycle valley.

  * (b)

If $s_{i}$ a rise and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is an
even fixed point in case
$\widehat{\xi}_{i}=\left\lceil\dfrac{h_{i}-1}{2}\right\rceil$
($=h_{i}/2=f_{i})$; otherwise it is a cycle double fall.

  * (c)

If $s_{i}$ is a fall and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is
an odd fixed point in case
$\widehat{\xi}_{i}=\left\lceil\dfrac{h_{i}}{2}\right\rceil$
($=(h_{i}+1)/2=f_{i}$); otherwise it is a cycle double rise.

  * (d)

If $s_{i}$ is a fall and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is
a cycle peak.

Proof. Completely analogous to the proof of Lemma 6.5: just use Lemma 6.9 in
place of Lemma 6.4. $\square$

######  Lemma 6.11 (Record statistics for the alternative labels).

  * (a)

If $\sigma^{-1}(i)$ is odd, then the index $\sigma^{-1}(i)$ is a record if and
only if $\widehat{\xi}_{i}=0$.

  * (b)

If $\sigma^{-1}(i)$ is even, then the index $\sigma^{-1}(i)$ is an antirecord
if and only if $\widehat{\xi}_{i}=0$.

Proof. This is an immediate consequence of the definition (LABEL:def.xi.b).
$\square$

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

We now recall the definitions

$F&=\\{2,4,\ldots,2n\\}\;=\;\hbox{even positions}\\\
F^{\prime}=\\{i\colon\sigma^{-1}(i)\text{ is
even}\\}\;=\;\\{\sigma(2),\sigma(4),\ldots,\sigma(2n)\\}\\\
G=\\{1,3,\ldots,2n-1\\}\;=\;\hbox{odd positions}\\\
G^{\prime}=\\{i\colon\sigma^{-1}(i)\text{ is
odd}\\}\;=\;\\{\sigma(1),\sigma(3),\ldots,\sigma(2n-1)\\}$ (6.56)

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

We can now describe the map $(\omega,\widehat{\xi})\mapsto\sigma$. Given the
almost-Dyck path $\omega$, we can immediately reconstruct the sets
$F,F^{\prime},G,G^{\prime}$. We now use the labels $\widehat{\xi}$ to
reconstruct the maps $\sigma\upharpoonright F\colon\>F\to F^{\prime}$ and
$\sigma\upharpoonright G\colon\>G\to G^{\prime}$ as follows: The even subword
$\sigma(2)\sigma(4)\cdots\sigma(2n)$ is a listing of $F^{\prime}$ whose right-
to-left value-based inversion table is given by
$q^{\prime}_{i}=\widehat{\xi}_{i}$ for all $i\in F^{\prime}$; this is the
content of (LABEL:def.xi.a). Similarly, the odd subword
$\sigma(1)\sigma(3)\cdots\sigma(2n-1)$ is a listing of $G^{\prime}$ whose
left-to-right value-based inversion table is given by
$p^{\prime}_{i}=\widehat{\xi}_{i}$ for all $i\in G^{\prime}$; this again is
the content of (LABEL:def.xi.a). See Figure 10 for an example.

$\begin{array}[]{r}F=\\{2i\;|\;1\leq i\leq 7\\}\\\\[8.53581pt]
F^{\prime}=\\{\sigma(2i)\;|\;1\leq i\leq 7\\}\\\\[8.53581pt] \text{Right-to-
left inversion table:}\;\widehat{\xi}_{\sigma(2i)}\\\
\end{array}\;\begin{pmatrix}\;2&4&6&8&10&12&14\;\\\\[8.53581pt]
\;1&2&4&6&3&12&13\;\\\\[8.53581pt] \;0&0&1&1&0&0&0\;\end{pmatrix}$

$\begin{array}[]{r}G=\\{2i-1\;|\;1\leq i\leq 7\\}\\\\[8.53581pt]
G^{\prime}=\\{\sigma(2i-1)\;|\;1\leq i\leq 7\\}\\\\[10.00002pt] \text{Left-to-
right inversion table:}\;\widehat{\xi}_{\sigma(2i-1)}\\\
\end{array}\;\begin{pmatrix}\;1&3&5&7&9&11&13\;\\\\[8.53581pt]
\;7&9&5&8&10&11&14\;\\\\[8.53581pt] \;0&0&2&1&0&0&0\;\end{pmatrix}$

$f_{i}$ | $\widehat{\xi}_{f_{i}}$ | Partial subword of $F^{\prime}$
---|---|---
$1$ | $0$ | $\underline{1}$
$2$ | $0$ | $1\;\underline{2}$
$3$ | $0$ | $1\;2\;\underline{3}$
$4$ | $1$ | $1\;2\;\underline{4}\;3$
$6$ | $1$ | $1\;2\;4\;\underline{6}\;3$
$12$ | $0$ | $1\;2\;4\;6\;3\;\underline{12}$
$13$ | $0$ | $1\;2\;4\;6\;3\;12\;\underline{13}$

$g_{i}$ | $\widehat{\xi}_{g_{i}}$ | Partial subword of $G^{\prime}$
---|---|---
$14$ | $0$ | $\underline{14}$
$11$ | $0$ | $\underline{11}\;14$
$10$ | $0$ | $\underline{10}\;11\;14$
$9$ | $0$ | $\underline{9}\;10\;11\;14$
$8$ | $1$ | $9\;\underline{8}\;10\;11\;14$
$7$ | $0$ | $\underline{7}\;9\;8\;10\;11\;14$
$5$ | $2$ | $7\;9\;\underline{5}\;8\;10\;11\;14$

Figure 10:  Reconstruction of the 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)$
from its almost-Dyck path $\omega$ and labels $\widehat{\xi}$. The value
$f_{i}$ is inserted so that it has $\widehat{\xi}_{f_{i}}$ entries to its
right in the partial subword; the value $g_{i}$ is inserted so that it has
$\widehat{\xi}_{g_{i}}$ entries to its left in the partial subword.

The only thing that remains to be shown is that the $\sigma$ thus constructed
is indeed a D-permutation. For this, we need to show that the following
inequalities hold:

$\sigma(2k-1)&\geq 2k-1{}\\\ \sigma(2k)\leq 2k{}$ (6.57)

We begin with a lemma:

######  Lemma 6.12.

  * (a)

Let $f_{1}<f_{2}<\ldots<f_{n}$ be the elements of $F^{\prime}$ in increasing
order. Then $f_{j}\leq 2j$ for every $j\in[n]$.

  * (b)

Let $g_{1}<g_{2}<\ldots<g_{n}$ be the elements of $G^{\prime}$ in increasing
order. Then $g_{j}\geq 2j-1$ for every $j\in[n]$.

Proof. (a) Notice that the number of rises among the steps
$s_{1},s_{2},\ldots,s_{i}$ is $(i+h_{i})/2$ (and the number of falls is
$(i-h_{i})/2$). As there are exactly $j$ rises among the steps
$s_{1},s_{2},\ldots,s_{f_{j}}$, we have

$\frac{f_{j}+h_{f_{j}}}{2}\;=\;j$ (6.58)

and hence

$f_{j}\;=\;2j-h_{f_{j}}\;\leq\;2j$ (6.59)

since $h_{f_{j}}\geq 0$.

The proof of (b) is similar, using the fact that $h_{g_{j}}\geq-1$. $\square$

Now consider any index $k\in[n]$. Let $j^{\prime}$ be the index for which
$f_{j^{\prime}}=\sigma(2k)$. From the definition of right-to-left inversion
table, we know that there are $\widehat{\xi}_{\sigma(2k)}$ elements to the
right of $\sigma(2k)$ in the word $\sigma(2)\sigma(4)\cdots\sigma(2n)$ which
are smaller than $\sigma(2k)$. On the other hand, there are $n-k$ elements to
the right of $\sigma(2k)$ in the word $\sigma(2)\sigma(4)\cdots\sigma(2n)$;
and there are $n-j^{\prime}$ elements in $F^{\prime}$ that are larger than
$f_{j^{\prime}}$. Therefore, there are at least
$(n-k)-(n-j^{\prime})=j^{\prime}-k$ elements to the right of $\sigma(2k)$ in
the word $\sigma(2)\sigma(4)\cdots\sigma(2n)$ that are smaller than
$f_{j^{\prime}}=\sigma(2k)$. Therefore,

$\widehat{\xi}_{\sigma(2k)}&\geq j^{\prime}-k\\\
={f_{j^{\prime}}+h_{f_{j^{\prime}}}\over 2}\,-\,k\qquad\hbox{[by
(\ref{eq.evenineqpi0})]}\\\ ={h_{\sigma(2k)}\over 2}+{\sigma(2k)-2k\over
2}\;.$ (6.60)

On the other hand, from (LABEL:eq.xihat.ineqs.a) we know that

$\widehat{\xi}_{\sigma(2k)}\;\leq\;\left\lceil\dfrac{h_{\sigma(2k)}-1}{2}\right\rceil\;\leq\;\dfrac{h_{\sigma(2k)}}{2}\;.$
(6.61)

Combining these two inequalities, we conclude that $\sigma(2k)\leq 2k$.

The proof that $\sigma(2k-1)\geq 2k-1$ is similar, using
(LABEL:eq.xihat.ineqs.b). $\square$

Remark. This proof of bijection is very close in spirit to that of
Randrianarivony [40, pp. 89–90]. $\blacksquare$

Proof of Theorem 3.12.  The computation of the weights is completely analogous
to what was done in Section 6.4, but using Lemmas 6.7–6.11 in place of Lemmas
6.2–6.6. We leave the details to the reader: the upshot is that for cycle
valleys and cycle peaks, “u” and “l” are interchanged compared to Section 6.4,
and all statistics are primed. This is exactly what we have in (3.33). It
therefore completes the proof of Theorem 3.12. $\square$

Proof of Theorem 3.13.  Comparing (3.35) with (3.33) and using Lemma 6.11, we
see that the needed weights in (3.33) are the same as given in (6.40)–(6.45).
Inserting these into Theorem 3.12 gives Theorem 3.13. $\square$

##  7 Second T-fraction: Proof of Theorems 4.2, 4.7 and 4.10

In this section we prove the second master T-fraction (Theorem 4.10) by a
bijection from D-permutations to labeled Schröder paths. Our construction
combines ideas of Randrianarivony [40] and Biane [2] together with some new
ingredients. After proving Theorem 4.10, we deduce Theorems 4.2 and 4.7 by
specialization.

Here we need to construct a bijection that will allow us to count the number
of cycles (cyc), which is a global variable. To do this, we employ a
modification of the Biane [2] bijection, just as in Section 6 we employed a
modification of the Foata–Zeilberger [23] bijection. Our bijection maps
${\mathfrak{D}}_{2n}$ to the set of
$\bm{({\bm{\mathcal{A}}},{\bm{\mathcal{B}}},{\bm{\mathcal{C}}})}$-labeled
0-Schröder paths of length $\bm{2n}$, where each label $\xi_{i}$ is a pair of
nonnegative integers $\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$ as
follows:

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

or equivalently

${\mathcal{A}}_{h}&=\\{0\\}\times\\{0\\}\qquad\qquad\;\hbox{for $h\geq 0$ and
$h=2k$}{}\\\ {\mathcal{A}}_{h}=\\{0\\}\times\\{0,\ldots,k\\}\quad\;\>\hbox{for
$h\geq 0$ and $h=2k-1$}{}\\\
{\mathcal{B}}_{h}=\\{0,\ldots,k\\}\times\\{0\\}\quad\;\>\hbox{for $h\geq 1$
and $h=2k$}{}\\\
{\mathcal{B}}_{h}=\\{0,\ldots,k\\}^{2}\qquad\qquad\\!\hbox{for $h\geq 1$ and
$h=2k+1$}{}\\\ {\mathcal{C}}_{0}=\\{0\\}\times\\{0\\}\\\
{\mathcal{C}}_{h}=\varnothing\qquad\qquad\qquad\quad\;\;\,\hbox{for $h\geq
1$}$ (7.2)

Our presentation of this bijection will follow the same steps as in Section 6.

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

The almost-Dyck path $\omega$ associated to a D-permutation
$\sigma\in{\mathfrak{D}}_{2n}$ is identical to the one employed in Section 6.
That is:

  * •

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

  * •

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

The interpretation of the heights $h_{i}$ is thus exactly as in Lemma 6.1. We
then define the 0-Schröder path ${\widehat{\omega}}=\psi(\omega)$ as before.

###  7.2 Step 2: Definition of the labels
$\bm{\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})}$

We define the labels $\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$ as
follows:

$\displaystyle\xi_{i}^{\prime}$ $\displaystyle=$
$\displaystyle\begin{cases}0&\textrm{if $\sigma^{-1}(i)$ is
even}\\\\[2.84526pt] \\#\\{j\colon\>\sigma^{-1}(j)<\sigma^{-1}(i)\leq
i<j\\}&\textrm{if $\sigma^{-1}(i)$ is odd}\end{cases}$ (7.3)
$\displaystyle\xi_{i}^{\prime\prime}$ $\displaystyle=$
$\displaystyle\begin{cases}0&\textrm{if $i$ is odd}\\\\[2.84526pt]
\\#\\{j\colon\>\sigma(j)<\sigma(i)\leq i<j\\}&\textrm{if $i$ is
even}\end{cases}$ (7.4)

These labels $\xi^{\prime}_{i},\xi^{\prime\prime}_{i}$ needed for the proof of
the second T-fraction are related to the labels $\xi_{i},\widehat{\xi}_{i}$
defined in (6.9) and (6.46) and employed in Section 6 for the proof of the
first T-fraction, as follows:

$&\sigma^{-1}(i)\hbox{ is odd}\iff i\in{\rm Cpeak}\cup{\rm Cdrise}\cup{\rm
Oddfix}\colon\quad\\\ \hskip
85.35826pt\xi^{\prime}_{i}(\textrm{Second})\>=\>\widehat{\xi}_{i}(\textrm{First})\>=\>\xi_{\sigma^{-1}(i)}(\textrm{First})\hskip
28.45274pt{}\\\ i\hbox{ is even}\iff i\in{\rm Cpeak}\cup{\rm Cdfall}\cup{\rm
Evenfix}\colon\quad\\\ \hskip
85.35826pt\xi^{\prime\prime}_{i}(\textrm{Second})=\xi_{i}(\textrm{First}){}$
(7.5)

Note that (LABEL:eq.1st.2nd.AA) refers to the cases (7.1c,d) where
$\xi^{\prime}_{i}$ is nontrivial [$\sigma^{-1}(i)$ odd means that $s_{i}$ is a
fall], while (LABEL:eq.1st.2nd.BB) refers to the cases (7.1b,d) where
$\xi^{\prime\prime}_{i}$ is nontrivial [$i$ even $\iff$ $h_{i}$ even $\iff$
$h=h_{i-1}$ odd]. Note in particular that cycle peaks belong to both cases
[cf. (7.1d)], while cycle valleys belong to neither [cf. (7.1a)].

It is worth remarking that these labels
$\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$ are the same as those in
the Biane bijection [46, Section 6.2, Step 2] whenever $i$ is not a fixed
point. Compare also (7.5) to [46, eq. (6.24)].

We can give these labels a nice interpretation by using (as in Section 6) the
representation of a permutation $\sigma\in{\mathfrak{S}}_{N}$ by a bipartite
digraph $\Gamma=\Gamma(\sigma)$ in which the top row of vertices is labeled
$1,\ldots,N$ and the bottom row $1^{\prime},\ldots,N^{\prime}$, and we draw an
arrow from $i$ to $j^{\prime}$ in case $\sigma(i)=j$. Recall that, for
$k\in[N]$, we denote by $\Gamma_{k}$ the induced subgraph of $\Gamma$ on the
vertex set $\\{1,\ldots,k\\}\cup\\{1^{\prime},\ldots,k^{\prime}\\}$. We can
consider the “history”
$\varnothing=\Gamma_{0}\subset\Gamma_{1}\subset\Gamma_{2}\subset\ldots\subset\Gamma_{N}=\Gamma$
as a process of building up the permutation $\sigma$ by successively
considering the status of indices $1,2,\ldots,N$.

Since we have here a D-permutation $\sigma\in{\mathfrak{D}}_{2n}$, we will
have vertices $1,\ldots,2n$ and $1^{\prime},\ldots,2n^{\prime}$. First recall
from (6.2)/(6.3) that $f_{i-1}$ is the number of free vertices in the top row
of $\Gamma_{i-1}$, and also the number of free vertices in the bottom row of
$\Gamma_{i-1}$; and recall from (6.6) that $f_{i-1}=\lceil h_{i-1}/2\rceil$.
We index the free vertices on each row of $\Gamma_{i-1}$ starting from 0: the
indices are thus $0,\ldots,f_{i-1}-1$. We then start from the digraph
$\Gamma_{i-1}$ and look at what happens at stage $i$ (see Figure 11):

  * •

If $i$ is a cycle valley, then at stage $i$ we add no arrows. Since no choices
are being made at this stage, we set
$\xi^{\prime}_{i}=\xi^{\prime\prime}_{i}=0$.

  * •

If $i$ is a cycle double fall or an even fixed point, then at stage $i$ we add
an arrow from $i$ on the top row to an unconnected dot $j^{\prime}$ on the
bottom row, where $j=\sigma(i)\leq i$; then $\xi^{\prime\prime}_{i}$ is the
index (left-to-right, counting from 0) of the unconnected dot $j^{\prime}$
among all the unconnected dots on the bottom row (together with the new dot
$i^{\prime}$) — that is the content of (7.4). Note that $j=i$ (an even fixed
point) corresponds to $\xi^{\prime\prime}_{i}=f_{i-1}$.

Since no unconnected dot on the top row was touched, we set
$\xi^{\prime}_{i}=0$.

  * •

Similarly, if $i$ is a cycle double rise or an odd fixed point, we add an
arrow from an unconnected dot $j$ on the top row to $i^{\prime}$ on the bottom
row, where $j=\sigma^{-1}(i)\leq i$; then $\xi^{\prime}_{i}$ is the index
(left-to-right, counting from 0) of the unconnected dot $j$ among all the
unconnected dots on the top row (together with the new dot $i$) — that is the
content of (7.3). Note that $j=i$ (an odd fixed point) corresponds to
$\xi^{\prime}_{i}=f_{i-1}$.

Since no unconnected dot on the bottom row was touched, we set
$\xi^{\prime\prime}_{i}=0$.

  * •

If $i$ is a cycle peak, then we add two arrows: from $i$ on the top row to the
unconnected dot $j^{\prime}$ on the bottom row, where $j=\sigma(i)<i$; and
also from the unconnected dot $k$ on the top row to $i^{\prime}$ on the bottom
row, where $k=\sigma^{-1}(i)<i$. Then $\xi^{\prime}_{i}$ (resp.
$\xi^{\prime\prime}_{i}$) is the index of $k$ (resp. $j^{\prime}$) among the
unconnected dots on the top (resp. bottom) row — that is the content of
(7.3)/(7.4).

All this is closely analogous to what was done in [46, Section 6.2, Step 2],
but with fixed points treated differently.

$\xi_{1}=(0,0)$$\xi_{2}=(0,\underline{0})$$\xi_{3}=(0,0)$$\xi_{4}=(0,\underline{0})$$\xi_{5}=(\underline{2},0)$$\xi_{6}=(0,\underline{1})$$\xi_{7}=(\underline{0},0)$$\xi_{8}=(\underline{1},\underline{1})$$\xi_{9}=(\underline{0},0)$$\xi_{10}=(\underline{0},\underline{0})$$\xi_{11}=(\underline{0},0)$$\xi_{12}=(0,\underline{0})$$\xi_{13}=(0,0)$$\xi_{14}=(\underline{0},\underline{0})$
Figure 11:  History of the permutation
$\sigma=7\,1\,9\,2\,5\,4\,8\,6\,10\,3\,11\,12\,14\,13=(1,5,7,8,2)\,(3,6,4)\,(9)\,(10)\,(11,14,12)\,(13)\in{\mathfrak{D}}_{14}$
for the second bijection. Each stage of the construction shows: the partial
almost-Dyck path $(\omega_{0},\ldots,\omega_{i})$, with the most recent step
in pink; the label $\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$, with
entries $\xi^{\prime}_{i}$ or $\xi^{\prime\prime}_{i}$ corresponding to new
edges in the bipartite digraph being underlined; and the bipartite digraph
$\Gamma_{i}$, with the new vertices and edges shown in pink. Note that the
final almost-Dyck path is that of Figure 4, and the final bipartite digraph is
that of Figure 5.

######  Lemma 7.1 (Nesting statistics for the second labels).

  * (a)

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

$\xi^{\prime}_{i}\;=\;\begin{cases}{\rm unest}^{\prime}(i,\sigma)&\hbox{\rm if
$i$ is not a fixed point}\\\\[2.84526pt] {\rm psnest}(i,\sigma)&\hbox{\rm if
$i$ is a fixed point}\end{cases}$ (7.6)

  * (b)

If $i$ is even, then

$\xi^{\prime\prime}_{i}\;=\;\begin{cases}{\rm lnest}(i,\sigma)&\hbox{\rm if
$i$ is not a fixed point}\\\\[2.84526pt] {\rm psnest}(i,\sigma)&\hbox{\rm if
$i$ is a fixed point}\end{cases}$ (7.7)

Proof. (a) follows from (LABEL:eq.1st.2nd.AA) and (6.47).

(b) follows from (LABEL:eq.1st.2nd.BB) and (6.11). $\square$

######  Lemma 7.2 (Inequalities satisfied by the second labels).

  * (a)

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

$0\;\leq\;\xi^{\prime}_{i}\;\leq\;\left\lceil\dfrac{h_{i}}{2}\right\rceil\;=\;\left\lceil\dfrac{h_{i-1}-1}{2}\right\rceil$
(7.8)

  * (b)

If $i$ is even, then

$0\;\leq\;\xi^{\prime\prime}_{i}\;\leq\;\dfrac{h_{i}}{2}\;=\;\begin{cases}\left\lceil\dfrac{h_{i-1}}{2}\right\rceil&\hbox{\rm
if $\sigma^{-1}(i)$ is even (i.e., $s_{i}$ is a rise)}\\\\[14.22636pt]
\dfrac{h_{i-1}-1}{2}&\hbox{\rm if $\sigma^{-1}(i)$ is odd (i.e., $s_{i}$ is a
fall)}\end{cases}\quad$ (7.9)

Lemma 7.2 will be an immediate consequence of the following identities:

######  Lemma 7.3 (Crossing statistics for the second labels).

  * (a)

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

$\left\lceil\dfrac{h_{i}}{2}\right\rceil\,-\,\xi^{\prime}_{i}&={\rm
ucross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is odd and }\sigma(i)\neq
i]\\\ ={\rm ucross}^{\prime}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle
double rise}]\;.$ (7.10)

  * (b)

If $i$ is even, then

$\dfrac{h_{i}}{2}\,-\,\xi^{\prime\prime}_{i}&={\rm lcross}(i,\sigma)\,+\,{\rm
I}[\sigma^{-1}(i)\hbox{\rm is even and }\sigma(i)\neq i]\\\ ={\rm
lcross}(i,\sigma)\,+\,{\rm I}[\hbox{\rm$i$ is a cycle double fall}]\;.$ (7.11)

Proof. (a) Combining (LABEL:eq.1st.2nd.AA) with (6.51) yields (7.10).

(b) If $i$ is even, then $h_{i}$ is also even. Combining (LABEL:eq.1st.2nd.BB)
with (6.15)/(6.17) yields (7.11). $\square$

We now consider the four possible combinations of $s_{i}$ (rise or fall) and
parity of $h_{i}$ (odd or even), and determine in each case the cycle
classification of the index $i$. Exactly as with the first bijection, $s_{i}$
tells us the parity of $\sigma^{-1}(i)$, while the parity of $h_{i}$ equals
the parity of $i$. So these two pieces of information again tell us what was
recorded in (2.47)/(2.48):

  * •

$\sigma^{-1}(i)$ even and $i$ odd $\iff$ $i$ is a cycle valley

  * •

$\sigma^{-1}(i)$ even and $i$ even $\iff$ $i$ is either a cycle double fall or
an even fixed point

  * •

$\sigma^{-1}(i)$ odd and $i$ odd $\iff$ $i$ is either a cycle double rise or
an odd fixed point

  * •

$\sigma^{-1}(i)$ odd and $i$ even $\iff$ $i$ is a cycle peak

So, once again, we need only disambiguate the fixed points from the cycle
double falls/rises in the middle two cases. We have:

######  Lemma 7.4 (Cycle classification for second bijection).

  * (a)

If $s_{i}$ a rise and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is a
cycle valley.

  * (b)

If $s_{i}$ a rise and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is an
even fixed point in case
$\xi_{i}^{\prime\prime}=\left\lceil\dfrac{h_{i}-1}{2}\right\rceil$
($=h_{i}/2=f_{i}$); otherwise it is a cycle double fall.

  * (c)

If $s_{i}$ is a fall and $h_{i}$ is odd (hence $h_{i-1}$ is even), then $i$ is
an odd fixed point in case
$\xi_{i}^{\prime}=\left\lceil\dfrac{h_{i}}{2}\right\rceil$
($=(h_{i}+1)/2=f_{i}$); otherwise it is a cycle double rise.

  * (d)

If $s_{i}$ is a fall and $h_{i}$ is even (hence $h_{i-1}$ is odd), then $i$ is
a cycle peak.

We remark that (b) also includes the case in which $(h_{i-1},h_{i})=(-1,0)$,
and (c) also includes the case in which $(h_{i-1},h_{i})=(0,-1)$.

Proof. (a,d) follow immediately from (2.47)/(2.48).

(b) From Lemma 7.3(b), we have

$\dfrac{h_{i}}{2}\,-\,\xi^{\prime\prime}_{i}\;\;\begin{cases}\geq 1&\textrm{if
$i$ is a cycle double fall}\\\\[2.84526pt] =0&\textrm{if $i$ is an even fixed
point}\end{cases}$ (7.12)

(c) Lemma 7.3(a), we have

$\left\lceil\dfrac{h_{i}}{2}\right\rceil\,-\,\xi^{\prime}_{i}\;\;\begin{cases}\geq
1&\textrm{if $i$ is a cycle double rise}\\\\[2.84526pt] =0&\textrm{if $i$ is
an odd fixed point}\end{cases}$ (7.13)

$\square$

######  Lemma 7.5 (Record statistics for the second bijection).

  * (a)

If $\sigma^{-1}(i)$ is odd, then the index $\sigma^{-1}(i)$ is a record if and
only if $\xi^{\prime}_{i}=0$.

  * (b)

If $i$ is even, then the index $i$ is an antirecord if and only if
$\xi^{\prime\prime}_{i}=0$.

Proof. This is an immediate consequence of the definitions (7.3) and (7.4).
$\square$

###  7.3 Step 3: Proof of bijection

We prove that the map $\sigma\mapsto(\omega,\xi)$ is a bijection by explicitly
describing the inverse map. That is, we let $\omega$ be any almost-Dyck path
of length $2n$ and let $\xi$ be any set of labels satisfying the inequalities
(7.1)/(7.2), and we show how to reconstruct the unique D-permutation $\sigma$
that gives rise to $(\omega,\xi)$ by the foregoing construction.

In fact, the interpretation as a bipartite digraph shows how to build the
digraph, and hence reconstruct the D-permutation $\sigma$, by successively
reading the steps $s_{i}$ and labels $\xi_{i}$. Specifically, at stage $i$ one
starts from the digraph $\Gamma_{i-1}$ and proceeds as follows (see again
Figure 11):

  * (i)

If $s_{i}$ is a rise from height $h_{i-1}=2k$ to height $h_{i}=2k+1$ (by Lemma
7.4(a) this corresponds to $i$ being a cycle valley), then we add no arrows.

  * (ii)

If $s_{i}$ is a rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$ and
$\xi_{i}=(0,k)$ [by Lemma 7.4(b) this corresponds to $i$ being an even fixed
point], we add an arrow from $i$ to $i^{\prime}$.

  * (iii)

If $s_{i}$ is a rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$ with
$\xi_{i}=(0,m)$ with $0\leq m<k$ (by Lemma 7.4(b) this corresponds to $i$
being a cycle double fall), we add an arrow from $i$ on the top row to the
$m$th free vertex (counting from 0) on the bottom row, call it $j^{\prime}$.
Of course $j<i$, because these are the only vertices visible in the digraph
$\Gamma_{i-1}$.

  * (iv)

If $s_{i}$ is a fall from height $h_{i-1}=2k$ to height $h_{i}=2k-1$ and
$\xi_{i}=(k,0)$ [by Lemma 7.4(c) this corresponds to $i$ being an odd fixed
point], we add an arrow from $i$ to $i^{\prime}$.

  * (v)

If $s_{i}$ is a fall from height $h_{i-1}=2k$ to height $h_{i}=2k-1$ and
$\xi_{i}=(l,0)$ with $0\leq l<k$ (by Lemma 7.4(c) this corresponds to $i$
being a cycle double rise), we add an arrow from the $l$th free vertex
(counting from 0) on the top row (which is of course $<i$) to $i^{\prime}$ on
the bottom row.

  * (vi)

If $s_{i}$ is a fall from height $h_{i-1}=2k+1$ to height $h_{i}=2k$ and
$\xi=(l,m)$ with $0\leq l,m\leq k$ (by Lemma 7.4(d) this corresponds to $i$
being a cycle peak), we add two arrows: one going from $i$ on the top row to
the $m$th free vertex (counting from 0) on the bottom row (which is of course
$<i$); and the other going from the $l$th free vertex (counting from 0) on the
top row to $i^{\prime}$ on the bottom row.

Clearly, once a vertex has become the source or sink of an arrow, it plays no
further role in the construction and in particular receives no further arrows.
Moreover, since $h_{2n}=0$, at the end of the construction there are no
unconnected vertices. The final result of the construction thus corresponds to
a bijection between $\\{1,\ldots,2n\\}$ and
$\\{1^{\prime},\ldots,2n^{\prime}\\}$, or in other words to permutation
$\sigma\in{\mathfrak{S}}_{2n}$.

Note now that a free vertex $i$ in the top row can be created only in
situations (i) and (v), and in this case $i$ is always odd. This means that a
free vertex on the top row is always odd. Therefore, when in situations (v)
and (vi) we connect a vertex $r<i$ on the top row to $i^{\prime}$ on the
bottom row, $r$ is always odd. On the other hand, we have already seen that in
situations (iii) and (vi) when we connect the vertex $i$ on the top row to a
vertex $j^{\prime}$ with $j<i$ on the bottom row, $i$ is always even. These
two facts together show that $\sigma$ is a D-permutation.

###  7.4 Step 4: Translation of the statistics

We begin by compiling the interpretations of heights and labels in terms of
crossing and nesting statistics:

######  Lemma 7.6 (Crossing and nesting statistics).

We have

  * (a)

When $i$ is even and $h_{i}=2k$,

$\xi_{i}^{\prime\prime}&={\rm lnest}(i,\sigma)\qquad\qquad\;\hbox{\rm if
}i\in{\rm Cpeak}\cup{\rm Cdfall}\\\ k-\xi_{i}^{\prime\prime}={\rm
lcross}(i,\sigma)\qquad\qquad\hbox{\rm if }i\in{\rm Cpeak}\\\
k-1-\xi_{i}^{\prime\prime}={\rm lcross}(i,\sigma)\qquad\qquad\hbox{\rm if
}i\in{\rm Cdfall}\\\ \xi^{\prime\prime}_{i}\,=\,k={\rm
psnest}(i,\sigma)\qquad\qquad\\!\\!\hbox{\rm if }i\in{\rm Evenfix}\\\
\xi^{\prime}_{i}={\rm unest}^{\prime}(i,\sigma)\qquad\qquad\\!\hbox{\rm if
}i\in{\rm Cpeak}\\\ k-\xi^{\prime}_{i}={\rm
ucross}^{\prime}(i,\sigma)\qquad\qquad\\!\\!\\!\hbox{\rm if }i\in{\rm Cpeak}$
(7.14)

  * (b)

When $i$ is odd and $h_{i-1}=2k$,

$\xi_{i}^{\prime}&={\rm unest}^{\prime}(i,\sigma)\qquad\qquad\\!\hbox{\rm if
}i\in{\rm Cdrise}\\\ k-1-\xi_{i}^{\prime}={\rm
ucross}^{\prime}(i,\sigma)\qquad\qquad\\!\\!\\!\hbox{\rm if }i\in{\rm
Cdrise}\\\ k={\rm ucross}(i,\sigma)+{\rm unest}(i,\sigma)\qquad\hbox{\rm if
}i\in{\rm Cval}\\\ \xi^{\prime}_{i}\,=\,k={\rm
psnest}(i,\sigma)\qquad\qquad\\!\\!\hbox{\rm if }i\in{\rm Oddfix}$ (7.15)

Proof. (a) When $i$ is even, $i$ can either be a cycle peak, a cycle double
fall or an even fixed point.

  * •

When $i$ is a cycle double fall, $\sigma^{-1}(i)$ is even, so $s_{i}$ is a
rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$. Then (7.14a) follows
from Lemma 7.1(b), and (7.14c) follows from Lemma 7.3(b).

  * •

When $i$ is a cycle peak, $\sigma^{-1}(i)$ is odd, so $s_{i}$ is a fall from
height $h_{i-1}=2k+1$ to height $h_{i}=2k$. Then (7.14a) follows from Lemma
7.1(b), (7.14b) follows from Lemma 7.3(b), (7.14e) follows from Lemma 7.1(a),
and (7.14f) follows from Lemma 7.3(a).

  * •

When $i$ is an even fixed point, $\sigma^{-1}(i)$ is even, so $s_{i}$ is a
rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$. Then (7.14d) follows
from Lemmas 7.1(b) and 7.4(b).

(b) When $i$ is odd, $i$ can either be a cycle valley, a cycle double rise or
an odd fixed point.

  * •

When $i$ is a cycle double rise, $\sigma^{-1}(i)$ is odd, so $s_{i}$ is a fall
from height $h_{i-1}=2k$ to height $h_{i}=2k-1$. Then (7.15a) follows from
Lemma 7.1(a), and (7.15b) follows from Lemma 7.3(a).

  * •

When $i$ is a cycle valley, $\sigma^{-1}(i)$ is even, so $s_{i}$ is a rise
from height $h_{i-1}=2k$ to height $h_{i}=2k+1$. As the almost-Dyck path is
the same as in the first bijection, we can use Lemmas 6.2 and 6.4(a) to obtain
$k={\rm ucross}(i,\sigma)+{\rm unest}(i,\sigma)$, which is 7.15c).

  * •

When $i$ is an odd fixed point, $\sigma^{-1}(i)$ is odd, so $s_{i}$ is a fall
from height $h_{i-1}=2k$ to height $h_{i}=2k-1$. Then (7.15d) follows from
Lemmas 7.1(a) and 7.4(c).

$\square$

Remarks. 1\. When $i$ is a cycle valley, $\sigma^{-1}(i)$ is even and $i$ is
odd, so Lemmas 7.1 and 7.3 tell us nothing about ucross and unest; and the
labels $\xi^{\prime}_{i}=\xi^{\prime\prime}_{i}=0$ carry no information. That
is why in this case we learn only about the sum ${\rm ucross}+{\rm unest}$,
which can be deduced from the heights alone.

2\. Our treatment of cycle double rises is slightly nicer than that achieved
in [46, Lemma 6.4], thanks to the introduction of ${\rm ucross}^{\prime}$ and
${\rm unest}^{\prime}$.

3\. In (7.14c) or (7.15b), $k=0$ is impossible. These would correspond,
respectively, to a rise from height $-1$ or a fall from height $0$, which by
Lemma 6.1 occur only when $i$ is a record-antirecord fixed point, not when it
is a cycle double fall or cycle double rise. $\blacksquare$

Finally, and most crucially, we come to the counting of cycles (cyc). We use
the term cycle closer to denote the largest element in a non-singleton cycle.
(This is the same as the “cycle peak maximum” defined in Section 4.1.)
Obviously every non-singleton cycle has precisely one cycle closer. A cycle
closer is always a cycle peak, but not conversely. So we need to know how many
of the cycle peaks are the cycle closers. The answer is as follows:

######  Lemma 7.7 (Counting of cycles).

Fix $i=2k$ such that $k\in[n]$, and fix $(s_{1},\ldots,s_{i-1})$ and
$(\xi_{1},\ldots,\xi_{i-1})$. Consider all permutations
$\sigma\in{\mathfrak{D}}_{2n}$ that have those given values for the first
$i-1$ steps and labels and for which $i$ is a cycle peak. Then:

  * (a)

The value of $\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$ completely
determines whether $i$ is a cycle closer or not.

  * (b)

For each value $\xi^{\prime}_{i}\in[0,(h_{i-1}-1)/2]$ there is precisely one
value $\xi^{\prime\prime}_{i}\in$ $[0,(h_{i-1}-1)/2]$ that makes $i$ a cycle
closer, and conversely.

The proof is similar to the proof of [46, Lemma 6.5].

Proof. We use once again the bipartite digraph of Figure 5, and let us also
draw a vertical dotted line (with an upwards arrow) to connect each pair
$j^{\prime}\to j$. Now consider the restriction of this digraph to the vertex
set $\\{1,\ldots,{i-1},1^{\prime},\ldots,{(i-1)^{\prime}}\\}$: as discussed in
Step 3, this restriction can be reconstructed from the steps
$(s_{1},\ldots,s_{i-1})$ and the labels $(\xi_{1},\ldots,\xi_{i-1})$. The
connected components of this restriction are of two types: complete directed
cycles and directed open chains; they correspond to cycles of $\sigma$ whose
cycle closers are, respectively, $\leq i-1$ and $>i-1$. Each directed open
chain runs from an unconnected dot on the bottom row to an unconnected dot on
the top row.

Now suppose that $i$ is a cycle peak. Then at stage $i$ we add two arrows:
from $i$ on the top row to an unconnected dot $j^{\prime}$ on the bottom row;
and also from an unconnected dot $k$ on the top row to $i^{\prime}$ on the
bottom row. Here $\xi^{\prime}_{i}$ (resp. $\xi^{\prime\prime}_{i}$) is the
index of $k$ (resp. $j^{\prime}$) among the unconnected dots on the top (resp.
bottom) row.

Now the point is simply this: $i$ is a cycle closer if and only if
$j^{\prime}$ and $k$ belong to the same directed open chain (with $j^{\prime}$
being its starting point and $k$ being its ending point). So for each value
$\xi^{\prime}_{i}\in[0,(h_{i-1}-1)/2]$ there is precisely one value
$\xi^{\prime\prime}_{i}\in[0,(h_{i-1}-1)/2]$ that makes $i$ a cycle closer,
and conversely. $\square$

###  7.5 Step 5: Computation of the weights

We can now compute the weights associated to the 0-Schröder path
${\widehat{\omega}}$ in Theorem 5.4, which we recall are $a_{h,\xi}$ for a
rise starting at height $h$ with label $\xi$, $b_{h,\xi}$ for a fall starting
at height $h$ with label $\xi$, and $c_{h,\xi}$ for a long level step at
height $h$ with label $\xi$. (Of course, in the present case we have long
level steps only at height 0.) We do this by putting together the information
collected in Lemmas 7.2, 7.4, 7.6 and 7.7:

  * (a)

Rise from height $h_{i-1}=2k$ to height $h_{i}=2k+1$ (hence $i$ odd):

    * –

By (7.2a), the label is $\xi_{i}=(0,0)$.

    * –

By Lemma 7.4(a), this is a cycle valley.

    * –

By (7.15c), $k={\rm ucross}(i,\sigma)+{\rm unest}(i,\sigma)$.

Therefore, from (4.34), the weight for this step is

$a_{2k,(0,0)}\;=\;{{\sf a}}_{k}\;.$ (7.16)

  * (b)

Rise from height $h_{i-1}=2k-1$ to height $h_{i}=2k$ (hence $i$ even):

    * –

By (7.2b) and Lemma 7.2(b), the label is $\xi_{i}=(0,\xi^{\prime\prime}_{i})$
with $0\leq\xi^{\prime\prime}_{i}\leq k$.

    * –

By Lemma 7.4(b), this is a cycle double fall if
$0\leq\xi_{i}^{\prime\prime}<k$, and an even fixed point if
$\xi_{i}^{\prime\prime}=k$.

    * –

By (7.14a,d),

$\xi_{i}^{\prime\prime}\;=\;\begin{cases}{\rm lnest}(i,\sigma)&\textrm{if $i$
is a cycle double fall}\\\ {\rm psnest}(i,\sigma)&\textrm{if $i$ is an even
fixed point}\end{cases}$ (7.17)

    * –

By (7.14c), ${\rm lcross}(i,\sigma)=k-1-\xi_{i}^{\prime\prime}$ when $i$ is a
cycle double fall.

Therefore, from (4.34), the weight for this step is

$a_{2k-1,(0,\xi^{\prime\prime})}\;=\;\begin{cases}{{\sf
c}}_{k-1-\xi^{\prime\prime},\xi^{\prime\prime}}&\textrm{if
$0\leq\xi^{\prime\prime}<k$}\\\\[2.84526pt] \lambda{{\sf e}}_{k}&\textrm{if
$\xi^{\prime\prime}=k$}\end{cases}$ (7.18)

  * (c)

Fall from height $h_{i-1}=2k$ to height $h_{i}=2k-1$ (hence $i$ odd):

    * –

By (7.2c) and Lemma 7.2(a), the label is $\xi_{i}=(\xi^{\prime}_{i},0)$ with
$0\leq\xi^{\prime}_{i}\leq k$.

    * –

By Lemma 7.4(c), this is a cycle double rise if $0\leq\xi_{i}^{\prime}<k$, and
an odd fixed point if $\xi_{i}^{\prime}=k$.

    * –

By (7.15a,d),

$\xi_{i}^{\prime}\;=\;\begin{cases}{\rm unest}^{\prime}(i,\sigma)&\textrm{if
$i$ is a cycle double rise}\\\ {\rm psnest}(i,\sigma)&\textrm{if $i$ is an odd
fixed point}\end{cases}$ (7.19)

    * –

By (7.15b), ${\rm ucross}^{\prime}(i,\sigma)=k-1-\xi_{i}^{\prime}$ when $i$ is
a cycle double rise.

Therefore, from (4.34), the weight for this step is

$b_{2k,(\xi^{\prime},0)}\;=\;\begin{cases}{{\sf
d}}_{k-1-\xi^{\prime},\xi^{\prime}}&\textrm{if
$0\leq\xi^{\prime}<k$}\\\\[2.84526pt] \lambda{{\sf f}}_{k}&\textrm{if
$\xi^{\prime}=k$}\end{cases}$ (7.20)

  * (d)

Fall from height $h_{i-1}=2k+1$ to height $h_{i}=2k$ (hence $i$ even):

    * –

By (7.2d) and Lemma 7.2(a,b), the label is
$\xi_{i}=(\xi^{\prime}_{i},\xi^{\prime\prime}_{i})$ with
$0\leq\xi^{\prime}_{i}\leq k$ and $0\leq\xi^{\prime\prime}_{i}\leq k$.

    * –

By Lemma 7.4(d), this is a cycle peak.

    * –

By (7.14a), $\xi_{i}^{\prime\prime}={\rm lnest}(i,\sigma)$.

    * –

By (7.14b), $k-\xi_{i}^{\prime\prime}={\rm lcross}(i,\sigma)$.

For each choice of $\xi_{i}^{\prime\prime}\in[0,k]$ there are $k+1$ possible
choices of $\xi_{i}^{\prime}$, of which one closes a cycle and the rest don’t;
this is the content of Lemma 7.7. Therefore, from (4.34), the total weight of
all such steps is

$b_{2k+1}\;\stackrel{{\scriptstyle\rm
def}}{{=}}\;\sum_{\xi^{\prime},\xi^{\prime\prime}}b_{2k+1,(\xi^{\prime},\xi^{\prime\prime})}\;=\;(\lambda+k)\sum_{\xi^{\prime\prime}=0}^{k}{{\sf
b}}_{k-\xi^{\prime\prime},\xi^{\prime\prime}}\;.$ (7.21)

  * (e)

Long level step at height $0$:
This corresponds in the almost-Dyck path $\omega$ to a fall from height $0$ to
height $-1$, followed by a rise from height $-1$ to height $0$. Applying case
(c) with $k=0$ and $\xi=0$, followed by case (b) with $k=0$ and $\xi=0$, we
obtain a weight

$c_{0,0}\;=\;\lambda^{2}{{\sf e}}_{0}{{\sf f}}_{0}\;.$ (7.22)

Putting this all together in Theorem 5.4, we obtain a T-fraction with

$\displaystyle\alpha_{2k-1}$ $\displaystyle=$ $\displaystyle(\hbox{rise from
$2k-2$ to $2k-1$})\,\times\,(\hbox{fall from $2k-1$ to $2k-2$})$ (7.23)
$\displaystyle=$ $\displaystyle{{\sf
a}}_{k-1}\>(\lambda+k-1)\biggl{(}\sum_{\xi=0}^{k-1}{{\sf
b}}_{k-1-\xi,\xi}\biggr{)}$ $\displaystyle\alpha_{2k}$ $\displaystyle=$
$\displaystyle(\hbox{rise from $2k-1$ to $2k$})\,\times\,(\hbox{fall from $2k$
to $2k-1$})$ (7.24) $\displaystyle=$ $\displaystyle\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{)}$
$\displaystyle\delta_{1}$ $\displaystyle=$ $\displaystyle\lambda^{2}{{\sf
e}}_{0}{{\sf f}}_{0}$ (7.25) $\displaystyle\delta_{n}$ $\displaystyle=$
$\displaystyle 0\qquad\hbox{for $n\geq 2$}$ (7.26)

This completes the proof of Theorem 4.10. $\square$

Proof of Theorem 4.7.  Comparing (4.23) with (4.34) and using Lemma 7.5, and
recalling that we are making the specializations $v_{1}=y_{1}$ and
$q_{+1}=p_{+1}$, we see that the needed weights in (4.34) are

$\displaystyle{{\sf a}}_{k}$ $\displaystyle=$ $\displaystyle
p_{+1}^{k}\,y_{1}$ (7.27) $\displaystyle{{\sf b}}_{k-1-\xi,\xi}$
$\displaystyle=$ $\displaystyle
p_{-1}^{k-1-\xi}q_{-1}^{\xi}\,\times\,\begin{cases}x_{1}&\textrm{if
$\xi=0$}\\\ u_{1}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (7.28)
$\displaystyle{{\sf c}}_{k-1-\xi,\xi}$ $\displaystyle=$ $\displaystyle
p_{-2}^{k-1-\xi}q_{-2}^{\xi}\,\times\,\begin{cases}x_{2}&\textrm{if
$\xi=0$}\\\ u_{2}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$ (7.29)
$\displaystyle{{\sf d}}_{k-1-\xi,\xi}$ $\displaystyle=$
$\displaystyle{\widehat{p}}_{+2}^{k-1-\xi}{\widehat{q}}_{+2}^{\xi}\,\times\,\begin{cases}{\widehat{y}}_{2}&\textrm{if
$\xi=0$}\\\ {\widehat{v}}_{2}&\textrm{if $1\leq\xi\leq k-1$}\end{cases}$
(7.30) $\displaystyle{{\sf e}}_{k}$ $\displaystyle=$
$\displaystyle\begin{cases}z_{\rm e}&\textrm{if $k=0$}\\\\[2.84526pt] s_{\rm
e}^{k}w_{\rm e}&\textrm{if $k\geq 1$}\end{cases}$ (7.31) $\displaystyle{{\sf
f}}_{k}$ $\displaystyle=$ $\displaystyle\begin{cases}z_{\rm o}&\textrm{if
$k=0$}\\\\[2.84526pt] s_{\rm o}^{k}w_{\rm o}&\textrm{if $k\geq 1$}\end{cases}$
(7.32)

Inserting these into (7.23)–(7.26) yields the continued-fraction coefficients
(4.26). $\square$

Remarks. 1\. We needed to make the specialization $v_{1}=y_{1}$ because Lemma
7.5 tells us nothing about the record status of cycle valleys, for which
$\sigma^{-1}(i)$ is even and $i$ is odd. Similarly, we needed to make the
specialization $q_{+1}=p_{+1}$ because, for cycle valleys, Lemma 7.6(b) does
not tell us about ${\rm ucross}$ and ${\rm unest}$ individually, but only
their sum.

2\. There is a variant master polynomial that we could have treated: instead
of weighting cycle peaks using ${{\sf b}}_{{\rm lcross}(i,\sigma),\,{\rm
lnest}(i,\sigma)}$ as in (4.34), we could instead weight them as ${{\sf
b}}_{{\rm ucross}^{\prime}(i,\sigma),\,{\rm unest}^{\prime}(i,\sigma)}$. Then
we would use (7.14e,f) instead of (7.14a,b); the resulting T-fraction would be
the same. $\blacksquare$

Proof of Theorem 4.2.  Specialize Theorem 4.7 to
$p_{-1}=p_{-2}=p_{+1}={\widehat{p}}_{+2}=q_{-1}=q_{-2}={\widehat{q}}_{+2}=s_{\rm
e}=s_{\rm o}=1$. $\square$

##  8 Some final remarks

When we began this work, we envisioned it as analogous to, though probably
more complicated than, the study of the “linear family” [cf. (1.3)] that was
undertaken in [46]: our goal was to make a corresponding study of the
“quadratic family” [cf. (1.4)]. What has surprised us is that the final
results, as well as the associated methods of proof, turned out to be, not
merely analogous to those of [46], but in fact very closely parallel — much
more closely parallel than we expected.

The key objects of [46] were permutations of $[n]$; the key results were
J-fractions; and the proofs involved bijections from permutations of $[n]$ to
labeled Motzkin paths of length $n$, using the Foata–Zeilberger bijection for
the first J-fraction (which did not involve the counting of cycles) and the
Biane bijection for the second J-fraction (which involved the counting of
cycles). The two bijections have the same paths but different labels.

By contrast, the key objects of the present paper are D-permutations of
$[2n]$; the key results are 0-T-fractions (that is, T-fractions that have
$\delta_{i}=0$ for all $i\geq 2$); and the proofs involve bijections from
D-permutations of $[2n]$ to labeled 0-Schröder paths (or equivalently, labeled
almost-Dyck paths) of length $2n$. Once again, the bijections for the first
and second continued fractions have the same paths but different labels. Since
these 0-Schröder paths are very different from the Motzkin paths of [46], the
definitions of the paths must also be very different, and indeed they are. The
surprise was that the definitions of the labels in our constructions turned
out to be almost identical to those employed in [46] (where “almost” means
that fixed points are treated differently): once again, we use the
Foata–Zeilberger labels for the first T-fraction (which does not involve the
counting of cycles) and the Biane labels for the second T-fraction (which
involves the counting of cycles).

The final results also turned out to be amazingly similar. Compare, for
instance, Theorem 3.9 with [46, Theorem 2.7]: our coefficient $\alpha_{2k-1}$
is identical to the coefficient $\beta_{k}$ in [46, eq. (2.53c)]; our
coefficient $\alpha_{2k}$ includes the same ingredients as the coefficient
$\gamma_{k}$ in [46, eq. (2.53b)], but combined as a product rather than a
sum. An analogous comparison holds between our first master T-fraction
(Theorem 3.11) and the first master J-fraction in the earlier work [46,
Theorem 2.9]. Furthermore, an analogous comparison holds between our
conjectured second T-fraction (Conjecture 4.1) and the conjectured second
J-fraction found in the earlier work [46, Conjecture 2.3], and between our
proved second T-fraction (Theorem 4.2) when specialized to
${\widehat{v}}_{2}={\widehat{y}}_{2}$ and the proved second J-fraction found
in the earlier work [46, Theorem 2.4]. Finally, an almost analogous comparison
holds between our second master T-fraction (Theorem 4.10) and the second
master J-fraction in the earlier work [46, Theorem 2.14], the only difference
being that the treatment of ${{\sf d}}$ looks a bit more natural in the
present work.

All this suggests to us that D-permutations are, among all the combinatorial
models of the Genocchi and median Genocchi numbers, a particularly well-
behaved one, which is closely analogous to ordinary permutations. It would be
interesting to know whether similar continued fractions, in a large (or
infinite) number of independent indeterminates, can be found for some of the
other models of the Genocchi and median Genocchi numbers. Our approach in [46]
and the present paper has been to introduce a natural classification of
indices into mutually exclusive categories — here the parity-refined record-
and-cycle classification (Section 2.7) — and to build a homogeneous
multivariate generating polynomial implementing this classification. It would
be interesting to find analogous natural classifications for the other
combinatorial models.

## Acknowledgments

We wish to thank Beáta Bényi, Sheila Sundaram and Jiang Zeng for helpful
conversations and/or correspondence.

The first author (B.D.) also wishes to thank the organizers of the Graduate
Student Combinatorics Conference (GSCC 2022), the Graduate Online
Combinatorics Colloquium (GOCC), the combinatorics seminar series at the
Institute of Mathematical Sciences (Chennai, India), and the Heilbronn
workshop on Positivity Problems Associated to Permutation Patterns (Lancaster,
UK) for providing the opportunity to present preliminary versions of this
work.

This research was supported in part by the U.K. Engineering and Physical
Sciences Research Council grant EP/N025636/1, and by a teaching assistantship
from the Department of Mathematics, University College London.

##  Appendix A J-fraction for the polynomials (4.1)

The first few polynomials

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

are too complicated to print even at $n=3$. But we can give the first few
J-fraction coefficients: they are

$\gamma_{0}&=\lambda x(\lambda x+y)\\\ \beta_{1}=\lambda
xy(\lambda+x)(\lambda+y)\\\ \gamma_{1}=(1+\lambda)(\lambda+x+y+xy)\\\
\beta_{2}=\lambda^{3}(1+xy)+\lambda^{2}(2+x+x^{2}+y+4xy+y^{2})+\\\
\lambda(1+3x+x^{2}+3y+4xy+x^{2}y+y^{2}+xy^{2}+x^{2}y^{2})+\\\
2(x+y+x^{2}y+xy^{2})$ (A.2)

followed by

$\gamma_{2}\;=\;\dfrac{N}{D}$ (A.3)

where

$\displaystyle N$ $\displaystyle=$
$\displaystyle(1+\lambda)\,\left[\lambda^{4}\,(1+xy)\;+\;\lambda^{3}\,(5+x+2x^{2}+y+10xy+2y^{2}+x^{2}y^{2})\right.$
$\displaystyle+\;\lambda^{2}\,(7+8x+8x^{2}+8y+26xy+4x^{2}y+2x^{3}y+8y^{2}+4xy^{2}+7x^{2}y^{2}+2xy^{3})$
$\displaystyle+\;\lambda\,(3+15x+8x^{2}+2x^{3}+15y+22xy+18x^{2}y+5x^{3}y+8y^{2}+18xy^{2}$
$\displaystyle\qquad+13x^{2}y^{2}+x^{3}y^{2}+2y^{3}+5xy^{3}+x^{2}y^{3})$
$\displaystyle+\;(8x+2x^{2}+2x^{3}+8y+5xy+18x^{2}y+x^{3}y+2y^{2}+18xy^{2}+4x^{2}y^{2}+4x^{3}y^{2}$
$\displaystyle\quad\;\left.+2y^{3}+xy^{3}+4x^{2}y^{3}+x^{3}y^{3})\right]$

and

$\displaystyle D$ $\displaystyle=$
$\displaystyle\lambda^{3}\,(1+xy)\;+\;\lambda^{2}\,(2+x+x^{2}+y+4xy+y^{2})$
$\displaystyle+\;\lambda\,(1+3x+x^{2}+3y+4xy+x^{2}y+y^{2}+xy^{2}+x^{2}y^{2})\;+\;2(x+y)(1+xy)$

It can then be shown that

  * (a)

$\gamma_{2}$ is not a polynomial in $x$ (when $y$ and $\lambda$ are given
fixed real values) unless $\lambda\in\\{-2,-1,+1\\}$ or $y\in\\{-1,+1\\}$.

  * (b)

$\gamma_{2}$ is not a polynomial in $y$ unless $\lambda\in\\{-2,-1,+1\\}$ or
$x\in\\{-1,+1\\}$.

  * (c)

$\gamma_{2}$ is not a polynomial in $\lambda$ unless $x\in\\{-1,+1\\}$ or
$y\in\\{-1,+1\\}$ or $x=y=0$.

We state the polynomials obtained from the foregoing specializations of
$\gamma_{2}$:

Specialization | $\gamma_{2}$
---|---
$\lambda=+1$ | $2(2+x)(2+y)$
$\lambda=-1$ | $0$
$\lambda=-2$ | $-1+x+y+xy/2$
$x=+1$ | $(2+\lambda)(3+\lambda+2y)$
$x=-1$ | $(1+\lambda)(4+\lambda-2y)$
$y=+1$ | $(2+\lambda)(3+\lambda+2x)$
$y=-1$ | $(1+\lambda)(4+\lambda-2x)$
$x=y=0$ | $(1+\lambda)(3+\lambda)$

These give rise to continued fractions as follows:

$\bm{\lambda=+1}$. By Theorem 3.3 specialized to $x_{1}=x_{2}=z_{\rm e}=z_{\rm
o}=x$, $y_{1}=y_{2}=y$, $u_{1}=u_{2}=v_{1}=v_{2}=w_{\rm e}=w_{\rm o}=1$, we
obtain a T-fraction with $\alpha_{2k-1}=(x+k-1)(y+k-1)$,
$\alpha_{2k}=(x+k)(y+k)$, $\delta_{1}=x^{2}$ and hence by contraction
(Proposition 2.1) a J-fraction with $\gamma_{0}=x(x+y)$,
$\gamma_{n}=2(x+n)(y+n)$ for $n\geq 1$, $\beta_{n}=(x+n-1)(x+n)(y+n-1)(y+n)$.

$\bm{x=+1}$. By the reversal map $i\mapsto 2n+1-i$, the weight $x^{{\rm
arec}(\sigma)}y^{{\rm erec}(\sigma)}$ is equivalent to $x^{{\rm
rec}(\sigma)}y^{{\rm earec}(\sigma)}$. Now apply Theorem 4.2 specialized to
$x_{1}=x_{2}=y$,
$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}=1$: we obtain a T-fraction with
$\alpha_{2k-1}=(\lambda+k-1)(y+k-1)$,
$\alpha_{2k}=(\lambda+k)(y+k-1+\lambda)$, $\delta_{1}=\lambda^{2}$. By
contraction this yields a J-fraction with $\gamma_{0}=\lambda(\lambda+y)$,
$\gamma_{n}=(\lambda+n)(\lambda+2n-1+2y)$ for $n\geq 1$,
$\beta_{n}=(\lambda+n-1)(\lambda+n)(y+n-1)(y+n-1+\lambda)$.

$\bm{y=+1}$. By Theorem 4.2 specialized to $x_{1}=x_{2}=z_{\rm e}=z_{\rm
o}=x$, $y_{1}={\widehat{y}}_{2}=u_{1}=u_{2}=v_{1}={\widehat{v}}_{2}=w_{\rm
e}=w_{\rm o}=1$, we obtain a T-fraction with
$\alpha_{2k-1}={(\lambda+k-1)(x+k-1)}$,
$\alpha_{2k}=(\lambda+k)(x+k-1+\lambda)$, $\delta_{1}=\lambda^{2}x^{2}$. By
contraction this yields a J-fraction with $\gamma_{0}=\lambda x(1+\lambda x)$,
$\gamma_{n}=(\lambda+n)(\lambda+2n-1+2x)$ for $n\geq 1$,
$\beta_{n}=(\lambda+n-1)(\lambda+n)(x+n-1)(x+n-1+\lambda)$.

$\bm{\lambda=-1}$. We conjecture a J-fraction with $\gamma_{0}=x(x-y)$,
$\gamma_{n}=0$ for $n\geq 1$, $\beta_{n}=-xy(1-x)(1-y)$. We have verified this
through $\gamma_{2}$ and $\beta_{3}$.

$\bm{\lambda=-2}$, $\bm{x=-1}$, $\bm{y=-1}$. These are polynomial through
$\gamma_{2}$ and $\beta_{3}$, but we are unable to guess the general formula,
and indeed we do not know whether they will continue to be polynomial at
higher orders.

$\bm{x=0}$. For all $n\geq 1$ and all $\sigma\in{\mathfrak{S}}_{n}$, the index
$n$ is an antirecord. Therefore, setting $x=0$ suppresses all permutations for
$n\geq 1$, and we have $P_{n}(0,y,\lambda)=\delta_{n0}$ (Kronecker delta). The
value of $\gamma_{2}$ stated in the table above is completely irrelevant,
because $\beta_{1}=0$.

$\bm{y=0}$. It is not difficult to show that the only permutation
$\sigma\in{\mathfrak{S}}_{n}$ with no exclusive records is the identity
permutation. (The index 1 is always a record, so if there are no exclusive
records it must be a fixed point; then the index 2 will be a record, and so
forth.) Therefore $P_{n}(x,0,\lambda)=\lambda^{2n}x^{2n}$. This gives an
S-fraction with $\alpha_{1}=\lambda^{2}x^{2}$ and $\alpha_{n}=0$ for $n\geq
2$. Equivalently, it gives a J-fraction with $\gamma_{0}=\lambda^{2}x^{2}$ and
all other coefficients zero. The value of $\gamma_{2}$ stated in the table
above is again completely irrelevant, because $\beta_{1}=0$.

## References

  * [1] D. Barsky, Congruences pour les nombres de Genocchi de 2e espèce [extrait d’un travail en commun avec Dominique Dumont], Groupe d’étude d’Analyse ultramétrique, 8e année (1980/81), Exposé no. 34, 13 pp.
  * [2] P. Biane, Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, European J. Combin. 14, 277–284 (1993).
  * [3] A. Burstein, S. Elizalde and T. Mansour, Restricted Dumont permutations, Dyck paths, and noncrossing partitions, Disc. Math. 306, 2851–2869 (2006).
  * [4] A. Burstein and O. Jones, Enumeration of Dumont permutations avoiding certain four-letter patterns, Discrete Math. Theor. Comput. Sci. 22, no. 2, paper #7 (2021).
  * [5] D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. 41, 305–318 (1974).
  * [6] D. Dumont, Pics de cycle et dérivées partielles, Séminaire Lotharingien de Combinatoire 13, article B13a (1986).
  * [7] D. Dumont, Further triangles of Seidel–Arnold type and continued fractions related to Euler and Springer numbers, Adv. Appl. Math. 16, 275–296 (1995).
  * [8] D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. 132, 37–49 (1994).
  * [9] D. Dumont and A. Randrianarivony, Sur une extension des nombres de Genocchi, European J. Combin. 16, 147–151 (1995).
  * [10] D. Dumont and G. Viennot, A combinatorial interpretation of the Seidel generation of Genocchi numbers, Ann. Discrete Math. 6, 77–87 (1980).
  * [11] D. Dumont and J. Zeng, Further results on the Euler and Genocchi numbers, Aequationes Math. 47, 31–42 (1994).
  * [12] R. Ehrenborg and E. Steingrímsson, Yet another triangle for the Genocchi numbers, European J. Combin. 21, 593–600 (2000).
  * [13] A. Elvey Price and A.D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, Electron. J. Combin. 27(4), article P4.6 (2020).
  * [14] G. Eneström, Die Schriften Eulers chronologisch nach den Jahren geordnet, in denen sie verfaßt worden sind, Jahresbericht der Deutschen Mathematiker-Vereinigung (Teubner, Leipzig, 1913).
  * [15] S.-P. Eu, T.-S. Fu, H.-H. Lai and Y.-H. Lo, Gamma-positivity for a refinement of median Genocchi numbers, arXiv:2103.09130 [math.CO].
  * [16] L. Euler, Methodis summandi superior ulterius promota, Chapter 7 of Institutiones Calculi Differentialis cum eius Usu in Analysi Finitorum ac Doctrina Serierum [Foundations of Differential Calculus, with Applications to Finite Analysis and Series] (Academiae Imperialis Scientiarum Petropolitanae, Saint Petersburg, 1755), pp. 479–514. Reprinted in Opera Omnia, ser. 1, vol. 10, pp. 368–395. Latin original available at http://eulerarchive.maa.org/pages/E212.html; English translation available at https://www.agtz.mathematik.uni-mainz.de/algebraische-geometrie/van-straten/euler-kreis-mainz/
  * [17] L. Euler, De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae 5, 205–237 (1760); reprinted in Opera Omnia, ser. 1, vol. 14, pp. 585–617. [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E247.html]
  * [18] L. Euler, De transformatione seriei divergentis $1-mx+m(m+n)x^{2}-m(m+n)(m+2n)x^{3}+\hbox{etc.}$ in fractionem continuam, Nova Acta Academiae Scientarum Imperialis Petropolitanae 2, 36–45 (1788); reprinted in Opera Omnia, ser. 1, vol. 16, pp. 34–46. [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E616.html]
  * [19] E. Feigin, The median Genocchi numbers, $q$-analogues and continued fractions, European J. Combin. 33, 1913–1918 (2012).
  * [20] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32, 125–161 (1980).
  * [21] D. Foata and G.-N. Han, Principes de combinatoire classique: Cours et exercices corrigés (Université Louis Pasteur, Strasbourg, Département de mathématique, 2008). Available on-line at https://irma.math.unistra.fr/~foata/AlgComb.pdf
  * [22] D. Foata and M.-P. Schützenberger, Nombres d’Euler et permutations alternantes, Technical report, University of Florida, 1971, 71 pp. Available on-line at http://www.emis.de/journals/SLC/books/foaschuetz1.html
  * [23] D. Foata and D. Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83, 31–59 (1990).
  * [24] E. Fusy and E. Guitter, Comparing two statistical ensembles of quadrangulations: A continued fraction approach, Ann. Inst. Henri Poincaré D 4, 125–176 (2017).
  * [25] A. Genocchi, Intorno all’espressione generale de’ numeri bernulliani, Annali di Scienze Mathematiche e Fisiche (Roma) 3, 395–405 (1852).
  * [26] G.-N. Han and J.-Y. Liu, Combinatorial proofs of some properties of tangent and Genocchi numbers, European J. Combin. 71, 99–110 (2018).
  * [27] G.-N. Han and J. Zeng, $q$-polynômes de Gandhi et statistique de Denert, Discrete Math. 205, 119–143 (1999).
  * [28] G.-N. Han and J. Zeng, On a $q$-sequence that generalizes the median Genocchi numbers, Ann. Sci. Math. Québec 23, 63–72 (1999).
  * [29] M. Josuat-Vergès, A $q$-analog of Schläfli and Gould identities on Stirling numbers, Ramanujan J. 46, 483–507 (2018).
  * [30] D.E. Knuth, The Art of Computer Programming, vol. 3, 2nd ed. (Addison-Wesley, Reading MA, 1998).
  * [31] A.G. Kuznetsov, I.M. Pak and A.E. Postnikov, Increasing trees and alternating permutations, Uspekhi Mat. Nauk 49, no. 6, 79–110 (1994) [= Russian Math. Surveys 49, no. 6, 79–114 (1994)].
  * [32] A.L. Lazar, The homogenized Linial arrangement and its consequences in enumerative combinatorics, Ph.D. thesis, University of Miami (August 2020), https://scholarship.miami.edu/discovery/delivery/01UOML_INST:ResearchRepository/12367619000002976?l#13367618990002976
  * [33] A. Lazar and M.L. Wachs, The homogenized Linial arrangement and Genocchi numbers, Combin. Theory 2, issue 1, paper no. 2 (2022), 34 pp.
  * [34] É. Lucas, Sur les théorèmes de Binet et de Staudt concernant les nombres de Bernoulli, Nouvelles Annales de Mathématiques (2e série) 16, 157–160 (1877).
  * [35] F.W. Olver, D.W. Lozier, R.F. Boisvert and C.W. Clark, eds., NIST Handbook of Mathematical Functions (U.S. Department of Commerce, Washington DC, 2010). Available on-line at http://dlmf.nist.gov
  * [36] The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org
  * [37] R. Oste and J. Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electron. J. Combin. 22, no. 2, #P2.8 (2015).
  * [38] Q. Pan and J. Zeng, Cycles of even-odd drop permutations and continued fractions of Genocchi numbers, arXiv:2108.03200 [math.CO].
  * [39] M. Pétréolle, A.D. Sokal and B.-X. Zhu, Lattice paths and branched continued fractions: An infinite sequence of generalizations of the Stieltjes–Rogers and Thron–Rogers polynomials, with coefficientwise Hankel-total positivity, preprint (2018), arXiv:1807.03271 [math.CO] at arXiv.org, to appear in the Memoirs of the American Mathematical Society.
  * [40] A. Randrianarivony, Fractions continues, $q$-nombres de Catalan et $q$-polynômes de Genocchi, Europ. J. Combin. 18, 75–92 (1997).
  * [41] A. Randrianarivony and J. Zeng, Une famille de polynômes qui interpole plusieurs suites classiques de nombres, Adv. Appl. Math. 17, 1–26 (1996).
  * [42] A. Randrianarivony and J. Zeng, Some equidistributed statistics on Genocchi permutations, Electron. J. Combin. 3, no. 2, Research Paper #22 (1996), 11 pp.
  * [43] L.J. Rogers, On the representation of certain asymptotic series as convergent continued fractions, Proc. London Math. Soc. (series 2) 4, 72–89 (1907).
  * [44] A.D. Sokal, The Euler and Springer numbers as moment sequences, Expositiones Mathematicae 38, 1–26 (2020).
  * [45] A.D. Sokal, Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials, in preparation.
  * [46] A.D. Sokal and J. Zeng, Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions, Adv. Appl. Math. 138, 102341 (2022).
  * [47] R.P. Stanley, A survey of alternating permutations, in: Combinatorics and Graphs, edited by R.A. Brualdi, S. Hedayat, H. Kharaghani, G.B. Khosrovshahi and S. Shahriari, Contemporary Mathematics #531 (American Mathematical Society, Providence, RI, 2010), pp. 165–196.
  * [48] T.J. Stieltjes, Sur la réduction en fraction continue d’une série procédant selon les puissances descendantes d’une variable, Ann. Fac. Sci. Toulouse 3, H1–H17 (1889).
  * [49] G. Viennot, Interprétations combinatoires des nombres d’Euler et de Genocchi, Séminaire de Théorie des Nombres (Bordeaux), Année 1980–81, exposé no. 11 (1981).
  * [50] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Notes de conférences données à l’Université du Québec à Montréal, septembre-octobre 1983. Available on-line at http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html
  * [51] J. Zeng, Sur quelques propriétés de symétrie des nombres de Genocchi, Discrete Math. 153, 319–333 (1996).