will use the same conventions for denoting Laguerre digraphs as in Section
6.2.

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

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

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

Stage (a): Going through $\bm{F=\\{2,4,\ldots,2n\\}}$:
We go through the even vertices in increasing order. From (7.13), we know that
$F={\rm Cdfall}(\sigma)\,\cup\,{\rm Evenfix}(\sigma)\,\cup\,{\rm
Cpeak}(\sigma)$ and $F^{\prime}={\rm Cdfall}(\sigma)\,\cup\,{\rm
Evenfix}(\sigma)\,\cup\,{\rm Cval}(\sigma)$ where $\sigma$ is the resulting
D-permutation obtained at the end of the inverse bijection.

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

######  Lemma 7.4.

The Laguerre digraph $\left.L\right|_{F}$ consists of the following connected
components:

  * •

loops on vertices $u\in{\rm Evenfix}$,

  * •

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

  * •

isolated vertices at $u\in G\,\cap\,G^{\prime}={\rm
Cdrise}(\sigma)\,\cup\,{\rm Oddfix}(\sigma)$.

Furthermore, it contains no directed cycles.

Stage (b): Going through $\bm{G=\\{2n-1,\ldots,3,1\\}}$:
We now go through the odd vertices in decreasing order. From (7.13), we know
that $G={\rm Cdrise}(\sigma)\,\cup\,{\rm Oddfix}(\sigma)\,\cup\,{\rm
Cval}(\sigma)$, and $G^{\prime}={\rm Cdrise}(\sigma)\,\cup\,{\rm
Oddfix}(\sigma)\,\cup\,{\rm Cpeak}(\sigma)$, where $\sigma$ is the resulting
D-permutation obtained at the end of the inverse bijection.

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

######  Lemma 7.5.

Let $u$ be the final vertex of a path with at least two vertices in
$\left.L\right|_{F\,\cup\,\\{2n-1,\ldots,2(n-j)+1\\}}$ for some index $j$
($1\leq j\leq n$). Then $u\in{\rm Cval}$.

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

######  Lemma 7.6.

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

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

######  Lemma 7.7.

Given a D-permutation $\sigma$ and associated sets $F^{\prime},G^{\prime}$ and
an odd $y\in\\{2n-1,\ldots,3,1\\}$ such that $y\in G\,\cap\,F^{\prime}={\rm
Cval}$. Then the following is true:

$\displaystyle\\#\\{u\in
G^{\prime}\backslash\\{\sigma(2n-1),\sigma(2n-3),\ldots,\sigma(y+2)\\}\colon\>u>y\\}$
$\displaystyle=$ $\displaystyle\lceil h_{y-1}/2\rceil+1$ (7.14)
$\displaystyle=$ $\displaystyle\lceil(h_{y}+1)/2\rceil$ $\displaystyle=$
$\displaystyle f_{y}$

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

###### Proof.

We first establish the following equality of sets:

$\\{u>y\colon\>\sigma^{-1}(u)\leq y\\}\;=\;\\{u\in
G^{\prime}\backslash\\{\sigma(2n-1),\sigma(2n-3),\ldots,\sigma(y+2)\\}\colon\>u>y\\}.$
(7.15)

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

$\\{u>y\colon\>\sigma^{-1}(u)\leq y\\}\;\supseteq\;\\{u\in
G^{\prime}\backslash\\{\sigma(2n-1),\sigma(2n-3),\ldots,\sigma(y+2)\\}\colon\>u>y\\}.$

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

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

$\displaystyle f_{y}$ $\displaystyle=$ $\displaystyle\\#\\{u\leq
y\colon\>\sigma(u)>y\\}$ (7.16) $\displaystyle=$
$\displaystyle\\#\\{u>y\colon\>\sigma^{-1}(u)\leq y\\}$

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

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

######  Lemma 7.8 (Counting of cycle closers for D-permutations).

Fix an almost-Dyck path $\omega$ of length $2n$ and construct
$F^{\prime},G^{\prime}$ (these are completely determined by $\omega$). Also
fix labels $\xi_{u}$ for vertices
$u\in\\{2,4,\ldots,2n\\}\,\cup\,\\{2n-1,\ldots,2(n-j)+1\\}$ satisfying (7.7).
Also let $y=2(n-j)-1\in G\cap F^{\prime}={\rm Cval}(\sigma)$. Then

  * (a)

The value of $\xi_{y}$ completely determines if $y$ is a cycle closer or not.

  * (b)

There is exactly one value $\xi_{y}\in\\{0,1,\ldots,\lceil h_{y-1}/2\rceil\\}$
that makes $y$ a cycle closer, and conversely.

Remark. Notice that one can also construct a variant of this interpretation
where stage (b) occurs before stage (a). The role of cycle closer will then be
played by cycle peak maximum. $\blacksquare$

####  7.1.3 Computation of weights

We can now compute the weights associated to the 0-Schröder path
${\widehat{\omega}}$ in Step 1. As our polynomial $\widehat{Q}$ defined in
(4.9) is almost the same as the polynomial introduced in [6, eq. (3.30)]
except for the extra factor $\lambda^{{\rm cyc}(\sigma)}$ and the index of
${{\sf a}}$, the dependence on cycle peaks, cycle double rises, cycle double
falls, and even and odd fixed points are same as in [6, eq. (3.30)] but the
treatment of cycle valleys is different. As we use the same bijection used to
obtain the continued fraction ([6, eq. (3.31)/(3.32)]) the computation of
weights corresponding to the variables ${{\sf b}},{{\sf c}},{{\sf d}},{{\sf
e}},{{\sf f}}$ are going to be exactly the same.

The only thing that remains is to compute the weights for the variables ${{\sf
a}}$. These correspond to steps $s_{i}$ in ${\widehat{\omega}}$ where $s_{i}$
is a rise starting at height $h_{i-1}=2k$ (so that $i$ is a cycle valley).
Then from Equations (7.6)/(7.8) we get $\lceil(h_{i-1}-1)/2\rceil=\lceil
h_{i}/2\rceil={\rm ucross}(i,\sigma)+{\rm unest}(i,\sigma)$ ($=k$). Also among
the possible choices of labels $\xi\in[0,k]$ there is exactly one which closes
a cycle and the others don’t (Lemma 7.8). Therefore, we obtain

$a_{2k}\;\stackrel{{\scriptstyle\rm
def}}{{=}}\;\sum_{\xi}a_{2k,\xi}\;=\;(\lambda+k){{\sf a}}_{2k}.$ (7.17)

This completes the proof of Theorem 4.4. ∎

Proof of Theorem 4.3.  Specialise Theorem 4.4 to

$\displaystyle{{\sf a}}_{k-1}$ $\displaystyle=$ $\displaystyle
p_{+1}^{k-1}\,\times\,y_{1}$ (7.18) $\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.19)
$\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.20)
$\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}$ (7.21)
$\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.22) $\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.23)

∎

Remark. Notice that the specialisation in the above proof is almost the same
as [6, eq. (6.40-45)], except for the treatment of ${{\sf a}}$. $\blacksquare$

Proof of Theorem 4.2.  Specialise Theorem 4.3 to

$p_{+1}=p_{-1}=p_{+2}=p_{-2}=q_{-1}=q_{+2}=q_{-2}=s_{\rm e}=s_{\rm o}=1.$
(7.24)

∎

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

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

####  7.2.1 Description of labels and inverse bijection

Step 2: Definition of the labels $\bm{\widehat{\xi}_{i}}$.

We recall the alternate definition of labels introduced in [6, eq. (6.46)]

$\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}$ (7.25)

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

######  Lemma 7.9 ([6, Lemma 6.7]).

We have

$\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}$ (7.26)

The labels $\widehat{\xi}_{i}$ satisfy the following inequalities:

######  Lemma 7.10 ([6, Lemma 6.8]).

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)}$ (7.27)

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

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

  * (a)

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

