# Bijections and congruences involving
lattice paths and integer compositions

Manosij Ghosh Dastidar  and  Michael Wallner<EMAIL_ADDRESS><EMAIL_ADDRESS>TU Wien, Institute of Discrete Mathematics and
Geometry, Wiedner Hauptstr. 8–10, 1040 Vienna, Austria

###### Abstract.

We prove new bijections between different variants of Dyck paths and integer
compositions, which give combinatorial explanations of their simple counting
formula $4^{n-1}$. These give relations between different statistics, such as
the number of crossings of the $x$-axis in classes of Dyck bridges or the
distribution of peaks in classes of Dyck paths, and furthermore relate them
with $k$\- and $g$-compositions. These allow us to find and prove congruence
results for Dyck paths and parity results for compositions. Our investigation
uncovers unexpected connections to mock theta functions, Hardinian arrays,
little Schröder paths, Fibonacci numbers, and irreducible pairs of
compositions, offering new insights into the structures of paths, partitions
and compositions.
Keywords: Integer compositions, lattice paths, Dyck paths, Schröder paths,
congruences for Dyck paths, bijections

##  1\. Introduction

This paper aims to establish a comprehensive framework connecting the fields
of lattice paths, integer compositions, integer partitions and related
combinatorial structures. Our investigation is motivated by the rich interplay
between these distinct areas and the intriguing bijections and properties that
link them. Therefore we start by defining the key concepts of the paper. A
_Dyck path_ is a lattice path in $\mathbb{Z}^{2}$ from $(0,0)$ to $(2n,0)$
with up steps $\mathtt{u}=(1,1)$ and down steps $\mathtt{d}=(1,-1)$ that never
crosses the $x$-axis. Dyck paths are ubiquitous in combinatorics and famously
enumerated by the Catalan numbers $\frac{1}{n+1}\binom{2n}{n}$; see, e.g.,
[46]. An _integer partition_ is a representations of a positive integer $n$ as
a sum of positive integers, where different orders of the summands are not
considered to be distinct. Similarly, an _integer composition_ is a
representation of a positive integer $n$ as a sum of positive integers but in
this case the different orders of the summands are considered to be distinct.

Over the course of history many other structures have been defined to
understand the world of paths, partitions and compositions. We provide a few
of them here to aid the understanding of the subsequent sections of this
paper:

  1. (1)

A _Dyck bridge_ is constructed when we relax the spatial restriction on Dyck
paths such that it is allowed to traverse below the $x$-axis but must still
end on the $x$-axis. Historically, Dyck bridges are also sometimes called
_Grand Dyck paths_.

  2. (2)

A _Dyck walk_ is constructed when we further relax the condition of a bridge
terminating on the $x$-axis, i.e., it is completely unconstrained and may end
at any altitude.

  3. (3)

A _strict left-to-right maximum_ is any peak ($\mathtt{u}\mathtt{d}$) that has
a greater height than all peaks to its left. Similarly, a _weak left-to-right
maximum_ is a peak that is greater than or equal to in height with all peaks
to its left. Note that all left-to-right maxima in this paper will be strict.

  4. (4)

A _pair of compositions_ of $n$ is an ordered pair
$((a_{1},\dots,a_{k}),(b_{1},\dots,b_{\ell}))$ such that
$n=a_{1}+\dots+a_{k}=b_{1}+\dots+b_{\ell}$ are two compositions of $n$.

  5. (5)

A _$k$ -composition_ of $n$, as introduced by Andrews [2], is a composition of
$n$ using parts made of $k$ distinct colors such that the last part is of the
first color.

Pairs of compositions of $n$$3$-compositions of $n$ [2]$g$-compositions of $n$
[38, 30]Unconstrained Dyck walks of length $2n-2$$2$-colored Dyck bridges of
length $2n-2$ Dyck paths with height-labelled peaks of length $2n$Left-to-
right maxima in Dyck bridges of length $2n$Prop. 2.3Prop. 2.1Prop. 2.5Prop.
2.15Prop. 2.16Prop. 2.12

Figure 1. Bijections proved in this paper of classes of paths and
compositions, all enumerated by $4^{n-1}$.

This paper is organized in three parts. In the first part, we prove a series
of bijections visualized in Figure 1, linking the world of compositions and
lattice paths by their enumeration formula $4^{n-1}$. We start in Section 2.1,
where we give natural bijections between pairs of compositions, Andrews’
$3$-compositions, $g$-compositions (a concept from quantum physics), and Dyck
walks. We further explore bijections between Hardinian arrays and pairs of
compositions with equal first parts. These bijections bring to light the
commonalities between these usually disparate combinatorial objects. We
continue in Section 2.2 with the study of peaks and crossings of the $x$-axis
in Dyck bridges. We present bijections between several classes of Dyck paths
with specific peak properties, among which many are also in bijection with the
compositions studied in Section 2.1. Our results extend to the enumeration of
Dyck bridges in restricted settings, highlighting the versatility of Dyck
paths in combinatorial enumerations. In Section 2.3, we then derive various
links between compositions and paths in a strip.

In the second part, we focus on congruences in classes of Dyck paths. Having
established a series of bijections between walks and compositions raises the
question of whether there are similar underlying structures at play here. For
this reason, we ask the questions of whether famous results in the theory of
partitions or compositions have analogous results in the theory of lattice
paths. We are pleased to answer this question in the affirmative. In
particular, in Section 3, we introduce the concept of a peak profile in
Definition 3.1, which is a statistic based on the number of peaks of a given
height. This leads us to creating congruence relations for Dyck paths
analogous to the celebrated congruence properties that have existed for the
partition function. Our main result is Theorem 3.8 based on a divisibility
property of Dyck paths with exactly $r$ peaks per reached height. This
analysis also leads us to unexpected connections with little Schröder paths
and plane trees.

In the third part, we generalize the key concepts like peaks in Dyck paths and
restrictions on parts in compositions. In Section 4.1, we generalize peaks to
summits, which may also occur at the beginning and the end of paths, and
analyze them in Dyck bridges together with certain restrictions. We show how
they are connected to other well-known objects like the Fibonacci numbers. In
Section 4.2, we consider limitations on the size of the first, greatest and
smallest peaks or parts impact the overall nature of paths and partitions (or
compositions). Euler’s famous pentagonal number theorem motivated Fine to find
a curiously analogous theorem for partitions into distinct parts where the
first part has parity either odd or even. Extending this result to integer
compositions we show in Theorem 4.11 a surprising link back to closed walks.
Inspired by these results we ask similar questions in the context of lattice
paths and we discover an unexpected connection to integer compositions again.

##  2\. Bijections between compositiosn and lattice paths

###  2.1. Bijections involving compositions and arrays

There are instances in literature where connections between walks and
compositions (including pairs of compositions) have been studied in detail.
Bender, Lawler, Pemantle, and Wilf [13] studied pairs of compositions in the
context of probability of a first return to the origin of a random walk, while
Bóna and Knopfmacher [15] have looked into the probability that pairs of
compositions with part sizes $a$ and $b$ have the same length (i.e., number of
parts) and in that context they have established bijections between these
objects and weighted lattice paths. Dunkl [23] has given relations between
pairs of compositions and hook-lengths in the modified Ferrer’s diagram which
could also be connected to walks via relations to adjusted Young’s tableaux.

The following straightforward bijection will serve as the link between lattice
paths and compositions.

######  Proposition 2.1.

There exists a natural bijection between pairs of compositions of $n$ and Dyck
walks of length $2n-2$.

###### Proof.

Let a pair $(A,B)$ of two compositions of $n$ be given. First, we convert each
composition to a binary sequence: For each element $k$ in a composition,
append $k-1$ zeros followed by a $1$. By construction, both of these sequences
have to end in $1$. So we remove these ones and then concatenate the binary
sequences, with $A$’s sequence coming first. Finally, after replacing each $0$
by an up step $\mathtt{u}$ and each $1$ by a down step $\mathtt{d}$ the claim
follows. For the reverse direction cut the walk in the middle into two parts,
and re-add the ones. ∎

Let us show how the above construction works on a concrete example.

######  Example 2.2.

Let the pair $(A,B)$ of compositions $A=(2,1,3)$ and $B=(3,2,1)$ of $6$ be
given. In the first step we get the two binary sequences $011001$ and
$001011$. Then, after erasing the ones at the end we concatenate them and get
$0110000101$.

Next, we show that pairs of compositions are in bijection with a special case
of Andrews’ $k$-compositions [2], namely for $k=3$.

######  Proposition 2.3.

There exists a natural bijection between $3$-compositions of $n$ and pairs of
compositions of $n$.

###### Proof.

Anticipating the result, we use the following convention for the three colors
$1,2,3$, anticipating a notion of left and right: Remove the labels of color
$1$, use label $L$ for color $2$, and label $R$ for color $3$.

Now we describe a map from $3$-compositions of $n$ to pairs of compositions of
$n$. First, we create two identical copies. In the first copy, we remove the
labels $R$ and add the parts labeled by $L$ to the next part. If the next part
has also a label $L$, then the addition continues to the next part, etc. This
gives a composition $A$ without any labels. Similarly, in the second copy, we
remove the labels $L$ and add the parts labeled by $R$ to the next part.
Again, if the next number has also a label $R$, then the addition continues,
and we get a composition $B$ without any labels. Observe that the size of both
compositions has not changed. Therefore, $(A,B)$ is a pair of compositions of
$n$.

To prove that this map is in fact a bijection, let us consider an arbitrary
pair $(A,B)$ of compositions of $n$. The key statistic to consider is the _run
of identical parts_ : Let $A=(a_{1},a_{2},\dots,a_{\ell_{A}})$ and
$B=(b_{1},b_{2},\dots,b_{\ell_{B}})$. A run is sequence of maximal length such
that $a_{1}=b_{1}$, $a_{2}=b_{2}$, and so on. If $a_{1}\neq b_{2}$ we say the
run has length $0$.

For the inverse map, we will describe a recursive algorithm which reduces the
sizes of $(A,B)$ step-by-step and builds a $3$-composition by distinguishing
two cases. First, assume $A=B$. Then we map the pair to $A$ with all parts
having label $1$. Note, that in this case the run is trivial as it consists of
the full composition.

Second, assume $A\neq B$. Let the run have length $k$, i.e., $a_{k+1}\neq
b_{k+1}$. Now we keep the first $k$ identical parts and attach a label $1$. If
$a_{k+1}<b_{k+1}$ we keep $a_{k+1}$ and attach a label $3$; if
$a_{k+1}>b_{k+1}$ we keep $b_{k+1}$ and attach a label $2$. Finally, we
subtract the extracted sequence from the first parts of $A$ and $B$, and
remove afterwards initial zeros.

We repeat this process with the new parts. As the sizes decrease in each step
by at least one, this process terminates. Moreover, note that in each step
both parts decrease by the same size. Hence, in the last step the process ends
with case one where both parts are equal, and therefore the final part gets
label $1$ as required in $3$-compositions. ∎

######  Example 2.4.

Consider the $3$-composition $6_{1}+1_{2}+4_{3}+2_{1}$ of $n=13$. First, we
remove the labels of color $1$, use label $L$ for color $2$, and label $R$ for
color $3$. Second, we create two identical copies. In the first copy, we
remove the labels $R$ and add the parts labeled by $L$ to the next part. If
the next part has also a label $L$, then the addition continues to the next
part, etc. Similarly, in the second copy, we remove the labels $L$ and add the
parts labeled by $R$ to the next part. This gives a pair of compositions of
$n$ without any labels, and we have shown in Proposition 2.3 that this is in
fact a bijection.

