Results 1 to 4 of 4

Math Help - Lattice Paths problem

  1. #1
    Newbie
    Joined
    Feb 2006
    Posts
    18

    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!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    Try breaking it down like this. The number N(A,E;B) of lattice paths from A to E avoiding B is the number 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 N(A,B) from A to B times the number 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If the equation of the line is,
    y=ax+b
    Then the number of lattice points below, this line on interval (p,q) is,
    \sum^{[q]}_{k=[p]}[ak+b] where [x] is the greatest integer function.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2006
    Posts
    18
    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 N(A,E;B) of lattice paths from A to E avoiding B is the number 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 N(A,B) from A to B times the number 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!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof lattice
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: January 12th 2012, 06:38 AM
  2. lattice points
    Posted in the Geometry Forum
    Replies: 1
    Last Post: February 19th 2011, 09:58 AM
  3. Lattice
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 30th 2010, 07:12 PM
  4. Lattice Problem!
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: December 9th 2008, 08:54 AM
  5. Lattice Problem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: June 1st 2008, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum