# A decomposition of ballot permutations, pattern avoidance and Gessel walks

Zhicong Lin  Research Center for Mathematics and Interdisciplinary Sciences,
Shandong University, Qingdao 266237, P.R. China<EMAIL_ADDRESS>,  David G.L.
Wang  School of Mathematics and Statistics & Beijing Key Laboratory on MCAACI,
Beijing Institute of Technology, 102488 Beijing, R.R. China<EMAIL_ADDRESS>and  Tongyuan Zhao  College of Science, China University of Petroleum, 102249
Beijing, P.R. China<EMAIL_ADDRESS>
###### Abstract.

A permutation whose any prefix has no more descents than ascents is called a
ballot permutation. In this paper, we present a decomposition of ballot
permutations that enables us to construct a bijection between ballot
permutations and odd order permutations, which proves a set-valued extension
of a conjecture due to Spiro using the statistic of peak values. This
bijection also preserves the neighbors of the largest letter in permutations
and thus resolves a refinement of Spiro’s conjecture proposed by Wang and
Zhang. Our decomposition can be extended to well-labelled positive paths, a
class of generalized ballot permutations arising from polytope theory, that
were enumerated by Bernardi, Duplantier and Nadeau.

We will also investigate the enumerative aspect of ballot permutations
avoiding a single pattern of length $3$ and establish a connection between
$213$-avoiding ballot permutations and Gessel walks.

###### Key words and phrases:

Ballot permutations; Odd cycles; Peak values; Pattern avoidance; Gessel walks

##  1\. Introduction

The integer sequence

$\\{b_{n}\\}_{n\geq 0}=\\{1,1,1,3,9,45,225,1575,11025,99225,\ldots\\}$

defined by the exponential generating function

$\sum_{n\geq 0}b_{n}\frac{z^{n}}{n!}=\sqrt{\frac{1+z}{1-z}}$

has several algebraic or combinatorial interpretations (see [13, A000246]),
among which are two classes of restricted permutations:

  * •

permutations whose any prefix has no more descents than ascents, called ballot
permutations;

  * •

permutations which are the products of cycles with odd lengths, called odd
order permutations.

Denote by $\mathcal{B}_{n}$ and $\mathcal{O}_{n}$ the set of ballot
permutations and odd order permutations of length $n$, respectively. For
instance,

$\displaystyle\mathcal{B}_{4}$
$\displaystyle=\\{1234,1243,1324,1342,1423,2314,2341,2413,3412\\}\quad\text{and}$
$\displaystyle\mathcal{O}_{4}$
$\displaystyle=\\{\mathrm{id},(1)(234),(1)(243),(134)(2),(143)(2),(124)(3),(142)(3),(123)(4),(132)(4)\\}.$

The fact that $|\mathcal{O}_{n}|=b_{n}$ is an application of the combinatorial
Exponential Formula [17, Corollary 5.1.6], while $|\mathcal{B}_{n}|=b_{n}$ was
proved by Bernardi, Duplantier and Nadeau [1].

Recently, Spiro [15] found a refinement of
$|\mathcal{B}_{n}|=|\mathcal{O}_{n}|$. Let $\mathfrak{S}_{n}$ be the set of
permutations of $[n]:=\\{1,2,\ldots,n\\}$. For each
$\pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in\mathfrak{S}_{n}$ with $\pi_{i}=\pi(i)$,
define

$\displaystyle\mathsf{asc}(\pi)$
$\displaystyle=|\\{i\in[n-1]:\pi_{i}<\pi_{i+1}\\}|,$
$\displaystyle\mathsf{des}(\pi)$
$\displaystyle=|\\{i\in[n-1]:\pi_{i}>\pi_{i+1}\\}|\quad\text{and}$
$\displaystyle\mathsf{exc}(\pi)$ $\displaystyle=|\\{i\in[n-1]:\pi_{i}>i\\}|,$

called the ascent number, the descent number and the excedance number of
$\pi$, respectively. The distribution of descent number or excedance number
over permutations interprets the classical Eulerian polynomials $A_{n}(t)$
(see [16, Chapter 1]), which can be defined by

$\frac{A_{n}(t)}{(1-t)^{n+1}}=\sum_{k\geq 0}(k+1)^{n}t^{k}.$

In other words, the Eulerian polynomial $A_{n}(t)$ equals

(1.1)
$\sum_{\pi\in\mathfrak{S}_{n}}t^{\mathsf{des}(\pi)}=\sum_{\pi\in\mathfrak{S}_{n}}t^{\mathsf{exc}(\pi)}.$

Interestingly, Spiro introduced a variation of excedance numbers, whose
distribution over $\mathcal{O}_{n}$ has the same distribution as descent
numbers over $\mathcal{B}_{n}$. For a cycle $C=(c_{1}c_{2}\cdots c_{k})$, let

$\mathsf{casc}(C):=|\\{i\in[k]:c_{i}<c_{i+1}\text{ where
$c_{k+1}=c_{1}$}\\}|\quad\text{and}\quad\mathsf{cdes}(C):=k-\mathsf{casc}(C)$

be the cyclic ascent number and the cyclic descent number of $c$,
respectively. Note that $\mathsf{exc}(\pi)$ can be defined as

$\mathsf{exc}(\pi)=\sum_{C}\mathsf{casc}(C),$

where the sum runs over all cycles $C$ of $\pi$. Introduce the variation of
excedance number

$\widetilde{\mathsf{exc}}(\pi)=\sum_{C}\min(\mathsf{casc}(C),\mathsf{cdes}(C)),$

where the sum runs over all cycles $C$ of $\pi$. For example, if
$\pi=(1,8,5,6,4)(2,3,9)(7)$ written as product of cycles, then
$\widetilde{\mathsf{exc}}(\pi)=2+1+0=3$. The following conjecture was posed by
Spiro [15, Conjecture 1.2] with several important special cases verified.

######  Conjecture 1.1 (Spiro).

For $n\geq 1$,

(1.2)
$\sum_{\pi\in\mathcal{B}_{n}}t^{\mathsf{des}(\pi)}=\sum_{\pi\in\mathcal{O}_{n}}t^{\widetilde{\mathsf{exc}}(\pi)}.$

Wang and Zhang [20] proposed a refinement of Spiro’s conjecture by tracking
the neighbors of the largest letter in permutations. For $k\in[n]$ and
$\pi\in\mathfrak{S}_{n}$,

  * •

if $1<\pi^{-1}(k)=\ell<n$, then the letters $\pi(\ell-1)$ and $\pi(\ell+1)$
are called the neighbors of $k$ in $\pi$;

  * •

if $\pi(k)\neq k$, then the letters $\pi^{-1}(k)$ and $\pi(k)$ are called the
cyclic neighbors of $k$ in $\pi$.

######  Conjecture 1.2 (Wang and Zhang).

For any letters $i\neq j$, let $\mathcal{B}_{n}(i,j)$ (resp.
$\mathcal{O}_{n}(i,j)$) be the set of elements $\pi\in\mathcal{B}_{n}$ (resp.
$\pi\in\mathcal{O}_{n}$) such that $i$ and $j$ are neighbors (resp. cyclic
neighbors) of $n$ in $\pi$. Then,

(1.3)
$\sum_{\pi\in\mathcal{B}_{n}(i,j)}t^{\mathsf{des}(\pi)}=\sum_{\pi\in\mathcal{O}_{n}(i,j)}t^{\widetilde{\mathsf{exc}}(\pi)}.$

Motivated by Gessel’s combinatorial interpretation of a decomposition of
formal Laurent series in terms of lattice paths [7], Wang and Zhao [21] found
a reversal-concatenation decomposition of ballot permutations and proved
Conjecture 1.1. Afterwards, Sun and Zhao [19] completed a proof of Conjecture
1.2. However, both proofs of Conjectures 1.1 and 1.2 uses generating function
and a bijective proof of (1.2) still remains mysterious. On the other hand,
the so-called Foata’s first fundamental transformation (see [12, pp. 197-199])
on permutations establishes (1.1) bijectively. In this paper, we present an
algorithm that decomposes ballot permutations into odd cycles, which proves a
far reaching generalization of both Conjectures 1.1 and 1.2.

Let $\pi\in\mathfrak{S}_{n}$ and $k\in\\{3,4,\ldots,n\\}$. The value $k$ is
called a peak of $\pi$ if $1<\pi^{-1}(k)=\ell<n$ and
$\pi(\ell-1)<k>\pi(\ell+1)$, and is called a cyclic peak of $\pi$ if
$\pi^{-1}(k)<k>\pi(k)$. Deonte by $\mathrm{PEAK}(\pi)$ (resp.
$\mathsf{cPEAK}(\pi)$) the set of pairs $(b,\\{a,c\\})$ such that $b$ is a
peak (resp. cyclic peak) of $\pi$ and $a,c$ are neighbors (resp. cyclic
neighbors) of $b$ in $\pi$. For example, if
$\pi=839164752=(1,8,5,6,4)(2,3,9)(7)\in\mathfrak{S}_{9}$, then

$\displaystyle\mathrm{PEAK}(\pi)$
$\displaystyle=\\{(9,\\{1,3\\}),(6,\\{1,4\\}),(7,\\{4,5\\})\\},$
$\displaystyle\mathsf{cPEAK}(\pi)$
$\displaystyle=\\{(8,\\{1,5\\}),(6,\\{4,5\\}),(9,\\{2,3\\})\\}.$

######  Theorem 1.3.