$6_{1}+1_{2}+4_{3}+2_{1}$$(6+1_{L}+4_{R}+2)$,
$(6+1_{L}+4_{R}+2)$$(6+1_{L}+4+2)$, $(6+1+4_{R}+2)$$(6,1_{L}+4,2)$,
$(6,1,4_{R}+2)$$(6,5,2)$, $(6,1,6)$

We end this discussion on compositions, by mentioning another class of
compositions introduced by Ouvry and Polychronakos [38] while working on
closed lattice random walks which confine a given area. A _$g$ -composition_
is a composition that allows both positive integers and zeros, such that at
most $g-2$ consecutive zeros may appear between positive parts. Hopkins and
Ouvry show that $g$-compositions are in bijection with Andrews’
$k$-compositions. We adapt their proof slightly, by considering the zeros
after a positive part.

######  Proposition 2.5 ([30]).

There is a natural bijection between $k$-compositions and $g$-compositions
with $g=k+1$.

###### Proof.

The number of zeros after a positive part $\lambda$ determine the color of
$\lambda$. If $\lambda$ is followed by $k$ zeros we map it to $\lambda_{k+1}$
(and vice versa). The order of appearance of positive parts remains unchanged.
Since, in $g$-composition there are at most $g-2$ zeros between positive
parts, these correspond in $k$-compositions to $k=g-1$ different colors. ∎

We have already seen how pairs of compositions serve as an important link
between the fields of compositions and lattice paths. To reinforce this point
we will add some more examples of how they are linked to predominant
combinatorial and analytic objects. Generic pairs of compositions can be also
be subdivided into two important pairs of subclasses: Concave compositions and
convex compositions. These are ubiquitous in contemporary literature and are
related to important concepts like mock theta functions and Hardinian arrays.

Pairs of CompositionsConcave CompositionsConvex CompositionsMock Theta
Functions [4]Hardinian Arrays [21]

There have been historically two different definitions of concave compositions
(which only slightly differ but the basic idea remains the same). Simply put,
concave compositions are compositions where parts decrease up to the middle
after which the parts increase again. Similarly convex compositions are those
compositions where the parts increase up to the middle after which they weakly
decrease till the end. Concave compositions are interesting because their
generating function is a mixed mock modular form, which is related to the
study of moonshine in Mathieu groups [8]. They are also related to partition
functions where the greatest part is odd/even and also partition functions
where the smallest non-appearing part is odd/even [3, 4, 34].

We will show now a new link between convex compositions and pairs of
compositions to Hardinian arrays, which were introduced by Dougherty-Bliss and
Kauers in [21].

######  Definition 2.6 (Hardinian Arrays).

For any positive integer $r$, let $H_{r}(n,k)$ be the number of $n\times k$
arrays which obey the following rules:

  * •

The entry in position $(1,1)$ is 0, and the entry in position $(n,k)$ is
$\max(n,k)-r-1$.

  * •

The entry in position $(i,j)$ must equal or be one more than each of the
entries in positions $(i-1,j)$, $(i,j-1)$, and $(i-1,j-1)$.

  * •

The entry in position $(i,j)$ must be within $r$ of $\max(i,j)-1$.

We consider the _hooks_ of the Hardinian array, i.e., the numbers appearing
above an element of the diagonal and the numbers to the left of the diagonal.
(These kind of shapes have been considered in the theory of partitions and
compositions so we borrow the definition of a hook from that literature). The
numbers in a hook in a Hardinian array are arranged such that they are weakly
increasing up to the diagonal element whether looked from left to right or top
to bottom. There are a number of operations that can be performed on a hook in
a Young’s diagram of a partition. The simplest one is just straightening the
hook around the diagonal element which is used to give an elementary proof of
why the number of partitions into odd, distinct parts is equal to the number
of self-conjugate partitions[47]. If we straighten the hooks in a Hardinian
array we can immediately see that we get for each hook a convex composition;
see Figure 2.

${\boldsymbol{0}}$${1}$${1}$${2}$${3}$${1}$${\boldsymbol{1}}$${1}$${2}$${3}$${2}$${2}$${\boldsymbol{2}}$${2}$${3}$${2}$${2}$${3}$${\boldsymbol{3}}$${3}$${3}$${3}$${3}$${3}$${\boldsymbol{3}}$$\left(\vbox{\hrule
height=36.30911pt,depth=36.30911pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=36.30911pt,depth=36.30911pt,width=0.0pt}\right)$${\boldsymbol{0}}$${1}$${\boldsymbol{1}}$${1}$${2}$${2}$${\boldsymbol{2}}$${1}$${1}$${2}$${2}$${3}$${\boldsymbol{3}}$${2}$${2}$${2}$${3}$${3}$${3}$${3}$${\boldsymbol{3}}$${3}$${3}$${3}$${3}$
Figure 2. An equivalent representation of a Hardinian array with $r=1$ as a
triangle of convex compositions (obeying rules analogous to Definition 2.6).

Dougherty-Bliss and Kauers show in [21, Theorem 1] that
$H_{1}(n,n)=\frac{1}{3}(4^{n-1}-1)$ for $n\geq 1$, which is immediately
connected to the $3$-compositions of Andrews we have just seen. If we restrict
in any $3$-composition the first part to be the same color as the last part,
then we automatically decrease the number of compositions by a factor of $3$
(except the case where the first part and the last part are equal). Therefore
the number of $3$-compositions with first and last part of the same color is
equal to $\frac{1}{3}(4^{n-1}-1)$ = $H_{1}(n,n)$. Now, Proposition 2.3
motivates the search for pairs of compositions, or by Proposition 2.1 for Dyck
walks. Note that by the bijections, if in a $3$-composition the first and last
color are the same, then the pairs of compositions have the same first part.

######  Proposition 2.7.

There is a natural bijection between Hardinian arrays of size $n\times n$ with
parameter $r=1$ and pairs of compositions of $n$ with equal first part.

###### Proof.

We are going to work in the equivalent number triangle introduced above. Then,
the center column starts with a $0$, ends with a $n-2$, and increases weakly
from top to bottom. Hence, one number is used twice and all the others only
once. Let $s\geq 2$ be the row of the second appearance. By the rules of a
Hardinian array in Definition 2.6, the $i$th row contains numbers from
$\\{i-1,i\\}$. Therefore, since each row is a convex composition, row $s$ and
all rows below rows are deterministically filled with the minimum entry.

It remains to consider the rows $2,3,\dots,s-1$, whose center column is
$1,2,\dots,s-1$. Observe that the center column separates the triangle into a
left and right one that are independent of each other. We will now map each
side to a composition of $n-s$ as illustrated in Figure 3. For this purpose we
define the following walk on the elements of the triangles. Start at the entry
next to row $s-1$. Recursively, for row $i$, if the current entry is $i$ go
the the left/right, if it is $i-1$ go up.111Note that equivalent paths already
appear in the original proof of [21, Theorem 1]. Count in each row the number
of visited entries (including a final entry when leaving the triangle). Read
this sequence from bottom to top. As these walks have $n-s$ steps, this gives
a composition of $n-s$, and each such composition corresponds to a unique
walk. This gives a composition $C_{L}$ for the left triangle, and $C_{R}$ for
the right triangle. Finally, attach the value $s$ as first part, and the claim
follows.

For the reverse bijection directly follows from reversing these steps: The
first part determines the center column, and the remaining parts the left and
right triangle. ∎

RowRange Comp. $C_{L}$ Comp.
$C_{R}$${1}$${\\{0\\}}$${\boldsymbol{0}}$${2}$${\\{0,1\\}}$${1}$${\boldsymbol{1}}$${1}$
${2}$${3}$${\\{1,2\\}}$${2}$
${2}$${2}$${\boldsymbol{2}}$${1}$${1}$${1}$${4}$${\\{2,3\\}}$${2}$${2}$${2}$${3}$${\boldsymbol{3}}$${2}$${2}$${2}$${1}$${5}$${\\{3,4\\}}$${3}$${3}$${3}$${3}$${\boldsymbol{3}}$${3}$${3}$${3}$${3}$
Figure 3. The Hardinian array from Figure 2 is in bijection with the pair of
compositions $((1,2,2),(1,1,1,2))$ with equal first part $1$; see Proposition
2.7.

######  Remark 2.8.

Let $M(n)$ denote integer compositions with equal first and last part. Then we
also find that $M(2n)=H_{1}(n,n)$. In general, $M(n)$ is equal to the number
of tilings of a $2\times n$ rectangle with $1\times 2$ dominoes and $2\times
2$ squares, which gives the Jacobsthal numbers A001045 and interestingly is
also equal to Hopkins and Ouvry’s $g$-compositions ($g=2$) of $n+1$ without
any 1s.

Dougherty-Bliss and Kauers [21] also prove that $H_{r}(n,n)$ satisfies linear
recurrences with polynomial coefficients for $r\geq 2$, which, however, do not
admit simple closed forms. But they show that for $r=1$ the rectangular case
has the solution $H_{1}(n,k)=4^{k-1}(n-k)+H_{1}(k,k)$ for $n\geq k\geq 1$,
which we also suspect to have an interpretation as a family of compositions.

In the next section we will extend the connection from Proposition 2.1 between
pairs of compositions and Dyck paths by proving further bijections between
different classes of lattice paths, among which some are enumerated by
$4^{n-1}$. In these classes, the distribution of peaks will play a key role.

###  2.2. Bijections involving peaks and crossings in paths

Let us first consider the number of peaks $\mathtt{u}\mathtt{d}$ in all Dyck
paths. A peak has _height $h$_ if its $\mathtt{u}$ step ends on height $h$. A
_Dyck path with marked peak_ is a Dyck path in which one peak gets a special
marker. We consider such paths to be different, if they are different paths,
or, if they consist of the same path but have different marked peaks.

Moreover, we will need the concept of _negative Dyck paths_ : these consist of
steps $\mathtt{u}$ and $\mathtt{d}$, start at the origin, end on the $x$-axis,
and always stay weakly below the $x$-axis. Note that there are many known
bijections between Dyck paths and negative Dyck paths, like, e.g., flipping
the path by swapping each $\mathtt{d}$ by $\mathtt{u}$ and vice versa; or,
alternatively, rotating the full path by $180^{\circ}$.

In our first result we connect Dyck paths with marked peaks and Dyck bridges
(i.e., paths ending at $0$ that may traverse below the $x$-axis).

######  Theorem 2.9.

There is an explicit bijection between Dyck paths with marked peak of height
$h$ and Dyck bridges starting with a $\mathtt{d}$ step and $h-1$ crossings of
the $x$-axis preserving the length. Therefore, the number of peaks in all Dyck
paths of length $2n$ is equal to $\binom{2n-1}{n}$.

###### Proof.

First, let a Dyck path $D$ with marked peak at height $h$ be given. Using this
peak, we decompose the path $D$ into a left part $L$ from the origin to this
peak and a right part $R$ from this peak to the end: $D=LR$ such that $L$ ends
with $\mathtt{u}$ and $R$ starts with $\mathtt{d}$. In $L$ we perform a last-
passage decomposition, cutting at the $\mathtt{u}$ leaving a certain altitude
for the last time; while in $R$ we perform a first-passage decomposition,
cutting at the $\mathtt{d}$ bringing us down to a new altitude the first time;
see Figure 4. More formally, we have

