This week's book giveaway is in the Android forum. We're giving away four copies of Head First Android and have Dawn & David Griffiths on-line! See this thread for details.

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?

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

Joined: Feb 18, 2005
Posts: 1036

4

posted

0

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

Joined: Feb 18, 2005
Posts: 1036

4

posted

0

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 ]