$\left\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}]\;.$ (7.28)

  * (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}]\;.$ (7.29)

Since the quantities (7.28), (7.29) are manifestly nonnegative, the
inequalities (7.27) are satisfied.

Step 3: Proof of bijection. The proof is similar to that presented in Step 3
Section 7.1.1, but using a value-based rather than position-based notion of
inversion table. Recall that if $S=\\{s_{1}<s_{2}<\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 [22, section 5.1.1]: We
start from an empty sequence, and insert $s_{k}$. Then we insert $s_{k-1}$ so
that the resulting word has $p^{\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)\\}$ (7.30)

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 (7.25). 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 (7.25).

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

######  Lemma 7.12.

Let $\sigma\in{\mathfrak{D}}_{2n}$ and let $\left(\omega,\widehat{\xi}\right)$
be its associated almost-Dyck path with an assignment of labels determined by
(7.25). Also let $G^{\prime}=\\{x_{1}<\ldots<x_{n}\\}$ and let
$F^{\prime}=\\{y_{1}<\ldots<y_{n}\\}$. Then

  * (a)

For any index $j$ ($1\leq j\leq n$), $\sigma^{-1}(x_{j})$ is the
$(\widehat{\xi}_{x_{j}}+1)$th smallest element of
$G\setminus\\{\sigma^{-1}(x_{1}),\ldots,\sigma^{-1}(x_{j-1})\\}$.

  * (b)

For any index $j$ ($1\leq j\leq n$), $\sigma^{-1}(y_{j})$ is the
$(\widehat{\xi}_{y_{j}}+1)$th largest element of
$F\setminus\\{\sigma^{-1}(y_{n}),\ldots,\sigma^{-1}(y_{j+1})\\}$.

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

####  7.2.2 Combinatorial interpretation using Laguerre digraphs

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

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

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

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

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

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

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

Stage (a): Going through $\bm{G^{\prime}}$:
From (7.30), we know that $G={\rm Cdrise}(\sigma)\,\cup\,{\rm
Oddfix}(\sigma)\,\cup\,{\rm Cval}(\sigma)$ and $G^{\prime}={\rm
Cdrise}(\sigma)\,\cup\,{\rm Oddfix}(\sigma)\,\cup\,{\rm Cpeak}(\sigma)$ where
$\sigma$ is the resulting D-permutation obtained at the end of the inverse
bijection.

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

######  Lemma 7.13.

The Laguerre digraph $\left.L^{\prime}\right|_{G^{\prime}}$ consists of the
following connected components:

  * •

loops on vertices $u\in{\rm Oddfix}$,

  * •

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

  * •

isolated vertices at $u\in F\,\cap\,F^{\prime}={\rm
Cdfall}(\sigma)\,\cap\,{\rm Evenfix}(\sigma)$.

Furthermore, it contains no directed cycles.

Stage (b): Going through $\bm{F^{\prime}}$:
We now go through the elements of $F^{\prime}$ in decreasing order. From
(7.30), we know that $F={\rm Cdfall}(\sigma)\,\cup\,{\rm
Evenfix}(\sigma)\,\cup\,{\rm Cpeak}(\sigma)$ and $F^{\prime}={\rm
Cdfall}(\sigma)\,\cup\,{\rm Evenfix}(\sigma)\,\cup\,{\rm Cval}(\sigma)$ where
$\sigma$ is the resulting D-permutation obtained at the end of the inverse
bijection. We let $F^{\prime}=\\{y_{1}<\ldots<y_{n}\\}$.

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

######  Lemma 7.14.

Let $u$ be the initial vertex of a path with at least two vertices in
$\left.L^{\prime}\right|_{G^{\prime}\,\cup\,\\{y_{n},\ldots,y_{j+1}\\}}$ for
some index $j$ ($1\leq j\leq n$). Then $u\in{\rm Cval}$.

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

######  Lemma 7.15.

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

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

######  Lemma 7.16.

