Lattice Paths and Catalan Numbers

Points of the plane are pairs of integers (The integers as equivalence classes of pairs of naturals), added componentwise:

$(x,y)+(x^{\mathrm{\prime }},y^{\mathrm{\prime }}):=(x+x^{\mathrm{\prime }},y+y^{\mathrm{\prime }}),-(x,y):=(-x,-y)\mathrm{.}$

Since $(\mathbb{Z},+,0)$ is a commutative group (The integers form a commutative ring) and each monoid axiom holds one coordinate at a time, $(\mathbb{Z}\times \mathbb{Z},+,(0,0))$ is a commutative monoid (Semigroup and monoid). A natural number written where an integer is expected denotes its image under the embedding $\mathbb{N}\to \mathbb{Z}$, $k\mapsto [(k,0)]$, of The naturals embed in the integers, which is injective and preserves addition, multiplication and the order; no symbol is written for it, so $2$, $n$ and $\mid S\mid$ denote integers when they occur in an integer expression.

A step set is a finite subset $S\subseteq \mathbb{Z}\times \mathbb{Z}$ (The cardinality $\mid A\mid$ of a finite set); its elements are steps.

Definition. Let $n\in \mathbb{N}$ and $P\in \mathbb{Z}\times \mathbb{Z}$. A lattice path of length $n$ with steps in $S$ from $P$ is a function $v:\{0,1,\dots ,n\}\to \mathbb{Z}\times \mathbb{Z}$ with $v(0)=P$ and $v(i)-v(i-1)\in S$ for every $i$ with $1\le i\le n$. It is a path from $P$ to $Q$ when moreover $v(n)=Q$. Write

${\mathcal{L}}_S(P;n):=\{v:v\text{ is a lattice path of length }n\text{ with steps in }S\text{ from }P\},$

and ${\mathcal{L}}_S(P,Q;n)$ for the subset of those with $v(n)=Q$.

A path is nothing but this function. No geometry of the plane is used, no continuous curve is attached to it, and the points $v(0),\dots ,v(n)$ are the only data.

The length-zero case, stated rather than left implicit. For $n=0$ the domain $\{0\}$ has one point and the condition on differences is vacuous, so ${\mathcal{L}}_S(P;0)$ has exactly one element, the function $v$ with $v(0)=P$. This is the empty path at $P$; it is a path from $P$ to $P$, and it exists even when $S=\mathrm{\varnothing }$.

The step word. Words of length $n$ over an alphabet are the functions $\{0,\dots ,n-1\}\to S$, and $S^n$ denotes the set of them (Finite words, contiguous factors, avoidance and proper-prefix states). The step word of a path $v\in {\mathcal{L}}_S(P;n)$ is the word $w\in S^n$ with

$w_{i-1}:=v(i)-v(i-1)(1\le i\le n),$

equivalently $w_j=v(j+1)-v(j)$ for $0\le j\le n-1$. The step word of the empty path is the empty word.

The path traced by a word. Conversely let $w\in S^n$ and $P\in \mathbb{Z}\times \mathbb{Z}$. The path traced by $w$ from $P$ is

$v_w(i):=P+{\sum }_{j<i}{w}_j(0\le i\le n),$

the sum being the finite product of The product $g_0{g}_1\cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ($n=0$) equal to the identity in the commutative monoid $\mathbb{Z}\times \mathbb{Z}$, written additively. Its two defining clauses read ${\sum }_{j<0}{w}_j=(0,0)$ and ${\sum }_{j<i+1}{w}_j={\sum }_{j<i}{w}_j+w_i$, so

$v_w(0)=P,v_w(i)=v_w(i-1)+w_{i-1}(1\le i\le n),$

and $v_w$ is a lattice path of length $n$ with steps in $S$ from $P$, since each displayed difference is the letter $w_{i-1}\in S$.

Concatenation. Let $v$ be a path of length $m$ from $P$ to $Q$ and let $v^{\mathrm{\prime }}$ be a path of length $n$ from $Q$ to $R$, with step words $w$ and $w^{\mathrm{\prime }}$. Their concatenation $v\cdot v^{\mathrm{\prime }}$ is the path of length $m+n$ traced from $P$ by the concatenated word $w{w}^{\mathrm{\prime }}$ (Finite words, contiguous factors, avoidance and proper-prefix states). The common endpoint condition ensures that its first $m$ steps are $v$ and its last $n$ steps are $v^{\mathrm{\prime }}$. Concatenating on the left with the empty path at $P$, or on the right with the empty path at $Q$, changes nothing because $\epsilon w=w=w\epsilon$.

