Question

8. (Extra Credits: You can get up to 60% more!) A grid in Cartesian coordinates with size 6 x 4 is shown in Figure 2a. We start from the original point (0,0) and repeat moving 1 unit length to the next grid point by either moving up (denoted as U-action or right (denoted as R-action), until we reach the destination point (6,4). Each sequence of such R- and U-actions forms a path. Figure 2b shows an example path of this sequence: RU, R, R, RU,U, R,R,U. 1U RR IRRR 0 R (a) Case setup (b) Example path sequence Figure 2 (a) (10 pts) Try writing down a few more sequences by yourself, and find the pattern among them. How many paths can we obtain in total? Explain how you get the result. (b) (10 pts) With a given grid point (2, 3) shown in Figure 3, how many paths are there if they must cover this point? Explain why.

Answer 1

a)

Some other path sequences that are possible are :

RRRRRRUUUU

UUUURRRRRR

URURURURRR

RRUURRUURR

The one pattern that is visible from the above sequences is that all of these sequences consist of 6 R'S and 4 U's.

This is pretty logical as well , when we are allowed only two types of moves of unit length namely moving one unit to the right or moving one unit upwards and the goal being moving from the bottom left corner to the top right corner which involves 6 rightward moves and 4 upward moves, thus it makes sense that every path sequence should have 6 R's and 4 U's.

Thus to calculate the total number of paths from the bottom-left to the top-right is equivalent to finding all the possible permutations of the 6 R's and 4 U's in the path sequence.

This is a clear case of permuting identical objects where we have in total 10 objects of which 6 R's are identical and 4 U's are identical.

Therefore total permutations = total paths = 10!/(6!*4!) = 210

When we have n objects of which p1 objects are identical and p2 objects are identical and p1+p2 = n

then the total number of permutations is given by n!/(p1!*p2!)

b)

When a path has to cover the point (2,3), we can calculate number of all such paths by finding the number of paths from (0,0) to (2,3) as n1 and total paths from (2,3) to the top-right as n2

Then all the paths from the bottom-left to the top-right is equal to n1*n2 (by rule of product)

To move from the bottom-left to the point (2,3) we need 2 R's and 3 U's

Thus as we calculated above , similarly we can find the total paths from (0,0) to (2,3)

i.e. n1 = 5!/(2!*3!) = 10

Similarly to move from (2,3) to (6,4) we need 4 R's and 1 U

Thus n2 = 5!/(4!*1!) = 5

Therefore total paths passing through (2,3) are n1*n2 = 50

c)

To find all the paths that do not pass through either (2,3) or (4,1), we first find the total number of paths through (2,3) and (4,1) and then subtract these number of paths from the total paths possible from (0,0) to (6,4)

We know n i.e total number of paths from (0,0) to (6,4) which is n=210(as calculated in part a) )

We know n1 i.e total number of paths passing through (2,3) which is n1 = 50(as calculated in part b))

We now calculate n2 i.e total number of paths passing through (4,1)

For n2:

We calculate p1 i.e total paths from (0,0) to (4,1) where every path requires 4 R's and 1 U

Therefore p1 = 5!/(4!*1!) = 5

Similarly we calculate p2 i.e total paths from (4,1) to (6,4) where every path requires 2 R's and 3 U's

Therefore p2 = 5!/(2!*3!) = 10

Thus n2 = p1*p2 =50

Now we find if it is possible that a path passes through both (2,3) and (4,1) and as we see it in the diagram,once we reach (2,3) to reach (4,1) we need to have a downward move but the only valid moves allowed are upwards and rightwards.Similarly once (4,1) is reached there is no way to reach (2,3) again.

(just in case if it was possible that a path would have existed from (2,3) to (4,1) or vice-versa then we would have had to add this number as it would be subtracted twice being part of n1 and being part of n2 as well)

Thus total paths not passing through either of (2,3) or (4,1) is equal to n - n1 - n2 = 210 - 50 - 50 = 110

d)

To find all the paths that do not pass through either (2,1) or (5,3), we first find the total number of paths through (2,1) and (5,3) and then subtract these number of paths from the total paths possible from (0,0) to (6,4) and add the paths that pass through both (2,1) and (5,3) to prevent over subtraction

We know n i.e total number of paths from (0,0) to (6,4) which is n=210(as calculated in part a) )

We find n1 which is total number of paths passing through (2,1)

For n1

We first find p1 = total paths from (0,0) to (2,1) and p2 = total paths from (2,1) to (6,4)

For p1 every path requires 2 R's and 1 U

Therefore p1 = 3!/(2!*1!) = 3

For p2 every path requires 4 R's and 3 U's

Therefore p2 = 7!/(4!*3!) = 35

Thus n1 = p1*p2 = 3*35 = 105

We find n2 which is total paths passing through (5,3)

For n2

We find q1 = total paths from (0,0) to (5,3) and q2 = total paths from (5,3) to (6,4)

For q1 every path requires 5 R's and 3 U's

Therefore q1 = 8!/(5!*3!) = 56

For q2 every path requires 1 R and 1 U

Therefore q2 = 2!/(1!*1!) = 2

n2 = q1*q2 = 2*56 = 112

Now we find total paths passing through both (2,1) and (5,3)

For n3

The paths from (0,0) to (2,1) to (5,3) to (6,4)

For (0,0) to (2,1) we have r1 = 3 (calculated above)

For (2,1) to (5,3) we have r2 = 5!/(3!*2!) = 10 (3 R's and 2 U's)

For (5,3) to (6,4) we have r3 = 2 (calculated above)

Therefore n3 = r1*r2*r3 = 60

Thus total paths not passing through (2,1) and (5,3) are n-n1-n2+n3 = 210-105-112+60 = 53

Thus there are 53 paths not passing through (2,1) and (5,3)