Given a D-permutation $\sigma$ and associated sets $F,G,F^{\prime},G^{\prime}$
where $F^{\prime}=\\{y_{1}<\ldots<y_{n}\\}$, and an index $j$ ($1\leq j\leq
n$) such that $y_{j}\in G\,\cap\,F^{\prime}={\rm Cval}$. Then the following is
true:

$\\#\\{u\in
F\backslash\\{\sigma^{-1}(y_{n}),\ldots,\sigma^{-1}(y_{j+1})\\}\colon\>u>y_{j}\\}=\lceil
h_{y_{j}-1}/2\rceil+1=\lceil(h_{y_{j}}+1)/2\rceil=f_{y_{j}}$ (7.31)

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

###### Proof.

Notice the equality of the following sets:

$\\{u\in
F\backslash\\{\sigma^{-1}(y_{n}),\ldots,\sigma^{-1}(y_{j+1})\\}\colon\>u>y_{j}\\}\;=\;\\{u>y_{j}\>\colon\sigma(u)\leq
y_{j}\\}.$ (7.32)

Next use (7.3) to notice that the set on the right hand side of (7.32) has
cardinality $f_{y_{j}}$. ∎

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

######  Lemma 7.17 (Counting of cycle closers for D-permutations using variant
labels).

Fix an almost-Dyck path $\omega$ of length $2n$ and construct
$F^{\prime},G^{\prime}$ (these are completely determined by $\omega$). Let
$y_{j}\in G\cap F^{\prime}$. Also fix labels $\widehat{\xi}_{u}$ for vertices
$u\in G^{\prime}\,\cup\,\\{y_{n},\ldots,y_{j+1}\\}$ satisfying (7.27). Then

  * (a)

The value of $\widehat{\xi}_{y_{j}}$ completely determines if $y_{j}$ is a
cycle closer or not.

  * (b)

There is exactly one value $\widehat{\xi}_{y_{j}}\in\\{0,1,\ldots,\lceil
h_{y_{j}-1}/2\rceil\\}$ that makes $y_{j}$ a cycle closer, and conversely.

####  7.2.3 Computation of weights

Proof of Theorem 4.7.  The computation of weights is completely analogous to
what was done in Section 7.1.3, but using Lemma 7.17 in place of Lemma 7.8. We
leave the details to the reader: the upshot (similar to the proof of [6,
Theorem 3.12]) is that for cycle valleys and cycle peaks, “u” and “l” are
interchanged compared to Section 7.1.3, and all the statistics are primed. It
therefore completes the proof of Theorem 4.7. ∎

Proof of Theorems 4.6 and 4.13.  Comparing (4.14) with (4.16) we see that the
needed specialisation in (4.16) are the same as given in (7.18)–(7.23).
Inserting these into Theorem 4.7 gives Theorem 4.6.

Similarly, the proof of Theorem 4.13 follows by specialising the weights in
Theorem 4.6 to (7.24). ∎

##  8 Final remarks

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

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

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

## Acknowledgements

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

This work was supported by a teaching assistantship from the Department of
Mathematics, University College London.