There exists a bijection $\Psi:\mathcal{B}_{n}\rightarrow\mathcal{O}_{n}$ that
transforms the pair $(\mathsf{des},\mathrm{PEAK})$ to
$(\widetilde{\mathsf{exc}},\mathsf{cPEAK})$.

Our bijection $\Psi$ can be extended to well-labelled positive paths, a class
of generalized ballot permutations arising from polytope theory, that were
introduced and enumerated by Bernardi, Duplantier and Nadeau [1].

Pattern $p$ |  First values of $|\mathcal{B}_{n}(p)|$: | Notes | OEIS seq.
---|---|---|---
$123$ |  $1,1,2,2,5,5,14,14,32,32,\ldots$ |  Catalan number $C(\lceil\frac{n}{2}\rceil)$ | A208355
$321$ |  $1,1,3,9,28,90,297,1001,3432,\ldots$ |  $\frac{3}{n+1}{2n-2\choose n-2}$ for $n>1$ | A071724
$132$ |  $1,1,2,4,10,25,70,196,588,1764,\ldots$ |  Catalan product $C(\lfloor\frac{n}{2}\rfloor)C(\lfloor\frac{n+1}{2}\rfloor)$ | A005817
$231$ |  Wilf-equivalent to pattern $132$ |  | A005817
$213$ | $1,1,3,6,21,52,193,532,2034,\ldots$ |  Gessel walks ending on the $y$-axis | A151396
$312$ |  Wilf-equivalent to pattern $213$ |  | A151396

Table 1. Length-$3$ patterns for Ballot permutations.

We will also investigate the enumerative aspect of pattern avoiding ballot
permutations. We say a word $w=w_{1}w_{2}\cdots w_{n}\in\mathbb{Z}^{n}$ avoids
the pattern $\sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{k}\in\mathfrak{S}_{k}$
($k\leq n$) if there does not exist $i_{1}<i_{2}<\cdots<i_{k}$ such that the
subword $w_{i_{1}}w_{i_{2}}\cdots w_{i_{k}}$ of $w$ is order isomorphism to
$\sigma$. For a set $\mathcal{W}$ of words, let $\mathcal{W}(\sigma)$ be the
set of $\sigma$-avoiding words in $\mathcal{W}$. Two patterns $\sigma$ and
$\tau$ are said to be Wilf-equivalent over $\mathcal{W}$ if
$|\mathcal{W}(\sigma)|=|\mathcal{W}(\tau)|$. One of the most famous
enumerative results in pattern avoiding permutations, attributed to MacMahon
and Knuth (see [10, 14]), is that $|\mathfrak{S}_{n}(\sigma)|=C(n)$ for each
pattern $\sigma\in\mathfrak{S}_{3}$, where

$C(n):=\frac{1}{n+1}\binom{2n}{n}$

is the $n$-th Catalan number. For pattern avoiding ballot permutations, our
enumerative results are summarized in Table 1, of which the most intriguing
one is the connection between the pattern $213$ and Gessel walks.

A Gessel walk is a lattice path confined to the quarter plane $\mathbb{N}^{2}$
using steps from the set $\\{\uparrow,\downarrow,\nearrow,\swarrow\\}$. See
Fig. 1 for an example of Gessel walk. Around 2000, Ira Gessel conjectured that
the number of $2n$-step Gessel walks that starting and ending at $(0,0)$ has
the simple hypergeometric formula

$g_{n}=16^{n}\frac{(5/6)_{n}(1/2)_{n}}{(5/3)_{n}(2)_{n}},$

where $(a)_{n}:=a(a+1)\cdots(a+n-1)$ is the ascending factorial. The sequence
$\\{g_{n}\\}_{n\geq 0}$ appears as A135404 in the OEIS [13]. This attractive
conjecture remained open for several years and now has at least three proofs:
the original proof was given by Kauers, Koutschan and Zeilberger [9] with the
aid of computer, the second one was proposed by Bostan, Kurkova and Raschel
[4] using deep machinery of complex analysis, and an elementary approach was
finally found by Bousquet-Mélou [5] in $2016$. For the enumeration of other
walks with small steps in the quarter plane, the reader is referred to [6].

$x$$y$$(0,0)$$(0,2)$$(0,7)$$x$$y$$(0,0)$$(2,0)$$(7,0)$$y=x$ Figure 1. (Left) A
$31$-step Gessel walk starting at $(0,2)$ and ending at $(0,7)$; (Right) a
$19$-step Gouyou-Beauchamps walk starting at $(2,0)$ and ending at $(7,0)$.

For any $i,j\in\mathbb{N}$, let $\mathcal{G}(n;i,j)$ be the set of $n$-step
Gessel walks that starting at $(0,i)$ and ending at $(0,j)$.

######  Theorem 1.4.

For any $n\geq 0$,

$|\mathcal{B}_{n+1}(213)|=\sum_{j=0}^{n}|\mathcal{G}(n;0,j)|.$

Along the way to the proof of Theorem 1.4, we have been able to find a certain
class of $213$-avoiding ballot permutations that are in bijection with
$\mathcal{G}(n;i,j)$. Consequently, a new combinatorial interpretation for the
integer sequence $\\{g_{n}\\}_{n\geq 0}$ is discovered. A ballot permutation
$\pi\in\mathfrak{S}_{2n+1}$ is called a Dyck permutation if
$\mathsf{asc}(\pi)=\mathsf{des}(\pi)=n$. Bidkhori and Sullivant [2] showed
that Dyck permutations are enumerated by the Eulerian-Catalan numbers. A
specialization of our result indicates that $213$-avoiding Dyck permutations
of length $2n+1$ are counted by $g_{n}$.

The rest of this paper is organized as follows. In Section 2, we introduce a
technical bijection that forms the main ingredient in our construction of
$\Psi$. Based on this bijection, we construct $\Psi$ and extend it to well-
labelled positive paths in Section 3. Section 4 is devoted to the enumeration
of ballot permutations avoiding patterns of length $3$. Finally, in Section 5
we conclude our paper with several problems for further research.

##  2\. A technical bijection

Our decomposition of ballot permutations is based on a crucial bijection that
we introduce in this section.

Let us begin with the introduction of two useful combinatorial objects. Let
$A=\\{a_{1},a_{2},\ldots,a_{k}\\}$ be a set of positive integers such that
$a_{1}<a_{2}<\cdots<a_{k}$. A word $w$ over the alphabet $A\cup\\{\Box\\}$ is
called a box-permutation on $A$ if each letter in $A$ appears exactly once in
$w$ and

  * •

if $\Box$ does not appear in $w$, then $w=a_{1}a_{2}\cdots a_{k}$;

  * •

otherwise, the subword of $w$ formed by integers before the first (or after
the last) box has length at least one and is increasing, and the subword of
$w$ formed by integers between two successive boxes has length at least two
and is increasing.

Roughly speaking, box-permutations on $A$ are some permutations of $A$ that
are separated properly into several increasing segments by boxes. Denote by
$\mathcal{BP}(A)$ the set of all box-permutations on $A$. For example, if
$A=[3]$, then

$\mathcal{BP}(A)=\\{123,1\Box 23,2\Box 13,3\Box 12,12\Box 3,13\Box 2,23\Box
1\\}.$

A cycle $C=(c_{1}c_{2}\cdots c_{2\ell+1})$ of length $2\ell+1$, $\ell\geq 0$,
with letters from $A\cup\\{\Box\\}$ is called an odd box-cycle (resp. a
reverse odd box-cycle) on $A$ if each letter in $A$ appears in $C$ at most
once and

  * •

either $C=(a)$ for a single element $a\in A$,

  * •

or $\ell\geq 1$ and $C$ contains at least one box and each maximal component
of $C$ formed by only integers has length at least two and is increasing
clockwise (resp. counterclockwise).

For example, the cycle $(1356\Box 279\Box)$ is an odd box-cycle, while
$(96531\Box 72\Box)$ is a reverse odd box-cycle. Note that as an odd box-
cycle, $(1356\Box 279\Box)=(56\Box 279\Box 13)$, and its two maximal
components formed by only integers are $1356$ and $279$ (written in clockwise
order). A group of cycles is called a cyclic box-permutation on $A$ if

  * •

each cycle is either an odd box-cycle or a reverse odd box-cycle on $A$,

  * •

and each element of $A$ appears once in exactly one of the cycles.

For example, the cycles $(16\Box 279\Box)(53\Box)(4)(8)$ is a cyclic box-
permutation on $[9]$. Denote by $c\mathcal{BP}(A)$ the set of all cyclic box-
permutations on $A$. For example, if $A=[3]$, then

$c\mathcal{BP}(A)=\\{(1)(2)(3),(1)(23\Box),(1)(32\Box),(2)(13\Box),(2)(31\Box),(3)(12\Box),(3)(21\Box)\\}.$

For a (cyclic) box-permutation $\pi$, the set of all the $2$-subsets
$\\{a,b\\}$ such that $a$ and $b$ are the two neighbors of a certain box in
$\pi$ is called the box-neighbor-set of $\pi$. For instance, the box-neighbor-
set of the box-permutation $23\Box 4679\Box 18\Box 5$ is
$\\{\\{3,4\\},\\{1,9\\},\\{5,8\\}\\}$, while the box-neighbor-set of $(16\Box
279\Box)(53\Box)(4)(8)$ is $\\{\\{2,6\\},\\{1,9\\},\\{3,5\\}\\}$.

