Permutations and Combinations
11. Number of Paths in a Grid
These questions are about calculating the number of unique paths from one corner of the grid to the other corner of the grid.
Let us take an example where you have to move from point A to point B in the given grid; you can only move along the positive X-axis or the positive Y-axis.
To calculate the different number of paths, first note that you will always have to take 7 steps, out of which 4 are along the x-axis and the rest 3 are along the y-axis. Let us name the steps along the x-axis as x steps and the steps along the y-axis as y steps.
Next, note that interchanging any x steps with y steps will result in a different path while interchanging any two x steps or any two y steps will result in the same path. So the question finally reduces to the number of ways of arranging 4 x's and 3 y's steps in a line:
x x x x y y y
This can be done in \(\frac{{7!}}{{4!
\times 3!}}\) ways as there are 4 identical x's and 3 identical y's.
To understand this better, let's take three different arrangements of x's and y's, each arrangement will result in a unique path. Here we have shown three paths corresponding to the three arrangements xxxxyyy, xxyyxxy and xyxyxyx
In general in a grid of size \(m\times n\), the total number of paths is \[\bbox[5px, border: 2px solid #0071dc]{^{m + n}{{\rm{C}}_m}\;{\rm{or}}\;{\,^{m + n}}{{\rm{C}}_n}}\]