• + 2 comments

    I thought about it this way: there is nothing special about it being a word (like "AWAY"), all we're trying to do is travel from the top left corner of a matrix to the bottom right by only moving right (R) or down (D).

    If the matrix has 'm' rows and 'n' columns, then any valid path needs 'm-1' moves down and 'n-1' moves to the right, so 1 simple path could look like this: RRRRR....RRDDDDD....DD with 'n-1' Right moves and then 'm-1' Down moves.

    How many valid paths are there? Well, each valid path has a total of (n+m-2) moves that can be reordered in (n+m-2)! ways. However, all the R's are identical so we need to remove all arrangements that are just shifting the R's around. Same argument applies to the D's, so the total number of valid paths is (n+m-2)! / (n-1)! / (m-1)! (this is why Pascal's triangle is also a correct way of thinking about the number of valid paths). To calculate this, follow the instructions in the discussion of the Sherlock and Permutations problem.