1. **Problem Statement:** We need to find the number of different paths from the bottom-left corner to the top-right corner of a 6 × 6 grid, moving only right or up, without crossing the main diagonal $y = x$.
2. **Understanding the problem:** Each path consists of exactly 6 moves right and 6 moves up, totaling 12 moves.
3. **Formula and concept:** The total number of paths from $(0,0)$ to $(6,6)$ without restrictions is given by the binomial coefficient $\binom{12}{6}$.
4. **Restriction:** Paths must not cross the diagonal $y = x$. This is a classic problem solved by the Catalan number.
5. **Catalan number formula:** The number of such paths is the $n$-th Catalan number:
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
where $n=6$.
6. **Calculate:**
$$ C_6 = \frac{1}{7} \binom{12}{6} $$
7. **Calculate $\binom{12}{6}$:**
$$ \binom{12}{6} = \frac{12!}{6!6!} = 924 $$
8. **Final number of paths:**
$$ C_6 = \frac{924}{7} = 132 $$
**Answer:** There are 132 different paths from the bottom-left corner to the top-right corner of the 6 × 6 grid that do not cross the main diagonal $y = x$.
Paths No Cross Bd9A79
Step-by-step solutions with LaTeX - clean, fast, and student-friendly.