(1) $\displaystyle\begin{aligned}
L&=L_{1}\mathtt{u}L_{2}\mathtt{u}\dots\mathtt{u}L_{h}\mathtt{u},\\\
R&=\mathtt{d}R_{h}\mathtt{d}R_{h-1}\mathtt{d}\dots\mathtt{d}R_{1},\end{aligned}$

where $L_{i}$ and $R_{i}$ for $j=1,\dots,h$ are Dyck paths. Now, we pair the
paths $L_{i}\mathtt{u}$ and $\mathtt{d}R_{i}$ with the same index and map them
to non-empty Dyck paths

$\displaystyle D_{i}=\mathtt{u}L_{i}\mathtt{d}R_{i}.$

Then we concatenate these parts, after mapping each other part to its negative
pair using any fixed bijection $\varphi$ between Dyck paths and negative Dyck
paths. This gives the Dyck bridge

(2)
$\displaystyle\varphi(D_{1})D_{2}\varphi(D_{3})D_{4}\dots\varphi(D_{h-1})D_{h}$

when $h$ is even. For odd $h$ it ends with $\varphi(D_{h})$. This bridge
starts with a down step $\mathtt{d}$ and crosses the $x$-axis $h-1$ times, as
claimed.

xyLR

xy

Figure 4. Dyck path with a marked peak (red dot) at height 6 and image under
bijection from Theorem 2.9 given by a Dyck bridge starting with a $\mathtt{d}$
step and 5=6-1 crossings (red dots). The black steps are used in the last-
passage (resp., first-passage) decomposition in the proof.

Second, let a Dyck bridge starting with a $\mathtt{d}$ step be given. We cut
at each crossing of the $x$-axis and recover the components $D_{i}$ and
$\varphi(D_{i})$. Hence, it is straightforward to recover the components
$L_{i}$ and $R_{i}$ and to rebuild the Dyck path $D$ with marked peak.

Finally, bridges of length $2n$ are counted by $\binom{2n}{n}$, as there is an
equal number of up and down steps. As half of them start with a down step, we
get $\frac{1}{2}\binom{2n}{n}=\binom{2n-1}{n}$. ∎

######  Remark 2.10.

The choice of $\varphi$ and the mapped pairs $L_{i}$ and $R_{i}$ that form
$D_{i}$ is arbitrary and many other choices are possible, which would lead to
different bijections between these two classes. For the map $\varphi$ any
bijection between Dyck paths and negative Dyck paths is usable. Moreover, the
above proof immediately also gives a bijection to Dyck bridges starting with
an $\mathtt{u}$ step, by applying $\varphi$ in (2) only to components with
even index.

######  Remark 2.11.

The counting sequence for the total number of peaks in Dyck paths is A001700
in the OEIS222The On-Line Encyclopedia of Integer Sequences: http://oeis.org/,
and counts many other combinatorial objects. One of those is a special class
of pairs of compositions, namely pairs $(A,B)$ of compositions of $n$ such
that $A$ and $B$ have equal number of parts or $A$ has one more part than $B$.
It is easy to see that these pairs are in bijection with compositions of $2n$
such that the sum of the elements at odd positions is equal to the sum of the
elements at even positions, mentioned in A001700.

Next we consider the sum of all heights in all Dyck paths of length $2n$. Our
chain of bijections will explain its remarkably simple formula $4^{n-1}$. For
this purpose we generalize the class of Dyck paths with marked peak. A _Dyck
path with height-labeled peak_ , is a Dyck path in which one peak gets a label
from $\\{1,2,\dots,h\\}$ where $h$ is the height of the specific peak.

######  Proposition 2.12.

There is an explicit bijection between Dyck paths with height-labeled peak
with label $\mu$ at height $h$ and Dyck bridges of the same length with marked
strict left-to-right maximum at height $\mu$ and $h-\mu$ crossings of the
$x$-axis after this maximum.

###### Proof.

This bijection follows directly from the one described in the proof of Theorem
2.9, whose notation we will use here. The difference is that here we
concatenate the (positive and negative) Dyck paths differently.

Let a Dyck path with height-labeled peak be given. Let $h$ be the height of
this peak and $\mu\in\\{1,\dots,h\\}$ be its label. First, we apply the
bijection $\varphi$ onto all parts $L_{i}$ in (1). From that we get the
following bridge in which the height-labeled peak is now a left-to-right
maximum (underlined):

$\displaystyle\varphi(L_{1})\mathtt{u}\varphi(L_{2})\mathtt{u}\dots\mathtt{u}\varphi(L_{h})\,\underline{\mathtt{u}\mathtt{d}}\,R_{h}\mathtt{d}R_{h-1}\mathtt{d}\dots\mathtt{d}R_{1}.$

Next, we transform this bridge, such that in the end the height-label $\mu$
constitutes the height of the left-to-right maximum. For this purpose, we
create and concatenate the paths $D_{i}$ and $\varphi(D_{i})$ in an
alternating fashion at the end:

(3)
$\displaystyle\varphi(L_{1})\mathtt{u}\varphi(L_{2})\mathtt{u}\dots\mathtt{u}\varphi(L_{\mu})\,\underline{\mathtt{u}\mathtt{d}}\,R_{\mu}\mathtt{d}R_{\mu-1}\mathtt{d}\dots\mathtt{d}R_{1}\,\varphi(D_{\mu+1})D_{\mu+2}\varphi(D_{\mu+3})\dots
D_{h},$

when $h-\mu$ is even. Otherwise, the last $D_{h}$ is replaced by
$\varphi(D_{h})$.

For the reverse direction, let a Dyck bridge with marked left-to-right maximum
be given. It is then straightforward to decompose it into (3) and to reverse
the steps above to build a Dyck path. The left-to-right maximum becomes the
height-labeled peak, labeled by its current height. Observe that the height-
labeled peak is lifted by the number of crossings of the $x$-axis to the left
of this peak. ∎

Next, we connect our results with yet another class of paths: _$2$ -colored
bridges_; see [11, Section 6.4]. They are defined as the concatenation of two
bridges such that the first bridge is colored in color $1$ and the second one
in color $2$. Note that contrary to [11], we allow each part to be empty.
Hence, it is easy to see that its generating function is equal to the square
of the generating function $B(z)=\frac{1}{\sqrt{1-4z^{2}}}$ of bridges:

$B(z)^{2}=\frac{1}{1-4z^{2}}.$

The following Proposition 2.15 provides a combinatorial explanation for this
equality with the generating function of unconstrained walks. For its proof we
will need the following lemma, which we enrich by the statistics of _negative
returns to zero_ , which are $\mathtt{u}$ steps that end on the $x$-axis,
i.e., they come from below.

######  Lemma 2.13 ([36]).

There is an explicit bijection between Dyck bridges with $k$ negative returns
to zero and Dyck meanders of the same length $2n$ ending at altitude $2k$.
Therefore the number of such paths is $\binom{2n}{n}$.

###### Proof.

See [36, p. 185 and Fig. 3]. Note that in this paper negative Dyck paths are
defined as minimal Dyck paths, i.e., they touch the $x$-axis only at the
beginning and at the end: $\mathtt{d}\varphi(D)\mathtt{u}$. However, classical
Dyck paths (i.e., stay always weakly above the $x$-axis) do not need to be
minimal and are therefore either empty or the shape $\mathtt{u}D\mathtt{d}D$.
∎

######  Remark 2.14 (Alternative bijection between even-length Dyck bridges
and meanders).

A different bijection can be derived using the ideas developed for Theorem
2.9. It then connects the number of crossings in the Dyck bridge with the
final altitude of the Dyck meander as follows. Given a Dyck bridge, cut at
each crossing of the $x$-axis. This gives decomposition (2) with an additional
Dyck path $D_{0}$ at the beginning, that could be empty in contrast to the
$D_{i}$ with $i>0$. Then, we get a meander ending at altitude $2h$ by flipping
each negative Dyck path $\varphi(D_{i})$ and replacing its final step by
$\mathtt{u}$. If the initial excursion $D_{0}$ is non-empty, then $h$ was the
number of crossings of the $x$-axis, while, if $D_{0}$ is empty, then the
number of crossings was $h-1$.

######  Proposition 2.15.

There is an explicit bijection between $2$-colored Dyck bridges and
unconstrained Dyck walks of the same length $2n$.

###### Proof.

In all cases we will use Lemma 2.13 to transform bridges into meanders.
Sometimes, it will be necessary to transform a meander further into a negative
meander, by flipping all steps, i.e., exchanging $\mathtt{u}$ by $\mathtt{d}$
and vice versa.

We distinguish four cases. First, the first and second bridges are non-empty.
The idea is that the change in color corresponds to the last crossing of the
$x$-axis. For this purpose we transform the second bridge into a meander or
negative meander and attach it to the first bridge such that the attached
meander continues on the other side of the $x$-axis. We can easily reverse
this procedure by cutting at the last crossing of the $x$-axis. All the other
cases will have no crossings of the $x$-axis. Second, if the first bridge is
non-empty and the second one is empty, we transform the first bridge into a
meander. Third, if the first bridge is empty and the second on is non-empty,
we transform the second bridge into a negative meander. Finally, if both
bridges are empty, we map them to the empty walk. ∎

The following proposition connects Dyck bridges with marked strict left-to-
right maximum and $2$-colored Dyck bridges and ends the chain of bijections of
objects all enumerated by $4^{n-1}$. For a proof using generating functions
see [14, Theorem 1].

######  Proposition 2.16.

There is an explicit bijection between Dyck bridges of length $2n$ with marked
strict left-to-right maximum at height $h$ and $2$-colored Dyck bridges of
length $2n-2$ with $h-1$ crossings of the $x$-axis in color $1$.

###### Proof.

Let us start with a Dyck bridge with marked strict left-to-right maximum of
length $2n$. Then, we cut the bridge at the first return to the $x$-axis after
this maximum. The second part to the right is a bridge, which we give color
$2$. Onto the first part we apply a similar idea as in the bijection of
Theorem 2.9. As before, we cut the path at the marked left-to-right maximum
into a left and right part given by $LR$, such that $L$ ends with $\mathtt{u}$
and $R$ starts with $\mathtt{d}$. Then, we further decompose it similar to (1)
into

$\displaystyle L$
$\displaystyle=L_{1}\mathtt{u}L_{2}\mathtt{u}\dots\mathtt{u}L_{h}\mathtt{u},$
$\displaystyle R$
$\displaystyle=\mathtt{d}R_{h}\mathtt{d}R_{h-1}\mathtt{d}\dots
R_{2}\mathtt{d},$

where $h$ is the height of the peak, the $L_{i}$ are negative excursions, and
the $R_{i}$ are excursions. Note that in this case $R$ ends with a
$\mathtt{d}$ step and contains only $h-1$ Dyck paths $R_{i}$. As in the proof
of Theorem 2.9 we form Dyck paths
$D_{i}=\mathtt{u}\varphi(L_{i})\mathtt{d}R_{i}$ for $i=2,\dots,h$, however, we
need to flip the parts $L_{i}$ here. Finally, we remove the two steps of the
marked peaks, and get the following bridges with $2$ steps less (compare with
Equation (2)):

$\displaystyle L_{1}D_{2}\varphi(D_{3})D_{4}\dots\varphi(D_{h-1})D_{h},$

when $h$ is even. For odd $h$ it ends with $\varphi(D_{h})$. ∎

After having proven the chain of bijections shown in Figure 1, we will explore
connections between Dyck paths with more space constraints and integer
compositions in the next section.

###  2.3. Compositions and paths in a strip

