Subjects combinatorics

Paths No Cross Bd9A79

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

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$.