Why the Number of Valid Bracket Sequences Is the Catalan Number
Counting the number of valid bracket (parenthesis) sequences formed by $n$ opening brackets ( and $n$ closing brackets ) is one of the most celebrated problems in combinatorics and computer science. Whether you are parsing expressions, counting binary trees, or analyzing stack permutations, the answer is always the $n$-th Catalan number: \[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}. \]In this post, we will formally define valid bracket sequences, build geometric intuition using lattice paths (Dyck paths), and prove the closed-form formula using André’s Reflection Principle as well as the first-return recurrence relation. ...