The reason to use box as a letter will become transparent in next section,
where each box in words receives a Dyck permutation. The following bijection
between $\mathcal{BP}(A)$ and $c\mathcal{BP}(A)$ forms the main ingredient for
our construction of the aforementioned map $\Psi$.

######  Theorem 2.1.

For any finite set $A=\\{a_{1}<a_{2}<\cdots<a_{k}\\}$ of positive integers,
there exists a box-neighbor-set-preserving bijection $\psi$ from
$\mathcal{BP}(A)$ to $c\mathcal{BP}(A)$.

A crucial lemma is needed before we proceed to prove Theorem 2.1. For any
$A=\\{a_{1}<a_{2}<\cdots<a_{k}\\}$, let us divide $\mathcal{BP}(A)$ into three
disjoint subsets as follows:

  * •

$\mathcal{BP}^{(1)}(A)$ is the set of box-permutations $\pi\in\mathcal{BP}(A)$
such that either $a_{1}$ appears in an even position of $\pi$, or
$\pi_{1}=a_{1}$ and $\pi_{2}=\Box$;

  * •

$\mathcal{BP}^{(2)}(A):=\\{\pi\in\mathcal{BP}(A):\pi_{1}=a_{1}\text{ and
$\pi_{2}\neq\Box$}\\}$;

  * •

$\mathcal{BP}^{(3)}(A):=\mathcal{BP}(A)\setminus(\mathcal{BP}^{(1)}(A)\cup\mathcal{BP}^{(2)}(A))$,
consisting of box-permutations $\pi\in\mathcal{BP}(A)$ such that $a_{1}$
appears in an odd position, other than the first position, of $\pi$.

For example, if $A=[3]$, then

$\mathcal{BP}^{(1)}(A)=\\{1\Box 23,23\Box
1\\},\mathcal{BP}^{(2)}(A)=\\{123,12\Box 3,13\Box 2\\}\text{ and
}\mathcal{BP}^{(3)}(A)=\\{2\Box 13,3\Box 12\\}.$

######  Lemma 2.2.

There exists a box-neighbor-set-preserving bijection $\phi$ between
$\mathcal{BP}^{(1)}(A)$ and $\mathcal{BP}^{(3)}(A)$.

###### Proof.

For any box-permutation $\pi\in\mathcal{BP}(A)$, denote by
$\mathsf{F}(\pi)=\pi_{1}$ the first letter of $\pi$, by $\mathsf{P}(\pi)$ the
position of $a_{1}$ and by $\mathsf{N}(\pi)$ the right neighbor (if any) of
$a_{1}$ in $\pi$. These three indices are useful in considering the inverse of
$\phi$. Now suppose $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in\mathcal{BP}^{(1)}(A)$
and we aim to construct $\phi(\pi)\in\mathcal{BP}^{(3)}(A)$ according to the
following four cases.

Case I: $\pi_{1}=a_{1}$ and $\pi_{2}=\Box$. In this case,

$\pi={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}\Box\pi_{3}}\pi_{4}\cdots\pi_{n}\text{
and define
}\phi(\pi)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{3}\Box
a_{1}}\pi_{4}\pi_{5}\cdots\pi_{n},$

the permutation obtained from $\pi$ by switching the first and the third
letters. Now for $\phi(\pi)=\pi^{\prime}$, we have
$\mathsf{P}(\pi^{\prime})=3$, $\pi^{\prime}_{2}=\Box$ and either $n=3$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$.

Case II: $\pi_{1}\neq a_{1}$. In this case, $a_{1}$ must be the right neighbor
of a box in $\pi$. Let $x$ be the left neighbor of the first box, if any, to
the right of $a_{1}$. Otherwise, no box appears to the right of $a_{1}$ and we
set $x=+\infty$. Let $a$ be the left neighbor of the first box in $\pi$.
Suppose that $\pi_{i}=a$, $\pi_{j}=a_{1}$ and $\pi_{k}=x$ (whenever
$x=+\infty$, set $k=n+1$) for some $i<j<k$. Let us consider the set of letters

$T:=\\{\pi_{\ell}:1\leq\ell<i\text{ or }j<\ell<k\\}$

and further distinguish three subcases.

  1. (1)

$T\neq\emptyset$ and $t=\min(T)<\min\\{a,x\\}$. In this case, either $t$ is
the first letter of $\pi$ or $t$ is the letter immediately after $a_{1}$. We
can flip $t$ back and forth between “the first letter of $\pi$” and “the
letter immediately after $a_{1}$” to get $\phi(\pi)$. To be more precise, if
$t=\pi_{1}$ is the first letter of $\pi$, then

$\pi={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t}\pi_{2}\cdots
a\Box\cdots\Box a_{1}\cdots$

and define

$\phi(\pi)=\pi_{2}\cdots a\Box\cdots\Box
a_{1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t}\cdots.$

Otherwise, $t=\pi_{j+1}$ and $\pi$ can be written as

$\pi=\pi_{1}\cdots a\Box\cdots\Box
a_{1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t}\cdots,$

then we define

$\phi(\pi)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t}\pi_{1}\cdots
a\Box\cdots\Box a_{1}\cdots.$

For the former $\phi(\pi)=\pi^{\prime}$, we have $\mathsf{P}(\pi^{\prime})\geq
3$, $\mathsf{F}(\pi^{\prime})>\mathsf{N}(\pi^{\prime})$ and
$\mathsf{N}(\pi^{\prime})$ is not the left neighbor of a box, while for the
later $\phi(\pi)=\pi^{\prime}$, we have $\mathsf{P}(\pi^{\prime})\geq 5$,
$\pi^{\prime}_{2}\neq\Box$ and either $n=\mathsf{P}(\pi^{\prime})$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$.

  2. (2)

$x<\pi_{1}<\cdots<\pi_{i}=a$ and $k=j+1$. In this case, $\pi$ has the form

$\pi=\pi_{1}\cdots a\Box\cdots\Box
a_{1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x\Box\pi_{k+2}}\cdots,$

then define

$\phi(\pi)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{k+2}\Box
x}\pi_{1}\cdots a\Box\cdots\Box a_{1}\cdots,$

i.e., delete the subword $x\Box\pi_{k+2}$ from $\pi$ and insert $\pi_{k+2}\Box
x$ at the beginning. Now for $\phi(\pi)=\pi^{\prime}$, we have
$\mathsf{P}(\pi^{\prime})\geq 7$, $\pi^{\prime}_{2}=\Box$ and either
$\mathsf{P}(\pi^{\prime})=n$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$.

  3. (3)

$\pi_{1}=a$ and $a<\pi_{j+1}<\cdots<\pi_{k}=x$ (possibly $j=n$). In this case,
$\pi$ has the form

$\pi={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a\Box\pi_{3}}\pi_{4}\cdots\Box
a_{1}\pi_{j+1}\cdots x\Box\cdots,$

then define

$\phi(\pi)=\pi_{4}\cdots\Box
a_{1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{3}\Box
a}\pi_{j+1}\cdots x\Box\cdots,$

i.e., delete the subword $a\Box\pi_{3}$ from $\pi$ and then insert
$\pi_{3}\Box a$ immediately after $a_{1}$. Now for $\phi(\pi)=\pi^{\prime}$,
we have $\mathsf{P}(\pi^{\prime})\geq 3$,
$\mathsf{F}(\pi^{\prime})>\mathsf{N}(\pi^{\prime})$ and
$\mathsf{N}(\pi^{\prime})$ is the left neighbor of a box.

It is clear from the above construction that the map
$\phi:\mathcal{BP}^{(1)}(A)\rightarrow\mathcal{BP}^{(3)}(A)$ preserves the
box-neighbor-set statistic. We observe that each of the four cases in the
construction of $\phi$ is reversible. Given any
$\pi^{\prime}=\pi^{\prime}_{1}\pi^{\prime}_{2}\cdots\pi^{\prime}_{n}\in\mathcal{BP}^{(3)}(A)$,
we consider the following four cases:

  * •

If $\mathsf{P}(\pi^{\prime})=3$, $\pi^{\prime}_{2}=\Box$ and either $n=3$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$, then we can apply the
reverse operation in Case I to get $\phi^{-1}(\pi^{\prime})$.

  * •

If $\mathsf{P}(\pi^{\prime})\geq 5$, $\pi^{\prime}_{2}\neq\Box$ and either
$\mathsf{P}(\pi^{\prime})=n$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$, then we can apply the
reverse operation in the second situation of Case II(1) to get
$\phi^{-1}(\pi^{\prime})$.

  * •

If $\mathsf{P}(\pi^{\prime})\geq 7$, $\pi^{\prime}_{2}=\Box$ and either
$\mathsf{P}(\pi^{\prime})=n$ or
$\mathsf{F}(\pi^{\prime})<\mathsf{N}(\pi^{\prime})$, then we can apply the
reverse operation in Case II(2) to get $\phi^{-1}(\pi^{\prime})$.

  * •

If $\mathsf{P}(\pi^{\prime})\geq 3$,
$\mathsf{F}(\pi^{\prime})>\mathsf{N}(\pi^{\prime})$ and
$\mathsf{N}(\pi^{\prime})$ is not the left neighbor of a box, then we can
apply the reverse operation in the first situation of Case II(1) to get
$\phi^{-1}(\pi^{\prime})$.

  * •

If $\mathsf{P}(\pi^{\prime})\geq 3$,
$\mathsf{F}(\pi^{\prime})>\mathsf{N}(\pi^{\prime})$ and
$\mathsf{N}(\pi^{\prime})$ is the left neighbor of any box, then we can apply
the reverse operation in Case II(3) to get $\phi^{-1}(\pi^{\prime})$.

