0
$\begingroup$

How many lattice paths are there from $(0, 0)$ to $(10, 10)$ that do not pass to the point $(5, 5)$ but do pass to $(3, 3)$?

What I have so far:

The number of lattice paths from $(0,0)$ to $(n,k)$ is equal to the binomial coefficient $\binom{n+k}n$ (according to Wikipedia). So the number of lattice paths from $(0, 0)$ to $(10, 10)$ is $\binom{20}{10}$, and the number of lattice paths through $(5, 5)$ is $\binom{10}{5}$, and the number of lattice paths that pass through $(3, 3)$ is $\binom{6}{3}$. What next?

$\endgroup$

3 Answers 3

1
$\begingroup$

Decompose your lattice paths in two parts: the one up until reaching $(3,3)$ and from $(3,3)$ to $(10, 10)$ not passing by $(5,5)$. We can translate this second part to be actually the number of paths from $(0, 0)$ to $(7,7)$ not passing by $(2,2)$. The fact that your paths must pass through $(3,3)$ make these problems independent.

For the first one we have ${6 \choose 3}$ possibilities

For the second one, the number of paths not passing through $(5,5)$ is all the paths minus those that do pass through $(5,5)$. We can calculate the second number using the same strategy splitting the path from $(3,3)$ to $(5,5)$ and then from $(5,5)$ to $(10, 10)$. This can be done in $${4 \choose 2}{10 \choose 5}$$ ways. So in total we get, for this second part $${14 \choose 7} - {4 \choose 2}{10 \choose 5}$$.

Since we can choose any path for the first part and combine it with any other one from the second, the nuumber we get is the product of the number for those parts which is $${6 \choose 3}\left({14 \choose 7} - {4 \choose 2}{10 \choose 5}\right)$$

$\endgroup$
1
$\begingroup$

Lets count,
T = Total number of paths from (0,0) to (n,k) = (n!k!)/(n!+k!).
A = Toatl number of paths from (0,0) to (a,b) = (a!b!)/(a!+b!).(In your question a,b =3,3)
B = Total number of paths from (a,b) to (n,k) = ((n-a)!(k-b)!)/((n-a)!+(k-b)!)
Ans = T-(A*B)

If there are more than one path which you dont want to visit then simply add all the paths which are not included then subtract from T.

$\endgroup$
1
0
$\begingroup$

From (0,0) to (3,3) there are $\binom{6}{3}=20$ paths.

From (3,3) to (10,10) there are $\binom{14}{7}=3432$ paths.

From (5,5) to (10,10) there are $\binom{10}{5}=252$ paths.(the paths you don't need) 6*252 paths that from (3,3) to (5,5) to (10,10)

Hence, total conditional lattice path will be 20*3432-20*6*252=38400.

$\endgroup$
4
  • $\begingroup$ There are 6 * 252 paths from (3,3) to (10,10) that pass through (5,5). $\endgroup$ Apr 14, 2015 at 19:08
  • $\begingroup$ Ohh got it! Cheers $\endgroup$ Apr 14, 2015 at 19:13
  • $\begingroup$ Actually I wrote 252 for no. Of paths from (5,5) to (10,10) $\endgroup$ Apr 14, 2015 at 19:14
  • $\begingroup$ $\binom42=6$ paths from (3,3) to (5,5), and $\binom{10}5= 252$ paths from (5,5) to (10,10). $\endgroup$ Apr 14, 2015 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .