[Math] Number of Unique Paths in $M\times N$ Matrix; Combination or Permutation

combinationspermutations

I was checking out this problem about # of unique paths in a mxn matrix where you go from top left to bottom right, using only down and right.

http://researchideas.ca/wmt/c6b3.html

There's a solution using combination, by rephrasing the problem as out of total steps to get to the goal how many can you have to pick them to be right (the other ones are down by default).

The article has this quote "In fact, the order of the moves does not matter as long as there are a total of 10 moves, five of which are right."

I don't understand that. If I didn't look at the solution using combination, I would have guessed this needs to be solved using permutation because order seem to matter:

D D D D D R R R R R is a different path than D D D D R D R R R R.

I'm confused at why the order doesn't matter? Why is this combination instead of permutation?

Best Answer

The task

Imagine a 𝑛×𝑚 matrix where one can make steps only in two directions - down and to the right.

The task is to find a number of unique paths connecting top left and bottom right corners.

As correctly mentioned above, there are exactly 𝑛 vertical and 𝑚 horizontal moves. This is an important assumption and having made it one is tempted to use it literally to represent a set of possible steps

$𝒮 =｛ \underbrace{ ℎ,…, ℎ }_\text{𝑚} , \underbrace{𝑣,…, 𝑣}_\text{𝑛} ｝$, i.e. by step types.

However, this is not a set as defined for the purpose of combinatorics formulas used - all elements must be unique. So the challenge is just to represent the steps set properly.

The trick

Here is the trick to solve this representation problem.
Instead of step types consider a set of step numbers

$𝒮 =｛ \underbrace{ 1,2,…,𝑛+𝑚−2 }_\text{𝑛+𝑚−2} ｝$.

Now, picking any 𝑛−1 step numbers to be vertical will uniquely represent a path forcing the remaining 𝑚-1 steps to be horizontal.

Finally, answering your very question

Say, out of 3 vertical and 5 horizontal steps in total we picked 3 vertical steps to be number 2, 4 and 8. That will leave us with steps number 1, 3, 5, 6 and 7 to be horizontal. These two are true sets, and picking {2,4,8} to be vertical ones is essentially the same as picking {8,2,4}. That is why, following the above representation we use combinations instead of permutations.

Due to the trivial identity of binomial coefficients, the number of ways to pick 𝑘 elements out of 𝑛 is equal to the number of ways to pick 𝑛-𝑘 elements. Hence we do not care which of type to pick, and consequently

$\binom{𝑛+𝑚−2}{𝑛−1} =\binom{𝑛+𝑚−2}{𝑚−1} = \frac{(𝑛+𝑚−2)!}{(𝑛−1)!(𝑚−1)!}$

Hope that helps.

Related Solutions

[Math] Number of paths in a MxN matrix

If m==n you can find the no of paths to reach the bottom right cell from the top left cell using slight modification of Backtracking problem. Find below the code in Java.

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}

[Math] Dice Combination / Permutation with Repetition

The thing with dice games is that we often want to know the odds of getting a particular event ('I have a pair of sixes').

Your result is correct for calculating the number of possible combinations, with interchangeable dices. However, if we want to find a result about, say, the sum of the dices, this way of counting cases is not particularly useful since there are less chances to get the combination (6,6,6,6,6) than the combination (1,2,3,4,5).

Your book calculates the number of 'outcomes' as if each dice is of a different colour (hence, not interchangeable) and getting (1,2,3,4,5) is not the same as getting (2,3,4,5,1). The main point of this approach is to have outcomes that all have the same odds of occuring (namely, $1/6^5$). Then you can solve a lot of probability questions (odds of at least one 6, odds of sum>20, etc) just by counting the favourable cases.