Catalan Counts for Nonnegative Bridges

Nonnegative Bridges and Their Counts

A simple symmetric random walk can return to its starting point while making substantial excursions above and below it. A more constrained path starts at zero, returns to zero at a specified even time, and never visits a negative value. Counting these paths leads to the Catalan numbers, a sequence that also appears in many problems involving nested or recursively split structures. Here the count will come directly from a decomposition of paths, rather than from a general counting formula for paths crossing a barrier.

For a precise setup, let $(\Omega,\mathcal{F},\mathbb{P})$ support independent increments $(\xi_n)_{n\ge1}$, each taking values $+1$ and $-1$ with probability $\tfrac12$. Set $S_0=0$ and $S_n=\sum_{r=1}^n \xi_r$, so $(S_n)_{n\ge0}$ is the simple symmetric random walk on state space $S=\mathbb{Z}$, in discrete time $n$. We use the filtration $\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. A length-$2m$ bridge is a specified sequence of $2m$ increments whose partial sums end at zero. It is nonnegative if every partial sum, including the endpoints, is at least zero.

Definition: Let $C_m$ be the number of length-$2m$ paths with increments $+1$ and $-1$, starting at zero, ending at zero, and satisfying $S_r\ge0$ for every $0\le r\le2m$. The path of length zero is included, so $C_0=1$. A step $+1$ may be denoted $U$ and a step $-1$ by $D$.

A bridge must have exactly $m$ up-steps and $m$ down-steps: if it has $u$ up-steps and $d$ down-steps, then $u+d=2m$ and $u-d=0$, which together give $u=d=m$. Thus the total number of bridges, without the nonnegativity restriction, is $\binom{2m}{m}$. The central task is to count which of those bridges stay nonnegative.

A First-Return Decomposition

Theorem: The counts satisfy $C_0=1$ and, for every integer $m\ge1$, $$ C_m=\sum_{k=0}^{m-1}C_kC_{m-1-k}. $$ Consequently, for every integer $m\ge0$, $$ C_m=\frac{1}{m+1}\binom{2m}{m}. $$

The recurrence comes from a unique split of each nonempty nonnegative bridge. Starting at zero, the first step must be $U$. There is a first later time at which the path returns to zero; the step immediately before that return must be $D$. Between the initial $U$ and this $D$, the path stays at height at least one. Subtracting one from each of those intermediate heights gives a nonnegative bridge. The rest of the original path is another nonnegative bridge. The split counts all possibilities without omission or duplication.

Proof. First consider $m=0$. There is exactly one length-zero path, so $C_0=1$. For $m\ge1$, take any path counted by $C_m$. Its first step is $U$. Since it ends at zero, it has a first return to zero after that step; write the time of this return as $2k+2$, where $0\le k\le m-1$. The segment from time $1$ to time $2k+1$, after subtracting one from its heights, is a length-$2k$ nonnegative bridge: it starts and ends at zero after the shift, and it cannot go below zero because the original path has not yet returned to zero. The step at time $2k+2$ is $D$. The segment after that step is a length-$2(m-1-k)$ nonnegative bridge, since it starts at zero and the original path is nonnegative. Conversely, given any such pair of bridges, place the first between an initial $U$ and a $D$, shifting its heights up by one, then append the second bridge. The resulting path is nonnegative, has length $2m$, and first returns to zero at time $2k+2$. The two constructions undo one another. For each $k$, there are therefore $C_kC_{m-1-k}$ paths, and the possible values of $k$ are disjoint and exhaust all paths. This proves the recurrence.

To solve it, define the formal power series $C(x)=\sum_{m\ge0}C_mx^m$. Multiplying the recurrence by $x^m$ and summing over $m\ge1$ gives $C(x)-1=xC(x)^2$: the coefficient of $x^{m-1}$ in $C(x)^2$ is exactly $\sum_{k=0}^{m-1}C_kC_{m-1-k}$. Thus $xC(x)^2-C(x)+1=0$. The solution with constant term $1$ is $$ C(x)=\frac{1-\sqrt{1-4x}}{2x}. $$ Indeed, the square root is the formal series with constant term $1$; the displayed numerator has zero constant term and is divisible by $x$. The other quadratic root has a nonzero $x^{-1}$ term and is not a formal power series.

For completeness, the coefficient expansion used next follows from the formal binomial theorem. For any fixed $\alpha$, set $b_n=\binom{\alpha}{n}$, where $b_0=1$ and $b_{n+1}=b_n(\alpha-n)/(n+1)$. The series $Y(z)=\sum_{n\ge0}b_nz^n$ satisfies $(1+z)Y'(z)=\alpha Y(z)$, as is verified by matching coefficients using this recurrence. Conversely, that differential equation and $Y(0)=1$ determine each coefficient successively by the same recurrence. Hence $Y(z)=(1+z)^\alpha$ as a formal series.

Apply this identity with $\alpha=\tfrac12$ and $z=-4x$. For $m\ge0$, the coefficient of $x^m$ in $C(x)$ is $$ C_m=-\frac12\binom{\tfrac12}{m+1}(-4)^{m+1}. $$ To simplify it, write $$ \binom{\tfrac12}{m+1} =\frac{(-1)^m(1\cdot3\cdot5\cdots(2m-1))}{2^{m+1}(m+1)!} $$ with the empty product interpreted as $1$ when $m=0$. Also $1\cdot3\cdots(2m-1)=(2m)!/(2^m m!)$, because the even factors in $(2m)!$ multiply to $2^m m!$. Substitution gives $$ C_m=\frac{(2m)!}{m!(m+1)!} =\frac{1}{m+1}\binom{2m}{m}. $$ This proves the claimed formula, including $m=0$, for which it gives $1$. $\square$

