Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Lattice Paths

Arjunkumar Shastry
Ranch Hand
Posts: 986
Imagine Cartesian coordinate grid,with x and y as integer values.Object is moving from (0,0) to (10,6).Object can ONLY move right or above and not in any other way.In how many ways object can move from source to destination?

Steve Fahlbusch
Bartender
Posts: 605
7
8008

fred rosenberger
lowercase baba
Bartender
Posts: 12203
35
isn't this a simple application of pascal's triangle?

Steve Fahlbusch
Bartender
Posts: 605
7
that's how i solved it. - or really combination of 16 things taken 6 at a time.
[ June 28, 2006: Message edited by: Steve Fahlbusch ]

Arjunkumar Shastry
Ranch Hand
Posts: 986
Thats right.16C6 or 16C10 is the answer.

Ryan McGuire
Ranch Hand
Posts: 1078
4
Originally posted by Steve Fahlbusch:
8008

I only found 8007 of them. I must have missed one.

Arjunkumar Shastry
Ranch Hand
Posts: 986
Originally posted by Ryan McGuire:

I only found 8007 of them. I must have missed one.

Are you writing a prorgam or anything else?

ankur rathi
Ranch Hand
Posts: 3830
Originally posted by Arjunkumar Shastry:
Thats right.16C6 or 16C10 is the answer.

How did you calculate??? And what is C???

[ October 25, 2006: Message edited by: rathi ji ]

Ryan McGuire
Ranch Hand
Posts: 1078
4
Originally posted by rathi ji:

How did you calculate??? And what is C???

[ October 25, 2006: Message edited by: rathi ji ]

Or xCy is the (x,y) in Pascal's Triangle:

The value of a cell is the sum of the value in the cells directly above and above to the left of it.

In other words:

xCy is the number of ways to select a set of y elements out of a super set of x elements. I there are twelve socks in a drawer, how many different pairs could I possibly pull out? The answer is 12C2.

Ryan McGuire
Ranch Hand
Posts: 1078
4
Originally posted by rathi ji:

How did you calculate??? And what is C???

[ October 25, 2006: Message edited by: rathi ji ]

As for how this relates to the original problem...

I'm sure people started out with easier version of the problem:

Starting at the origin and only moving up and/or right, how many paths lead to...
• (1,0)? That's easy... 1
• (0,1)? Also easy: 1
• (anything positive, 0)? Well if I even move up off the x axis, I can never move back down, so the answer is 1.
• (0, anything positive)? Similar reasoning... 1.
• (1,1): The second-to-last move to get to (1,1) must have gone through either (1,0) or (0,1). Therefore the number of paths to (1,1) is the sum of the paths leading to (1,0) and the paths leading to (0,1). 1+1=2
• any (x,y) where x and y are both > 0: the sum of the paths leading to (x,y-1) and the paths leading to (x-1,y).

• If you plot the first few values on a piece of graph paper...
...the numbers start to look really familiar. It doesn't take long to notice that number of ways to get to (x,y) is (x+y)Cx (which is equal to (x+y)Cy).

Cool?
[ October 26, 2006: Message edited by: Ryan McGuire ]

ankur rathi
Ranch Hand
Posts: 3830
Originally posted by Ryan McGuire:

Cool?

Super cool. You are genius man.