[Math] Determine the number of paths to move from the top-left cell to the bottom-right cell such that there are an even number of direction changes

combinatoricscontest-math

Determine the number of paths to move from the top-left cell to the bottom-right cell in the $8 \times 6$ (so the height is $6$ units and the length $8$ units) cell grid using a sequence of downwards moves and rightwards moves such that there are an even number of direction changes.

I'm a little lost on this. I know that there are $(8+6)!/(8!\cdot 6!)$ ways to get from the top left corner to the bottom left corner, but otherwise I'm not sure what to do. Of course, I did try to "get my hands dirty" and worked out possible paths that have an even and an odd number of direction changes, but I'm not sure if they have helped me much so far.

Best Answer

Observe that if you first move right, you must end with a move to the right, and if you first move down, you must end with a move down. In the former case, you are left with a grid of $6 \times 6,$ which has $12 \choose 6$ valid moves. In the latter case, you are left with a grid of $8 \times 4,$ which has $12 \choose 8$ valid moves. The number of ways to achieve an even number of direction changes thus equals:

$${12 \choose 6} + {12 \choose 8} = 924 + 495 = 1419$$

Related Question