• Why the step set is required to be finite. Nothing in the definition of a path needs it; it is imposed because every count on this page is a count of words over $S$, and a finite $S$ makes every $S^n$ finite. If the finiteness requirement were relaxed, the converse would hold for $n\ge 1$; at $n=0$ the set $S^0$ is the singleton containing the empty word for every $S$.

• A path records where it starts. Two paths with the same step word and different starting points are different functions. Every set of paths written down here therefore fixes a start point, and translation from one start point to another is a separate statement each time it is used.

Let $S$ be a step set, $P\in \mathbb{Z}\times \mathbb{Z}$ and $n\in \mathbb{N}$. The map sending a lattice path to its step word is a bijection

$\mathrm{\Phi }:{\mathcal{L}}_S(P;n)⟶S^n,$

whose inverse sends $w$ to the path $v_w$ traced by $w$ from $P$ (Lattice paths, step sets and step words). Consequently ${\mathcal{L}}_S(P;n)$ is finite with

$\mid {\mathcal{L}}_S(P;n)\mid =\mid S{\mid }^n,$

the power being the natural-number exponentiation of Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$.

• What the lemma is for. Every count on this page is obtained by counting words and transporting the answer along this bijection, so the correspondence is proved once here and cited rather than re-established.

• The start point is fixed throughout. The map $\mathrm{\Phi }$ forgets $P$, and a step word alone therefore determines a path only after a start point has been named.

Put $E:=(1,0)$ and $N:=(0,1)$. A monotone lattice path is a lattice path whose steps lie in the step set $\{E,N\}$ with $E=(1,0)$ and $N=(0,1)$ (Lattice paths, step sets and step words). Write

$\mathcal{M}(P;\mathrm{\ell }):={\mathcal{L}}_{\{E,N\}}(P;\mathrm{\ell }),\mathcal{M}(P,Q):={\bigcup }_{\mathrm{\ell }\in \mathbb{N}}{\mathcal{L}}_{\{E,N\}}(P,Q;\mathrm{\ell }),$

so $\mathcal{M}(P,Q)$ is the set of monotone paths from $P$ to $Q$ of any length. The letters $E$ and $N$ are the two steps and are also used as the two letters of the alphabet of a step word.

Where a monotone path is after $i$ steps. Let $v\in \mathcal{M}((a,b);\mathrm{\ell })$ have step word $w$, and for $0\le i\le \mathrm{\ell }$ let

$\nu (i):=\mid \{j\in \mathbb{N}:j<i,w_j=N\}\mid$

be the number of $N$ letters among the first $i$ (The cardinality $\mid A\mid$ of a finite set). Then

$v(i)=(a+i-\nu (i),b+\nu (i))(0\le i\le \mathrm{\ell })\mathrm{.}$

Indeed $\nu (0)=0$ and $v(0)=(a,b)$; and if the formula holds at $i-1$ then $v(i)=v(i-1)+w_{i-1}$, where $w_{i-1}=E$ gives $\nu (i)=\nu (i-1)$ and raises the first coordinate by $1$, while $w_{i-1}=N$ gives $\nu (i)=\nu (i-1)+1$ and raises the second coordinate by $1$; in both cases the formula holds at $i$. Induction on $i$ (The principle of mathematical induction) gives it for every $i\le \mathrm{\ell }$. Note $\nu (i)\le i$, so the first coordinate is again a point of $\mathbb{Z}$ with $a+i-\nu (i)\ge a$.

Three consequences, recorded because every count below uses them.

(a) Both coordinates are nondecreasing along a monotone path, since $i\mapsto \nu (i)$ and $i\mapsto i-\nu (i)$ are both nondecreasing.

(b) The endpoint determines the length and the letter count. A path $v\in \mathcal{M}((a,b);\mathrm{\ell })$ satisfies $v(\mathrm{\ell })=(c,d)$ if and only if $\nu (\mathrm{\ell })=d-b$ and $\mathrm{\ell }=(c-a)+(d-b)$.

(c) Existence. $\mathcal{M}((a,b),(c,d))$ is nonempty exactly when $a\le c$ and $b\le d$; in that case every one of its members has length $(c-a)+(d-b)$, and the word $E^{c-a}{N}^{d-b}$ traces one of them. Here $c-a$ and $d-b$ denote the natural numbers whose images under the embedding of $\mathbb{N}$ into $\mathbb{Z}$ are those differences.

