These are unique kind of problems trying to find the number of ways of travelling from one point to another in n-dimension space. Here n could be anything, from 1 dimension to 2 dimension or 3 dimension et al. I initially encountered these problems during my GATE exam preparation and till the exam I couldn’t find a way to deal with them. In short, I went to the exam without solving such problems, even though being aware of the fact that these questions had repeated themselves in disguise. Fortunately enough, paper setters didn’t mind to test me on these! But then I was destined to understand and solve them only after the exam. And little did I know that even though these problems sounded weird related to geometry or astronomy, but they were the easiest to crack once I had clear understanding of permutations and combinations. Thanks to Kenneth Rosen!
A typical problem sounds like –
“Given a 2 dimensional space how many paths exist from point (0,0) to point (x,y) with the condition that we are allowed to move either up or right and no other direction?”
Here usually (x,y) is specified, for example (3,2) or (5,6) and both of them are completely random, no correlation whatsoever.
Indeed it sounds scary enough to give goose bumps. But let’s start with simple 1 dimension space. The number of paths from point 0 to x is 1. C’mon that’s lame. No matter what is x, the number of paths remain still 1. And the condition is irrelevant.
Ok, having cracked 1 dimension space, let’s move on to 2 dimensions. Here the condition matters. In fact this condition suggests us a cue to reach the solution. We are restricted in our movement, only two choices are available at any point. So let’s model the path from point (0,0) to point (x,y) as combinations of rights and/or ups. Let’s further encode right as 0 and up as 1. Thus any path between the above points is string containing 0s and 1s and its length exactly is x+y. Since any path to point (x,y) should exactly contain x rights and y ups, we find that our string denoting the path contains preciously x 0s and y 1s.
So we have morphed the original problem to familiar field of permutation and combinations. What only remains is finding the number of strings of length x+y which had preciously x 0s and y 1s. And that would reflect the required number of paths and the answer. Now, a simple solution for the new transformed problem is from permutation perspective which has few objects of each type. A typical problem of such type would be finding the number of distinct words possible from the word – “SUCCESS”. And it’s quite simple (I’m refraining from technicalities here)-
= 7!/(2!2!)
So our problem reduces to finding the number of distinct strings that are possible from the string that contains x 0s and y 1s. So that’s just a cakewalk now –
= (x+y)!/(x!y!)
And this preciously is the solution for the above 2 dimension problem. For example, the number paths between the points (0,0) and (3,2) is
=(3+2)!/(3!2!)
=5!/(3!2!) = 10
And you could verify this by enumerating all the paths. Another perspective to solve such problem is to think as number of ways of arranging x 0s (or y 1s) in a string of length x+y i.e.
= (x+y)Cx = (x+y)Cy
Using the same example, the solution now would be
=5C3 = 5C2 = 10
Wow! I liked the thing when permutations and combinations converge to give the same solution. Both in fact attack the same problem from their perspective to drive the solution out of the box!
Ok, take a long breath as we move on to 3 dimensions. But that should also be another cakewalk. Isn’t it? Any point (x,y,z) would exactly contain x rights, y ups and z inwards(if restriction is on going outwards). So modeling on similar lines we get a string of length x+y+z containing x 0s, y 1s and z 2s. So the solution on the similar lines is
=(x+y+z)!/(x!y!z!)
Going through the combinations way, we find the same answer too. However it’s bit tricky now. First we find the number of ways to arrange x 0s in the string of length x+y+z and then number of ways to arrange y 1s in the remaining string of length y+z i.e.
= (x+y+z)Cx * (y+z)Cy
Verifying that both the formulae have same destination is simple matter of substituting values of x,y and z.
And similarly, an n dimensions problem could be attacked and morphed into a simple permutation or combination problem of grade 10. But the initial problem could be tweaked to raise the difficulty level. For example, instead of having point(0,0) as the origin, any arbitrary point could be selected (does that really matter?) or putting a roadblock between two points on the way from source to destination like putting a constraint that there is only one path between point(3,2) to point (4,3) which lie on the midway between the source or destination. And similarly, restrictions and tweaks could go on to design more fascinating and intriguing problems!
