Restricting Dyck Paths and 312-avoiding Permutations
Elena Barcucci, Antonio Bernini,

Stefano Bilotta, Renzo Pinzani

Dipartimento di Matematica e Informatica “Ulisse Dini”
Università di Firenze

Viale G. B. Morgagni 65, 50134 Firenze, Italy

###### Abstract

Dyck paths having height at most $h$ and without valleys at height $h-1$ are
combinatorially interpreted by means of 312-avoding permutations with some
restrictions on their _left-to-right maxima_. The results are obtained by
analyzing a restriction of a well-known bijection between the sets of Dyck
paths and 312-avoding permutations. We also provide a recursive formula
enumerating these two structures using ECO method and the theory of production
matrices.

As a further result we obtain a family of combinatorial identities involving
Catalan numbers.

_AMS 2020 Mathematics Subject Classifications:_ Primary 05A19; Secondary
05A05, 05A15.

_Keywords:_ Dyck path, avoiding permutation, Catalan number.

##  1 Introduction

Dyck paths have been widely used in several combinatorial applications. Here,
we only recall their involvement in theory of codes [1, 9], cryptography [19]
and partial ordered structures [8]. Dyck paths enumeration has also received
much attention in recent decades. An interesting paper dealing with this
matter is the one by E. Deutsch [15] where the author enumerates Dyck paths
according to various parameters.

A subclass of these paths has been considered thanks to the simple behavior of
the recursive relations describing them and the rational nature of the related
generating function. More precisely, the generating function associated to
Dyck paths is algebraic and it is rational when the paths are bounded [12,
13], for example with respect to the height. Kallipoliti et al. [17] consider
Dyck paths having height less or equal to a precise value $k$. Moreover, in
the same paper a further restriction is considered: the authors analyze some
characteristics of Dyck paths avoiding valleys at specified height.

In our work we consider Dyck paths having height equal or less than $h$ and
having no valleys at height $h-1$. We obtain an interesting relation with a
subclass of $312$-avoiding permutations (actually, we obtain a bijection)
having some constraints on the _left-to-right_ maxima.

The paper structure is the following. In Section 2 some preliminaries on Dyck
paths and pattern avoiding permutations are introduced. Here we also recall a
well-known bijection between the sets of Dyck paths and $312$-avoiding
permutations, we are going to largely use in the whole paper. Sections 3 and 4
are devoted to the generation of the considered Dyck paths (having height
equal or less than $h$ and having no valleys at height $h-1$) and the
corresponding $312$-avoiding permutations with some restriction on their left
to right maxima. The enumerative results are presented in Section 5. they
provide the generating functions for the above mentioned classes, and a
recurrence relation for their enumeration according to their size.

Finally, we conclude the paper proposing some further developments on the
present topics.

##  2 Preliminaries

A Dyck path is a lattice path in the discrete plane $\mathbb{Z}^{2}$ from
$(0,0)$ to $(2n,0)$ with up and down steps in $\\{(1,1),(1,-1)\\}$, never
crossing the $x$-axis. The number of up steps in any prefix of a Dyck path is
greater or equal to the number of down steps and the total number of steps
(the _length_ of the path) is $2n$. We denote the set of Dyck paths having
length $2n$ (or equivalently semilength $n$) by $\mathcal{D}_{n}$. A Dyck path
can be codified by a string over the alphabet $\\{U,D\\}$, where $U$ and $D$
replace the up and down steps, respectively. The empty Dyck path is denoted by
$\varepsilon$.

The height of a Dyck path $P$ is the maximum ordinate reached by one of its
steps. A _valley_ of $P$ is an occurrence of the substring $DU$ while a _peak_
is an occurrence of the substring $UD$. The height of a valley (peak) is the
ordinate reached by $D$ ($U$).

We denote by $\mathcal{D}_{n}^{(h,k)}$ the set of Dyck paths having semilength
$n$ and height at most $h$, and avoiding $k-1$ consecutive valleys at height
$h-1$. The set of Dyck paths having semilength $n$ with height at most $h$
(without restriction on the number of valleys) is denoted by
$\mathcal{D}_{n}^{(h)}$. Moreover, $\mathcal{D}^{(h)}=\displaystyle\sum_{n\geq
0}\mathcal{D}_{n}^{(h)}$ and $\mathcal{D}^{(h,k)}=\displaystyle\sum_{n\geq
0}\mathcal{D}_{n}^{(h,k)}$.

The cardinalities of $\mathcal{D}_{n}^{(h,k)}$ and $\mathcal{D}_{n}^{(h)}$ are
indicated by $D_{n}^{(h,k)}$ and $D_{n}^{(h)}$, respectively. Finally, the set
$\mathcal{D}_{n}$ of unrestricted Dyck paths having semilength $n\geq 0$ is
enumerated by the $n$-Catalan number

$C_{n}=\frac{1}{n+1}\binom{2n}{n}\ .$

When $k=2$, the set $\mathcal{D}_{n}^{(h,2)}$ represents the set of Dyck paths
avoiding valleys at height $h-1$. In the present work we describe a
combinatorial interpretation of $\mathcal{D}_{n}^{(h,2)}$ in terms of
restricted permutations.