Degenerate rectangles are included. Under the existence hypotheses $a\le c$ and $b\le d$, if $c=a$ then every step is $N$ and $\mathcal{M}((a,b),(c,d))$ has one element; likewise if $d=b$. If $c=a$ and $d=b$ its one element is the empty path at $(a,b)$.

• "Monotone" names the conclusion of (a), not an extra hypothesis. The definition fixes a step set; the monotonicity of the coordinates is then forced and is proved above rather than assumed.

• Why $\mathcal{M}(P,Q)$ may be written without a length. By (c) all its members have one and the same length, so no information is lost by suppressing it. For a step set in which two different lengths join the same two points this notation would be ambiguous, and it is not used there.

For all $m,n\in \mathbb{N}$ the set $\mathcal{M}((0,0),(m,n))$ of monotone lattice paths from $(0,0)$ to $(m,n)$ (Monotone lattice paths with steps $E=(1,0)$ and $N=(0,1)$) is finite with

$\mid \mathcal{M}((0,0),(m,n))\mid =\left(\genfrac{}{}{0px}{}{m+n}{n}\right),$

the binomial coefficient of The set $[A{]}^k$ of $k$-element subsets and the binomial coefficient $\left(\genfrac{}{}{0px}{}{n}{k}\right):=\mid [n{]}^k\mid$. More generally, if $a\le c$ and $b\le d$ in $\mathbb{Z}$ and $m,n\in \mathbb{N}$ are the natural numbers with $m=c-a$ and $n=d-b$, then

$\mid \mathcal{M}((a,b),(c,d))\mid =\left(\genfrac{}{}{0px}{}{m+n}{n}\right)\mathrm{.}$

• The general-endpoint clause is not decoration. Every later count on this page is a count of paths between two points neither of which is the origin, and it is obtained from this clause rather than by repeating the argument.

• Where the monotonicity is spent. Only in [F2]: it makes the endpoint determine the numbers of $E$- and $N$-steps and hence the length. A fixed start and a fixed step word always determine one endpoint, for every step set; what can fail for a step set containing negative steps is the converse assertion that the endpoint determines the letter counts used by this binomial count.

A diagonal lattice path is a lattice path whose steps lie in the step set $\{U,D\}$ with $U=(1,1)$, $D=(1,-1)$ (Lattice paths, step sets and step words). Write

$\mathcal{W}(P;n):={\mathcal{L}}_{\{U,D\}}(P;n)$

for the diagonal paths of length $n$ from $P$.

Every diagonal path advances one unit in the first coordinate at each step. Both steps have first coordinate $1$, so if $v\in \mathcal{W}((0,a);n)$ and $x(i)$ denotes the first coordinate of $v(i)$ then $x(0)=0$ and $x(i)=x(i-1)+1$ for $1\le i\le n$; induction on $i$ (The principle of mathematical induction) gives $x(i)=i$. Hence

$v(i)=(i,h(i))(0\le i\le n)$

for a unique function $h:\{0,1,\dots ,n\}\to \mathbb{Z}$ (The integers as equivalence classes of pairs of naturals), the height function of $v$. It satisfies

$h(0)=a,h(i)-h(i-1)\in \{1,-1\}(1\le i\le n),$

and conversely every such $h$ is the height function of exactly one $v\in \mathcal{W}((0,a);n)$: the word $w$ with $w_{i-1}=U$ when $h(i)-h(i-1)=1$ and $w_{i-1}=D$ otherwise is the only step word producing those heights, and step words correspond bijectively to paths (For each start point the step word is a bijection onto $S^n$). A diagonal path from $(0,a)$ and its height function are therefore the same datum, and the two are used interchangeably below.

Height after $i$ steps. With $w$ the step word of $v$ and

$\mu (i):=\mid \{j\in \mathbb{N}:j<i,w_j=U\}\mid$

the number of up-steps among the first $i$ (The cardinality $\mid A\mid$ of a finite set), one has

$h(i)=a+\mu (i)-(i-\mu (i))=a+2\mu (i)-i(0\le i\le n)\mathrm{.}$

Indeed $\mu (0)=0$ and $h(0)=a$; and if the formula holds at $i-1$, then $w_{i-1}=U$ raises $h$ by $1$ and $\mu$ by $1$, while $w_{i-1}=D$ lowers $h$ by $1$ and leaves $\mu$ unchanged, so it holds at $i$. Induction on $i$ finishes it.

