Learn / Library / Combinatorics

Paths with few turns

CombinatoricsHard

A path from $(0, 0)$ to $(6, 4)$ uses unit moves east or north. A turn is a move whose direction differs from the move before it. How many paths have exactly $3$ turns?

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

Hint

Exactly the right number of turns fixes how many straight runs the path has.

Solution

Exactly $3$ turns means the path consists of $4$ straight runs that alternate between east and north.
If the path starts east, there are $2$ east runs adding up to $6$ and $2$ north runs adding up to $4$ .
Splitting $6$ into $2$ positive parts can be done in $5$ ways and splitting $4$ in $3$ ways, so $5 \times 3 = 15$ paths start east.
The same argument gives $15$ paths that start north, so the total is $15 + 15 = 30$ .

Answer: $30$

Next question Back to the library