Chapter 11: Special Counting Sequences and Lattice Paths

How many paths stay above a diagonal?

A north–east lattice path is a sequence of steps $N=(0,1)$ and $E=(1,0)$ between integer-coordinate points. From $(0,0)$ to $(n,n)$, every path contains exactly $n$ steps of each kind, so there are $\binom{2n}{n}$ unrestricted paths. How many satisfy $y\ge x$ at every visited vertex? Here “above” includes touching the diagonal.

The endpoint alone does not enforce this condition. The word $EN$ ends at $(1,1)$ but immediately visits $(1,0)$, below the diagonal. Record the height $h=y-x$: an $N$ increases it by one, an $E$ decreases it by one, and admissibility means every prefix has nonnegative height. The same rule governs balanced parentheses and a queue whose removals never exceed its insertions. We will count these paths, build explicit bijections, and extend the method to other step sets and several paths at once.

11.1 Catalan numbers

Replace $N,E$ by $U=(1,1),D=(1,-1)$ while retaining their order. A Dyck path of semilength $n$ starts at $(0,0)$, ends at $(2n,0)$, and never has negative height. It has $n$ up-steps and $n$ down-steps. Let $C_n$ count these paths, including $C_0=1$ for the empty path.

Every nonempty Dyck path has a unique first return to height zero. The up-step at its start and the down-step making this return enclose a shorter Dyck path $P$, shifted up by one unit. A second Dyck path $Q$ follows the return. In symbols the path is $UPDQ$. If $P$ has semilength $i$, then $Q$ has semilength $n-1-i$. Conversely, any such pair gives a valid path, so

$$ C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}\qquad(n\ge1). $$

For example, $C_1=1$, $C_2=1+1=2$, and $C_3=2+1+2=5$. The five paths for $n=3$ are $UUUDDD$, $UUDUDD$, $UUDDUD$, $UDUUDD$, and $UDUDUD$. The first few Catalan numbers are therefore $1,1,2,5,14,42$.

If $C(z)=\sum_{n\ge0}C_nz^n$, the same decomposition gives the formal power-series equation $C(z)=1+zC(z)^2$. The recurrence determines its coefficients uniquely from constant term one. Section 11.4 will prove the explicit formula

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

Exercise. Compute $C_4$ using the recurrence. Hint: split the remaining semilength three between $P$ and $Q$. Answer: $5+2+2+5=14$.

11.2 Difference sequences and finite differences

For a sequence $(a_n)_{n\ge0}$, its forward difference is $\Delta a_n=a_{n+1}-a_n$. Repeat this operation to obtain $\Delta^2a_n$, $\Delta^3a_n$, and so on. For instance, the triangular numbers $T_n=\binom{n+1}{2}$ begin $0,1,3,6,10,15$; their first differences are $1,2,3,4,5$, their second differences are all one, and their third differences are zero.

Differences play the role of derivatives for polynomial sequences. If $a_n=p(n)$ for a polynomial of degree $d\ge1$ with leading coefficient $c$, then $p(n+1)-p(n)$ has degree $d-1$ and leading coefficient $dc$. Consequently $\Delta^{d+1}a_n=0$ for every $n$. A useful reconstruction formula is

$$ p(n)=\sum_{r=0}^{d}\binom nr\Delta^r p(0). $$

To justify it, use the polynomial basis $\binom n0,\binom n1,\ldots,\binom nd$. Their distinct degrees make them a basis, and Pascal's identity gives $\Delta\binom nr=\binom n{r-1}$ for $r\ge1$, while the constant basis element has difference zero. Applying $\Delta^s$ at $n=0$ extracts exactly the coefficient of $\binom ns$.

For the triangular numbers, the initial differences are $T_0=0$, $\Delta T_0=1$, and $\Delta^2T_0=1$. Thus $T_n=n+\binom n2=n(n+1)/2$. This proves the formula for every nonnegative integer, because the polynomial model was already established.

A finite difference table alone does not prove that an infinite sequence is polynomial. Any initial list through index $N$ has an interpolating polynomial of degree at most $N$, but its next term need not follow that polynomial. For example, the first five Catalan values $1,1,2,5,14$ have initial differences $1,0,1,1,3$. Their degree-four interpolating polynomial predicts $1+\binom52+\binom53+3\binom54=36$ at index five; the Catalan recurrence gives $42$.

Exercise. Reconstruct $a_n=n^2$ from its initial differences. Hint: use $a_0=0$, $\Delta a_0=1$, and $\Delta^2a_0=2$. Answer: $n+2\binom n2=n^2$.