Prescribing the endpoint. For $b\in \mathbb{Z}$ put

$\mathcal{W}((0,a),(n,b)):=\{v\in \mathcal{W}((0,a);n):h(n)=b\},$

which by the previous paragraph is the set of $v$ whose step word has $2\mu (n)=n+b-a$. It is nonempty exactly when $2$ divides $n+b-a$ (Divisibility in $\mathbb{Z}$: $d\mid a$ when $a=dq$ for some integer $q$) and

$-n\le b-a\le n,$

the second condition being $\mid b-a\mid \le n$, since $\mid x\mid$ is $x$ or $-x$ according as $x\ge 0$ or $x<0$ (The absolute value $\mathrm{\mid }a\mathrm{\mid }$ of an integer). For if such a $v$ exists then $2\mu (n)=n+b-a$ with $0\le \mu (n)\le n$, giving both conditions; and if they hold, then $u:=\mu (n)$ is forced to be the natural number with $2u=n+b-a$, which satisfies $0\le u\le n$, and the word $U^u{D}^{n-u}$ traces such a path.

Levels. For $c\in \mathbb{Z}$ a diagonal path with height function $h$ touches the level $c$ when $h(i)=c$ for some $i$ with $0\le i\le n$; it stays strictly above the level $c$ when $h(i)>c$ for every such $i$, and stays weakly above $c$ when $h(i)\ge c$ for every such $i$.

• The two conditions on the endpoint are not interchangeable. The parity condition says which heights are reachable at all after $n$ steps; the range condition says the height cannot move further than one unit per step. Dropping either leaves an empty set, and the count below is stated so that it returns $0$ in both cases rather than being undefined.

• The height function is the object, the path is the packaging. Every statement below about diagonal paths is a statement about $h$, and the pair $(i,h(i))$ is carried only so that the results of Lattice paths, step sets and step words apply unchanged.

Let $u,d\in \mathbb{N}$ and put $n:=u+d$. Replacing each letter $U$ of a step word by $N$ and each letter $D$ by $E$ induces a bijection

$\mathrm{\Lambda }:\mathcal{W}((0,0),(n,u-d))⟶\mathcal{M}((0,0),(d,u))$

from the diagonal paths of length $n$ from $(0,0)$ ending at height $u-d$ (Diagonal lattice paths with steps $U=(1,1)$ and $D=(1,-1)$, and the height function) onto the monotone paths from $(0,0)$ to $(d,u)$ (Monotone lattice paths with steps $E=(1,0)$ and $N=(0,1)$).

Moreover the two pictures agree step by step: if $v$ has height function $h$ and $\mathrm{\Lambda }(v)(i)=(x_i,y_i)$, then

$h(i)=y_i-x_i(0\le i\le n)\mathrm{.}$

Consequently, for every $c\in \mathbb{Z}$ and every $i$, the height inequality $h(i)\ge c$ holds if and only if $y_i-x_i\ge c$; in particular staying weakly above the level $0$ corresponds to staying weakly above the diagonal $y=x$.

• Why this is a lemma and not a convention. The page uses the rectangular picture for the binomial count and the diagonal picture for heights, levels and reflections. The sources use one or the other and state no correspondence, so a page using both must prove they agree once. Every later statement that moves between the pictures cites this lemma and does not restate it.

• What the correspondence does not do. It matches the two step sets and the two positions, and nothing else. The number of steps is preserved and the two endpoints determine each other, but a level in one picture is a diagonal line in the other, which is why the level statements below are made in the diagonal picture only.

Let $a,b\in \mathbb{Z}$ and $n\in \mathbb{N}$, and let $\mathcal{W}((0,a),(n,b))$ be the set of diagonal lattice paths of length $n$ from $(0,a)$ whose height function ends at $b$ (Diagonal lattice paths with steps $U=(1,1)$ and $D=(1,-1)$, and the height function).

1. Suppose $2$ divides $n+b-a$ and $-n\le b-a\le n$, and let $u\in \mathbb{N}$ be the natural number with $2u=n+b-a$; then $0\le u\le n$ and

   $\mid \mathcal{W}((0,a),(n,b))\mid =\left(\genfrac{}{}{0px}{}{n}{u}\right)\mathrm{.}$

2. If either condition fails then $\mathcal{W}((0,a),(n,b))=\mathrm{\varnothing }$, so its cardinality is $0$.

In both cases the set is finite, and the count depends on $a$ and $b$ only through the difference $b-a$.