In our context, the above mentioned permutations are related to the notion of
pattern avoidance which can be generally described as the absence of a
substructure inside a larger structure. In particular, an occurrence of a
pattern $\sigma$ in a permutation $\pi=\pi_{1}\pi_{2}\dots\pi_{n}$ of length
$n$ is a sub-sequence (not necessarily constituted by consecutive entries) of
$\pi$ whose entries appear in the same relative order as those in $\sigma$.
Otherwise, we say that $\pi$ avoids the pattern $\sigma$, or that $\sigma$ is
a forbidden pattern for $\pi$. For example, $\pi=352164$ contains two
occurrences of $\sigma=312$ in the sub-sequences $514$ and $524$, while
$\pi=34251$ avoids the pattern $\sigma$. The set $\mathcal{S}_{n}(312)$
denotes the set of 312-avoiding permutations of length $n$ which are
enumerated by the $n$-Catalan number.

We are going to briefly recall a well-known bijection $\varphi$, useful in the
rest of the paper, between the classes $\mathcal{D}_{n}$ and
$\mathcal{S}_{n}(312)$ (see for example [15, 18]). Fix a Dyck path $P$ and
label its up steps by enumerating them from left to right (so that the
$\ell$-th up step is labelled $\ell$). Next assign to each down step the same
label of the up step it corresponds to. Now consider the permutation whose
entries are constituted by the labels of the down steps read from left to
right. Such a permutation $\pi=\varphi(P)$ is easily seen to be 312-avoiding.
As far as the inverse map $\varphi^{-1}$ is concerned, once fixed a
312-avoiding permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$ we can consider its
factorization in terms of descending sub-sequences whose first elements
coincide with the _left-to-right maxima_ of $\pi$. A left-to-right maximum
(l.r.M for short) is an element $\pi_{i}$ which is greater than all the
elements to its left, i.e., greater than all $\pi_{j}$ with $j<i$. Denoting
$\pi_{i_{1}},\pi_{i_{2}},\ldots,\pi_{i_{\ell}}$ the left-to-right maxima of
$\pi$, the corresponding Dyck path $P=\varphi^{-1}(\pi)$ is obtained as
follows:

  * •

write as many $U$’s as $\pi_{i_{1}}(=\pi_{1})$ followed by as many $D$’s as
the cardinality of the first descending sub-sequence headed by $\pi_{i_{1}}$;

  * •

for each $j=2,\ldots,\ell$, add as many $U$’s as $\pi_{i_{j}}-\pi_{i_{j-1}}$
followed by as many $D$’s as the cardinality of the sub-sequence headed by
$\pi_{i_{j}}$.

Two easy properties of l.r.M of $\pi\in S_{n}(312)$, and the corresponding
steps in $P=\varphi^{-1}(\pi)$ are summarized in the following:

######  Proposition 1.

Let $P$ be a Dyck path in $\mathcal{D}_{n}$ and
$\pi=\varphi(P)=\pi_{1}\ldots\pi_{n}$ be the associated permutation in
$S_{n}(312)$. Each entry $\pi_{i_{j}}$ corresponding to the first down step of
a sub-sequence of consecutive down steps in $P$ is a left to right maximum.
Moreover, $\pi_{i_{j}}-i_{j}$ is the height reached by the descending step in
$P$ corresponding to $\pi_{i_{j}}$.

##  3 A generating algorithm

The set $\mathcal{D}^{(h,2)}$ can be exhaustively generated by means an ECO
operator [3] which allows to construct all the paths of a certain length $n+1$
(the size of the combinatorial objects) staring from the ones of size $n$.

To this aim, consider a Dyck path $P\in\mathcal{D}_{n}^{(h,2)}$ which,
obviously, starts with $t\leq h$ up steps $U$. We mark these steps factorizing
the path $P$ as $P=U_{1}U_{2}\cdots U_{t}DP^{\prime}$, where $P^{\prime}$ is a
suitable Dyck suffix of length $n-t-1$. The idea is to consider some _sites_
in $P\in\mathcal{D}_{n}^{(h,2)}$ where an insertion of the factor
$\mathbf{UD}$ is allowed in order to obtain paths in
$\mathcal{D}_{n+1}^{(h,2)}$ from $P$ (so that the sites are called _active
sites_).

Thus, we define an operator $\vartheta$ for the class
$\mathcal{D}_{n}^{(h,2)}$ as follows:

  * -

if $P=U_{1}U_{2}\cdots U_{t-1}U_{t}DP^{\prime}\in\mathcal{D}_{n}^{(h,2)}$,
with $t<h$, then

$\begin{array}[]{ll}\vartheta(P)=\\{&\mathbf{UD}U_{1}U_{2}\cdots
U_{t-1}U_{t}DP^{\prime},\\\ &U_{1}\mathbf{UD}U_{2}\cdots
U_{t-1}U_{t}DP^{\prime},\\\ &\cdots\\\ &U_{1}U_{2}\cdots
U_{t-1}\mathbf{UD}U_{t}DP^{\prime},\\\ &U_{1}U_{2}\cdots
U_{t-1}U_{t}\mathbf{UD}DP^{\prime}\ \\}\ ;\end{array}$

  * -

if $P=U_{1}U_{2}\cdots U_{t-1}U_{t}DP^{\prime}\in\mathcal{D}_{n}^{(h,2)}$,
with $t=h$, then

