# Lattice Paths problem

• Mar 11th 2006, 10:35 PM
hotmail590
Lattice Paths problem
http://i43.photobucket.com/albums/e3...tticePaths.jpg

http://i43.photobucket.com/albums/e3...tticePaths.jpg

Can some one please check if I am solving this problem correctly?

I am supposed to calculate the number of lattice paths from origin to pt (9,9) that avoids (2,2) (3,5) and (6,7)

The total number of possible paths from origin to (9,9) can be found out by using

C(x+y, x) = C(9+9, 9) = C(18, 9)

Lets say for the picture shown above:

1 = number of paths from origin to (2,2)
2 = number of paths from (2,2) to (3,5)
3 = # of paths from (3,5) to (6,7)
4 = # of paths from (6,7) to (9,9)

Now I will take C(18,9) - 1*2*3*4 to find out the number of lattice paths from origin to pt (9,9) that avoids (2,2) (3,5) and (6,7).

Another question I am not too sure how to find number of paths from (3,5) and (2,2) would it be C(3-2 + 5-2, 3-2) ?

Will that be correct? Thank you very much for your help!!
• Mar 12th 2006, 03:00 AM
rgep
Try breaking it down like this. The number $\displaystyle N(A,E;B)$ of lattice paths from A to E avoiding B is the number $\displaystyle N(A,E)$ of all paths from A to E minus the number of paths from A to E that go via B: and this is the number $\displaystyle N(A,B)$ from A to B times the number $\displaystyle N(B,E)$ from B to E.

You need to generalise this using inclusion-exclusion. You get N(A,E;B,C) = N(A,E) - N(A,B)N(B,E) - N(A,C)N(C,E) + N(A,B)N(B,C)N(C,E) since otherwise the last term would have been counted in twice.
• Mar 12th 2006, 09:58 AM
ThePerfectHacker
If the equation of the line is,
$\displaystyle y=ax+b$
Then the number of lattice points below, this line on interval $\displaystyle (p,q)$ is,
$\displaystyle \sum^{[q]}_{k=[p]}[ak+b]$ where $\displaystyle [x]$ is the greatest integer function.
• Mar 12th 2006, 11:51 AM
hotmail590
First of all, thanks for all the great replies! I really appreciated them!

Quote:

Originally Posted by rgep
Try breaking it down like this. The number $\displaystyle N(A,E;B)$ of lattice paths from A to E avoiding B is the number $\displaystyle N(A,E)$ of all paths from A to E minus the number of paths from A to E that go via B: and this is the number $\displaystyle N(A,B)$ from A to B times the number $\displaystyle N(B,E)$ from B to E.

You need to generalise this using inclusion-exclusion. You get N(A,E;B,C) = N(A,E) - N(A,B)N(B,E) - N(A,C)N(C,E) + N(A,B)N(B,C)N(C,E) since otherwise the last term would have been counted in twice.

rgep, how come it is only from A to B to C to E? Where is D? I think I understand your explanation so I shall try it with my problem

if A = (0,0) B =(2,2) C=(3,5) D= (6,7) and E =(9,9)

and I am trying to find the number of paths from A to E avoiding B C and D

N(A,E) - N(A,B)N(B,E) - N(A,C)N(C,E) - N(A,D)N(D,E) + N(A,B)N(B,C)N(C,D)N(D,E)

Would that be correct? Thanks for the help!!