Since the above five cases are disjoint and exhaust all possible
$\pi^{\prime}\in\mathcal{BP}^{(3)}(A)$, the map $\phi$ is a bijection. ∎

Now we are in a position to prove Theorem 2.1.

###### Proof of Theorem 2.1.

For any box-permutation $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in\mathcal{BP}(A)$,
we construct $\psi(\pi)\in c\mathcal{BP}(A)$ by factoring out odd cycles step
by step according to the following three cases:

  1. (1)

If $\pi\in\mathcal{BP}^{(2)}(A)$, then form the cycle $C_{1}=(a_{1})$ and the
box-permutation
$\tilde{\pi}=\pi_{2}\pi_{3}\cdots\pi_{n}\in\mathcal{BP}(A\setminus\\{a_{1}\\})$.
Define

$\psi(\pi)=\\{C_{1},\psi(\tilde{\pi})\\}.$

  2. (2)

If $\pi\in\mathcal{BP}^{(3)}(A)$, then the letter $a_{1}$ appears in position
$2\ell+1$ of $\pi$ for some $\ell\geq 1$. Form the odd box-cycle
$C_{1}=(a_{1}\pi_{1}\pi_{2}\cdots\pi_{2\ell})$ and the box-permutation
$\tilde{\pi}=\pi_{2\ell+2}\pi_{2\ell+3}\cdots\pi_{n}\in\mathcal{BP}(\tilde{A})$,
where $\tilde{A}=A\setminus\\{\pi_{i}:1\leq i\leq{2\ell+1}\text{ and
}\pi_{i}\neq\Box\\}$. Define

$\psi(\pi)=\\{C_{1},\psi(\tilde{\pi})\\}.$

  3. (3)

If $\pi\in\mathcal{BP}^{(1)}(A)$, then
$\pi^{\prime}=\phi(\pi)\in\mathcal{BP}^{(3)}(A)$. Now the letter $a_{1}$
appears in position $2\ell+1$ of $\pi^{\prime}$ for some $\ell\geq 1$. Form
the reverse odd box-cycle
$C_{1}=(a_{1}\pi^{\prime}_{2\ell}\pi^{\prime}_{2\ell-1}\cdots\pi^{\prime}_{1})$
and the box-permutation
$\tilde{\pi}^{\prime}=\pi^{\prime}_{2\ell+2}\pi^{\prime}_{2\ell+3}\cdots\pi^{\prime}_{n}\in\mathcal{BP}(\tilde{A})$,
where $\tilde{A}=A\setminus\\{\pi^{\prime}_{i}:1\leq i\leq{2\ell+1}\text{ and
}\pi^{\prime}_{i}\neq\Box\\}$. Define

$\psi(\pi)=\\{C_{1},\psi(\tilde{\pi}^{\prime})\\}.$

It is clear from the above construction that $\psi:\mathcal{BP}(A)\rightarrow
c\mathcal{BP}(A)$ is a bijection as
$\phi:\mathcal{BP}^{(1)}(A)\rightarrow\mathcal{BP}^{(3)}(A)$ does. ∎

######  Example 2.3.

Let $A=\\{2,4,5,6,7,8,9,11,14,16,17,18\\}$. Consider the box-permutation

$\pi={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}\,6\,\Box\,2\,7\,16\,\Box\,9\,11\,14\,\Box\,5\,18\,\Box\,8\,17\in\mathcal{BP}(A).$

Applying the operation in Case II(1) to $\pi$ we get

$\phi(\pi)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}6\,\Box\,2}\,4\,7\,16\,\Box\,9\,11\,14\,\Box\,5\,18\,\Box\,8\,17$

and so

(2.1)
$\psi(\pi)=\\{(6,2,\Box),\psi({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}\,7\,16\,\Box\,9\,11\,14\,\Box\,5\,18\,\Box\,8\,17)\\}=\\{(6,2,\Box),(4),\psi(\pi^{\prime})\\},$

where
$\pi^{\prime}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}7}\,16\,\Box\,9\,11\,14\,\Box\,5\,18\,\Box\,8\,17$.
Applying the operation in Case II(1) to $\pi^{\prime}$ we get
$\phi(\pi^{\prime})={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}16\,\Box\,9\,11\,14\,\Box\,5}\,7\,18\,\Box\,8\,17$
and so

$\displaystyle\psi(\pi^{\prime})$
$\displaystyle=\\{(16,5,\Box,14,11,9,\Box),\psi(7\,18\,\Box\,8\,17)\\}$
$\displaystyle=\\{(16,5,\Box,14,11,9,\Box),(7),(8,18,\Box),(17)\\}.$

Thus, by (2.1) we have

(2.2)
$\psi(\pi)=\\{(6,2,\Box),(4),(16,5,\Box,14,11,9,\Box),(7),(8,18,\Box),(17)\\}.$

Consider another box-permutation

$\pi={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2\,\Box\,8}\,9\,\Box\,7\,14\,17\,18\,\Box\,4\,11\,\Box\,5\,6\,\Box\,16\in\mathcal{BP}(A).$

Applying the operation in Case I to $\pi$ we get

$\phi(\pi)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}8\,\Box\,2}\,9\,\Box\,7\,14\,17\,18\,\Box\,4\,11\,\Box\,5\,6\,\Box\,16$

and so

(2.3) $\psi(\pi)=\\{(8,2,\Box),\psi(\pi^{\prime})\\},$

where
$\pi^{\prime}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}9\,\Box\,7}\,14\,17\,18\,\Box\,4\,11\,\Box\,5\,6\,\Box\,16$.
Applying the operation in Case II(3) to $\pi^{\prime}$ we get

$\phi(\pi^{\prime})=14\,17\,18\,\Box\,4\,7\,\Box\,9\,11\,\Box\,5\,6\,\Box\,16$

and so $\psi(\pi^{\prime})=\\{(18,17,14,4,\Box),\psi(\pi^{\prime\prime})\\}$,
where $\pi^{\prime\prime}=7\,\Box\,9\,11\,\Box\,5\,6\,\Box\,16$. Applying the
operation in Case II(2) to $\pi^{\prime\prime}$ we get

$\phi(\pi^{\prime\prime})=16\,\Box\,6\,7\,\Box\,9\,11\,\Box\,5$

and so $\psi(\pi^{\prime\prime})=(16,5,\Box,11,9,\Box,7,6,\Box)$. Therefore,
by (2.3) we have

(2.4)
$\psi(\pi)=\\{(8,2,\Box),(18,17,14,4,\Box),(16,5,\Box,11,9,\Box,7,6,\Box)\\}.$

##  3\.  The construction of $\Psi$ and extension

This section is devoted to the construction of our main bijection $\Psi$
stated in Theorem 1.3.

4627169111451881710131213201519$x$$y$ Figure 2. The ballot path associated
with the ballot permutation
$\pi=4\,6\,10\,13\,12\,1\,3\,2\,7\,16\,20\,9\,11\,14\,15\,5\,18\,19\,8\,17\in\mathcal{BP}_{20}$.

A lattice path confined to the quarter plane $\mathbb{N}^{2}$ using steps from
the set $\\{\nearrow,\searrow\\}$ is called a ballot path. A Dyck path is a
ballot path that begins with $(0,0)$ and ends at the $x$-axis. Every ballot
permutation $\pi\in\mathcal{B}_{n}$ can be associated with a ballot path
$L(\pi)$ starting at $(0,0)$ whose $i$th step is $U=(1,1)$ or $D=(1,-1)$
according to $\pi_{i}<\pi_{i+1}$ or $\pi_{i}>\pi_{i+1}$. The $i$th lattice
point of such a path will be labeled by the $i$th letter $\pi_{i}$ of $\pi$.
See Fig. 2 for an example of a labeled ballot path associated with a ballot
permutation. The letter $\pi_{i}$ (or the $i$th lattice point of $L(\pi)$) is
said to has height $h$ if

$\mathsf{asc}(\pi_{1}\pi_{2}\cdots\pi_{i})-\mathsf{des}(\pi_{1}\pi_{2}\cdots\pi_{i})=h.$

Clearly, a ballot permutation is a Dyck permutation if its associated ballot
path is a Dyck path, i.e., the height of the last letter has height zero. A
letter $\pi_{i}$ is called an ascent bottom (resp. a descent bottom) of $\pi$
if $\pi_{i}<\pi_{i+1}$ (resp. $\pi_{i-1}>\pi_{i}$).

The algorithm $\Psi$. Given a permutation $\pi\in\mathcal{B}_{n}$, we perform
the following three steps to get $\Psi(\pi)\in\mathcal{O}_{n}$:

  1. (1)

Firstly, we decompose $\pi$ into a pair $(D,\sigma)$, where $D$ is the set of
all maximal consecutive subwords of $\pi$ that are Dyck permutations of size
at least $3$ and $\sigma$ is the box-permutation obtained from $\pi$ by
replacing each maximal Dyck permutation (retaining its two boundary letters)
in $D$ by a box. We could find out all the maximal Dyck permutations (of size
at least $3$) like this:

     * (i)

find the right-most descent bottom with the minimum height in $\pi$, say
$\pi_{i}$ whose height is $h_{1}$; find the left-most ascent bottom with
height $h_{1}$, say $\pi_{i^{\prime}}$ with $i^{\prime}<i-1$; then the
interval $\pi_{i^{\prime}}\pi_{i^{\prime}+1}\cdots\pi_{i}$ forms the first
maximal Dyck permutation;

     * (ii)

