A balanced parenthesis string never closes more parentheses than it has opened in any prefix. Encode an opening parenthesis as an up step and a closing one as a down step. A valid string with n pairs becomes a path of 2n steps from height zero back to zero that never goes below zero. Such paths are called Dyck paths. Merely choosing n up-step positions counts all balanced paths, including invalid prefixes.
Predict
Predict how to count the bad paths without enumerating every prefix condition. Every bad balanced path has a unique first visit to height minus one. Reflect its steps up to that visit, exchanging up and down. The reflected prefix ends at plus one, so the entire transformed path ends at plus two. This changes the total to n+1 up steps and n−1 down steps. The inverse uses the first visit to plus one, making the reflection a bijection.
Experiment
Compare unrestricted and forbidden counts.
n
Balanced paths C(2n, n)
Bad paths C(2n, n+1)
Dyck paths
1
2
1
1
2
6
4
2
3
20
15
5
Draw the first-return decomposition of each size-three valid path. Confirm that the five shapes separate into interior sizes zero, one and two with counts two, one and two.
Understand
The reflection bijection proves the Catalan formula C_n=C(2n, n)−C(2n, n+1)=C(2n, n)/(n+1), with C_0=1. Its proof includes both the transformation and the inverse; merely observing that reflection changes the endpoint would not establish a count. A second decomposition yields C_n=Σ from i=0 to n−1 of C_i C_(n−1−i). A nonempty Dyck path begins with an up step, then a Dyck path shifted upward, then the down step returning to zero for the first time, then a remaining Dyck path. The first-return location makes the split unique.
Apply
Let C(z)=ΣC_n z^n. The recurrence becomes C=1+zC². Solving the quadratic gives (1−sqrt (1−4z))/(2z), with the branch selected by the constant term one; the other expression has a pole and is not the required formal power series. The same recursive decomposition describes full ordered binary trees: a root has a left and right subtree, either of which can be a leaf corresponding to the empty path. Thus C_n also counts trees with n internal vertices. Ordered means that exchanging unequal left and right subtrees produces a different tree.
Continue
Use the recurrence to generate an object rather than only a number: choose an interior size, recursively choose the two smaller objects, and assemble them. A uniform choice of the interior size does not generate uniform random Dyck paths because the sizes have different numbers of completions. The reflection method generalizes to ballot problems with shifted barriers, but each endpoint and inverse must be checked afresh. The current proof concerns a fixed zero barrier and equally many unit up and down steps, not arbitrary lattice constraints.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Count Dyck paths with four up and four down steps.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Count full ordered binary tree shapes with three internal vertices.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove the bad-path count is C(2n, n+1).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove C_n=Σ from i0 to n−1 of C_i C_(n−1−i).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Derive C(z)=1+zC (z)² and select the correct quadratic root.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Explain the bijection between Dyck paths and full ordered binary trees.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
