Permutations & Combinations
Non-crossing Paths
Grade 11
Question:
<p>Find the number of paths from <span class="mathfrak">(0, 0)</span> to <span class="mathfrak">(n, n)</span> such that the path never crosses the line <span class="mathfrak">y = x</span>.</p>
<p>(A) <span class="mathfrak">2^n</span></p>
<p>(B) <span class="mathfrak">C_{n-1}</span></p>
<p>(C) <span class="mathfrak">2C_n</span></p>
<p>(D) <span class="mathfrak">\frac{2}{n+1}\binom{2n}{n}</span></p>
Step-by-Step Solution
Key Concept: Use the ballot problem and reflection principle to count paths that do not cross y = x.
<p>Paths that never cross <span class="mathfrak">y = x</span> must stay either strictly below or strictly above. By symmetry, paths strictly below the diagonal = paths strictly above. The count is <span class="mathfrak">2 \times \frac{1}{n+1}\binom{2n-1}{n} = \frac{2}{n+1}\binom{2n}{n}</span> after careful combinatorial analysis.</p>
Correct Answer: D