In this section, we will explore connection between integer compositions and
Dyck paths and bridges in strips.

######  Theorem 2.17.

There is an explicit bijection between Dyck paths of length $2n$ and height at
most $2$ with $k$ returns to zero and integer compositions of $n$ with $k$
parts.

###### Proof.

Let a Dyck path $\mathcal{D}$ with the claimed properties be given. We cut at
each return to zero and decompose it into a sequences of arches:
$\mathcal{D}=A_{1}A_{2}\dots A_{k}$. Let now $p_{2,i}\geq 0$ be the number of
peaks at level $2$ of $A_{i}$. Note that each $\mathtt{u}$ step that does not
leave the $x$-axis, contributes to a peak by the constraint of height at most
$2$. Hence the _$2$ -peak profile_ $(p_{2,i})_{i=1}^{k}$ uniquely
characterizes $\mathcal{D}$. Finally, we need to shift the $2$-peak profile by
$+1$ to get the claimed integer composition of $n$. Note that this $+1$ may be
associated to the unique $\mathtt{u}$ leaving the $x$-axis. Hence, each
$\mathtt{u}$ step contributes to exactly one part.

$\displaystyle
n=\left(p_{2,1}+1\right)+\left(p_{2,2}+1\right)+\dots+\left(p_{2,k}+1\right).$

For the inverse bijection one simply reverses the above steps. ∎

The previous bijection yields the following interpretation of Andrews’
$k$-compositions.

######  Corollary 2.18.

There is an explicit bijection between Dyck paths of length $2n$ and height at
most $2$ in which each return to the $x$-axis bar the last one has one of $k$
colors and Andrews’ $k$-compositions. Therefore, they are enumerated by
$(k+1)^{n-1}$.

###### Proof.

By Theorem 2.17 each return corresponds to one part, hence, each color may be
associated to this part and the claim holds. An alternative proof of the
counting formula follows directly from the explicit generating function of the
considered Dyck paths. ∎

We can further generalize this class of Dyck paths as follows.

######  Theorem 2.19.

The number of Dyck bridges of length $2n$ in the strip $[-2,2]$ such that each
crossing of the $x$-axis is colored by one of $k$ colors, is equal to
$2(k+2)^{n-1}$

###### Proof.

Note that half of the paths start with an up step and half of them with a down
step, which explains the factor $2$. Let us enumerate the paths starting with
an up step. First, we cut at each crossing of the $x$-axis. Each part (after a
flip along the $x$-axis) is an instance of a Dyck path of length $2n_{i}$ of
height at most $2$. Hence, by Theorem 2.17 the $i$th part is in bijection with
a composition of $n_{i}$ and therefore enumerated by $2^{n_{i}-1}$. Finally,
we attribute the color of the crossing to the part starting at that crossing.
Hence, each, except the first part, may have one of $k$ colors. Therefore, the
total number of such paths is

$\displaystyle\sum_{i=1}^{n}\sum_{\begin{subarray}{c}n_{1}+\dots+n_{i}=n\\\
n_{i}\geq
1\end{subarray}}k^{i-1}2^{n_{1}+\dots+n_{i}-i}=2^{n-1}\sum_{i=1}^{n}\left(\frac{k}{2}\right)^{i-1}\binom{n-1}{i-1}=\left(k+2\right)^{n-1},$

proving the claim. ∎

We leave it as an open problem to build an explicit bijection between these
bridges starting with an up step and $(k-1)$-compositions. Inspired by our
proved bijections, we will study arithmetic properties of classes of Dyck
paths that are hard to enumerate in the next section.

##  3\. Congruences and Peak Profiles for Paths

Arithmetic properties of integer compositions and partitions have been studied
in detail for the greater part of the last century [41, 37, 1, 6, 35, 31, 29].
Motivated by our previous connections between compositions and Dyck paths, we
show now arithmetic properties of certain classes of Dyck paths without
explicit and “simple” closed forms in terms of formulas or generating
functions.

One such class are Dyck paths in which we restrict the number of allowed peaks
per level. Recall from Section 2.2 that a peak $\mathtt{u}\mathtt{d}$ has
height $h$ if its $\mathtt{u}$ step ends on height $h$.

######  Definition 3.1 (Peak profile).

The _peak profile_ $(p_{i})_{i>0}$ of a Dyck path $\mathcal{P}$ is a sequence
of non-negative integers such that $p_{i}$ is equal to the number of peaks of
height $i$ in $\mathcal{P}$

Previously, the equivalent concept of a _peak heights multiset_ appeared in
the literature. For a given Dyck path, it is the multiset of all heights of
peaks. Callan and Deutsch proposed the problem [18] of counting all distinct
peak height multisets (or equivalently, peak profiles) for Dyck paths of
length $2n$. The answer is $2^{n}-\sum_{k=0}^{n-1}p(k)$ where $p(k)$ is the
number of integer partitions of $k$; see [19] and A208738. This formula can
also be interpreted as the difference of the number of compositions of $n+1$
and the number of $1$s in all partitions of $n$ [28, Result 4].

Note that in the proof of Theorem 2.17, we already encountered a special case
of this concept in terms of the $2$-peak profile. This definition is motivated
by the profile of rooted trees, which associates to each tree the sequence
$(t_{i})_{i\geq 0}$, where $t_{i}$ is the number of nodes at depth $i$; see
[22]. In particular, by the glove bijection [26], which maps Dyck paths of
length $2n$ to rooted plane trees with $n+1$ nodes, the peaks of height $i$
are exactly the leaves at depth $i$. Thus, the peak profile corresponds to the
_leaf profile_ of rooted plane trees.

In this section, we will study Dyck paths with given peak profile. For a given
parameter $r\in\mathbb{N}$ we will focus on the class of profiles
$P_{r}=\\{(p_{i})_{i>0}\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists
k\geq 0:p_{1}=\dots=p_{k}=r,p_{i}=0\text{ for }i>k\\}$. In other words, the
Dyck paths have exactly $r$ peaks at each reached depth. By the previous
discussion, these are in bijection with trees that have exactly $r$ leaves in
each reached level. Let $D_{r}(n)$ be the number of Dyck paths whose profile
is in $P_{r}$. Note that the counting sequences for $r=1$ and $r=2$ are listed
in the OEIS: $(D_{1}(n))_{n\geq 0}=(1,1,0,2,0,4,6,8,24,\dots)$ is A287846 and
$(D_{2}(n))_{n\geq 0}=(1,0,1,0,0,3,6,0,9,\dots)$ is A287845. Even though these
numbers are difficult to compute, our techniques will allow us to derive
certain arithmetic properties. The main result of this section will be Theorem
3.8, in which we will show that $r+1$ divides $D_{r}(n)$ for $n>r$.

As a motivation of such a result, let us first consider some simpler peak
profiles. First, let $\Delta=\\{(p_{i})_{i>0}\leavevmode\nobreak\
:\leavevmode\nobreak\ 0\leq p_{i}\leq 1\text{ for all }i>0\\}$, which means
that no two peaks occur at the same height. Let $D_{\Delta}(n)$ be the number
of such Dyck paths of length $n$. For these no closed form is known, but we
can derive combinatorially the following congruence.

######  Lemma 3.2.

We have $D_{\Delta}(n)\equiv 1\mod(2)$.

###### Proof.

For a given path, we can associate another path to it by traversing it from
right-to-left instead of left-to-right. This involution maps the path with
only one peak to itself, while it maps all other paths to a different path.
Hence the total number is always odd. ∎

As a second introductory example, consider the profile class
$S_{r}=\\{(p_{i})_{i>0}\leavevmode\nobreak\ :\leavevmode\nobreak\
\sum_{i>0}p_{i}=r\\}$ that characterizes Dyck paths with exactly $r$ peaks. It
is well known, that the number $D_{S_{r}}(n)$ of associated Dyck paths of
length $n$ is equal to the famous Narayana numbers
$N(n,r)=\frac{1}{n}\binom{n}{r}\binom{n}{r-1}$. The following divisibility
result follows directly from [16, Theorem 1.2].

######  Lemma 3.3.

Let $e\geq 2$ and $n,k\geq 0$ be integers. Then it holds that

$\displaystyle N(2^{e}n+2,2^{e}k+1)$ $\displaystyle\equiv
N(2^{e}n+2,2^{e}k+2)\mod(2),$ $\displaystyle N(2^{e}n+2,2^{e}k+i)$
$\displaystyle\equiv 0\mod(2)$ $\displaystyle\text{ for }3\leq i\leq 2^{e}.$

It remains to find a combinatorial interpretation of these results. As a
direct corollary, one can consider the profile class $S_{\leq
r}=\\{(p_{i})_{i>0}\leavevmode\nobreak\ :\leavevmode\nobreak\
\sum_{i>0}p_{i}\leq r\\}$ that characterizes Dyck paths with at most $r$
peaks. Then it holds that the associated number $D_{S_{\leq r}}(n)$ of Dyck
paths of length $n$ is divisible by $2$ for all $n\equiv 2\mod(2^{e})$ and
$r\not\equiv 1\mod(2^{e})$.

Our goal in this section is to study the divisibility properties of Dyck paths
with exactly $r$ peask _per reached level_ associated with $P_{r}$. For this
purpose, we will need the class of _little Schröder paths_ that we discuss in
the next section.

###  3.1. Little and large Schröder paths

These are lattice paths with steps $\mathtt{u}=(1,1)$, $\mathtt{d}=(1,-1)$,
and $\mathtt{h}_{2}=(2,0)$, without $\mathtt{h}_{2}$ steps at height zero,
that start at $(0,0)$, end at $(2n,0)$, and always stay weakly above the
$x$-axis. _Large Schröder paths_ are defined as above, but the steps
$\mathtt{h}_{2}$ are allowed everywhere. Note that the semi-length is given by
the sum of $\mathtt{u}$ and $\mathtt{h}_{2}$ steps. The number of little
Schröder paths of semi-length $n$ is given by A001003. When fixing the number
of $\mathtt{u}$ steps, they satisfy the following simple formula.

######  Lemma 3.4.

Let $s_{n,i}$/$\ell_{n,i}$ be the number of little/large Schröder paths of
semi-length $n$ with $i$ steps $\mathtt{u}$. They satisfy the following closed
forms

$\displaystyle s_{n,i}$
$\displaystyle=\frac{1}{n+1}\binom{n+i}{i}\binom{n-1}{i-1},$
$\displaystyle\ell_{n,i}$
$\displaystyle=\frac{1}{i+1}\binom{n+i}{i}\binom{n}{i}.$

The sequence for $s_{n,i}$ is A033282, also counting the dissections of a
complex $(n+1)$-gon into $i$ regions. The sequence for $\ell_{n,i}$ is
A088617.

###### Proof.

Define the bivariate generating functions $S(t,u)=\sum_{n,i\geq
0}s_{n,i}t^{n}u^{i}$ and $L(t,u)=\sum_{n,i\geq 0}\ell_{n,i}t^{n}u^{i}$. From
the definitions, we directly get

$\displaystyle S(t,u)$ $\displaystyle=\frac{1}{1-tuL(t,u)},$ $\displaystyle
L(t,u)$ $\displaystyle=1+tL(t,u)+tuL(t,u)^{2}.$

Therefore $S(t,u)$ satisfies the equation

$\displaystyle t(u+1)S(t,u)^{2}-(t+1)S(t,u)+1=0.$

Thus $D(t,u)=tS(t,u)$ is the generating function of dissections of a convex
$(n+1)$-gon into $i$ regions; see [25, Theorem 3(i) and Section 3.1]. The
coefficients of $D(t,u)$ can be extracted using Lagrange inversion. The result
for large Schröder paths follows analogously. ∎

######  Remark 3.5.

An alternative derivation of $S(t,u)$ uses the well-known generating function
$D(t,u)=\sum_{n,i\geq 0}d_{n,i}t^{n}u^{i}$ of Narayana numbers
$d_{n,i}=\frac{1}{n}\binom{n}{i-1}\binom{n}{i}$: number of Dyck paths of semi-
length $n$ with $i$ peaks (and $i-1$ valleys). Choose a subset of the $i-1$
valleys and replace each $\mathtt{d}\mathtt{u}$ in the chosen valley by
$\mathtt{h}_{2}$. The semi-length stays the same and there are no
$\mathtt{h}_{2}$ steps on the $x$-axis. Moreover, all such paths are different
and we create all little Schröder paths. Hence, this proves $S(t,u)=D(t+1,u)$;
see the comment by Paul Boddington in A033282.

Before we give the main result of this section, let us comment on the
following “combinatorial curiosity” [25, p. 216] nicely linking with the
results of the previous section. Let $s_{r}=\sum_{i\geq 0}s_{r,i}$ be the
total number of little Schröder paths, also known as _Schröder numbers_ ,
_super-Catalan numbers_ , or _Schröder–Hipparchus numbers_ ; see [45].

######  Proposition 3.6.

Dyck paths of height $2$ with exactly $r$ peaks at each height are in
bijection with $(r+1)$-tuples of integer compositions (including the
composition of $0$ into $0$) with grand total sum $r$. Both are enumerated by
$(r+1)s_{r}$.

###### Proof.

Let Dyck path with the claimed properties be given. First, we decompose the
path into an $r+1$ tuple by removing the $r$ hills (i.e., peak at height $1$).
The first part is the subpath before the first hill, the second part is the
subpath between the first and second hill, and so on. Note that these parts
are either empty or contain only peaks at height $2$.

Second, we map each part to an integer composition as in Theorem 2.17. If the
part is empty, it is mapped to $0$. Otherwise, we cut at the returns to zero
and map each subpart to the number of peaks at height $2$. As the total sum of
peaks at height $2$ is $r$ the grand total sum of the compositions is also
$r$.

For the inverse map, it suffices to reverse these steps. Finally, the
enumeration sequence was derived in [25, p. 216]. Alternatively, it follows
from the proof of Theorem 3.8; see Remark 3.9. ∎

This result allows us to give the following interpretation for the central
binomial coefficients. Note that it also directly gives a new interpretation
for the Catalan numbers $\frac{1}{r+1}\binom{2r}{r}$, imposing that number of
2-pyramids never exceeds the number of hills (or vice versa).

######  Corollary 3.7.

Dyck paths with exactly $r$ hills ($\mathtt{u}\mathtt{d}$) and $r$ pyramids of
height $2$ ($\mathtt{u}\mathtt{u}\mathtt{d}\mathtt{d}$) are in bijection with
Dyck bridges of semi-length $r$ and $(r+1)$-tuples of integer compositions
consisting only of $1$s with grand total sum $r$. Hence, all these objects are
enumerated by $\binom{2r}{r}$.

###### Proof.

For the first bijection, replace each hill by an $\mathtt{u}$ step and each
pyramid of height $2$ by a $\mathtt{d}$ step (or vice versa). The second part
directly follows from Proposition 3.6. Combining both bijections, observe that
the $i$th composition, corresponds to the run of up steps after the $i$th down
step; see [10]. ∎

###  3.2. Dyck paths with exactly r peaks per reached level

After this discussion of Schröder paths, we are ready to prove the following
divisibility property.

######  Theorem 3.8.

Let $D_{r}(n)$ be the number of Dyck paths with semi-length $n$ and with
exactly $r$ peaks for every reached height. Then $D_{r}(n)\equiv 0\mod(r+1)$
for $n>r$.

###### Proof.

We will construct the paths recursively height-by-height, by lifting all
possible paths of a given height by one. Let a Dyck path with $k$ returns to
zero and exactly $r$ peaks for every reached height be given. Thus, it
decomposes into a sequence of $k$ non-empty arches:

$\displaystyle A_{1}A_{2}\dots A_{k}.$

Let us call the returns inside the path _contacts_ , i.e., the path above has
$k-1$ contacts. Now we will cut at a subset $S$ of the contacts and lift the
full paths by one: We attach an $\mathtt{u}$ step at the beginning,
$\mathtt{d}$ at the end, and insert at each chosen contact a valley
$\mathtt{d}\mathtt{u}$. The height of this new path increased by one and its
length by $i+1$. Furthermore, it has $i=|S|$ contacts and $i+1$ returns to
zero. This gives the new decomposition

$\displaystyle\widetilde{A}_{1}\widetilde{A}_{2}\dots\widetilde{A}_{i+1}.$

Note that this new path still satisfies the constraint of having exactly $r$
peaks for each reached height greater than one. It remains to insert $r$ hills
of the form $\mathtt{u}\mathtt{d}$ at ground level, which is equivalent to
inserting at the beginning, the end, or between the new arches
$\widetilde{A}_{j}$. For this purpose we choose a multiset consisting of $r$
of these $i+2$ positions. In total this gives $\binom{r+i+1}{r}$ possibilities
that fulfill the peak constraint.

Note that the construction above creates all Dyck paths with the given
constraint. We can reverse it by removing all steps on ground level and
concatenating the parts. The same reasoning as above gives the number of
equivalent paths we create in each step.

Let us now define the generating function
$F(z,u)=\sum_{n,k}f_{n,k}z^{n}u^{k}$, where $f_{n,k}$ gives the number of Dyck
paths with exactly $r$ peaks for each reached height of semi-length $n$ with
$k$ returns to zero. Next we define a linear operator
$\operatorname{\mathcal{L}}_{r}$ that implements the construction discussed
above:

(4)
$\displaystyle\operatorname{\mathcal{L}}_{r}(u^{k})=\sum_{i=0}^{k-1}\binom{r+i+1}{r}\binom{k-1}{i}(zu)^{r+i+1}.$

The sum goes over all subset sizes of a $k-1$ element set, the term
$\binom{k-1}{i}$ represents the number of such subsets, and the $+1$ in the
power of $zu$ comes from the initial $\mathtt{u}$ and final $\mathtt{d}$ after
a lift. Then we extend this operator linearly to polynomials in $u$, by
treating the variable $z$ as a constant. Note that this operator can also be
expressed in terms of hypergeometric functions

$\displaystyle\operatorname{\mathcal{L}}_{r}(u^{k})=(r+1)(zu)^{r+1}{}_{2}F_{1}\left(\begin{matrix}r+2,\leavevmode\nobreak\
1-k\\\ -2\end{matrix};-zu\right)$

This hypergeometric function has in general no integer coefficients, and in
particular most terms are divided by $r+1$. Because of that this
representation does not prove the divisibility property; however, it gives a
strong hint.

By the reasoning above, this allows us to define the functional equation

$\displaystyle
F(z,u)=(zu)^{r}+\operatorname{\mathcal{L}}_{r}\left(F(z,u)\right).$

The term $(zu)^{r}$ corresponds to the unique path of height $1$ that consists
of $r$ peaks: $(\mathtt{u}\mathtt{d})^{r}$. Note that this functional equation
has a unique formal power series solution, as the length in $z$ increases by
at least one in each iteration.

In order to prove the divisibility of $D_{r}(n)$ by $r+1$ for $n>r$, we will
use the linearity of the operator: We will show that all terms after one
lifting operation fulfil this property, and therefore all terms in the
sequence. We start with the only path of length $r$ given by
$(\mathtt{u}\mathtt{d})^{r}$ corresponding to the monomial $(zu)^{r}$. This
path contains $r$ returns to zero, and we compute

(5)
$\displaystyle\operatorname{\mathcal{L}}_{r}((zu)^{r})=z^{r}\sum_{i=1}^{r}\binom{r+i}{i}\binom{r-1}{i-1}(zu)^{r+i}.$

Here, we rediscover the sequence $s_{r,i}$ from Lemma 3.4, yet multiplied by
$r+1$. Hence, the claimed divisibility property follows. ∎

######  Remark 3.9.

Note that setting $z=u=1$ in (5), this proves the formula $(r+1)s_{r}$ for
Dyck paths of height $2$ with $r$ peaks at each height from Proposition 3.6.
Yet, setting only $z=1$ this gives a refined count, showing that $s_{r,i}$
counts such paths with exactly $i$ double-falls $\mathtt{d}\mathtt{d}$.

However, it remains a combinatorial mystery why the Schröder numbers $s_{r}$
(or, rather, $(r+1)s_{r}$) appear here. In addition to the above
interpretations for $s_{r,i}$, these numbers also enumerate plane trees whose
with $r$ leaves and $i$ internal nodes of (out-)degree greater than or equal
to $2$, as well as to plane trees of height at most $2$, with $r$ leaves each
in levels $1$ and $2$ and $i$ internal nodes in level $1$. The latter
interpretations follows from an application of the glove bijection (traversing
the contour of a plane tree) to the Dyck paths of Proposition 3.6.

The lifting technique of Theorem 3.8 can also be used to study Dyck paths with
different peak profiles. For example, the profile $P_{\leq
r}=\\{(p_{i})_{i>0}\leavevmode\nobreak\ |\leavevmode\nobreak\ 0\leq p_{i}\leq
r\\}$ corresponds to Dyck paths with at most $r$ peaks per level. Let
$E_{r}(n)$ be the number of such paths of length $n$. In order to enumerate
them, one simply replaces in (4) each $r$ in the summands by $j$ and adds an
inner sum for $j$ from $0$ to $r$. For small values of $r$ these sequences are
in the OEIS: $(E_{1}(n))_{n\geq 0}=(1,1,1,3,5,13,31,71,\dots)$ is A281874,
$(E_{2}(n))_{n\geq 0}=(1,1,2,4,12,31,90,\dots)$ is A287966, $(E_{3}(n))_{n\geq
0}=(1,1,2,5,13,40,119,\dots)$ is A287967. This information led us to the
following result.

######  Proposition 3.10.

$E_{1}(n)\equiv 1\mod(2)$.

###### Proof.

As discussed in the beginning of this section, by the glove bijection, Dyck
paths with at most $1$ peak per level are in bijection with plane trees with
at most $1$ leaf per level. We now partition the trees of size $n$ into one
singleton set and sets of size $k!$ for $k\geq 2$. Thus, the total number of
trees of size $n$ is odd.

First, the singleton set consists of the unary _chain_ , i.e., a tree that
never branches. Second, let a tree different from the chain be given. When
traversing this tree starting from the root, there is a first node that
branches. Let $k$ be its outdegree. Then, we define a set associated to this
tree by considering all $k!$ permutations of the respective children. Note
that all of these are distinct as each level consists of at most $1$ leaf. ∎

Up till $r=10$ we did not discover any further arithmetic properties for this
class of peak profiles. We invite the reader to study his/her favorite peak
profile, and derive more such results.

###  3.3. Congruences for the number of specific steps in paths

As the number of up steps in Schröder paths was the key parameter for proving
the previous congruences, we will discuss general congruences for the number
of specific steps in general directed lattice paths at the end of this
section. The paths start at $(0,0)$ and draw their steps from a finite step
set $\mathcal{S}\subset\mathbb{Z}$. For example, $\mathcal{S}=\\{-1,1\\}$
corresponds to steps of Dyck paths, and $\mathcal{S}=\\{-1,0,1\\}$ to steps of
Motzkin paths. As before, we call bridges paths ending on the $x$-axis,
meanders paths never crossing the $x$-axis, and excursions paths that are at
the same time bridges and meanders.

