Problem
COM-B2-M03-P015 Parentheses and Paths
Construct a bijection between correct parenthesis sequences with \(n\) pairs of parentheses and paths from \((0,0)\) to \((n,n)\) that never go above the diagonal \(y=x\).
It is convenient to encode a closing parenthesis as a right step and an opening parenthesis as an up step, or conversely; choose a convention and check the prefix condition.
Encode an opening parenthesis as a step \(R\), and a closing parenthesis as a step \(U\). In a correct parenthesis sequence, every prefix has at least as many opening parentheses as closing ones, so the number of \(U\)'s does not exceed the number of \(R\)'s. This is exactly \(y\le x\). There are \(n\) opening and \(n\) closing parentheses, so the path ends at \((n,n)\). Conversely, any path with \(y\le x\) gives a sequence whose every prefix has at least as many openings as closings, hence a correct parenthesis sequence.
The convention must match the inequality.