Count balanced paths and nested structures with Catalan numbers: five admissible six-step paths, a first-return recurrence and the boundary conventions that matter.
Catalan numbers
Catalan numbers count balanced paths that never fall below their starting level, as well as many recursively nested structures. For a quant, they provide an exact benchmark for a constrained path calculation: ending with zero inventory does not mean that an event sequence avoided negative inventory along the way.
The value C0=1 counts the single empty structure, rather than “no possibilities.” NIST's definition uses up/right lattice paths above a diagonal; the up/down representation below is equivalent.
Three units in, three units out
Consider a fictional inventory system that starts empty. Each arrival adds one unit, U=+1, and each departure removes one, D=−1. There are three arrivals and three departures. A sequence is admissible only if every departure can be filled: inventory may reach zero, but must never become negative.
There are (36)=20 unrestricted orders. Exactly five are admissible:
C3=41(36)=5.
Such an up/down path is called a Dyck path. Its semilength is n, the number of up-steps, so n=3 means six events. The Dyck-word definition says the same thing without a diagram: every prefix contains at least as many U's as D's, and the complete word has equal totals.
Under uniform ordering of the fixed totals, the admissible fraction is 5/20=1/4. More generally it is 1/(n+1). That is a probability conditional on ending at zero. For a fair six-step simple random walk, the unconditional probability of both staying nonnegative and ending at zero is instead 5/26=5/64. The denominator answers a different question. The bridge interpretation is also made explicit in Chalmers' lecture notes, remark 7.7.
Cut at the first return
A nonempty Dyck path has a unique decomposition
UADB.
The displayed D is the step that first returns to zero. Between the opening U and that D, the path A starts and ends at height one; shifting it down one unit gives another Dyck path. B is the remaining Dyck path at height zero.
For total semilength n+1, if A has semilength k, then B has semilength n−k. Choosing each part and summing over the possible cut positions gives the recurrence relation
Cn+1=k=0∑nCkCn−k,C0=1.
Uniqueness matters: cutting at an arbitrary later return would count some paths more than once. The construction is developed in Manytamaris' counting proof.
For C3, the possible first returns are at events 2, 4 and 6. They contribute C0C2=2, C1C1=1 and C2C0=2.
All five nonnegative six-step paths with three up and three down steps, grouped by first return to zero: two at event 2, one at event 4 and two at event 6. Their balanced-parenthesis encodings are shown beneath them.
Original exact enumeration of the unit-inventory example. The first-return groups give the three terms in the Catalan recurrence; touching zero is allowed.
Read U as an opening parenthesis and D as a closing one. Nonnegative inventory becomes “never close more parentheses than have been opened”; the final zero means all are closed. The five encodings in the figure are therefore exactly the five balanced strings with three pairs. This is a reversible correspondence, not a coincidence between two formulas.
Why nested structures produce the same sequence
An ordered full binary tree has either one leaf or a root joining a left tree and a right tree. “Full” means every internal node has exactly two children; “ordered” means left and right are distinguished. With n internal nodes it has n+1 leaves. Splitting the remaining internal nodes between the two subtrees gives the same recurrence and therefore the same Cn count. Dropping the full or ordered convention changes the counting problem.
As an analytic power series, this identity holds for ∣z∣<1/4. The last expression has its value at zero defined by its limit, C(0)=1. The other quadratic branch cannot represent this power series. Peter Shor's MIT lecture develops the tree decomposition and generating-function argument. These are counts of possible structures, not a rule that makes each structure equally probable.
Check the model before using the count
Catalan paths allow intermediate returns to zero. Requiring strict positivity at every event, including the final one, would exclude every balanced path. The ballot theorem and lattice-path counting article treats the broader strict-versus-weak boundary problem and the reflection argument.
Independent signs with a common up-probability p∈(0,1) still give uniform orders after conditioning on equal totals: every bridge has weight pn(1−p)n. Changing step sizes, starting inventory, barriers or the original dependence structure requires a new count or weighted calculation. A realistic trading inventory process may also allow short positions, so the toy nonnegative boundary must be justified before treating Catalan counts as relevant.
For the underlying counting toolkit, see SelfMadeQuant's Counting and Combinatorics. The link opens a public preview; the full lesson requires membership.
Practice: one uninterrupted excursion
Choose uniformly from the 14 Dyck paths with four up-steps and four down-steps. How many return to zero only at the final event, and what is their probability?
Answer. Remove the initial U and final D, then shift the remaining path down one unit. The result can be any Dyck path with three pairs, and reversing the operation gives exactly one original path. Thus there are C3=5 such paths, with probability 5/14. Intermediate zero inventory is permitted in an ordinary Dyck path, so all 14 do not meet this stronger condition.
