[Math] How many ways are there to travel from the top left corner to the bottom right corner

combinatorics

Came up with this question when studying combinatorics.

How many ways are there to travel from the top left hand corner to the bottom left hand corner of a $m\times n$ block if: (1) in every moves you can only go right a block or go down a block; (2) two consecutive moves cannot be the same (which means, you can't go right twice or going down twice).

Thanks!

Best Answer

HINT: Clearly you must make $m+n$ steps altogether, $m$ down and $n$ to the right. Think of a route as a string of $m+n$ symbols, each of which is either $R$ (go right) or $D$ (go down).

  • How many such strings are there?
  • Once you know where the $D$’s are, you also know where the $R$’s are. How many ways are there to choose $m$ places in the string for the $D$’s?

If two consecutive moves cannot be the same, the only possible strings are alternating strings, $DRDR\ldots$ or $RDRD\ldots\;$. This puts some very stringent limitations on the possible combinations of $m$ and $n$; what are they? Once you know what combinations of $m$ and $n$ are possible, it’s not hard to count the possible paths.

Related Question