######  Lemma 3.11.

Let $b_{n}(s)$ be the number of steps $s\in\mathcal{S}$ in all bridges of
length $n$. Then, we have for $n>0$

$\displaystyle b_{n}(s)$ $\displaystyle\equiv 0\pmod{n}.$

Moreover, for a symmetric step set $\mathcal{S}=-\mathcal{S}$, we have for
$n>0$

$\displaystyle b_{n}(s)$ $\displaystyle\equiv 0\pmod{2}.$

Hence, for a symmetric step set and odd $n$ it holds that $b_{n}(s)\equiv
0\pmod{2n}$.

###### Proof.

The results follow from transformations in the spirit of the previous
sections. For the first result, we build cyclic shift inspired by the cycle
lemma. Let $\mathcal{B}$ be a bridge of length $n$. Then, there exists a
unique representation of $\mathcal{B}$ as the concatenation of a minimal
bridge $\mathcal{B}^{\prime}$ of size $n^{\prime}=\frac{n}{m}$ repeated $m$
times, i.e.,

$\mathcal{B}=(\mathcal{B}^{\prime})^{m}.$

Note that $m\geq 1$, as $\mathcal{B}^{\prime}=\mathcal{B}$ is a candidate, yet
in general not the minimal one. Let $b(s)$ and $b^{\prime}(s)$ be the number
of steps $s$ in $\mathcal{B}$ and $\mathcal{B}^{\prime}$, respectively. Then,
the above decomposition shows that $b(s)=mb^{\prime}(s)$. Let
$\sigma(\mathcal{B})$ be the cyclic shift of the steps in $\mathcal{B}$, i.e.,
the first step of $\mathcal{B}$ is moved to the end. Observe that we have

$\displaystyle\sigma(\mathcal{B})=\sigma(\mathcal{B}^{\prime})^{m}.$

Moreover, due to the minimality of $\mathcal{B}^{\prime}$, the first
$n^{\prime}-1$ cyclic shifts lead to mutually distinct bridges
$\sigma^{k}(\mathcal{B})$ (equivalently, different
$\sigma^{k}(\mathcal{B}^{\prime})$), while
$\sigma^{n^{\prime}}(\mathcal{B})=\mathcal{B}$. Hence, the orbit of this
operation consists of $n^{\prime}$ different bridges. Since each of these
bridges has $mb^{\prime}(s)$ steps $s$, the total number of steps $s$ in this
orbit is equal to $n^{\prime}mb^{\prime}(s)=nb^{\prime}(s)$. Finally, note
that these orbits form a partition of all bridges and therefore the result
follows.

For the second result, we apply the repeatedly used involution on bridges of
mirroring along the $x$-axis. Thereby, each bridge is mapped into a different
bridge in which the positions of $s$ and $-s$ swap. The final claim follows
directly by combining the previous two results. ∎

######  Example 3.12.

For Dyck bridges with step set $\mathcal{S}=\\{-1,1\\}$ it is easy to see that
$b_{2n}(s)=n\binom{2n}{n}$ (and $b_{2n+1}(s)=0$), as every Dyck bridges is
composed of an equal number of steps $-1$ and $1$. Hence, our result implies
that $\binom{2n}{n}\equiv 0\pmod{2}$ and $\binom{4n+2}{2n+1}\equiv 0\pmod{4}$
for $n>0$. Alternatively, this result follows from Kummer’s famous result [33]
that the highest power of a prime $p$ dividing $\binom{m+n}{n}$ is equal to
the number of carries in the addition of $m$ and $n$ in base $p$; for more
details see [44].

##  4\. Restrictions on peaks and parts

###  4.1. Restricted summits

We have previously seen the notion of peaks $\mathtt{u}\mathtt{d}$ in Dyck
paths. Now, we want to analyze them in more detail in Dyck bridges. As bridges
may go below the $x$-axis, we introduce the following more general notion of
summits.

######  Definition 4.1 (Summit).

A summit in a path is a point that has a larger ordinate than all its direct
neighbors.

Therefore, in a Dyck bridge (and walk) three types of summits may occur: A
point inside the path if it is part of the pattern $\mathtt{u}\mathtt{d}$, the
starting point is a summit if the first step is $\mathtt{d}$, the end point is
a summit if the last step is $\mathtt{u}$. Let us consider Dyck bridges with
non-decreasing summits. Dyck paths with the same property where studied in
[40]; see A048285.

######  Theorem 4.2.

The number of Dyck bridges of semi-length $n$ with non-decreasing summits is
equal to the odd Fibonacci number $F_{2n+1}$ (i.e., $F_{0}=0$, $F_{1}=1$,
$F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 2$) given by A001519.

###### Proof 1 (Generating functions).

We give a first proof using generating functions. The key observation of non-
decreasing summits is the following: every non-terminal sequence of down steps
has to be followed by a sequence of up steps of at least the same length.

We perform a first-passage decomposition and cut the bridge at the first up
steps leading to a new level. If there are any summits at this level they have
to appear before the next up step leading to the next level. Moreover, no
summits may be below this level. Thus, these “first” up steps are followed by
(possibly empty) sequences of flipped pyramids $\mathtt{d}^{k}\mathtt{u}^{k}$.
Let $\overline{\mathcal{P}}=\\{\mathtt{d}^{k}\mathtt{u}^{k}:k\geq 1\\}$ be the
set of flipped pyramids. Therefore, we get the following decomposition

$\operatorname{SEQ}\left(\operatorname{SEQ}(\overline{\mathcal{P}})\mathtt{u}\right)\operatorname{SEQ}(\overline{\mathcal{P}})\mathtt{d}^{h},$

where $h$ is the height of the last up step, thus, returning to the $x$-axis.
This translates into the following generating function. Note that as we count
paths by semi-length, it suffices to weight up steps by $z$.

$\frac{1}{1-\frac{z}{1-\frac{z}{1-z}}}\frac{1}{1-\frac{z}{1-z}}=\frac{1-z}{1-3z+z^{2}}.$

This is the generating function of odd Fibonacci numbers, which proves the
claim. ∎

###### Proof 2 (Bijection)..

Deutsch and Prodinger [20] show that several combinatorial objects are counted
by the odd Fibonacci numbers. A particular class is given by Dyck paths of
semi-length $n+1$ with non-decreasing valley heights. We will now present an
explicit bijection between these and Dyck bridges of semi-length $n$ and non-
decreasing summits.

The key observation is that both classes satisfy related decompositions. For
this purpose recall that
$\overline{\mathcal{P}}=\\{\mathtt{d}^{k}\mathtt{u}^{k}:k\geq 1\\}$ is the set
of flipped pyramids, and let
$\mathcal{P}=\\{\mathtt{u}^{k}\mathtt{d}^{k}:k\geq 1\\}$ be the set of
pyramids. Let a Dyck bridge be given, and decompose it using a first-passage
decomposition into

$\displaystyle B_{0}\mathtt{u}B_{1}\mathtt{u}\dots B_{k}\mathtt{d}^{k},$

where $B_{i}=\operatorname{SEQ}(\overline{\mathcal{P}})$ for $i=0,\dots,k$.
Next, we flip each part $B_{i}$, by exchanging $\mathtt{u}$ and $\mathtt{d}$
steps mapping flipped pyramids to pyramids. Moreover, we insert a peak
$\mathtt{u}\mathtt{d}$ before the final $\mathtt{d}^{k}$, in order to remember
where to cut.

For the reverse bijection, we decompose the Dyck path with non-decreasing
valleys using a last-passage decomposition, i.e., we cut at the last time we
leave a certain height. We get

$\displaystyle D_{0}\mathtt{u}D_{1}\mathtt{u}\dots
D_{k}\,\mathtt{u}\mathtt{d}\,\mathtt{d}^{k},$

where $D_{i}=\operatorname{SEQ}(\mathcal{P})$ for $i=0,\dots,k$. Observe that
these paths necessarily end with an $\mathtt{u}\mathtt{d}$ before the final
run of $\mathtt{d}$ steps. Now, we remove this $\mathtt{u}\mathtt{d}$ and flip
each part $D_{i}$ to regain bridges. ∎

######  Remark 4.3 (More bijections with summits).

Note that Deutsch and Prodinger [20] discuss many further bijections and
enumeration results, which can now be combined with our results and promising
many further interesting bijections worth investigating. For example, the
number of summits minus one is equal to the number of columns in column convex
polyominoes of area $n+1$.

######  Remark 4.4 (OEIS connections).

When we do not allow the full path to be below the $x$-axis, we get A061667:
$F_{2n+1}-2^{n-1}$. This can be seen from the generating function, by
subtracting the generating function for sequences of pyramids given by
$\frac{1-z}{1-2z}$.

When additionally the end point is not considered as a summit, i.e., bridges
could end with $\mathtt{u}$, then the sequence is A105693: $F_{2n+2}-2^{n}$.
To prove this result, simply multiply the previous generating function by the
one for one (possibly empty) pyramid given by $1/(1-z)$.

Note that the class of paths when additionally the paths weakly below the
$x$-axis are allowed, is not in the OEIS. The counting sequence starts as
$(1,2,6,17,47,128,345,\dots)$.

In addition, let us return to peaks, i.e., $\mathtt{u}\mathtt{d}$ inside the
path. When these peaks may start below the $x$-axis, but still have to be non-
decreasing, we get A094864. This sequence also counts the number of one-cell
columns in all directed column-convex polyominoes of area $n$; see [12, Lemma
3.4]. Moreover, this sequence also connected to special cells in stacks of
area $n+1$; see [42, Equation 7].

######  Remark 4.5 (Asymptotic consequences).

Asymptotically, the numbers of Dyck excursions and bridges of semi-length $n$
with non-decreasing summits only differ in the multiplicative constants; both
satisfy $cst\cdot(\frac{3+\sqrt{5}}{2})^{n}$; see [40, Theorem 2]. For
excursions the constant is $c_{E}\approx 0.11998$ whereas for bridges it is
$c_{B}\approx 0.7236$. Therefore, asymptotically, about one out of $6$ bridges
with non-decreasing _summits_ is an excursion.

We conclude this section with another class of compositions linked to
Fibonacci numbers.

######  Definition 4.6 (Decorated Compositions).

A composition of $n$ is called a _decorated composition_ if any $k$ occurring
in the composition can come with $k$ decorations/labels.

For example, the $8$ decorated compositions of $3$ are $3_{1}$, $3_{2}$,
$3_{3}$, $2_{1}+1_{1}$, $2_{2}+1_{1}$, $1_{1}+2_{1}$, $1_{1}+2_{2}$, and
$1_{1}+1_{1}+1_{1}$.

######  Proposition 4.7.

The number of decorated compositions of $n$ is equal to the even Fibonacci
number $F_{2n}$; see A001906.

###### Proof.

There are $k$ decorations for a part $k$ therefore the number of compositions
of $n$ into $m$ parts is given by $(x+2x^{2}+3x^{3}+\dots)^{m}$. Summing over
$m$, gives $\sum_{m=1}^{\infty}\frac{x^{m}}{(1-x)^{2m}}=\frac{x}{1-3x+x^{2}}.$
This is the required generating function for the even Fibonacci numbers. ∎

######  Remark 4.8.

