Permutations & Combinations
Catalan Numbers
Grade None
Question:
<p>Find the number of paths from <span class="mathfrak">(0, 0)</span> to <span class="mathfrak">(n, n)</span> such that <span class="mathfrak">y \leq x</span> at every lattice point on the path.</p>
<p>(A) <span class="mathfrak">C_n</span></p>
<p>(B) <span class="mathfrak">C_{n+1}</span></p>
<p>(C) <span class="mathfrak">C_{n-1}</span></p>
<p>(D) <span class="mathfrak">\frac{1}{n+1}\binom{2n}{n}</span></p>
Step-by-Step Solution
Key Concept: Catalan numbers count lattice paths that never go above the diagonal line y = x.
<p>Paths from <span class="mathfrak">(0,0)</span> to <span class="mathfrak">(n,n)</span> where <span class="mathfrak">y \leq x</span> at every point are counted by the Catalan number <span class="mathfrak">C_n = \frac{1}{n+1}\binom{2n}{n}</span>.</p>
Correct Answer: A