11.3 Lattice paths, Schröder and Motzkin numbers

A lattice-path count depends on its allowed steps, endpoints, boundary conditions, and size parameter. We now add horizontal steps to Dyck paths, using two different conventions.

A Motzkin path of length $n$ uses $U=(1,1)$, $D=(1,-1)$, and $H=(1,0)$, stays at nonnegative height, and ends at $(n,0)$. Let $M_n$ count it, with $M_0=1$. A nonempty path either begins with $H$ followed by another Motzkin path, or has first-return decomposition $UPDQ$, where $P,Q$ are Motzkin paths. Since the enclosing $U,D$ consume two steps,

$$ M_n=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}\qquad(n\ge1), $$

where an empty sum is zero. Thus $M_1=1$, $M_2=2$, and $M_3=4$. The four length-three paths are $HHH$, $HUD$, $UHD$, and $UDH$. For $M(z)=\sum_{n\ge0}M_nz^n$, this decomposition becomes $M(z)=1+zM(z)+z^2M(z)^2$.

A large Schröder path of semilength $n$ uses $U,D$ and $H_2=(2,0)$, stays at nonnegative height, and ends at $(2n,0)$. Its horizontal step spans two units and is allowed at height zero. Let $R_n$ count these paths, with $R_0=1$. Both an initial $H_2$ and an enclosing $UD$ pair consume one unit of semilength. Consequently

$$ R_n=R_{n-1}+\sum_{i=0}^{n-1}R_iR_{n-1-i},\qquad R(z)=1+zR(z)+zR(z)^2. $$

The values begin $1,2,6,22,90$. At semilength two, the six paths are $UUDD$, $UDUD$, $H_2UD$, $UDH_2$, $UH_2D$, and $H_2H_2$. The adjective “large” fixes the convention: small Schröder paths prohibit horizontal steps at height zero.

In the diagram, every panel uses the same integer grid and endpoint $(4,0)$. The Motzkin horizontal segments each span one column; the Schröder horizontal segment spans two. These are three representative paths, not the complete families.

Exercise. Compute $M_4$ and $R_2$ from their recurrences. Hint: account separately for an initial horizontal step and an enclosing $UD$ pair. Answer: $M_4=4+(2+1+2)=9$, while $R_2=2+(2+2)=6$.

11.4 Ballot theorem and reflection principle

Suppose candidate $A$ receives $p$ votes and candidate $B$ receives $q$, with integers $p\ge q\ge0$. A vote ordering is a word containing $p$ letters $A$ and $q$ letters $B$; votes for the same candidate are indistinguishable. Translate $A$ to an up-step and $B$ to a down-step. The weak ballot condition says $A$ has at least as many votes as $B$ after every prefix.

There are $\binom{p+q}{q}$ unrestricted words. A rejected word first reaches height $-1$ at a uniquely defined step. Interchange $A$ and $B$ in the prefix through that step. The original prefix had one more $B$ than $A$, so the reflected word has $p+1$ letters $A$ and $q-1$ letters $B$ in total.

This map is invertible when $q\ge1$: a word with those new totals ends at height $p-q+2\ge2$ and therefore has a first visit to height $+1$. Interchanging its letters through that visit recovers the rejected original word. Thus the number of weak ballot orderings is

$$ \binom{p+q}{q}-\binom{p+q}{q-1} =\frac{p-q+1}{p+1}\binom{p+q}{q}. $$

We take $\binom{m}{-1}=0$ for $m\ge0$, so this also handles $q=0$, when the unique word is admissible. For $p=q=n$, the formula gives $C_n=\binom{2n}{n}/(n+1)$, proving the closed form promised in section 11.1.

For example, $p=3,q=2$ gives $10-5=5$ weak ballot words: $AAABB$, $AABAB$, $AABBA$, $ABAAB$, and $ABABA$. Reflecting the rejected word $ABBAA$ through its first negative height turns the prefix $ABB$ into $BAA$, giving $BAAAA$; reflecting through the latter word's first visit to height $+1$ reverses the operation.

The strict ballot condition requires $A$ to lead after every nonempty prefix. Assume $p>q$. The first letter must be $A$; remove it and lower subsequent heights by one. The remainder is a weak ballot word with $p-1$ up-steps and $q$ down-steps. Therefore its count is

$$ \binom{p+q-1}{q}-\binom{p+q-1}{q-1} =\frac{p-q}{p+q}\binom{p+q}{q}. $$

For $p=3,q=2$, only $AAABB$ and $AABAB$ satisfy the strict condition. Equality with the diagonal is the difference between the two models.

Exercise. For $p=4,q=2$, find the weak and strict counts. Hint: use the two separate formulas. Answer: $15-6=9$ weak orderings and $(2/6)15=5$ strict orderings.

11.5 Dyck paths and Catalan bijections

A bijection must specify a map, check that its output belongs to the claimed family, and construct an inverse. Recognizing identical initial counts is only a clue.

Balanced parentheses. Replace $U$ with an opening parenthesis and $D$ with a closing parenthesis. At each prefix, height equals the number of unmatched openings. Nonnegative height prevents an unmatched closing, and final height zero means all openings are closed. Conversely, a balanced-parenthesis word has these two properties and reconstructs a Dyck path. Thus there are $C_n$ balanced words with $n$ pairs. For example, $UUDDUD$ becomes (())().

Plane rooted trees. Such a tree has a distinguished root and a specified left-to-right order on the children of every vertex. Traverse its edges in depth-first order, visiting children in their given order. Write $U$ on moving away from the root and $D$ on returning along an edge. Each of the $n$ edges is traversed twice, and height is distance from the root, so the result is a Dyck path of semilength $n$.

For the inverse, start with a root and a stack containing it. On $U$, create a new last child of the current vertex and push it; on $D$, pop the current vertex and return to its parent. Nonnegative height prevents popping past the root, and final height zero leaves the traversal at the root. These procedures undo each other. Hence $C_n$ counts plane rooted trees with $n$ edges and $n+1$ vertices. For $UUDDUD$, the root has two children: its first child has one child, and its second child is a leaf.

Ordered full binary trees. Here each internal vertex has exactly two ordered children; a single leaf has zero internal vertices. Recursively send the empty Dyck path to a leaf and $UPDQ$ to an internal root with left subtree encoded by $P$ and right subtree encoded by $Q$. The inverse recursively reads these two subtrees. The number of internal vertices is the path's semilength, because each enclosing $UD$ pair contributes one. In particular, $UUDDUD=U(UD)D(UD)$ encodes a root whose left and right children are both internal vertices with two leaf children. This tree has three internal vertices and four leaves.

The size conventions differ: a plane rooted tree is counted by edges, whereas a full binary tree is counted by internal vertices. Keeping this distinction explicit makes the Catalan correspondence usable.

Exercise. Decode $UDUD$ as parentheses and as a plane rooted tree. Hint: each return to height zero finishes one child subtree of the root. Answer: ()() and a root with two ordered leaf children.

11.6 Narayana numbers and refined Catalan statistics

Optional extension. The chapter foundation does not require this section. We now refine a Catalan count by a statistic rather than changing the path family.

A peak is an adjacent pair $UD$. For $n\ge1$ and $1\le k\le n$, let $N(n,k)$ count Dyck paths of semilength $n$ with exactly $k$ peaks. These are the Narayana numbers:

$$ N(n,k)=\frac1n\binom nk\binom n{k-1}. $$

This interpretation and formula are recorded in David Callan's paper on generalized Narayana numbers. arxiv.org

We can derive the formula using the first-return decomposition and Lagrange inversion from the preceding chapter. Let $C(z,u)$ sum $z^nu^k$ over all Dyck paths, including the empty path with weight one. In $UPDQ$, the enclosing steps create a new peak exactly when $P$ is empty. Thus

$$ C(z,u)=1+z\bigl(C(z,u)-1+u\bigr)C(z,u). $$

Setting $F=C-1$ gives $F=z(F+u)(F+1)$. Lagrange inversion, applied formally over $\mathbb{Q}[u]$, yields

$$ [z^n]F=\frac1n[t^{n-1}]\bigl((t+u)^n(t+1)^n\bigr). $$

To extract $u^k$, choose $k$ factors contributing $u$ in the first product, leaving $t^{n-k}$. The second product must then contribute $t^{k-1}$. Their choices give $\binom nk\binom n{k-1}/n$, as claimed.

At $n=3$, the paths $UUUDDD$ and $UDUDUD$ have one and three peaks respectively. The other three paths listed in section 11.1 each have two. The row is therefore $1,3,1$, with sum $5=C_3$. In general, summing $N(n,k)$ over $k$ gives $C_n$ because every nonempty Dyck path has a unique peak count.

Exercise. Find the Narayana row for $n=4$. Hint: compute the formula for $k=1,2,3,4$. Answer: $1,6,6,1$, summing to $14$.

11.7 Delannoy paths and lattice-walk enumeration