The same proof also shows that the even Fibonacci numbers also enumerate the
norms of the compositions of $n$. The _norm of a composition_ is the product
of its parts, as defined for partitions, see, e.g., [43].

###  4.2. First, Greatest and Smallest Parts

In the theory of partitions it is a well established phenomenon that the first
part and the last part govern the shape of the partition [5, 32, 7]. Nathan
Fine in his manuscript “Some New Results on Partitions” had left several
intriguing theorems on partitions in the Proceedings of the National Academy
of the Sciences but the proofs were not published subsequently. George Andrews
found the subsequent proofs in Fine’s manuscript later and went on to
generalise these theorems connecting them to the Rogers–Ramanujan identities.

The theorem that we are going to discuss below has a striking connection to
Euler’s famous Pentagonal Number Theorem. Nathan Fine himself writes [24] that
the theorem “bears some resemblance to the famous pentagonal theorem of Euler,
but we have not been able to establish any real connection between the two
theorems.”

######  Theorem 4.9.

Let $D_{e}(n)$ and $D_{o}(n)$ be the sets of partitions $\lambda$ of $n$ into
distinct parts, such that the first part $\lambda_{1}$ is even and odd,
respectively. Then:

$D_{e}(n)-D_{o}(n)=\begin{cases}1,&\text{if }n=\frac{k(3k+1)}{2},\\\
-1,&\text{if }n=\frac{k(3k-1)}{2},\\\ 0,&\text{otherwise}.\end{cases}$

We obviously notice from the start that the sign changes occur at pentagonal
numbers. It is only recently that Igor Pak proved the above theorem using an
argument similar to Sylvester and Franklin’s famous constructive proof of the
pentagonal number theorem thereby proving a connection of this theorem to
Euler’s celebrated result in his paper [39]. In a recent article [27] we
examine the following flipped question for integer partitions.

######  Theorem 4.10.

Let $V_{e}(n)$ and $V_{o}(n)$ be the sets of partitions $\lambda$ of $n$ into
distinct parts, such that the last part $\lambda_{1}$ is even and odd,
respectively. Then for $n>6$ we get: $V_{o}(n)>V_{e}(n)$.

We can find a similar theorem for integer compositions into distinct parts
with respective first parts being odd (resp. even). But first we begin with a
simpler setting, i.e. integer compositions such that the first part is odd
(resp. even). Let $C_{o}(n)$ denote the number of integer compositions such
that the first part is odd and $C_{e}(n)$ denote the number of compositions
where the first part is even.

######  Theorem 4.11.

Let $C_{o}(n)$ denote the number of integer compositions such that the first
part is odd and $C_{e}(n)$ denote the number of compositions where the first
part is even. Let $G(n)$ denote the number of closed walks on a triangle
(starting from a chosen vertex). Then:

(6) $\displaystyle C_{o}(n)-C_{e}(n)$ $\displaystyle=G(n-1).$

###### Proof 1 (Generating function and transfer matrix).

We start with the generating function of the number of compositions such that
the first part is odd. The number of compositions of $n$ into $k$ parts such
that the first part is $(2r-1)$ is given by the coefficient of $x^{n}$ in
$x^{2r-1}(x+x^{2}+x^{3}+\dots)^{k-1}$. Therefore the number of compositions of
$n$ into $k$ parts such that the first part is odd is given by
$\frac{x}{1-x^{2}}\frac{x^{k-1}}{1-x^{k-1}}$. So we sum over $k$ to find

$\displaystyle\sum_{n=0}^{\infty}C_{o}(n)x^{n}$
$\displaystyle=\sum_{k=1}^{\infty}\frac{x}{1-x^{2}}{\frac{x^{k-1}}{1-x^{k-1}}}=\frac{x}{1-x-2x^{2}}.$

Similarly we can find the number of compositions of $n$ such that the first
part is even to be the coefficient of $x^{n}$ in the expansion of
$\frac{x^{2}}{1-x^{2}}\frac{1-x}{1-2x}=\frac{x^{2}}{1-x-2x^{2}}$. Therefore,
we see that

$\displaystyle\sum_{n=0}^{\infty}(C_{o}(n)-C_{e}(n))x^{n}=\frac{x(1-x)}{1-x-2x^{2}}.$

Decomposing into partial fractions and simplifying we can see that the
difference between the number of integer compositions with first part
respectively odd and even is given by
$C_{o}(n)-C_{e}(n)=(2^{n-1}+2\,(-1)^{n-1})/3$.

Now the adjacency matrix for the triangle is simply
$A=\left(\begin{smallmatrix}0&1&1\\\ 1&0&1\\\ 1&1&0\end{smallmatrix}\right)$.
If we consider the $n$th power of $A$, the entry in the $i$th row and $j$th
column gives the number of walks of length $n$ from vertex $i$ to vertex $j$.
Thus, the number of closed walks are the diagonal entries of $A^{n}$. Due to
symmetry and the regular degree of each vertex, all diagonal entries are
equal.

The eigenvalues of matrix $A$ are $-1$ (with multiplicity $2$) and $2$ (with
the multiplicity $1$). Therefore, the number of closed walks of length $n$
starting from any of the three vertices and ending at the same vertex is
$2^{n}+2\,(-1)^{n}$. Dividing by $3$, we get the number of closed walks
starting from a definite vertex and ending there which proves our theorem. ∎

###### Proof 2 (Bijection).

First we show that $C_{o}(n)=C_{e}(n)+2C_{e}(n-1)$. Let a composition of $n$
with odd first part $n_{1}$ be given. If $n_{1}>1$ then subtracting $1$ from
the first part, gives a composition of $n-1$ with even first part enumerated
by $C_{e}(n-1)$. If $n_{1}=1$ then removing $n_{1}$ gives an unconstrained
composition of $n-1$ that is enumerated by $C_{o}(n-1)+C_{e}(n-1)$. Therefore,
$C_{o}(n)=C_{o}(n-1)+2C_{e}(n-1)$. Finally, note that $C_{o}(n-1)=C_{e}(n)$ as
adding $1$ to the first part is a bijection. Thus, Claim (6) is equivalent to

$\displaystyle 2C_{e}(n)=G(n),$

which we will prove now bijectively.

In the triangle, we fix a root vertex and label it by $1$ and the other
vertices by $2$ and $3$. This allows us to interpret the factor $2$ as a fixed
first step from vertex $1$ to $2$, and it remains to show that these closed
walks are enumerated by $C_{e}(n)$. For this purpose, we assign to each edge
$(a,b)$, connecting vertices $a$ and $b$, a label $\ell(a,b)$ as follows:

$\displaystyle\ell(1,2)=2,\qquad\ell(1,3)=\bar{2},\qquad\ell(2,3)=\ell(3,2)=1,\qquad\ell(2,1)=\ell(3,1)=\varepsilon,$

where $\varepsilon$ denotes an empty label. The key observation is that each
closed path from $1$ to $1$ of length $n$ is in bijection with a word
$\\{1,2,\bar{2}\\}^{n}$, by reading the edge labels along its traversal.
Observe that in each such traversal, each step $(1,2)$ (resp., $(1,3)$) needs
to be followed by a $(2,1)$ or $(3,1)$ step, because the path is closed.
Therefore, the sum of the labels in the word is equal to the length of the
path.

Finally, each such word is in bijection with a composition of $n$ with even
first part. The idea is similar to Proposition 2.3: We go through the word
from left to right. Each time we read a $\bar{2}$ we remove it and increase
the left neighbor by $2$. After all parts $\bar{2}$ have been removed, what
remains is a composition with even first part, because the path started with a
step from $1$ to $2$.

For the reverse bijection, replace each even part $2m>2$ by the word
$2\bar{2}\dots\bar{2}$ containing $m-1$ letters $\bar{2}$, and each odd part
$2m+1>2$ by $1\bar{2}\dots\bar{2}$ consisting of $m$ letters $\bar{2}$. In
other words, the sum of parts ($\bar{2}$ is treated like $2$) gives $2m$
(resp., $2m+1$). By the above mapping, these words then correspond to a unique
path in the triangle. ∎

######  Remark 4.12.

The previous bijection is a combinatorial interpretation of the underlying
recurrence relation (proved above)

(7) $\displaystyle C_{e}(n)=C_{e}(n-1)+2\,C_{e}(n-2),$

for $n\geq 2$, where $C_{e}(1)=0$ and $C_{e}(2)=1$. As $C_{o}(n)=C_{e}(n-1)$,
the same recurrence with shifted initial conditions $C_{o}(1)=1$ and
$C_{o}(2)=1$ holds for compositions starting with an odd part.

More generally, let $m>0$ be a positive integer. Then the same combinatorial
construction works for compositions $(n_{1},n_{2},\dots,n_{k})$ such that
$n_{1}\equiv i\mod(m)$ for a fixed $i\in\\{0,1,\dots,m-1\\}$. In particular,
let $C_{i}(n)$ be the number of such compositions of $n$. Then, it is easy to
show

$\displaystyle C_{i}(n)=C_{i}(n-1)+\dots+C_{i}(n-m+2)+2\,C_{i}(n-m+1),$

for $n\geq m$ and suitable initial conditions. Then, these are in bijection
with words in the alphabet $\\{1,2,\dots,m-1,m,\bar{m}\\}$ such that the sum
of letters is equal to $n$ ($\bar{m}$ is treated like $m$). Then, one can also
associate to these compositions walks in a (multi-)graph with the labels from
the alphabet. However, it seems to be only “nice” for $m=2$, i.e., the
triangular case.

######  Remark 4.13.

A third proof idea of Theorem 4.11 builds on $C_{o}(n)=C_{e}(n-1)$ combined
with the observation that $C_{o}(n)+C_{e}(n)=2^{n-1}$, as every composition
has either an odd or even first part. Thus, one gets the recurrence
$C_{e}(n)+C_{e}(n-1)=2^{n-1}$, which can be solved using standard methods.

Note that this approach also works for $C_{i}(n)$ for any modulus $m$, as
$C_{i}(n)=C_{i+1}(n+1)$ for $i\in\\{1,2,\dots,m-1\\}$, and obviously
$C_{0}(n)+\dots+C_{m-1}(n)=2^{n-1}$.

In a similar manner we will study the influence of the first steps on the
behavior of lattice paths. We will mention one specific intriguing result from
recent times due to Andrei Asinowski regarding Dyck paths where the first peak
is the highest; see A287709.

######  Theorem 4.14 ([9]).

The number of Dyck paths of semilength $(n-1)$ whose peak of maximum height is
attained by the initial ascent is equal to the number of Dyck paths of
semilength $n$ such that every peak at height $h>1$ is preceded by at least
one peak of height $h-1$.

The analogous question is easily solved for Dyck bridges.

######  Lemma 4.15.

The number of Dyck bridges such that the first peak is the highest is
enumerated by the Catalan numbers.

###### Proof.

We start by decomposing a Dyck bridge in the following fashion; see Figure 5:
We mark the points where the path reaches a particular height for the last
time. Then one down step from each of those points to the next marked point
forms a (possibly empty) negative Dyck path, which becomes a usual Dyck path
after reflection. Because the first peak is the highest (of height $k$ say)
the path may be decomposed as $B_{k}(z)$ = $z^{k+1}D(z)^{k}z^{k-1}$ =
$z^{2k}D(z)^{k}$, where $D(z)$ is the generating function of Dyck
paths/Catalan numbers. Therefore summing over $k$ we obtain all possible Dyck
bridges where the first peak is the highest one:

