Thread: Lattice Paths problem

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!!

Try breaking it down like this. The number of lattice paths from A to E avoiding B is the number 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 from A to B times the number 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.

If the equation of the line is,

Then the number of lattice points below, this line on interval is,
where is the greatest integer function.

First of all, thanks for all the great replies! I really appreciated them!

Originally Posted by rgep

Try breaking it down like this. The number of lattice paths from A to E avoiding B is the number 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 from A to B times the number 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!!