Worked Counts and Probability Checks

Worked Example: Bridges of Length Four

Count the nonnegative bridges of length $4$, so $m=2$. The recurrence gives $C_0=1$, $C_1=C_0C_0=1$, and $$ C_2=C_0C_1+C_1C_0=(1)(1)+(1)(1)=2. $$ The two paths are $UUDD$, whose partial sums are $0,1,2,1,0$, and $UDUD$, whose partial sums are $0,1,0,1,0$. Each partial sum is at least zero, so both qualify.

Each specified length-four increment sequence has probability $(\tfrac12)^4=\tfrac1{16}$. Therefore the probability that the walk is a nonnegative bridge of length four is $2\cdot\tfrac1{16}=\tfrac18$. As a check, there are $\binom42=6$ bridges in total, so the probability of ending at zero is $6\cdot\tfrac1{16}=\tfrac38$; among those six bridges, two are nonnegative. The conditional fraction is $2/6=\tfrac13$, and $\tfrac38\cdot\tfrac13=\tfrac18$, as required.

Worked Example: Bridges of Length Six

For $m=3$, the recurrence gives $$ C_3=C_0C_2+C_1C_1+C_2C_0=(1)(2)+(1)(1)+(2)(1)=5. $$ The five paths are $UUUDDD$, $UUDUDD$, $UUDDUD$, $UDUUDD$, and $UDUDUD$. Their partial sums, respectively, are $$ \begin{aligned} &0,1,2,3,2,1,0; \qquad 0,1,2,1,2,1,0;\\ &0,1,2,1,0,1,0; \qquad 0,1,0,1,2,1,0;\\ &0,1,0,1,0,1,0. \end{aligned} $$ Every displayed partial sum is nonnegative, and the recurrence count shows that there are exactly five.

Each path has probability $(\tfrac12)^6=\tfrac1{64}$, so the probability of a nonnegative bridge of length six is $5\cdot\tfrac1{64}=\tfrac5{64}$. The closed formula gives the same count: $$ \frac{1}{3+1}\binom63=\frac14\cdot20=5, $$ where $\binom63=6\cdot5\cdot4/(3\cdot2\cdot1)=20$. Thus the recurrence and the formula agree for this value.

Worked Example: Bridges of Length Eight

Use $C_0=1$, $C_1=1$, $C_2=2$, and $C_3=5$ to calculate the count for $m=4$: $$ \begin{aligned} C_4 &=C_0C_3+C_1C_2+C_2C_1+C_3C_0\\ &=(1)(5)+(1)(2)+(2)(1)+(5)(1)=14. \end{aligned} $$ Independently, the closed formula gives $$ \frac{1}{4+1}\binom84=\frac15\cdot70=14, $$ since $\binom84=8\cdot7\cdot6\cdot5/(4\cdot3\cdot2\cdot1)=70$. This substitution checks the recurrence computation against the formula.

A specified length-eight path has probability $(\tfrac12)^8=\tfrac1{256}$, so the probability of a nonnegative bridge is $14/256=7/128$. The total number of bridges is $70$, and $70/256=35/128$ is the probability of ending at zero. The fraction of bridges that are nonnegative is $14/70=1/5$; multiplying gives $(35/128)(1/5)=7/128$, confirming the probability directly.

Why the Constraint Matters

The formula counts paths that satisfy two conditions at once: they end at zero, and no partial sum is negative. It is not the count of all paths ending at zero. For a fair walk, every length-$2m$ path has probability $2^{-2m}$, so the count immediately gives the joint probability of ending at zero and staying nonnegative. Dividing $C_m$ by $\binom{2m}{m}$ instead gives the fraction of bridges that stay nonnegative, or equivalently the conditional probability of staying nonnegative given that the walk ends at zero. These are different probabilities; the unconditional event also requires the endpoint condition.

Common mistake. For $m=2$, counting only the up-steps gives $\binom42=6$, but that is the number of all bridges, not the number of nonnegative bridges. For example, $DUUD$ has partial sums $0,-1,0,1,0$, so it ends at zero but fails the nonnegativity condition. In fact, only $UUDD$ and $UDUD$ qualify, giving $C_2=2$, not $6$. The correction is to impose the partial-sum condition as well as the endpoint condition, as the recurrence’s path decomposition does.

The decomposition also explains why the Catalan count is recursive: once the first return splits off the initial portion, the remaining portion is an independent choice of another nonnegative bridge. The closed formula makes the count easy to evaluate, while the recurrence keeps visible the path structure behind it. In probability calculations, first identify whether the question asks for a count, a joint probability, or a probability conditional on returning to zero; then use the corresponding denominator.

Check Your Understanding

Use the definition and recurrence, and check that each answer respects both the endpoint and nonnegativity conditions.

How many nonnegative bridges of length $2$ are there? Write the qualifying path and its partial sums.
Use the recurrence to compute $C_3$ from $C_0=1$, $C_1=1$, and $C_2=2$.
For a fair walk, what is the probability of a nonnegative bridge of length $4$? Show how the path count enters.
For $m=4$, calculate $C_4$ both from the recurrence and from $\frac{1}{m+1}\binom{2m}{m}$.
Explain why $\binom{2m}{m}$ counts all bridges but generally overcounts the nonnegative bridges.

Catalan Counts for Nonnegative Bridges

What You'll Learn