Learn / Library / Combinatorics

Paths below a diagonal

CombinatoricsHard

A path goes from $(0, 0)$ to $(7, 5)$ using unit moves east or north. At every point $(x, y)$ that the path visits, it must hold that $y \leq x$ . How many such paths are there?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Count all paths, then subtract those that touch the forbidden line, using a reflection.

Solution

There are $(5 12) = 792$ paths with no restriction.
A bad path first touches the line $y = x + 1$ at some point; reflecting the part before that point in this line turns the start into $(- 1, 1)$ .
So bad paths correspond one-to-one to unrestricted paths from $(- 1, 1)$ to $(7, 5)$ , which have $8$ east moves and $4$ north moves, giving $(4 12) = 495$ of them.
The answer is $792 - 495 = 297$ .

Answer: $297$

Next question Back to the library