# Lattice Paths

Arjunkumar Shastry

Ranch Hand

Posts: 986

posted 10 years ago

isn't this a simple application of pascal's triangle?

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Arjunkumar Shastry

Ranch Hand

Posts: 986

Ryan McGuire

Ranch Hand

Posts: 1085

4

Arjunkumar Shastry

Ranch Hand

Posts: 986

ankur rathi

Ranch Hand

Posts: 3830

Ryan McGuire

Ranch Hand

Posts: 1085

4

posted 10 years ago

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.

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: 1085

4

posted 10 years ago

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

Cool?

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

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

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 ]