if the suffix $\bar{\pi}=\pi_{i+1}\pi_{i+2}\cdots\pi_{n}$ is increasing, then
stop finding; otherwise, continue to extract the next maximal Dyck permutation
as (i) with $\pi$ replaced by $\bar{\pi}$.

For the example of ballot permutation in Fig. 2, $D$ contains four Dyck
permutations which are painting in red and
$\sigma={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4\,6}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2\,7\,16}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}9\,11\,14}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}5\,18}\,\Box{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\,8\,17}$
is a box-permutation.

  2. (2)

Next, using the map $\psi$ in Theorem 2.1 to form the cyclic box-permutation
$\psi(\sigma)$. Continuing with the example, we get the cyclic box-permutation

$\psi(\sigma)=(6,2,\Box)(4)(16,5,\Box,14,11,9,\Box)(7)(8,18,\Box)(17)$

from (2.2).

  3. (3)

Finally, inserting each Dyck permutation in $D$ back to its corresponding box
in $\psi(\sigma)$ properly to form $\Psi(\pi)$. Here proper means that for
each Dyck permutation $d=d_{1}d_{2}\cdots d_{k}$ from $D$,

     * •

if the odd box-cycle in $\psi(\sigma)$ containing the letters $d_{1}$ and
$d_{k}$ has the form $(\ldots,d_{1},\Box,d_{k},\ldots)$, then the resulting
odd cycle is $(\ldots,d_{1},d_{2},\ldots,d_{k},\ldots)$;

     * •

otherwise, the odd box-cycle in $\psi(\sigma)$ containing the letters $d_{1}$
and $d_{k}$ has the form $(\ldots,d_{k},\Box,d_{1},\ldots)$, and the resulting
odd cycle is $(\ldots,d_{k},d_{k-1},\ldots,d_{1},\ldots)$.

Since $\psi$ is proved in Theorem 2.1 to be box-neighbor-set-preserving, such
inserting operation is possible.

Continuing with the above example, after inserting all the four Dyck
permutations back to $\psi(\sigma)$, we get the odd order permutation

$\Psi(\pi)=(6,2,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3,1,12,13,10})(4)(16,5,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}15},14,11,9,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}20})(7)(8,18,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}19})(17).$

It is clear from the above construction that $\Psi$ is box-neighbor-set-
preserving. To see that $\Psi$ is bijective, we aim to construct its inverse
$\Psi^{-1}$ explicitly.

The algorithm $\Psi^{-1}$. Suppose that $\pi\in\mathcal{O}_{n}$ and
$\pi=C_{1}C_{2}\cdots C_{\ell}$, where each $C_{i}$ is an odd cycle. We
perform the following three steps to get $\Psi^{-1}(\pi)\in\mathcal{B}_{n}$:

  1. (I)

Firstly, we decompose $\pi$ into a pair $(D,\sigma)$, where

     * •

$D$ is the set of all maximal consecutive subwords of all cycles of $\pi$ that
are Dyck permutations of size at least $3$;

     * •

and $\sigma$ is the cyclic box-permutation formed by all cyclic box-
permutations obtained from all odd cycles of $\pi$ by replacing each maximal
Dyck permutation (retaining its two boundary letters) in $D$ by a box.

For each odd cycle $C=(c_{1}c_{2}\cdots c_{k})$ of $\pi$ with length $k\geq 3$
and $c_{1}$ is any cyclic peak of $C$ (i.e. $c_{k}<c_{1}>c_{2}$), we could
find out the maximal Dyck permutation that contains $c_{1}$ in $C$ like this:

     * •

For each $2\leq i\leq k$, define

$h_{i}^{+}=\mathsf{asc}(c_{1}c_{2}\cdots c_{i})-\mathsf{des}(c_{1}c_{2}\cdots
c_{i})$

and

$h_{i}^{-}=\mathsf{des}(c_{1}c_{k}c_{k-1}\cdots
c_{i})-\mathsf{asc}(c_{1}c_{k}c_{k-1}\cdots c_{i}).$

     * •

We need to distinguish two cases:

       1. (a)

If $h_{k}^{+}\geq 0$, then find the greatest index $r$ such that

$h_{r}^{+}=\min\\{h_{i}^{+}:2\leq i\leq k-1\\}$

and find the smallest index $l$, $l>r$, such that

$h_{l}^{-}=h_{r}^{+}\quad\text{and}\quad h_{l}^{-}=\min\\{h_{i}^{-}:l\leq
i\leq k\\}.$

       2. (b)

Otherwise, $h_{k}^{+}<0$. Find the smallest index $l$ such that

$h_{l}^{-}=\min\\{h_{i}^{-}:3\leq i\leq k\\}$

and then find the greatest index $r$, $r<l$, such that

$h_{r}^{+}=h_{l}^{-}\quad\text{and}\quad h_{r}^{+}=\min\\{h_{i}^{+}:2\leq
i\leq r\\}.$

     * •

The consecutive subword $c_{l}c_{l+1}\cdots c_{k}c_{1}c_{2}\cdots c_{r}$ of
$C$ is the maximal Dyck permutation in $C$ that contains $c_{1}$.

Note that no two maximal Dyck permutations of a cycle $C$ can overlap. For
example, the interior of each maximal Dyck permutation in

$\pi=(6,2,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3,1,12,13,10})(4)(16,5,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}15},14,11,9,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}20})(7)(8,18,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}19})(17).$

are colored red. Replacing the interior of each maximal Dyck permutation in
$\pi$ by a box gives the cyclic box-permutation

$\sigma=(6,2,\Box)(4)(16,5,\Box,14,11,9,\Box)(7)(8,18,\Box)(17).$

  2. (II)

Next, using the map $\psi^{-1}$ in Theorem 2.1 to form the box-permutation
$\psi^{-1}(\sigma)$. Continuing with the example, we get the box-permutation

$\psi^{-1}(\sigma)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4\,6}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2\,7\,16}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}9\,11\,14}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}5\,18}\,\Box{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\,8\,17}.$

  3. (III)

Finally, inserting each Dyck permutation in $D$ back to its corresponding box
in $\psi^{-1}(\sigma)$ properly (in the sense of step (3) of the algorithm
$\Psi$) to form $\Psi^{-1}(\pi)$.

Since the map $\psi$ in Theorem 2.1 is bijective, it is routine to check that
$\Psi$ and $\Psi^{-1}$ are inverse to each other, which completes the proof of
Theorem 1.3.

###  3.1. Extend $\Psi$ to well-labelled positive paths

In the rest of this section, we aim to extend $\Psi$ from ballot permutations
to well-labelled positive paths. As an application, the generating function
for the number of well-labelled positive paths is calculated smoothly.

A lattice path confined to the quarter plane $\mathbb{N}^{2}$ using steps from
the set $\\{\nearrow,\rightarrow,\searrow\\}$ is called a positive path. A
well-labelled positive path of size $n$ is a pair $(p,\pi)$, where

  * •

$p$ is a positive path with $n-1$ steps starting at $(0,0)$ and

  * •

$\pi$ is a permutation in $\mathfrak{S}_{n}$ satisfying $\pi_{i}<\pi_{i+1}$
(resp. $\pi_{i}>\pi_{i+1}$) whenever the $i$th step of $p$ is $\nearrow$
(resp. $\searrow$) for each $i\in[n-1]$.

See Fig. 3 for a well-labelled positive path of size $20$. Let
$\mathcal{P}_{n}$ be the set of all well-labelled positive paths of size $n$.

2897141718411561610151912113203$x$$y$ Figure 3.  A well-labelled positive path
of size $20$.

In order to extend $\Psi$ to well-labelled positive paths, we need to
introduce a generalization of odd cycles. A word with distinct letters from
$\mathbb{P}$ is called a cluster. For convenience, we underline a cluster when
it has at least two letters, i.e., size at least two. Two clusters are
disjoint if they contain no common letter. A cycle $C=(c_{1}c_{2}\cdots
c_{k})$ is called a cluster-cycle of order $k$ if all letters $c_{i}$’s are
disjoint clusters. Note that any cyclic shifting $(c_{i}c_{i+1}\cdots
c_{k}c_{1}\cdots c_{i-1})$ is considered as the same cluster-cycle as $C$. A
cluster-cycle of odd order is called an odd cluster-cycle. For example,
$(2,\underline{9\,1\,7},\underline{11\,13},3)$ is a cluster-cycle of order
$4$. A group of odd cluster-cycles is called an odd order cluster-permutation
(OCP for short) of size $n$ if

  * •

each cluster of the cycles is a word over $[n]$,

  * •

and each element of $[n]$ appears once in exactly one of the cluster of the
cycles.

For example, $(\underline{13},\underline{47},6)(\underline{25})$ is an OCP of
size $7$. Note that odd order permutations are OCPs without any underlined
cluster. Denote by $\mathcal{OC}_{n}$ the set of all OCPs of size $n$.

For the sake of convenience, we will represent a well-labelled positive path
$(p,\pi)\in\mathcal{P}_{n}$ by a permutation $\underline{\pi}$ whose letters
are clusters, that we call a cluster-permutation, obtained from $\pi$ by
underlining each pair of adjacency letters $(\pi_{i},\pi_{i+1})$ whenever the
$i$th step of $p$ is $\rightarrow$. For example, for the well-labelled
positive path $(p,\pi)$, its cluster-permutation representation is

