← Back to the programme
    OlympiadHardCombinatorics10–12

    How many paths from (0,0)(0,0) to (5,5)(5,5), moving one step right or one step up at a time, never rise above the line y=xy = x?

    Quantos caminhos de (0,0)(0,0) até (5,5)(5,5), dando de cada vez um passo para a direita ou um passo para cima, nunca sobem acima da reta y=xy = x?

    Answer options

    Solution

    This is the Catalan number C5=15+1(105)=2526=42C_{5} = \frac{1}{5 + 1}\binom{10}{5} = \frac{252}{6} = 42. The 252252 counts all paths, with no restriction.