$\begin{array}[]{ll}\vartheta(P)=\\{&\mathbf{UD}U_{1}U_{2}\cdots
U_{t-1}U_{t}DP^{\prime},\\\ &U_{1}\mathbf{UD}U_{2}\cdots
U_{t-1}U_{t}DP^{\prime},\\\ &\cdots\\\
&U_{1}U_{2}\cdots\mathbf{UD}U_{t-1}U_{t}DP^{\prime}\\}\ .\end{array}$

We note that the insertion of $\mathbf{UD}$ may create a valley in the paths
of $\vartheta(P)$. In particular,

  * •

the insertion of $\mathbf{UD}$ before the step $U_{j}$, with
$j=1,2,\ldots,t-1$, gives the occurrence of the valley $\mathbf{D}U_{j}$
having height $j-1<h-1$ in any case;

  * •

the insertion of $\mathbf{UD}$ before the step $U_{t}$ in the case $t<h$ gives
the occurrence of the valley $\mathbf{D}U_{t}$ having height equal to
$t-1<h-1$;

  * •

the insertion of $\mathbf{UD}$ after the step $U_{t}$ in the case $t<h$ does
note give the occurrence of a valley (since the next step is again a $D$
step).

In other words, the valley possibly generated by the insertion of
$\mathbf{UD}$ has height less than $h-1$, therefore we have:

######  Proposition 2.

If $x\in\vartheta(P)$, with $P\in\mathcal{D}_{n}^{(h,2)}$, then
$x\in\mathcal{D}_{n+1}^{(h,2)}$.

In the spirit of ECO method, we have to prove the following proposition.

######  Proposition 3.

The operator $\vartheta$ is an ECO operator.

###### Proof.

The proof consists in the following steps:

  * i)

If $x,y\in\mathcal{D}_{n}^{(h,2)}$ with $x\neq y$, then
$\vartheta(x)\cap\vartheta(y)=\emptyset$.

  * ii)

If $x\in\mathcal{D}_{n+1}^{(h,2)}$ then $\exists\ y\in\mathcal{D}_{n}^{(h,2)}$
such that $x\in\vartheta(y)$.

For case i), we suppose that exists a path $P$ such that $P\in\vartheta(x)$
and $P\in\vartheta(y)$, with $x\neq y$. From the description of the operator
$\vartheta$ it is easy to realize that the first peak of $P$ is precisely
generated by the insertion of the factor $\mathbf{UD}$. By removing such a
peak from $P$, we obtain an unique path. Thus, we would have $x=y$, against
the hypothesis.

For case ii), if $x\in D_{n+1}^{(h,2)}$, then $x=U^{j}\mathbf{UD}T^{\prime}$,
with $j=0,1,\ldots,h-1$, where $T^{\prime}$ is a suitable Dyck suffix of
suitable length. Then, the path $y=U^{j}T^{\prime}$ starts with at most $h$ up
steps $U$ so that $x\in D_{n}^{(h,2)}$. Clearly, it is $x\in\vartheta(y)$
since $y$ is obtained by the insertion of $\mathbf{UD}$ in $x$.

∎

A generating algorithm can be naturally described by means of the concept of
_succession rule_. Such a concept was introduced by Chung et al. [14] to study
reduced Baxter permutations. Recently this technique has been successfully
applied to other combinatorial objects [10, 11] and it has been recognized as
an extremely useful tool for the ECO method [3]. In all these cases there is a
common approach to the examined enumeration problem: a generating tree is
associated to certain combinatorial class, according to some enumerative
parameters, in such a way that the number of nodes appearing on level $n$ of
the tree gives the number of $n$-sized objects in the class.

A succession rule is a formal system constituted by an _axiom_ $(a)$ and some
_productions_ (possibly only one) having the form

$(k)\rightsquigarrow\left(e_{1}(k)\right)\left(e_{2}(k)\right)\ldots\left(e_{k}(k)\right)\
,$

so that a succession rule $\Omega$ is often denoted by