$\underline{\pi}=2\,\underline{10\,15}\,19\,12\,8\,\underline{9\,1\,7}\,14\,17\,\underline{18\,4}\,\underline{11\,13}\,20\,\underline{3\,5}\,\underline{6\,16},$

which has $7$ clusters of size one, $5$ clusters of size two and $1$ cluster
of size three. Any cluster-permutation that represents a well-labelled
positive path is called a ballot cluster-permutation. In what follows,
elements in $\mathcal{P}_{n}$ are also considered as ballot cluster-
permutations. For a cluster $c=\underline{a_{1}a_{2}\ldots a_{k}}$, let
$c^{r}=\underline{a_{k}a_{k-1}\ldots a_{1}}$ be the reverse cluster of $c$.

######  Theorem 3.1.

There exists a bijection $\Phi:\mathcal{P}_{n}\rightarrow\mathcal{OC}_{n}$
such that for any $\underline{\pi}\in\mathcal{P}_{n}$

(3.1) $\text{$c$ is a cluster in $\underline{\pi}$ }\Longleftrightarrow\text{
either $c$ or $c^{r}$ is a cluster in $\Phi(\underline{\pi})$}.$

Moreover, $\Phi$ is an extension of $\Psi$, i.e.,
$\Phi|_{\mathcal{B}_{n}}=\Psi$.

Since the construction of $\Phi$ is almost the same as $\Psi$, we will
outlined it below and leave the rather routine details to the readers.

###### Sketch of the proof of Theorem 3.1.

A positive path starting at $(0,0)$ and ending at the $x$-axis is called a
Motzkin path. A ballot cluster-permutation $(p,\pi)\in\mathcal{P}_{n}$ is
called a Motzkin permutation if $p$ is a Motzkin path.

The algorithm $\Phi$. Given a ballot cluster-permutation
$\underline{\pi}=(p,\pi)\in\mathcal{P}_{n}$, we perform the following three
steps to get $\Psi(\pi)\in\mathcal{O}_{n}$:

  1. (1)

Firstly, we decompose $\underline{\pi}$ into a pair $(D,\sigma)$, where $D$ is
the set of all maximal consecutive subwords of $\underline{\pi}$ that are
Motzkin permutations of size at least $2$ and $\sigma$ is the box-permutation
obtained from $\pi$ by replacing each maximal Motzkin permutation (retaining
its two boundary letters) in $D$ by a box.

For the example of ballot cluster-permutation

$\underline{\pi}=2\,\underline{10\,15}\,19\,12\,8\,\underline{9\,1\,7}\,14\,17\,\underline{18\,4}\,\underline{11\,13}\,20\,\underline{3\,5}\,\underline{6\,16},$

in Fig. 3, $D$ contains four Motzkin permutations which are painting in red
and
$\sigma={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}8\,9}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}7\,14\,17\,18}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4\,11}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}5\,6}\,\Box\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}16}$
is a box-permutation.

  2. (2)

Next, using the map $\psi$ in Theorem 2.1 to form the cyclic box-permutation
$\psi(\sigma)$. Continuing with the example, we get the cyclic box-permutation

$\psi(\sigma)=(8,2,\Box),(18,17,14,4,\Box),(16,5,\Box,11,9,\Box,7,6,\Box)$

from (2.4).

  3. (3)

Finally, inserting each Motzkin permutation in $D$ back to its corresponding
box in $\psi(\sigma)$ properly to form $\Phi(\underline{\pi})$. Continuing
with the above example, after inserting all the four Motzkin permutations back
to $\psi(\sigma)$, we get the OCP

$\Phi(\underline{\pi})=(8,2,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\underline{10\,15},19,12}),(17,14,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\underline{4\,18}}),({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\underline{5\,3},20,\underline{13\,11}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\underline{9\,1\,7}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\underline{6\,16}}).$

It is clear from the construction that $\Phi$ satisfies property (3.1). The
construction of $\Phi^{-1}$ is almost identical to $\Psi^{-1}$ and will be
omitted. This proves that $\Phi$ is a bijection. The second statement is clear
from the construction of $\Phi$ above. ∎

Denote by $\mathcal{C}_{n}$ the set of OCPs in $\mathcal{OC}_{n}$ with only
one odd cluster-cycle and by $\mathcal{C}_{n,2k+1}$ the set of cluster-cycles
in $\mathcal{C}_{n}$ with order $2k+1$.

######  Lemma 3.2.

For any $n\geq 1$ and $0\leq k\leq\lfloor(n-1)/2\rfloor$,

$|\mathcal{C}_{n,2k+1}|={n\choose 2k+1}(n-1)!.$

###### Proof.

Every odd cluster-cycle in $\mathcal{C}_{n,2k+1}$ can be constructed in two
steps:

  1. (1)

arrange the letters $1,2,\ldots n$ in an ordinary cycle;

  2. (2)

among the $n$ pairs of adjacency letters, choose $n-2k-1$ pairs and underline
them.

There are $(n-1)$ ways to form one ordinary cycle and ${n\choose
n-2k-1}={n\choose 2k+1}$ ways to choose $n-2k-1$ pairs of adjacency letters to
underline them, the result then follows. ∎

It follows from Lemma 3.2 that the exponential generating function for odd
cluster-cycles by size and order is

$\displaystyle\sum_{n,k}|\mathcal{C}_{n,2k+1}|t^{2k+1}\frac{z^{n}}{n!}$
$\displaystyle=\sum_{n,k}{n\choose 2k+1}(n-1)!t^{2k+1}\frac{z^{n}}{n!}$
$\displaystyle=\sum_{n}\frac{z^{n}}{n}\sum_{k}{n\choose 2k+1}t^{2k+1}$
$\displaystyle=\sum_{n}\frac{z^{n}}{n}\frac{(1+t)^{n}-(1-t)^{n}}{2}$
$\displaystyle=\frac{1}{2}\ln\biggl{(}\frac{1-z+zt}{1-z-zt}\biggr{)}.$

Let us define the order of an OCP to be the sum of all its cluster-cycles,
i.e., the number of clusters in its cluster-cycles. Denote by
$\mathcal{OC}_{n,k}$ the set of all OCPs in $\mathcal{OC}_{n}$ with order $k$.
By the above e.g.f. for odd cluster-cycles and the permutation version of the
Compositional Formula [17, Corollary 5.1.8], the e.g.f. for OCPs by size and
order is

(3.2) $1+\sum_{n,k\geq
1}|\mathcal{OC}_{n,k}|t^{k}\frac{z^{n}}{n!}=\sqrt{\frac{1-z+zt}{1-z-zt}}.$

Define the order of a ballot cluster-permutation by the number of its
clusters. Denote by $\mathcal{P}_{n,k}$ the set of all ballot cluster-
permutations (or well-labelled positive paths) in $\mathcal{P}_{n}$ with order
$k$. An immediate consequence of Theorem 3.1 and Eq. (3.2) is the following
e.g.f. formula for well-labelled positive paths by size and order.

######  Corollary 3.3.

The e.g.f. for well-labelled positive paths by size and order is

(3.3) $1+\sum_{n,k\geq
1}|\mathcal{P}_{n,k}|t^{k}\frac{z^{n}}{n!}=\sqrt{\frac{1-z+zt}{1-z-zt}}.$

Note that Eq. (3.3) is equivalent to a result of Bernardi, Duplantier and
Nadeau [1, Corollary 13], which asserts that the number of well-labelled
positive paths $(p,\pi)\in\mathcal{P}_{n}$ with $p$ having $k$ horizontal
steps is

$\begin{cases}{n\choose k}{n-1\choose k}k![(n-k-1)!!]^{2}\qquad&\text{if $n-k$
is even,}\\\ {n\choose k}{n-1\choose
k}k!(n-k)!!(n-k-2)!!&\text{otherwise}.\end{cases}$

##  4\. Patterns in ballot permutations

This section deals with the enumerative results presented in Table 1.

It is known in [18, Page 85] (see also [11]) that $123$-avoiding up-down
permutations of length $n$ is counted by the Catalan number
$C(\lceil\frac{n}{2}\rceil)$. Since $123$-avoiding ballot permutations are
necessarily up-down, we have
$|\mathcal{B}_{n}(123)|=C(\lceil\frac{n}{2}\rceil)$.

######  Theorem 4.1.

For $n\geq 2$,

$|\mathcal{B}_{n}(321)|=C(n)-C(n-1)=\frac{3}{n+1}{2n-2\choose n-2}.$

###### Proof.

It is known that a permutation is $321$-avoiding if and only if both the
subsequence formed by its excedance values and the one formed by the remaining
non-excedance values are increasing. Thus, a $321$-avoiding permutation
$\pi\in\mathfrak{S}_{n}$ that is not a ballot permutation in
$\mathcal{B}_{n}(321)$ if and only if $\pi_{2}=1$. It follows that the map
$\pi\mapsto\pi^{\prime}$, where $\pi^{\prime}$ is obtained from $\pi$ by
removing its second entry and subtracting the other entries by one, sets up an
one-to-one correspondence between
$\mathfrak{S}_{n}(321)\setminus\mathcal{B}_{n}(321)$ and
$\mathfrak{S}_{n-1}(321)$. The result then follows from the fact [14] that
$|\mathfrak{S}_{n}(321)|=C(n)$. ∎

4852111610379$x$$y$$h$$b$ Figure 4. A $(h,b)$-ballot permutation
$2\,8\,5\,4\,11\,1\,6\,10\,3\,7\,9$ with $(h,b)=(2,4)$.