## 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] N. Blitvić and E. Steingrimsson, Permutations, moments, measures, Trans. Amer. Math. Soc. 374, 5473-5508 (2021).
  * [3] P. Biane, Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, European J. Combin. 14, 277–284 (1993).
  * [4] S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math. 38, 149–163 (2007).
  * [5] B. Deb, A. Dyachenko, M. Pétréolle and A.D. Sokal, Lattice paths and branched continued fractions III: Generalizations of the Laguerre, rook and Lah polynomials, in preparation.
  * [6] B. Deb and A.D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, preprint (December 2022), arXiv:2212.07232 [math.CO] at arXiv.org.
  * [7] D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. 41, 305–318 (1974).
  * [8] D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. 132, 37–49 (1994).
  * [9] D. Dumont and J. Zeng, Further results on the Euler and Genocchi numbers, Aequationes Math. 47, 31–42 (1994).
  * [10] A. Elvey Price and A.D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, Electron. J. Combin. 27(4), article P4.6 (2020).
  * [11] L. Euler, De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae 5, 205–237 (1760); reprinted in Opera Omnia, ser. 1, vol. 14, pp. 585–617. [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E247.html]
  * [12] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32, 125–161 (1980).
  * [13] P. Flajolet and R. Sedgewick, Analytic Combinatorics (Cambridge University Press, Cambridge, 2009).
  * [14] D. Foata and V. Strehl, Combinatorics of Laguerre polynomials, in Enumeration and Design, edited by D.M. Jackson and S.A. Vanstone (Academic Press, Toronto, 1984), pp. 123–140.
  * [15] D. Foata and D. Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83, 31–59 (1990).
  * [16] D. Foata and G.-N. Han, Principes de combinatoire classique: Cours et exercices corrigés (Université Louis Pasteur, Strasbourg, Département de mathématique, 2008). Available on-line at https://irma.math.unistra.fr/~foata/AlgComb.pdf
  * [17] J. Françon and G. Viennot, Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi. Discrete Mathematics, 28(1) 21–35 (1979).
  * [18] E. Fusy and E. Guitter, Comparing two statistical ensembles of quadrangulations: A continued fraction approach, Ann. Inst. Henri Poincaré D 4, 125–176 (2017).
  * [19] G.-N. Han and J.-Y. Liu, Combinatorial proofs of some properties of tangent and Genocchi numbers, European J. Combin. 71, 99–110 (2018).
  * [20] G.-N. Han and J. Zeng, On a $q$-sequence that generalizes the median Genocchi numbers, Ann. Sci. Math. Québec 23, 63–72 (1999).
  * [21] M. Josuat-Vergès, A $q$-analog of Schläfli and Gould identities on Stirling numbers, Ramanujan J. 46, 483–507 (2018).
  * [22] D.E. Knuth, The Art of Computer Programming, vol. 3, 2nd ed. (Addison-Wesley, Reading MA, 1998).
  * [23] A.L. Lazar, The homogenized Linial arrangement and its consequences in enumerative combinatorics, Ph.D. thesis, University of Miami (August 2020),
  * [24] A. Lazar and M.L. Wachs, The homogenized Linial arrangement and Genocchi numbers, arXiv:1910.07651 [math.CO], Combin. Theory 2, issue 1, paper no. 2 (2022), 34 pp.
  * [25] É. Lucas, Sur les théorèmes de Binet et de Staudt concernant les nombres de Bernoulli, Nouvelles Annales de Mathématiques (2e série) 16, 157–160 (1877).
  * [26] The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org
  * [27] R. Oste and J. Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electron. J. Combin. 22, no. 2, #P2.8 (2015).
  * [28] A. Randrianarivony, Fractions continues, $q$-nombres de Catalan et $q$-polynômes de Genocchi, Europ. J. Combin. 18, 75–92 (1997).
  * [29] A. Randrianarivony and J. Zeng, Some equidistributed statistics on Genocchi permutations, Electron. J. Combin. 3, no. 2, Research Paper #22 (1996), 11 pp.
  * [30] A. Randrianarivony, Moments des polynômes orthogonaux unitaires de Sheffer généralisés et spécialisations, European J. Combin. 19, 507–518 (1998).
  * [31] A.D. Sokal, Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials, in preparation.
  * [32] A.D. Sokal, Multiple Laguerre polynomials: Combinatorial model and Stieltjes moment representation, Amer. Math. Soc. 150, 1997–2005 (2022).
  * [33] 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).
  * [34] R.P. Stanley, Enumerative Combinatorics, vol. 1, Second Edition, Cambridge University Press, 2012.
  * [35] G. Viennot, Interprétations combinatoires des nombres d’Euler et de Genocchi, Séminaire de Théorie des Nombres (Bordeaux), Année 1980–81, exposé no. 11 (1981). https://www.jstor.org/stable/44165433
  * [36] 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