Permutations and Combinations – Shortest Paths :We have been given this rectangular grid of paths with this being the starting point and this being the destination. Zara’s at the starting point and wants to reach the cake shop which is at the destination.
Think of these lines as paths Zara can take to travel to the cake shop. With this, we have been asked for the number of different shortest paths Zara can take, to reach the cake shop.
This is the typical permutations and combinations problem you see in the competitive exams. Sometimes we don’t even realize that it’s a permutations and combinations problem.
Are we asked to select or arrange objects? No! Then how is it a permutations and combinations problem? Read the question again! The number of shortest paths! Shortest is the key word here.
We have been asked to select the shortest path. How do we find the number of shortest paths? Before you start thinking, let me tell you the worst thing you could possibly do. Manually count the shortest paths.
Don’t even think of making that mistake as you will end up losing a lot of time. Now to find the shortest paths we first need to understand what the shortest path is.
Many students assume that going to the right and then straight up is one of the shortest paths. And the other is going straight up to the right to reach the destination.
These are the two shortest paths students directly think of. They assume all other paths are longer. To know if this is true let’s take a random path from inside.
Right up, right up, right up, right up and right. We covered nine units lengths when we took this path. Let’s take another random path.
Up, up, right, right, up, right, up, right, right.
Again nine units. Now let’s look at the earlier paths that had crossed our minds as the shortest paths. Right, right ,right, right, right, up, up, up and up.
Again nine units, We had also thought of up, up, up, up, right, right, right, right and right. The shortest path will cover nine units. That’s our conclusion. We will come back to this point, but let’s answer a question that some of you all would be wondering about.
What is not a shortest path? The answer is simple! At any point if you travel left or down it will not be a shortest path. So you go right, up, left, up, up, up, right, right, right, right, and right.
This will be 11 units and it’s clearly longer than 9. It’s because we took a left here. The same logic applies if we go down.
Up, up, right, down, right, right, right, right, up, up, and up. 11 units more than 9. So for the shortest paths, we can either travel right or up, not left or down.
Now going back to a previous point, the shortest part will cover 9 units. What is this 9? It is the sum of the number of columns and the number of rows. Yes, this grid has 5 columns.
1, 2, 3, 4 & 5. And it has 4 rows 1, 2, 3, & 4. 5 plus 4 is 9. So now you know what a shortest path is! Now let’s move on to solving the problem.
In every case we saw Zara had to move 5 units to the right and 4 units up. The sum of these two is 9 units. So looking at this, can we say that out of the nine units Zara travels to reach the destination, five have to be rightwards?
Yes, we can say that, out of the nine units for any shortest path we have to select five which go to the right. So ‘9 C 5’ will give us the number of shortest paths Zara can take to reach the destination.
Wait, can we also say that out of the nine units Zara takes for the shortest path, 4 have to be upwards? Yes, ‘9 C 4’ will also give us the same answer.
These two will be equal.In case you’re unable to recollect, the formula for ‘N C R’ is n factorial divided by R factorial times N minus R factorial. This will equal 9 factorial divided by 5 factorial times 9 minus 5 factorial.
And this will be 9 factorial divided by 4 factorial times 9 minus 4 factorial. Same answer! 126 different shortest paths Zara can take to reach the destination. Okay, we have the answer now!
But is there another interesting way to arrive at this answer? Can we use another approach we have used before?
Think!
Could you think of anything? Okay, so we know that Zara will be moving 5 units to the right and 4 units upwards. We know that for sure! No matter which shortest path she takes, it will be total of 9 units out of which 5 will be to the right,
and 4 will be upwards. So we write ‘R’ five times and ‘U’ four times. This is what we need to arrange. All possible arrangements of these nine letters will give us the number of different shortest paths Zara can take.
This should remind you of the anagram problem we had solved. We had the word ‘excessive’. As there were nine letters we wrote 9 factorial. E was present thrice, hence divided this by 3 factorial.
S was present twice hence divided again by 2 factorial. We applied the same logic here, As there are nine letters present, we write nine factorial. ‘R’ appears five times so divide this by ‘5’ factorial.
And as ‘U’ appears four times we divide this by ‘4 factorial’. This also gives us the same answer. All three give us the answer as 126. Zara can take 126 different shortest paths to reach the cake shop.
You may use any method you like, depends on what you are comfortable with. But make sure you understand the concept well .