In order to prove Theorem 1.4, we need to consider another generalization of
ballot permutations. For two nonnegative integers $h$ and $b$, a permutation
$\pi\in\mathfrak{S}_{n+1}$ is called a $(h,b)$-ballot permutation if the
lattice path starting at $(0,h)$, whose $i$th step is $\nearrow$ (resp.
$\searrow$) if $\pi_{i}<\pi_{i+1}$ (resp. $\pi_{i}>\pi_{i+1}$) for each
$i\in[n]$, and ending exactly at $(n,b)$ does not pass below the $x$-axis. See
Fig. 4 for an example of $(2,4)$-ballot permutation. Note that each usual
ballot permutation is just a $(0,b)$-ballot permutation for certain $b\geq 0$.
Let $\mathcal{B}_{n+1}^{(h,b)}$ be the set of all $(h,b)$-ballot permutations
in $\mathfrak{S}_{n+1}$. The introduction of $(h,b)$-ballot permutation turns
out to be extremely important in our proof of Theorem 1.4. In fact, the
following generalization of Theorem 1.4 is true.

######  Theorem 4.2.

Let $E_{n}(h,b):=|\mathcal{B}_{n+1}^{(h,b)}(213)|$ and let
$F_{n}(h,b):=|\mathcal{G}(n;h,b)|$. Then,

(4.1) $E_{n}(h,b)=F_{n}(h,b)\qquad\text{for any integers $n,h,b\geq 0$}.$

We will prove this equinumerosity by showing $E_{n}(h,b)$ and $F_{n}(h,b)$
share the same recurrence relation.

######  Lemma 4.3.

The number of Gessel walks $F_{n}(h,b)$ satisfies the recurrence relation:

(4.2) $F_{n}(h,b)=F_{n-1}(h+1,b)+F_{n-1}(h-1,b)+\sum_{0\leq i\leq
n-2\atop{0\leq a}}F_{i}(h+1,a+1)F_{n-2-i}(a,b)$

for $n\geq 1$ and $h,b\geq 0$ with initial condition $F_{0}(h,b)=\chi(h=b=0)$.

###### Proof.

Consider the first time after the starting point that a Gessel walk
$G\in\mathcal{G}(n;h,b)$ arrives the $y$-axis:

  1. (1)

The first step of $G$ is $\uparrow$. The number of such walks is
$F_{n-1}(h+1,b)$.

  2. (2)

The first step of $G$ is $\downarrow$. The number of such walks is
$F_{n-1}(h-1,b)$.

  3. (3)

The first step of $G$ is $\nearrow$. For fixed integers $a,i\geq 0$, the
number of such walks that first arrive the $y$-axis at $(0,a)$ after $i+2$
steps is $F_{i}(h+1,a+1)F_{n-2-i}(a,b)$.

Summing over all the above three cases gives (4.2). ∎

For integers $1\leq k\leq n$, let $[k,n]:=\\{k,k+1,\ldots,n\\}$. Lemma 4.3
together with the following recursion for $E_{n}(h,b)$ proves Theorem 4.2.

######  Lemma 4.4.

The number of permutations $E_{n}(h,b)$ satisfies the recurrence relation:

(4.3) $E_{n}(h,b)=E_{n-1}(h+1,b)+E_{n-1}(h-1,b)+\sum_{0\leq i\leq
n-2\atop{0\leq a}}E_{i}(h+1,a+1)E_{n-2-i}(a,b)$

for $n\geq 1$ and $h,b\geq 0$ with initial condition $E_{0}(h,b)=\chi(h=b=0)$.

###### Proof.

Any $213$-avoiding permutation $\pi\in\mathfrak{S}_{n+1}(213)$ with
$\pi_{1}=k$ can be decomposed into $k\pi^{\prime}\pi^{\prime\prime}$, where
$\pi^{\prime}$ is a $213$-avoiding permutation of $[k+1,n+1]$ and
$\pi^{\prime\prime}$ is a $213$-avoiding permutation of $[k-1]$. Now consider
the first letter of a permutation $\pi\in\mathcal{B}_{n+1}^{(h,b)}(213)$:

  1. (1)

If $\pi_{1}=1$, then $\pi=1\pi^{\prime}$ with $\pi^{\prime}$ a $213$-avoiding
$(h+1,b)$-ballot permutation of $[2,n+1]$. There are $E_{n-1}(h+1,b)$ such
permutations arising in this case.

  2. (2)

If $\pi_{1}=n+1$, then $\pi=(n+1)\pi^{\prime\prime}$ with $\pi^{\prime\prime}$
a $213$-avoiding $(h-1,b)$-ballot permutation of $[n]$. There are
$E_{n-1}(h-1,b)$ such permutations arising in this case.

  3. (3)

If $\pi_{1}=n-i$ for some $0\leq i\leq n-2$, then
$\pi=(n-i)\pi^{\prime}\pi^{\prime\prime}$, where $\pi^{\prime}$ is a
$213$-avoiding permutation of $[n-i+1,n+1]$ and $\pi^{\prime\prime}$ is a
$213$-avoiding permutation of $[n-i-1]$. Moreover, if $\pi^{\prime}$ is a
$(h+1,a+1)$-ballot permutation for some $a\geq 0$, then $\pi^{\prime\prime}$
is a $(a,b)$-ballot permutation. Thus, there are
$E_{i}(h+1,a+1)E_{n-2-i}(a,b)$ such permutations arising in this case for any
fixed integer $a\geq 0$.

Summing over all the above three cases gives (4.3). ∎

We have two remarks concerning our approach to (4.1).

######  Remark 4.5.

The proofs of Lemmas 4.3 and 4.4 actually induce a recursive bijection between
$\mathcal{G}(n;h,b)$ and $\mathcal{B}_{n+1}^{(h,b)}(213)$.

######  Remark 4.6.

By considering the position of the letter $1$, any
$\pi\in\mathfrak{S}_{n+1}(213)$ can be decomposed as
$\pi=\pi^{\prime}1\pi^{\prime\prime}$, where $\pi^{\prime}$ and
$\pi^{\prime\prime}$ are both $213$-avoiding and all letters in $\pi^{\prime}$
are greater than that in $\pi^{\prime\prime}$. This consideration leads to
another recursion for $E_{n}(h,b)$ essentially different with (4.3):

(4.4) $E_{n}(h,b)=E_{n-1}(h+1,b)+E_{n-1}(h,b+1)+\sum_{0\leq i\leq
n-2\atop{0\leq a}}E_{i}(h,a+1)E_{n-2-i}(a+1,b).$

We failed to find a parallel decomposition of Gessel walks that could lead to
the same recursion as above for $F_{n}(h,b)$. It remains mysterious to find
such a decomposition for Gessel walks.

An interesting consequence of Theorem 4.2 is a new interpretation of $g_{n}$.

######  Corollary 4.7.

The number of $213$-avoiding Dyck permutations of length $n$ is

$g_{n}=16^{n}\frac{(5/6)_{n}(1/2)_{n}}{(5/3)_{n}(2)_{n}},$

which enumerates $2n$-step Gessel walks that starting and ending at $(0,0)$.

Regarding $231$-avoiding ballot permutations, we have a connection to another
class of lattice walks that was studied by Gouyou-Beauchamps in [8]. A Gouyou-
Beauchamps walk (GB walk for short) is a lattice path confined to the quarter
plane $\mathbb{N}^{2}$ using steps from the set
$\\{\uparrow,\downarrow,\leftarrow,\rightarrow\\}$ and lying weakly below the
main diagonal $y=x$. See Fig. 1 (right graph) for an example of GB walk. A
nice enumerative result due to Gouyou-Beauchamps [8] asserts that the number
of $n$-step GB walks that starting at $(0,0)$ and ending at $x$-axis is the
product of Catalan numbers

$C(\lfloor(n+1)/2\rfloor)C(\lfloor(n+2)/2\rfloor).$

This integer sequence appears as A005817 in the OEIS [13], where several other
intriguting combinatorial interpretations are known.

For any $h,b\in\mathbb{N}$, let $\mathcal{H}(n;h,b)$ be the set of $n$-step GB
walks that starting at $(h,0)$ and ending at $(b,0)$. The following result for
$231$-avoiding ballot permutations is parallel to Theorem 4.2.

######  Theorem 4.8.

Let $G_{n}(h,b):=|\mathcal{B}_{n+1}^{(h,b)}(231)|$ and let
$H_{n}(h,b):=|\mathcal{H}(n;h,b)|$. Then,

(4.5) $G_{n}(h,b)=H_{n}(h,b)\qquad\text{for any integers $n,h,b\geq 0$}.$

In particular, $|\mathcal{B}_{n}(231)|=C(\lfloor
n/2\rfloor)C(\lfloor(n+1)/2\rfloor)$.

We will prove Theorem 4.8 by showing $G_{n}(h,b)$ and $H_{n}(h,b)$ share the
same recurrence relation.

######  Lemma 4.9.

The number of GB walks $H_{n}(h,b)$ satisfies the recurrence relation:

(4.6) $H_{n}(h,b)=H_{n-1}(h+1,b)+H_{n-1}(h-1,b)+\sum_{0\leq i\leq
n-2\atop{0\leq a}}H_{i}(h-1,a)H_{n-2-i}(a+1,b)$

for $n\geq 1$ and $h,b\geq 0$ with initial condition $H_{0}(h,b)=\chi(h=b=0)$.

###### Proof.

