Motivation
Choosing which positions contain up steps counts words with a prescribed final height. It does not ensure that their intermediate heights stay nonnegative. A prefix constraint remembers the order of the symbols, so it cannot be imposed merely by asking for equal totals.
Reflection repairs this mismatch with an exact bijection. A path that first goes below zero can have its initial segment flipped, turning the failure into a different endpoint count. Subtracting those failures produces the Catalan numbers. Their first-return decomposition then explains why the same sequence counts ordered binary trees, parenthesizations and triangulations. The point is to identify reversible constructions, rather than list unrelated objects with matching small counts.
Formal generating functions are used as coefficient identities, without assuming analytic convergence.
Definitions
Definition 2.8.1
(Prefix height and the ballot conditions)
An up step increases height by one and a down step decreases it by one. A word with up steps and down steps starts at zero and ends at height . A weak ballot word has nonnegative height after every prefix, including the empty prefix. A strict ballot word is nonempty and has strictly positive height after every nonempty prefix.
A Dyck word of semilength is a weak ballot word with up and down steps. The empty word is the unique Dyck word of semilength zero. Let count these words. Equivalently interpret as an opening parenthesis and as a closing one: no prefix closes more parentheses than it opens, and the final totals match.
Definition 2.8.2
(Plane full binary tree and its size)
A plane full binary tree is a rooted tree where each vertex is either a leaf or has exactly two ordered children, distinguished as left and right. Its size here is its number of internal vertices, not total vertices. An internal vertex's two subtrees are separate ordered choices. Swapping them may change the tree.
For binomial counts use when or , with nonnegative . This makes the boundary case of no down steps explicit. All paths below are finite step words, rather than arbitrary geometric curves.
Theorem/Proposition
Theorem 2.8.3
(Reflection gives the weak and strict ballot formulas)
For integers , the number of weak ballot words is
In particular for every . For integers , the number of strict ballot words is
The strict statement concerns nonempty words; it does not assign a contradictory status to the empty Dyck word.
Theorem 2.8.4
(First return gives the Catalan recurrence and series)
The initial value is , and for ,
Consequently the ordinary formal series is the unique series with constant term one satisfying , and
where the formal square root has constant term one. Plane full binary trees with internal vertices and full parenthesizations of fixed ordered factors are each counted by .
The factor in the closed form follows from the reflection count; it is not an instruction to divide all objects into unnamed groups of that size. Every later interpretation needs its own bijection or a proved recurrence with the same initial value.
Proof sketch or proof idea
Proof
(Reflection at the first visit to height )
There are unrestricted words with the prescribed totals. Suppose and a word fails nonnegativity. Locate its first prefix ending at height minus one, and exchange with throughout that prefix. The prefix had one more down step than up, so the transformed full word has ups and downs.
Conversely any word with those transformed totals ends at height . It therefore has a first prefix ending at height one. Exchange its steps in that prefix. Before the selected first positive height, all heights were nonpositive; after reflection they are nonnegative until the new prefix first reaches minus one. The two operations undo each other, with exactly the identified first hitting times. Thus bad words are in bijection with all words with down steps, counted by . If , there are no bad words and the stated convention gives zero for that subtraction term.
Subtracting yields the weak formula; elementary factorial cancellation gives its displayed ratio form. With equal totals it gives the Catalan closed form, including the empty word. For a strict ballot word with , the first step must be up. Delete it and shift the remaining heights down by one. Strict positivity of the original nonempty prefixes is exactly weak nonnegativity of this suffix, with ups and downs. Apply the weak formula and simplify using . This gives the strict ratio.
Proof X-ray
The first hitting time makes reflection invertible
Three choices make the map a bijection. First, the cut point is the first prefix at height ; flipping an arbitrary offending segment would not specify how to reconstruct the original. Second, the flipped prefix has exactly one more than , so the image has totals and ; this is the only place where the step counts change, and it is why the subtracted term is .
Third, the inverse needs a first visit to height in every word with the new totals. It exists because such a word ends at (here is used) and heights move by one. Before that visit the heights are at most , so after flipping they are at least , and the flipped prefix ends at : the first visit to of the image occurs at the same position. The two first hitting times therefore correspond, every transformed word is counted once, and no failure is missed or duplicated. The case never enters the reflection; it is absorbed by the convention .
Proof
(First-return decomposition and its encodings)
For the recurrence, a nonempty Dyck word starts with . Let its first return to height zero be the matching down step. It has the unique form , where and are Dyck words: subtract one from the heights inside the initial matched pair, and view the suffix after return from zero. If has semilength , the suffix has semilength . Conversely any such pair gives a Dyck word with that first return. Summing the products of the two independent counts proves the recurrence.
Formal coefficient multiplication now gives . Each coefficient after the constant is determined from earlier ones by the recurrence, proving uniqueness. Set . Substitution gives and . A square root with that constant is unique: at each positive degree its new coefficient appears twice, plus expressions already determined, and two is invertible over the rationals. This proves the square-root expression. Its numerator has zero constant term, so division by produces a formal power series. The other quadratic sign has nonzero numerator constant and would introduce a negative power, so it is not an alternative series solution.
A plane full binary tree is either one leaf, size zero, or one internal root with an ordered left-right subtree pair. Encode the leaf by the empty Dyck word and the internal root by , where encode its subtrees. First return reconstructs the root split uniquely, so this is a size-preserving bijection. For parenthesizations, turn each multiplication into an internal vertex and its left and right operands into ordered subtrees; the fixed factor order labels the leaves from left to right. This reversible syntax-tree construction proves the second interpretation.
Worked examples
Worked example 2.8.5
(Two independent calculations give fourteen)
For semilength four, the reflection formula gives . From , first return gives . Each term fixes the semilength inside the first matched pair. The total unrestricted balanced words is seventy, so most prescribed-total words fail the prefix condition.
Worked example 2.8.6
(Weak and strict positivity count different events)
With seven ups and four downs, there are unrestricted words. The weak count is . The strict count is . A weak word may return to zero before continuing; a strict word may not. Their final height is the same three, so endpoint information alone does not distinguish the two conditions.
The explorer below flips the prefix of a bad word at its first visit to height and compares the enumerated weak, strict and bad counts with their formulas, including , .
Worked example 2.8.7
(Five ordered binary structures on four factors)
With three internal vertices, root subtree sizes can be , or , contributing two, one and two choices. Thus there are five plane full binary trees. On four ordered factors they correspond to , , , and .
Left-right order is part of every construction. These are distinct written parenthesizations even when evaluating them under an associative operation gives the same value. Enumeration counts syntax or tree structure, not distinct numerical results.
Worked example 2.8.8
(A distinguished polygon edge supplies another root split)
In a convex polygon with cyclically ordered vertices, distinguish one boundary edge. The triangle incident to that edge in a triangulation has a unique third vertex. It separates two smaller polygonal regions, whose triangulations can be chosen independently; convexity keeps their diagonals inside their respective regions.
Let count these triangulations for , and set for an empty region consisting only of a boundary edge, not a genuine two-sided polygon. Choosing the third vertex gives region sizes indexed by and , so . Conversely joining their triangulations to the distinguished triangle reconstructs the original uniquely. With the same initial value this is the Catalan recurrence; a pentagon therefore has five triangulations. The empty-region convention is what handles a third vertex adjacent to an endpoint of the root edge.
Enumeration does not settle recognition memory
The Dyck words have an exact formula and a short algebraic generating-function identity, but their whole language is not regular. The prefixes for nonnegative are pairwise distinguished by suffixes : exactly the matching exponent makes a balanced nonnegative word. The finite-index criterion proved in the automata notes therefore rules out a finite-state recognizer. A counting formula and a bounded-memory recognition algorithm are different mathematical objects.
Concept lensCombinatorial
First return preserves an ordered pair of smaller objects
The factorization has an inside part and a following part, not an unordered collection of components. That is why ordinary series multiply without a factorial divisor and why left-right tree structure matters. Each object comes with a uniquely recoverable split, so recurrence equality records a bijection rather than a numerical coincidence.
Common mistakes
Counterexample mode
Balanced totals and a first up step are still insufficient
At semilength two, six words have two ups and two downs, but only and are Dyck. The word starts upwards and ends at zero, yet its third prefix has height minus one. Nonnegativity is required at every prefix, not only at the first and last. Reflection counts exactly these intermediate failures.
Common mistake
(Halving the plane count to forget left and right)
Do not divide plane-tree counts by two to erase left-right order: different shapes have different symmetries. Swapping the two subtrees of the root fixes the shape of but changes the shape of , so the plane count is not a fixed multiple of the unordered count.
Common mistake
(Using the strict formula with equal totals)
Do not use the strict formula with equal positive totals, since strict positivity would fail at the final zero height. For there are no strict ballot words, while the formula requires .
Common mistake
(Choosing the square-root sign analytically)
Formal square-root selection is determined by the constant term and allowed powers, not by assuming an analytic limit that has not been introduced. The sign has numerator constant , and dividing by would produce the negative power .
Summary
First-hitting reflection converts forbidden-prefix words into an unrestricted endpoint count, proving weak and strict ballot formulas and the Catalan closed form. First return gives an ordered decomposition, a quadratic formal series and reversible tree/parenthesization encodings. Polygon triangulations obey the same rooted split with a precise empty-region convention.
Exercises
Quick check
(Count weak and strict ballot words with five up steps and three down steps.)
Give both integer counts and identify the shared unrestricted total.
Solution · Answer
The unrestricted total is . Weak positivity gives , while strict positivity gives . Both calculations count fixed step totals. The difference records words that touch zero after beginning, which weak positivity permits and strict positivity excludes.
Quick check
(Among Dyck words of semilength five, count those whose first return occurs after four steps, and those whose first return is only at the end.)
Convert return time to the inside semilength in .
Solution · Answer
A first return at step means the inside Dyck word has semilength . Four steps gives , so the count is . First return only at the end, step ten, gives , so the count is . These are disjoint subfamilies of the total ; the other return times supply the remaining terms in the recurrence.
Quick check
(How many unordered rooted full binary tree shapes have three internal vertices? Explain why dividing the plane count by two gives the wrong answer.)
Classify the root split and account for swapping identical subtrees.
Solution
Either the root has one internal vertex in each child subtree, giving one balanced shape, or it has a leaf and a two-internal-vertex subtree. The latter subtree has only one unordered shape, so it gives one further shape. There are two unordered shapes in total.
The balanced shape gives one plane shape because swapping its identical child shapes changes nothing. The unbalanced shape gives four plane shapes: choose which root side is the leaf and which side of its internal child continues. Thus the five plane shapes have multiplicities one and four over the two unordered shapes, not a common factor two. A uniform division would fail both arithmetically and as a counting argument.