OlympiadHardCombinatorics10–12
How many paths from (0,0) to (5,5), moving one step right or one step up at a time, never rise above the line y = x?
Quantos caminhos de (0,0) até (5,5), dando de cada vez um passo para a direita ou um passo para cima, nunca sobem acima da reta y = x?
Answer options
Solution
This is the Catalan number C_{5} = \frac{1}{5 + 1}\binom{10}{5} = \frac{252}{6} = 42. The 252 counts all paths, with no restriction.