Consider the first time after the starting point that a GB walk
$H\in\mathcal{H}(n;h,b)$ visits the $x$-axis:

  1. (1)

The first step of $H$ is $\rightarrow$. The number of such walks is
$H_{n-1}(h+1,b)$.

  2. (2)

The first step of $H$ is $\leftarrow$. The number of such walks is
$H_{n-1}(h-1,b)$.

  3. (3)

The first step of $H$ is $\uparrow$. For fixed integers $a,i\geq 0$, the
number of such walks that first return the $x$-axis at $(a+1,0)$ after $i+2$
steps is $H_{i}(h-1,a)H_{n-2-i}(a+1,b)$.

Summing over all the above three cases gives (4.6). ∎

In view of Lemma 4.9, the following recurrence relation for $G_{n}(h,b)$
proves Theorem 4.8.

######  Lemma 4.10.

The number of permutations $G_{n}(h,b)$ satisfies the recurrence relation:

(4.7) $G_{n}(h,b)=G_{n-1}(h+1,b)+G_{n-1}(h-1,b)+\sum_{0\leq i\leq
n-2\atop{0\leq a}}G_{i}(h-1,a)G_{n-2-i}(a+1,b)$

for $n\geq 1$ and $h,b\geq 0$ with initial condition $G_{0}(h,b)=\chi(h=b=0)$.

###### Proof.

Any $231$-avoiding permutation $\pi\in\mathfrak{S}_{n+1}(231)$ with
$\pi_{1}=k$ can be decomposed into $k\pi^{\prime}\pi^{\prime\prime}$, where
$\pi^{\prime}$ is a $231$-avoiding permutation of $[k-1]$ and
$\pi^{\prime\prime}$ is a $231$-avoiding permutation of $[k+1,n+1]$. Now
consider the first letter of a permutation
$\pi\in\mathcal{B}_{n+1}^{(h,b)}(231)$:

  1. (1)

If $\pi_{1}=1$, then $\pi=1\pi^{\prime}$ with $\pi^{\prime}$ a $231$-avoiding
$(h+1,b)$-ballot permutation of $[2,n+1]$. There are $G_{n-1}(h+1,b)$ such
permutations arising in this case.

  2. (2)

If $\pi_{1}=n+1$, then $\pi=(n+1)\pi^{\prime\prime}$ with $\pi^{\prime\prime}$
a $231$-avoiding $(h-1,b)$-ballot permutation of $[n]$. There are
$G_{n-1}(h-1,b)$ such permutations arising in this case.

  3. (3)

If $\pi_{1}=i+2$ for some $0\leq i\leq n-2$, then
$\pi=(i+2)\pi^{\prime}\pi^{\prime\prime}$, where $\pi^{\prime}$ is a
$231$-avoiding permutation of $[i+1]$ and $\pi^{\prime\prime}$ is a
$231$-avoiding permutation of $[i+3,n+1]$. Moreover, if $\pi^{\prime}$ is a
$(h-1,a)$-ballot permutation for some $a\geq 0$, then $\pi^{\prime\prime}$ is
a $(a+1,b)$-ballot permutation. Thus, there are $G_{i}(h-1,a)G_{n-2-i}(a+1,b)$
such permutations arising in this case for any fixed integer $a\geq 0$.

Summing over all the above three cases gives (4.7). ∎

In Table 1, we still need to prove the Wilf-equivalences of $213$ and $312$
and of $132$ and $231$ over ballot permutations. They are direct consequence
of two simple recursive bijections
$\varphi:\mathfrak{S}_{n}(213)\rightarrow\mathfrak{S}_{n}(312)$ and
$\eta:\mathfrak{S}_{n}(132)\rightarrow\mathfrak{S}_{n}(231)$ that preserve the
positions of descents:

  * •

If $\pi\in\mathfrak{S}_{n}(213)$, then $\pi=\pi^{\prime}1\pi^{\prime\prime}$.
Define $\varphi(\pi)=\varphi(\pi^{\prime\prime})1\varphi(\pi^{\prime})$.

  * •

If $\pi\in\mathfrak{S}_{n}(132)$, then $\pi=\pi^{\prime}n\pi^{\prime\prime}$.
Define $\eta(\pi)=\eta(\pi^{\prime\prime})n\eta(\pi^{\prime})$.

##  5\. Final remarks, open problems

This paper focus mainly on the enumerative aspect of ballot permutations. Two
main achievements are:

  1. (1)

A Foata-style bijection between ballot permutations and odd order permutations
that not only proves bijectively two conjectures uniformly but also can be
extended perfectly to well-labelled positive paths, a class of generalized
ballot permutations arising from polytope theory.

  2. (2)

Complete the enumeration of ballot permutations avoiding a pattern of length
$3$. Connections with Gessel walks and Gouyou-Beauchamps walks are
established.

Our work can be extended in several directions. For ${\bf
m}=(m_{1},\ldots,m_{n})\in\mathbb{N}^{n}$, let $\mathfrak{S}_{{\bf m}}$ be the
set of multipermutations of $\\{1^{m_{1}},2^{m_{2}},\ldots,n^{m_{n}}\\}$. An
element $\pi\in\mathfrak{S}_{{\bf m}}$ is called a ballot multipermutations if
for each $i$, $1\leq i<\sum_{i=1}^{n}m_{n}$, there holds

$|\\{j\in[i]:\pi_{j}<\pi_{j+1}\\}|\geq|\\{j\in[i]:\pi_{j}>\pi_{j+1}\\}|.$

######  Problem 5.1.

For fixed ${\bf m}\in\mathbb{N}^{n}$, can the ballot multipermutations in
$\mathfrak{S}_{{\bf m}}$ be enumerated?

For classical patterns in ballot permutations, one further direction to
continue would be to consider a pair of length-$3$ patterns or a single
pattern of length $4$. Moreover, it would also be interesting to explore
systematically ballot permutations avoid consecutive patterns or the more
general vincular patterns [10].

For any $i,j\in\mathbb{N}$, let $g_{n}(i,j)$ be the number of $n$-step Gessel
walks that starting at $(0,0)$ and ending at $(i,j)$. Bostan and Kauers [3]
proved that the trivariate generating function $\sum_{n,i,j\geq
0}g_{n}(i,i)t^{n}x^{i}y^{j}$ is algebraic. In view of their result, we pose
the following problem for further research.

######  Problem 5.2.

Are the generating functions for Gessel walks and Gouyou-Beauchamps walks

$F(t,x,y)=\sum_{n,h,b\geq 0}F_{n}(h,b)t^{n}x^{h}y^{b}\quad\text{and}\quad
H(t,x,y)=\sum_{n,h,b\geq 0}H_{n}(h,b)t^{n}x^{h}y^{b}$

algebraic?

## Acknowledgement

Lin was supported by the National Science Foundation of China grant 11871247
and the project of Qilu Young Scholars of Shandong University. Wang was
supported by the National Science Foundation of China grant 11671037. Zhao was
supported by the Science Foundation of China University of Petroleum, Beijing
(Grant No. 2462020YXZZ004).

## References

  * [1] O. Bernardi, B. Duplantier and P. Nadeau, A bijection between well-labelled positive paths and matchings, Sém. Lothar. Combin., 63 (2010), Article B63e.
  * [2] H. Bidkhori and S. Sullivant, Eulerian-catalan numbers, Electron. J. Combin., 18 (2011), #P187.
  * [3] A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic (With an appendix by Mark van Hoeij), Proc. Amer. Math. Soc., 138 (2010), 3063–3078.
  * [4] A. Bostan, I. Kurkova, K. Raschel, A human proof of Gessel’s lattice path conjecture, Trans. Amer. Math. Soc., 369 (2017), 1365–1393.
  * [5] M. Bousquet-Mélou, An elementary solution of Gessel’s walks in the quadrant, Adv. Math., 303 (2016), 1171–1189.
  * [6] M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, Algorithmic probability and combinatorics, 1–39, Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010.
  * [7] I.M. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A, 28 (1980), 321–337.
  * [8] D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableaux de Young, pp. 112–125 of "Combinatoire énumérative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
  * [9] M. Kauers, C. Koutschan and D. Zeilberger, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA, 106 (2009) 11502–11505.
  * [10] S. Kitaev, Patterns in permutations and words, Springer Science & Business Media, 2011.
  * [11] J.B. Lewis, Pattern avoidance for alternating permutations and Young tableaux, J. Combin. Theory Ser. A, 118 (2011), 1436–1450.
  * [12] M. Lothaire, Combinatorics on words, Cambridge University Press, 1997 (Encyclopedia of Math. and its Appl., v. 17).
  * [13] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2020.
  * [14] R. Simion, F. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.
  * [15] S. Spiro, Ballot permutations and odd order permutations, Discrete Math., 343 (2020), 111869.
  * [16] R.P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge Stud. Adv. Math., vol. 49, Cambridge University Press, Cambridge, 1997.
  * [17] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Stud. Adv. Math., vol. 62, Cambridge University Press, Cambridge, 1999.
  * [18] R.P. Stanley, Catalan numbers, Cambridge University Press, New York, 2015.
  * [19] Y. Sun and T. Zhao, Refined Eulerian numbers and ballot permutations, in preparation.
  * [20] D.G.L. Wang and J.J.R. Zhang, A Toeplitz property of ballot permutations and odd order permutations, Electron. J. Combin. 27(2) (2020), P2.55.
  * [21] D.G.L. Wang and T. Zhao, The peak and descent statistics over ballot permutations, arXiv: 2009.05973v2.