A Delannoy path uses $E=(1,0)$, $N=(0,1)$, and $J=(1,1)$, with no diagonal boundary restriction. Let $D_{m,n}$ count paths from $(0,0)$ to $(m,n)$ for integers $m,n\ge0$. The diagonal step $J$ advances both coordinates at once.

For $m,n\ge1$, classify a path by its last step. Removing that step leaves a path to one of three predecessors, so

$$ D_{m,n}=D_{m-1,n}+D_{m,n-1}+D_{m-1,n-1}, \qquad D_{m,0}=D_{0,n}=1. $$

These boundary values count the unique straight paths, including the empty path at $(0,0)$. The recurrence gives the small table below.

There is also a direct count. If a path has $k$ diagonal steps, it has $m-k$ east steps and $n-k$ north steps. Arrange this multiset of $m+n-k$ steps. Summing over feasible $k$ gives

$$ D_{m,n}=\sum_{k=0}^{\min(m,n)} \frac{(m+n-k)!}{(m-k)!(n-k)!k!}. $$

For $(m,n)=(2,2)$, the terms for $k=0,1,2$ are $6,6,1$, totaling $13$. Equivalently, a step has weight $x$, $y$, or $xy$, so the formal generating function for arbitrary finite step sequences is

$$ \sum_{m,n\ge0}D_{m,n}x^my^n =\sum_{\ell\ge0}(x+y+xy)^\ell =\frac{1}{1-x-y-xy}. $$

The coefficient extraction is finite at each pair of exponents, making this a valid formal identity.

How does this connect to Schröder paths? Restrict a Delannoy path from $(0,0)$ to $(n,n)$ by $y\ge x$, and change coordinates to $(s,h)=(x+y,y-x)$. Then $N$ becomes $U$, $E$ becomes $D$, and $J$ becomes $H_2$. This is an invertible correspondence with large Schröder paths of semilength $n$. For an inverse, recover $(x,y)=((s-h)/2,(s+h)/2)$; the allowed steps preserve the parity needed for integer coordinates. Thus the constrained count at $(2,2)$ is $R_2=6$, whereas the unrestricted count is $D_{2,2}=13$.

Exercise. Count paths to $(1,2)$. Hint: separate zero and one diagonal step. Answer: three words with steps $E,N,N$ and two words with steps $J,N$, giving $D_{1,2}=5$.

11.8 Nonintersecting paths and the Lindström–Gessel–Viennot lemma

Optional extension. This section is not required for the chapter foundation. A graph consists of vertices joined by edges; a directed edge has a specified direction. Here paths must follow that direction. A directed acyclic graph has no directed cycle. Its vertices can be put in a topological order in which every edge points forward. These are the only graph notions needed below; see the course roadmap for the planned fuller treatment in section 15.1, “Graphs, subgraphs, degree sequences.”

Take a finite directed acyclic graph, distinct source vertices $A_1,\ldots,A_r$, and distinct sink vertices $B_1,\ldots,B_r$, with all $2r$ designated vertices different. Define $M_{ij}$ to be the number of directed paths from $A_i$ to $B_j$. The Lindström–Gessel–Viennot lemma expresses $\det M$ as a signed count of vertex-disjoint path families: the path from $A_i$ ends at $B_{\sigma(i)}$ for a permutation $\sigma$, and the family's sign is $\operatorname{sgn}(\sigma)$. An unsigned counting interpretation additionally requires that every disjoint family use the identity pairing $A_i\to B_i$. The general path-matrix framework and tail-swapping method are discussed in Kelli Talaska's paper on weighted path matrices. arxiv.org

Here is the cancellation argument. Expand

$$ \det M=\sum_{\sigma\in S_r}\operatorname{sgn}(\sigma) \prod_{i=1}^{r}M_{i,\sigma(i)}. $$

Each product chooses one path for each source. For a family containing an intersection, choose its earliest shared vertex in a fixed topological order, then the lexicographically first pair of source indices whose paths share that vertex. Exchange the two path tails after the chosen vertex. The new endpoint permutation differs by a transposition, so its sign is reversed.

Why is this an involution? Prefixes through the chosen vertex are unchanged, while every vertex of an exchanged tail lies later in the topological order. Hence neither an earlier shared vertex nor the chosen pair changes; applying the swap again restores the family. The same ordering prevents a swapped path from revisiting its prefix. Intersecting families cancel in pairs, leaving precisely the signed disjoint families. This explains the finiteness and acyclicity hypotheses.

For lattice applications of the determinant method, see Igor Pak's MIT lecture on Gessel–Viennot determinants. ocw.mit.edu

For a concrete example, use the north–east grid on vertices $(x,y)$ with $0\le x,y\le2$. Set

$$ A_1=(0,0),\quad A_2=(0,1),\quad B_1=(2,1),\quad B_2=(2,2). $$

A path with displacement $(a,b)$ has $\binom{a+b}{a}$ possible step words, giving

$$ M=\begin{pmatrix}3&6\\1&3\end{pmatrix}, \qquad \det M=3\cdot3-6\cdot1=3. $$

We must check the pairing hypothesis. In a crossed family, the path from $A_2$ to $B_1$ is the horizontal word $EE$, visiting every vertex $(x,1)$ for $x=0,1,2$. Any north–east path from $A_1$ to $B_2$ must visit one of those vertices when it first reaches height one. Thus crossed families cannot be disjoint.

The three surviving identity-paired families are listed explicitly. Each word is read from its own source.

Exercise. Why is the pair $(EEN,EEN)$ rejected? Hint: calculate the endpoint of the first path and the penultimate vertex of the second. Answer: both visit $(2,1)$. Sharing a designated endpoint of another path still counts as an intersection.

11.9 André's reflection method and applications

Section 11.4 reflected a first boundary violation for a walk starting at zero. The same method works with an initial buffer. Let $K_\ell(a,b)$ count walks with $\ell$ steps, each $+1$ or $-1$, starting at integer height $a\ge0$, ending at integer height $b\ge0$, and never going below zero.

An unrestricted walk needs $(\ell+b-a)/2$ up-steps. A rejected walk first visits $-1$ at a unique time. Reflect its prefix, including the starting point, across the horizontal line of height $-1$: a height $h$ becomes $-2-h$. The reflected walk starts at $-a-2$, joins the untouched suffix at $-1$, and still ends at $b$. It therefore has $(\ell+b+a+2)/2$ up-steps.

Conversely, every walk from $-a-2$ to $b\ge0$ must visit $-1$. Reflect its prefix through the first such visit to recover a rejected walk from $a$. This bijection proves

$$ K_\ell(a,b)= \binom{\ell}{(\ell+b-a)/2} -\binom{\ell}{(\ell+b+a+2)/2}. $$

For this formula, a binomial coefficient is zero when its lower argument is not an integer or lies outside $0,\ldots,\ell$. This handles impossible parity and displacement automatically. At $a=b=0$ and $\ell=2n$, it reduces to the Catalan formula, since $\binom{2n}{n+1}=\binom{2n}{n-1}$.

For example, $K_4(1,1)=\binom42-\binom44=5$. There are six words with two up-steps and two down-steps. Starting at height one, only $DDUU$ goes below zero: its heights are $1,0,-1,0,1$, including the initial height. The other five words are admissible. This models four insert/remove operations on a queue initially containing one item and finally containing one item, with no attempted removal from an empty queue.

A queue with capacity $H$ imposes a second boundary: its height must stay in $0,\ldots,H$. The preceding one-boundary formula does not impose that extra condition. Instead, let $v_t(h)$ count allowed length-$t$ walks from an initial height $a$. Initialize $v_0(a)=1$ and all other values to zero, then use

$$ v_{t+1}(h)=v_t(h-1)+v_t(h+1)\qquad(0\le h\le H), $$

with values outside the interval set to zero at every stage. Each admissible walk has exactly one final predecessor, which proves this recurrence. For six operations starting and ending empty, capacity two allows four of the five semilength-three Dyck paths; only $UUUDDD$ reaches height three. Capacity one allows only $UDUDUD$.

Exercise. Find $K_4(2,0)$. Hint: there must be one up-step and three down-steps. Answer: $\binom41-\binom44=3$, realized by $UDDD$, $DUDD$, and $DDUD$; $DDDU$ falls below zero.

Build Catalan bijections and count a nonintersecting path family

The chapter's three main mechanisms are now connected. First-return decomposition gives a recurrence; explicit bijections transfer its Catalan count to trees and parentheses; André's reflection method proves the closed form by removing precisely the paths with a boundary violation. A determinant extends cancellation from a single forbidden boundary to intersections among several paths.

For a queue, height is its occupancy. A Dyck path describes a sequence of insertions and removals starting and ending empty without underflow, so Catalan numbers count admissible action schedules with equally many actions of each kind. This counts action types only: it does not count choices of inserted values or attach probabilities to schedules. A capacity limit is a separate boundary handled by the recurrence in section 11.9.