Permutations & Combinations
Lattice Paths and Catalan Numbers
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 either <span class="mathfrak">x > y</span> at all interior lattice points or <span class="mathfrak">y > x</span> at all interior lattice points.</p>
<p>(A) <span class="mathfrak">C_{n}</span></p>
<p>(B) <span class="mathfrak">2C_{n}</span></p>
<p>(C) <span class="mathfrak">C_{n}^{2}</span></p>
<p>(D) <span class="mathfrak">2C_{n}^{2}</span></p>
Step-by-Step Solution
Key Concept: Use Catalan numbers to count lattice paths that stay strictly on one side of the diagonal (except endpoints).
<p>Paths where <span class="mathfrak">x > y</span> at all interior points correspond to Catalan paths staying strictly below the diagonal until reaching <span class="mathfrak">(n,n)</span>. Similarly for <span class="mathfrak">y > x</span>. Each contributes <span class="mathfrak">C_n</span> paths (the <span class="mathfrak">n</span>-th Catalan number). Total = <span class="mathfrak">2C_n</span>.</p>
Correct Answer: B