$\Omega:\left\\{\begin{array}[]{l}(a)\\\ \\\
(k)\rightsquigarrow\left(e_{1}(k)\right)\left(e_{2}(k)\right)\ldots\left(e_{k}(k)\right)\
.\\\ \end{array}\right.$

The symbols $(a)$,$(k)$ and $e_{i}(k)$ are called _labels_ (their values are
positive integers), and play a crucial role when the the succession rule
$\Omega$ is represented by a _generating tree_. This is a rooted tree whose
nodes are the labels of $\Omega$. More precisely, the root is labelled with
$(a)$ and each node having label $(k)$ has $k$ children having labels
$e_{1}(k),e_{2}(k),\ldots,e_{k}(k)$, according to the productions in $\Omega$.

In our case the generating algorithm for $\mathcal{D}^{(h,2)}$ is performed by
the operator $\vartheta$ and from its definition is easy to realize that:

  * •

the empty path $\varepsilon$ can be labelled with the axiom $(1)$ having
production $(1)\rightsquigarrow(2)$: the path $\varepsilon$ generates the path
$UD$, having in turns label $(2)$;

  * •

every other path $P$ can have label $(2)$, $(3)$, …or $(h)$ depending on the
number $t$ of its starting up steps $U$. More precisely, if $1\leq t\leq h-1$
then $P$ is labelled $(t+1)$. Otherwise, if $t=h$, then $P$ is labelled
$(h-1)$.

In order to write the productions of the labels $(k)$ of $P$, with
$k=2,3,\ldots,h$ we observe that:

  * •

if $k<h$ then the $k$ paths in $\vartheta(P)$ start, respectively, with
$1,2,\ldots\ \mbox{or}\ k$ up steps, so that, in turns, they are labelled
$(2),(3),\ldots(k+1)$. Then we can write the production

$(k)\leadsto(2)(3)\cdots(k)(k+1),\ 2\leq k<h.$

  * •

if $k=h$ then the $k$ paths in $\vartheta(P)$ start, respectively, with
$1,2,\ldots\ \mbox{or}\ h$ up steps. Since the path having $h$ starting up
steps is labelled $(h-1)$, then we can write the production

$(h)\leadsto(2)(3)\cdots(h-1)^{2}(h).$

The two paths having label $(h-1)$ are precisely the one starting with $h$ up
steps and the one starting with $h-2$ up steps.

Finally, the generating algorithm for $\mathcal{D}^{(h,2)}$ can be described
by the succession rule (for $h\geq 3$) as follows:

$\Omega_{h}:\left\\{\begin{array}[]{ccl}(1)&&\\\ (1)&\leadsto&(2)\\\
(k)&\leadsto&(2)(3)\cdots(k)(k+1),\quad\quad 2\leq k<h\\\
(h)&\leadsto&(2)(3)\cdots(h-1)^{2}(h)\end{array}\right.$ (1)

##  4 The bjection with a subset of 312-avoiding permutations

Let $\mathcal{S}_{n}^{(h)}(312)\subseteq S_{n}(312)$ be the subset of
permutations $\pi\in S_{n}(312)$ such that $\pi_{i_{j}}-i_{j}\leq h-1$, for
each l.r.M. $\pi_{i_{j}}$ of $\pi$. The reader can easily check that the
restriction $\varphi_{\big{|}D_{n}^{(h)}}$ of $\varphi$ to the set
$D_{n}^{(h)}$ is a bijection between $D_{n}^{(h)}$ and $S_{n}^{(h)}(312)$
(using Proposition 1).

We now consider the paths in $D_{n}^{(h,2)}$ and characterize the
corresponding permutations via the restriction of $\varphi$ to this set. The
following proposition holds.

######  Proposition 4.

Let $P$ be a Dyck path in $\mathcal{D}_{n}$. Then,
$P\in\mathcal{D}_{n}^{(h,2)}$ if and only if in the corresponding permutation
$\pi=\varphi(P)$ there is no left-to-right maximum $\pi_{i_{j}}$ such that

  1. 1.

$\pi_{i_{j}}-i_{j}=h-1$ and

  2. 2.

$\pi_{i_{j+1}}=\pi_{i_{j}}+1$.

###### Proof.

Suppose that $\pi=\varphi(P)$ has no a left-to-right maximum $\pi_{i_{j}}$
such that $\pi_{i_{j}}-i_{j}=h-1$ and $\pi_{i_{j+1}}=\pi_{i_{j}}+1$. Let
$P=\varphi^{-1}(\pi)$ be the corresponding path. We have to prove that
$P\in\mathcal{D}_{n}^{(h,2}$.

  * •

If $P$ has height less than $h$, then, surely, $P\in\mathcal{D}_{n}^{(h,2)}$
and the proof is completed.

  * •

Suppose that $P$ has height equal to $h$ and suppose, ad absurdum, that
$P\notin\mathcal{D}_{n}^{(h,2)}$. Therefore, there exists a valley having
height $h-1$. Thus, $P$ can be written as
$P^{\prime}U_{i}D_{i}U_{i+1}D_{i+1}P^{\prime\prime}$, where $P^{\prime}$ and
$P^{\prime\prime}$ are, respectively, a Dyck prefix and a Dyck suffix having
height $h-1$. Considering the permutation
$\pi=\varphi(P)=\pi_{1}\ldots\pi_{i}\pi_{i+1}\ldots\pi_{n}$ (where we
highlighted the entries $\pi_{i}$ and $\pi_{i+1}$ corresponding to the steps
$D_{i}$ and $D_{i+1}$), thanks to Proposition 1, it is possible to observe
that the elements $\pi_{i}$ and $\pi_{i+1}$ associated to $U_{i}$ and
$U_{i+1}$, respectively, are l.r.M. in $\pi$. Again from Proposition 1, we
have $\pi_{i}-i=h-1$ and $\pi_{i+1}-(i+1)=h-1$ and, by substitution, it is
$\pi_{i+1}=\pi_{i}+1$, against the hypothesis. Thus,
$P\in\mathcal{D}_{n}{(h,2)}$.

On the other side, suppose that $P\in\mathcal{D}_{n}^{(h,2)}$ and suppose, ad
absurdum, that
$\pi=\varphi(P)=\pi_{1}\ldots\pi_{i}\pi_{i+1}\ldots\pi_{n}\in\mathcal{S}_{n}^{(h)}(312)$
has a left to right maximum $\pi_{i}$ with $\pi_{i+1}=\pi_{i}+1$ and
$\pi_{i}-i=h-1$. Then, it is
$\pi=\pi_{1}\ldots\pi_{i}(\pi_{i}+1)\ldots\pi_{n}$. Since $\pi_{i}<\pi_{i+1}$
and $\pi$ is a 312-avoiding permutation, then there is not $\pi_{l}>\pi_{i}$
with $l<i$. Thus, both $\pi_{i}$ and $\pi_{i+1}$ are l.r.M. in $\pi$. From
Proposition 1, the quantities $\pi_{i}-i$ and $\pi_{i+1}-(i+1)$ are the
heights reached by the corresponding descending steps in $P$. Moreover, from
the two hypotheses $\pi_{i}-i=h-1$ and $\pi_{i+1}=\pi_{i}+1$, we deduce
$\pi_{i+1}-(i+1)=\pi_{i}+1-(i+1)=h-1$. Thus, $P=\varphi^{-1}(\pi)$ can be
factorized as $P=P^{\prime}U_{i}D_{i}U_{i+1}D_{i+1}P^{\prime\prime}$ showing
that $P$ admits a valley having height $h-1$, against the hypothesis
$P\in\mathcal{D}_{n}^{(h,2)}$.

∎

The permutations corresponding to the paths in $\mathcal{D}_{n}^{(h,2)}$ are
denoted by $\mathcal{S}_{n}^{(h,2)}(312)$. By means of the above proposition,
we proved the following one.

######  Proposition 5.

There exists a bijection between the classes $\mathcal{S}_{n}^{(h,2)}(312)$
and $\mathcal{D}_{n}^{(h,2)}$, which is the restriction
$\varphi_{\big{|}D_{n}^{(h,2)}}$.

From Proposition 5, a generating algorithm for the class
$\mathcal{S}_{n}^{(h,2)}(312)$ according to the succession rule $\Omega_{h}$
can be obtained. A combinatorial interpretation of $\Omega_{h}$ in terms of
permutations is then desired.

First of all we note that, if
$\pi=\pi_{1}\dots\pi_{n}\in\mathcal{S}_{n}^{(h,2)}(312)$, then $\pi_{1}\leq
h$. After that, we have to find an interpretation of the parameters comparing
in the rule $\Omega_{h}$. The axiom $(1)$ at level 0 can be associated to the
_empty_ permutation and its production labelled with $(2)$ can be associated
to the permutation $1$. The parameter $(k)$ at level $n$ in the rule
$\Omega_{h}$ admits the following interpretation according to the value of
$\pi_{1}$ in $\pi\in S_{n}^{(h,2)}(312)$:

$(k)=\begin{cases}\pi_{1}+1&\text{if }\pi_{1}\neq h\ ;\\\ \pi_{1}-1&\text{if
}\pi_{1}=h.\end{cases}$ (2)

More precisely, if $\pi_{1}<h$, a permutation
$\pi=\pi_{1}\dots\pi_{n}\in\mathcal{S}_{n}^{(h,2)}(312)$ at level $n$,
produces $k=\pi_{1}+1$ sons at level $n+1$ by inserting the element $\ell$,
with $\ell=1,2,\ldots,\pi_{1}+1$, before $\pi_{1}$ and rescaling the sequence
$\ell\pi$ in order to obtain a permutation
$\pi^{\prime}\in\mathcal{S}_{n+1}^{(h,2)}(312)$ (for the sake of clearness,
each entry $\pi_{i}$ of $\pi$ equal or greater than $\ell$ is increased by $1$
in order to obtain $\pi^{\prime}$).

Otherwise, when $\pi_{1}=h$, a given permutation
$\pi=\pi_{1}\dots\pi_{n}\in\mathcal{S}_{n}^{(h,2)}(312)$ at level $n$,
produces $k=\pi_{1}-1=h-1$ sons at level $n+1$ by inserting the element
$\ell$, with $\ell=1,2,\ldots,h-1$, before $\pi$. Analogously,
$\pi^{\prime}\in\mathcal{S}_{n+1}^{(h,2)}(312)$ is obtained by rescaling the
sequence $\ell\pi$, for each $\ell$.

As an example, fixed $h=3$, the succession rule for
$\mathcal{S}_{n}^{(3,2)}(312)$, or equivalently for $\mathcal{D}_{n}^{(3,2)}$,
is as follows:

$\Omega_{3}:\left\\{\begin{array}[]{ccl}(1)&&\\\ (1)&\leadsto&(2)\\\
(2)&\leadsto&(2)(3)\\\ (3)&\leadsto&(2)(2)(3)\end{array}\right.$ (3)

In Figure 1 a graphical representation of the first levels of $\Omega_{3}$ is
shown in terms of permutations in $\mathcal{S}_{n}^{(3,2)}$.

Figure 1: Graphical representation of the generating tree associated with
$\mathcal{S}_{n}^{(3,2)}$ where the label associated to each permutation is
shown in brackets.

##  5 Enumeration

The case $h=2$ is not included in the general formula (1) for the succession
rules. However, it is easy to see that in this case it is

$\Omega_{2}:\left\\{\begin{array}[]{ccl}(1)&&\\\ (1)&\leadsto&(2)\\\
(2)&\leadsto&(1)(2)\\\ \end{array}\right.$ (4)

The succession rule (4) defines the Fibonacci numbers.

According to the theory developed by Deutsch et al. [16], the production
matrix $P_{2}$ associated to $\Omega_{2}$ is

$P_{2}=\left(\begin{matrix}0&1\\\ 1&1\\\ \end{matrix}\right)$ (5)

and, for $h\geq 3$,

$P_{h}=\left(\begin{matrix}0&u^{t}\\\ 0&P_{h-1}+eu^{t}\\\ \end{matrix}\right)$
(6)

where $u^{t}$ is the row vector $(1\ 0\ 0\ldots)$ and $e$ is the column vector
$(1\ 1\ 1\ \ldots)^{t}$, of appropriate size and for what the generating
function $f_{h}(x)$ of the sequence corresponding to $\Omega_{h}$ is
concerned, we have [16], for $h\geq 2$,

$f_{h}(x)=\frac{1}{1-xf_{h-1}(x)}\ .$ (7)

When $h=1$, clearly the unique paths in $\mathcal{D}_{n}^{(1,2)}$ are the
empty path $\varepsilon$ and $UD$, so that the sequence
$(D_{n}^{(1,2)})_{n\geq 0}$ is $\\{1,1,0,0,\ldots\\}$, whose generating
function is $f_{1}(x)=1+x$ which is rational. Thanks to (7) it is possible to
deduce that also $f_{h}(x)$ with $h\geq 2$ is rational, too. Therefore, we can
consider its general form as follows:

$f_{h}(x)=\frac{p_{h}(x)}{q_{h}(x)}\ ,$ (8)

where $p_{h}(x)$ and $q_{h}(x)$ are polynomials with suitable degrees. From
(7) and (8) we obtain

$\displaystyle p_{h}(x)$ $\displaystyle=q_{h-1}(x)$ (9) $\displaystyle
q_{h}(x)$ $\displaystyle=q_{h-1}(x)-xq_{h-2}(x)\ .$

Since the degree of the polynomial $q_{h}(x)$ is
$\left\lceil{\frac{h+1}{2}}\right\rceil$ (it can be easily seen by induction),
we can assume

$q_{h}(x)=a_{h,0}-a_{h,1}x-a_{h,2}x^{2}-\ldots-
a_{h,j}x^{j}\quad\mbox{with}\quad j=\left\lceil{\frac{h+1}{2}}\right\rceil.$

Clearly, it is $a_{h,j}=0$ if $j>\left\lceil{\frac{h+1}{2}}\right\rceil$.

As $a_{1,0}=1$, thanks to (9) we have $a_{h,0}=a_{h-1}$, and

$a_{h,0}=1\ \ \mbox{for each}\ \ h\geq 1\ .$

Moreover,

$q_{h}(x)=1-a_{h,1}x-a_{h,2}x^{2}-\ldots-a_{h,j}x^{j}\quad\mbox{with}\quad
j=\left\lceil{\frac{h+1}{2}}\right\rceil.$ (10)

Using the expression for $q_{h}(x)$ in (9), we obtain

$\displaystyle q_{h}(x)=$ $\displaystyle\ 1-a_{h-1,1}x-a_{h-1,2}x^{2}-\ldots-
a_{h-1,j-1}x^{j-1}$ (11)
$\displaystyle-x\left(1-a_{h-2,1}x-a_{h-2,2}x^{2}-\ldots-
a_{h-2,j-2}x^{j-2}\right).$

For the identity theorem for polynomials, comparing formulas (10) and (11) for
$q_{h}(x)$, it is

$a_{h,j}=\begin{cases}a_{h-1,1}+1&\text{for }j=1\\\
a_{h-1,j}-a_{h-2,j-1}&\text{for
}j=2,3,\ldots,\left\lceil{\frac{h+1}{2}}\right\rceil.\end{cases}$ (12)

In Table 1 we list the first numbers of the coefficients $a_{h,j}$ for some
fixed values of $h\geq 1$ and $j\geq 1$. On the diagonals, it is possible to
observe a similarity with the $A112467$ sequence in The On-line Encyclopedia
of Integer Sequences [20].

$h$ / $j$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0
4 | 3 | 0 | -1 | 0 | 0 | 0 | 0 | 0
5 | 4 | -2 | -2 | 0 | 0 | 0 | 0 | 0
6 | 5 | -5 | -2 | 1 | 0 | 0 | 0 | 0
7 | 6 | -9 | 0 | 3 | 0 | 0 | 0 | 0
8 | 7 | -14 | 5 | 5 | -1 | 0 | 0 | 0
9 | 8 | -20 | 14 | 5 | -4 | 0 | 0 | 0
10 | 9 | -27 | 28 | 0 | -9 | 1 | 0 | 0
11 | 10 | -35 | 48 | -14 | -14 | 5 | 0 | 0
12 | 11 | -44 | 75 | -42 | -14 | 14 | -1 | 0
13 | 12 | -54 | 110 | -90 | 0 | 28 | -6 | 0
14 | 13 | -65 | 154 | -165 | 42 | 42 | -20 | 1
Table 1: The coefficients $a_{h,j}$ for some fixed values of $h$ and $j$.

We have an explicit formula for the coefficients $a_{h,j}$ thanks to the
following proposition.

######  Proposition 6.

For $h\geq 2$ and for $j=1,2,\ldots,\left\lceil{\frac{h+1}{2}}\right\rceil$ we
have:

$a_{h,j}=\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}$ (13)

###### Proof.

We proceed by induction on $h$. For $h=2$, it is $j=1,2$, and expression (13)
gives $a_{2,1}=1$ and $a_{2,2}=1$, agreeing with the expression for
$f_{2}(x)=\frac{1}{1-x-x^{2}}$ derived from (7) and $f_{1}(x)=1+x$.

For $h>2$, we first analyze the case $j=1$. Using $a_{h,1}=a_{h-1,1}+1$ from
(12) and the inductive hypothesis, we have

$a_{h,1}=\ a_{h-1,1}+1=(2-h)(-1)^{1}+1=h-1\\\ $

which matches the value of $a_{h,1}$ returned by (13).

For $j>2$, we use $a_{h,j}=a_{h-1,j}-a_{h-2,j-1}$ from (12) and, again, the
inductive hypothesis. We get

$\displaystyle a_{h,j}$ $\displaystyle=\ a_{h-1,j}-a_{h-2,j-1}$
$\displaystyle=\frac{3j-h-1}{j}\binom{h-j}{j-1}(-1)^{j}-\frac{3j-h-3}{j-1}\binom{h-j}{j-2}(-1)^{j-1}$
$\displaystyle=\frac{3j-h-1}{j}\binom{h-j}{j-1}(-1)^{j}+\frac{3j-h-3}{j-1}\binom{h-j}{j-2}(-1)^{j}\
.$

Expanding the binomial coefficients and with some manipulations, it is

$a_{h,j}=\frac{(-1)^{j}(h-j+1)!(3j-h-2)}{j(j-1)!(h-2j+2)!}=\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}\
,$

as required. The proof is completed.

∎

In the sequel, we are going to evaluate a recurrence relation for the terms
$D_{n}^{(h,2)}$ involving the series expansion at $x=0$ of the generating
function

$f_{h}(x)=\frac{p_{h}(x)}{q_{h}(x)}=\frac{q_{h-1}(x)}{q_{h}(x)}=\sum_{n\geq
0}D_{n}^{(h,2)}x^{n}\ .$

The expression for $q_{h}(x)$ becomes

$q_{h}(x)=1-\sum_{j=1}^{\lceil{\frac{h+1}{2}}\rceil}\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}x^{j}$
(14)

Thus, we obtain

$f_{h}(x)=\frac{1-\displaystyle\sum_{j=1}^{\lceil{\frac{h}{2}}\rceil}\frac{3j-h-1}{j}\binom{h-j}{j-1}(-1)^{j}x^{j}}{1-\displaystyle\sum_{j=1}^{\lceil{\frac{h+1}{2}}\rceil}\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}x^{j}}\
$ (15)

and

$\displaystyle\left({1-\displaystyle\sum_{j=1}^{\lceil{\frac{h+1}{2}}\rceil}\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}x^{j}}\right)\left(\sum_{n\geq
0}D_{n}^{(h,2)}x^{n}\right)=$
$\displaystyle=1-\displaystyle\sum_{j=1}^{\lceil{\frac{h}{2}}\rceil}\frac{3j-h-1}{j}\binom{h-j}{j-1}(-1)^{j}x^{j}$

Sorting the first part according to the increasing powers of $x$ we have

$\displaystyle\sum_{n\geq
0}\left(D_{n}^{(h,2)}-\sum_{j=1}^{\lceil{\frac{h+1}{2}}\rceil}D_{n-j}^{(h,2)}\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}\right)x^{n}=$
$\displaystyle=1-\displaystyle\sum_{j=1}^{\lceil{\frac{h}{2}}\rceil}\frac{3j-h-1}{j}\binom{h-j}{j-1}(-1)^{j}x^{j}$

where $D_{\ell}^{(h,2)}=0$ whenever $\ell\leq 0$.

For the identity theorem for polynomials we can deduce the desired recurrence
relation

$D_{n}^{(h,2)}=\begin{cases}1&\text{for }n=0\ ;\\\ &\\\
\displaystyle\sum_{j=1}^{\lceil{\frac{h+1}{2}}\rceil}D_{n-j}^{(h,2)}\frac{3j-h-2}{j}\binom{h-j+1}{j-1}(-1)^{j}-\frac{3n-h-1}{n}\binom{h-n}{n-1}(-1)^{n}&\text{for
}n\geq 1\ .\end{cases}$

A very interesting note arises when, once $h$ is fixed, we ask for the number
$D_{n}^{(h,2)}$ of Dyck paths having semilength $n\leq h$. Clearly, in this
case, it is $D_{n}^{(h,2)}=C_{n}$ since all the Dyck paths of a certain
semilegth $n\leq h$ have height at most equal to $n$. Thanks to the above
argument it is possible to derive interesting relations involving Catalan
numbers. Indeed, for the above remark, posing $h=n+\alpha,$ we can write
$D_{n}^{(n+\alpha,2)}=C_{n}$, where $\alpha\geq 0$ is integer. Then, it is
possible to deduce the combinatorial identity involving Catalan numbers as
follows:

$C_{n}=\displaystyle\sum_{j=1}^{n}C_{n-j}\frac{3j-n-\alpha-2}{j}\binom{n+\alpha-j+1}{j-1}(-1)^{j}-\frac{2n-\alpha-1}{n}\binom{\alpha}{n-1}(-1)^{n}\
.$ (16)

##  6 Further developments

In this paper we analyzed the case $k=2$ leading to bounded Dyck paths
avoiding valleys at given height (i.e., $h-1$) corresponding to the
permutations in $\mathcal{S}_{n}^{(h,2)}(312)$. An interesting generalization
could concern the cases $k>2$ in order to investigate what are the arising
constraints on the subclasses of $312$-avoiding permutations. The number $k-1$
of consecutive valleys allowed at height $h-1$ clearly affects the value and
position of the l.r.M., as we have seen in the $k=2$ case. For values of $k$
larger than $2$, the permutations probably have a structure that can be
described in terms of a suitable block decomposition.

The above combinatorial identity (16) is obtained by means of a purely
combinatorial consideration. By virtue of this, similar relations are expected
to arise even in cases $k>2$. It might then be possible to derive a family of
combinatorial identities as $k$ varies.

Another further line of research could consider the possibility to list the
paths of $\mathcal{D}_{n}^{(h,2)}$ in a Gray code sense using the tools
developed by Barcucci, Bernini et al. [1, 4, 5, 7, 6]. As mentioned in Section
2, these paths can be encoded by strings on the alphabet $\\{U,D\\}$, so the
problem of defining a Gray code could be addressed by starting from the
techniques developed by Vajnovszki et al. [21].