$\displaystyle\sum_{k=0}^{\infty}z^{2k}D(z)^{k}=\frac{1}{1-z^{2}D(z)}=D(z),$

since $D(z)=1+z^{2}D(z)^{2}$. ∎

######  Remark 4.16.

As demonstrated repeatedly in Section 2.2, we can rearrange and flip the
decomposition in Lemma 4.15 into a sequence of arches giving a classical Dyck
path in a bijective fashion. However, Theorem 4.14 has so far no bijective
explanation and the problem seems rather difficult.

xy Figure 5. Last-passage decomposition of a Dyck bridge used in Lemmas 4.15
and 4.17

Modifying Asinowski’s theorem for the case of Dyck bridges we get back a
surprising connection to pairs of compositions again. Bender, Lawler, Pemantle
and Wilf [13] define irreducible ordered pairs of compositions as follows: Let
$n=b_{1}+\dots+b_{k}=b^{\prime}_{1}+\dots+b^{\prime}_{k}$ be a pair of
compositions of $n$ into $k$ positive parts. This pair is called _irreducible_
if there is no positive $j<k$ for which
$b_{1}+\dots+b_{j}=b^{\prime}_{1}+\dots+b^{\prime}_{j}$. Note that Callan [17]
showed that these are also in bijection with hill-free Dyck bridges. We will
now present a bijection with a different subfamily of Dyck bridges.

######  Lemma 4.17.

The number of Dyck bridges with semi-length $n$, featuring a single highest
peak and initiating with a hill, where each peak of height $h>1$ is preceded
by a peak of height $h-1$, corresponds precisely to the number of irreducible
ordered pairs of compositions of $n$.

###### Proof.

We split the path into two parts such that the first part starts from the
origin and continues up to the vertex of the highest peak. This is the point
where the second part starts and ends when the path finally ends on the
$x$-axis.

The first part is decomposed such that we mark the last time the path crosses
each successive height. So in effect we have a chain beginning with an up step
followed by a non-empty Dyck path followed by an up step and a non-empty Dyck
path and so on, up to the highest peak. Assuming that the highest peak has
height $k$, the path decomposes as $z^{k}(D(z)-1)^{k-1}$ (since the highest
peak is just $\mathtt{u}\mathtt{d}$).

The second part we decompose as we have done just in the previous lemma, such
that we mark the point when path reaches a particular height for the last
time. Then one down step from each of those points to the next marked point
forms a (possibly empty) negative Dyck path and so the path decomposes into
$z^{k}D(z)^{k}$.

So gluing them together gives us the entire path and to find all of these
paths we sum over $k$ which gives us the generating function of all such paths
as

$\displaystyle\sum_{k=1}^{\infty}z^{2k}(D(z)-1)^{k-1}D(z)^{k}=\frac{z^{2}D(z)}{1-z^{2}(D(z)-1)D(z)}=\frac{z^{2}}{z^{2}+\sqrt{1-4z^{2}}}.$

By [13, Theorem 1], $\frac{z}{z+\sqrt{1-4z}}$ is the generating function of
the number of irreducible ordered pairs of compositions of $n$, and the claim
follows. ∎

######  Remark 4.18.

We may also ask the opposite question: What are the number of Dyck bridges
such that the first peak is of the smallest height? We can prove that such
paths are enumerated by the partial sums of Catalan numbers. We leave it as an
open problem to explore whether there is any connections to these numbers and
integer compositions in some paradigm.

## Acknowledgements

This research was supported by the Austrian Science Fund (FWF): P 34142.

## References

  * [1] Zakir Ahmed, Nayandeep Deka Baruah, and Manosij Ghosh Dastidar.  New congruences modulo 5 for the number of 2-color partitions.  J. Number Theory, 157:184–198, 2015.  [doi].
  * [2] George E. Andrews.  The Theory of Compositions, IV: Multicompositions.  The Mathematics student, 76:25, 2007.
  * [3] George E. Andrews.  Concave compositions.  Electron. J. Comb., 18(2):research paper p6, 13, 2011.
  * [4] George E. Andrews.  Concave and convex compositions.  Ramanujan J., 31(1-2):67–82, 2013.  [doi].
  * [5] George E. Andrews.  Partitions with early conditions.  In Advances in combinatorics, pages 57–76. Springer, Heidelberg, 2013.  [doi].
  * [6] George E. Andrews and F. G. Garvan.  Dyson’s crank of a partition.  Bull. Amer. Math. Soc. (N.S.), 18(2):167–171, 1988.  [doi].
  * [7] George E. Andrews and David Newman.  The minimal excludant in integer partitions.  J. Integer Seq., 23(2):article 20.2.3, 11, 2020.
  * [8] George E. Andrews, Robert C. Rhoades, and Sander P. Zwegers.  Modularity of the concave composition generating function.  Algebra Number Theory, 7(9):2103–2139, 2013.  [doi].
  * [9] Andrei Asinowski, 2024.  Private communication.
  * [10] Andrei Asinowski, Benjamin Hackl, and Sarah J. Selkirk.  Down-step statistics in generalized Dyck paths.  Discrete Math. Theor. Comput. Sci., 24(1):Paper No. 17, 40, 2022\.  [doi].
  * [11] Cyril Banderier, Markus Kuba, and Michael Wallner.  Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions.  arXiv, 2022.
  * [12] Elena Barcucci, Renzo Pinzani, and Renzo Sprugnoli.  Directed column-convex polyominoes by recurrence relations.  In TAPSOFT ’93: theory and practice of software development (Orsay, 1993), pages 282–298. Berlin: Springer-Verlag, 1993.  [doi].
  * [13] Edward A. Bender, Gregory F. Lawler, Robin Pemantle, and Herbert S. Wilf.  Irreducible compositions and the first return to the origin of a random walk.  Sém. Lothar. Combin., 50:Art. B50h, 13, 2003/04.
  * [14] Aubrey Blecher, Arnold Knopfmacher, and Helmut Prodinger.  Left-to-right maxima in Dyck bridges and walks.  Bull. Inst. Combin. Appl., Forthcoming articles:1–15, 2024\.
  * [15] Miklós Bóna and Arnold Knopfmacher.  On the probability that certain compositions have the same number of parts.  Annals of Combinatorics, 14:291–306, 2010.
  * [16] Miklós Bóna and Bruce E. Sagan.  On divisibility of Narayana numbers by primes.  J. Integer Seq., 8(2):Article 05.2.4, 5, 2005.
  * [17] David Callan.  An identity for the central binomial coefficient.  arXiv, 2012.  arXiv:1206.3174.
  * [18] David Callan and Emeric Deutsch.  Problem 11624.  Amer. Math. Monthly, 119(2):162–163, 2012.
  * [19] Charles Delorme.  Solution of Problem 11624: Peak Heights in Dyck Paths.  Amer. Math. Monthly, 121(3):272–273, 2014.
  * [20] Emeric Deutsch and Helmut Prodinger.  A bijection between directed column-convex polyominoes and ordered trees of height at most three.  Theor. Comput. Sci., 307(2):319–325, 2003.  [doi].
  * [21] Robert Dougherty-Bliss and Manuel Kauers.  Hardinian Arrays.  arXiv:2309.00487, 2023.
  * [22] Michael Drmota.  Random Trees.  Springer, 2009.
  * [23] Charles F. Dunkl.  Hook-lengths and pairs of compositions.  Journal of computational and applied mathematics, 199(1):39–47, 2007.
  * [24] Nathan J. Fine.  Some new results on partitions.  Proc. Nat. Acad. Sci. U.S.A., 34:616–618, 1948.  [doi].
  * [25] Philippe Flajolet and Marc Noy.  Analytic combinatorics of non-crossing configurations.  Discrete Math., 204(1-3):203–229, 1999.  [doi].
  * [26] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [27] Manosij Ghosh Dastidar.  Parity Bias in Partitions II.  Preprint, pages 1–7, 2024.  Submitted.
  * [28] Manosij Ghosh Dastidar and Sourav Sen Gupta.  Generalization of a few results in integer partitions.  Notes Number Theory Discrete Math., 19(2):69–76, 2013.
  * [29] Hung P. Hoang and Torsten Mütze.  Combinatorial generation via permutation languages. II. Lattice congruences.  Israel J. Math., 244(1):359–417, 2021.  [doi].
  * [30] Brian Hopkins and Stéphane Ouvry.  Combinatorics of multicompositions.  In Combinatorial and additive number theory IV, volume 347 of Springer Proc. Math. Stat., pages 307–321. Springer, Cham, 2021\.  [doi].
  * [31] Fredric T. Howard.  A combinatorial problem and congruences for the Rayleigh function.  Proc. Amer. Math. Soc., 26:574–578, 1970.  [doi].
  * [32] Jiayu Kang, Runqiao Li, and Andrew Y. Z. Wang.  Partition identities related to the minimal excludant.  Discrete Math., 346(4):12, 2023.  Id/No 113302.  [doi].
  * [33] Ernst E. Kummer.  Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen.  J. Reine Angew. Math., 44:93–146, 1852.  [doi].
  * [34] Xiao-Chuan Liu.  On flushed partitions and concave compositions.  European J. Combin., 33(4):663–678, 2012.  [doi].
  * [35] Toufik Mansour, Mark Shattuck, and Mark C. Wilson.  Congruence successions in compositions.  Discrete Math. Theor. Comput. Sci., 16(1):327–338, 2014.
  * [36] Philippe Marchal.  Constructing a sequence of random walks strongly converging to Brownian motion.  In Proceedings of Discrete Random Walks (DRW’03), pages 181–190. Discr. Math. Theor. Comput. Sci., 2003.
  * [37] Ken Ono.  Distribution of the partition function modulo $m$.  Ann. of Math. (2), 151(1):293–307, 2000.  [doi].
  * [38] Stéphane Ouvry and Alexios P. Polychronakos.  Exclusion statistics and lattice random walks.  Nuclear Phys. B, 948:114731, 21, 2019.  [doi].
  * [39] Igor Pak.  On Fine’s partition theorems, Dyson, Andrews, and missed opportunities.  Math. Intelligencer, 25(1):10–16, 2003.  [doi].
  * [40] Jean-Guy Penaud and Olivier Roques.  Génération de chemins de Dyck à pics croissants.  Discrete Math., 246(1-3):255–267, 2002.  [doi].
  * [41] Srinivasa Ramanujan.  Congruence properties of partitions.  In Collected papers of Srinivasa Ramanujan, pages 232–238. AMS Chelsea Publ., Providence, RI, 2000.
  * [42] S. Rinaldi and D. G. Rogers.  How the odd terms in the Fibonacci sequence stack up.  The Mathematical Gazette, 90(519):431–442, 2006.
  * [43] Robert Schneider and Andrew V. Sills.  The product of parts or “norm” of a partition.  Integers, 20A(Proceedings of the Integers Conference 2018):Paper No. A13, 16, 2020.
  * [44] Lukas Spiegelhofer and Michael Wallner.  Divisibility of binomial coefficients by powers of two.  J. Number Theory, 192:221–239, 2018.  [doi].
  * [45] Richard P. Stanley.  Hipparchus, Plutarch, Schröder, and Hough.  Amer. Math. Monthly, 104(4):344–350, 1997.  [doi].
  * [46] Richard P. Stanley.  Catalan numbers.  Cambridge University Press, New York, 2015.  [doi].
  * [47] James J. Sylvester.  The collected mathematical papers of James Joseph Sylvester. Volume IV: (1882–1894). Edited by H. F. Baker.  Cambridge: Cambridge University Press, 2011.