Discrete Mathematics: Counting problem

72 Views Asked by At

Consider an infinite grid labeled with ordered pairs of $\mathbb Z \times \mathbb Z$.

You want to move a tile from one intersection of the grid to another and the only valid moves are up(North) or to the right(East).

How many ways are there to go from $(2,3)$ to $(52,33)$ passing through $(27,23)$?

Also, what if our starting point is $(4,5)$ and we're asked to get to $(2,3)$? What can I say? (since we can only go North and East)

1

There are 1 best solutions below

1
On BEST ANSWER

Since you can only go up or right, partition the path into two independent parts $(2,3)$ to $(27,23)$ and $(27,23)$ to $(52,53)$. The first part has 25 right and 20 up steps, so there are $45\choose 25$ ways to do it. Similarly the second part has $35\choose 25$ possibilities so the whole path can be drawn in $\binom{45}{25} \binom{35}{25}$ ways.

In the second question there are no paths from $(4,5)$ to $(2,3)$ so the answer is $0$.