Moreover, the considered Dyck paths could be used for the construction of a
strong non-overlapping code proposed by Barcucci et al. [2].

## References

  * [1] E. Barcucci, A. Bernini, and R. Pinzani. Strings from linear recurrences: a Gray code, in _Combinatorics on Words: 13th International Conference, WORDS 2021, Rouen, France, September 13–17, 2021_ , Lect. Notes in Comp. Sci., Vol. 12857, Springer, 2021, pp. 40–49.
  * [2] E. Barcucci, A. Bernini, and R. Pinzani. A strong non-overlapping Dyck code, in _DLT, 2021_ , Lect. Notes in Comp. Sci., Vol. 12811, 2021, pp. 43–53.
  * [3] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: a methodology for the enumeration of combinatorial object, J. Difference Equ. Appl. 5 (1999), 435–490.
  * [4] A. Bernini, S. Bilotta, R. Pinzani, A. Sabri, and V. Vajnovszki, Prefix partitioned Gray codes for particular cross-bifix-free sets, Cryptogr. Commun. 6 (2014), 359–369.
  * [5] A. Bernini, S. Bilotta, R. Pinzani, A. Sabri, and V. Vajnovszki, Gray code orders for q-ary words avoiding a given factor, Acta Inform. 52 (2015), 573–592.
  * [6] A. Bernini, S. Bilotta, R. Pinzani, and V. Vajnovszki, A Gray code for cross-bifix-free sets, Math. Structures Comput. Sci. 27 (2017), 184–196.
  * [7] A. Bernini, S. Bilotta, R. Pinzani, and V. Vajnovszki, A trace partitioned Gray code for q-ary generalized Fibonacci strings, J. Discrete Math. Sci. Cryptogr. 18 (2015), 751–761.
  * [8] A. Bernini, G. Cervetti, L. Ferrari, and E. Steingrímsson, Enumerative combinatorics of intervals in the Dyck pattern poset, Order 38 (2021), 473–487.
  * [9] S. Bilotta, Variable-length non-overlapping codes, IEEE Trans. Inform. Theory 63 (2017), 6530–6537.
  * [10] S. Bilotta, E. Grazzini, E. Pergola, and R. Pinzani, Avoiding cross-bifix-free binary words, Acta Inform. 50 (2013), 157–173.
  * [11] S. Bilotta, E. Pergola, R. Pinzani, S. Rinaldi, Recurrence relations, succession rules and the positivity problem, J. Comput. System Sci. 104 (2019), 102–118.
  * [12] M. Bousquet-Mélou, Discrete excursion, Sém. Lothar. Combin 57 (2008), B57d.
  * [13] M. Bousquet-Mélou and Y. Ponty, Culminating paths, Discrete Math. Theoret. Comput. Sci. 10 (2008), 125–152.
  * [14] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, and M. Kleimann, The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978), 382–394.
  * [15] E. Deutsch, Dyck path enumeration, Discrete Math. 24 (1999), 167–222.
  * [16] E. Deutsch, L. Ferrari, S. and Rinaldi, Production matrices, Adv. in Appl. Math.34 (2005), 101–122.
  * [17] M. Kallipoliti, R. Sulzgruber, and E. Tzanaki, Patterns in Shi Tableaux and Dyck Paths, Order 39 (2022), 263–289.
  * [18] D. E. Knuth, _The Art of Computer Programming: Sorting and Searching_ , Addison-Wesley, 1966.
  * [19] M. Saracevic, S. Adamovic, and E. Bisevac, Application of Catalan Numbers and the Lattice Path Combinatorial Problem in Cryptography, Acta Polytechnica Hungarica 15 (2018), 91–110.
  * [20] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.
  * [21] V. Vajnovszki, and T. Walsh, A loop-free two-close Gray-code algorithm for listing $k$-ary Dyck words, J. Discrete Algorithms 4 (2006), 633–648.