Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Counting number of moves on a grid

I'm trying to solve this computer programming problem on Project Euler: http://projecteuler.net/index.php?section=problems&id=15

Starting in the top left corner of a $2\times2$ grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a $20\times20$ grid?

I've seen a solution using nCr, where n = 40 and r = 20.

Could someone explain to me how this work, please?

share|improve this question

marked as duplicate by Arturo Magidin, leonbloy, mixedmath, Hans Lundmark, amWhy Jul 27 '11 at 2:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 0 down vote accepted

HINT:

Consider the general problem of the number of paths in a rectangular grid $m\times n$. Call $P(m,n)$ this number.

You should be able to figure out a formula for $P(m,n)$ observing that $P(1,n)=P(m,1)=1$ and $P(m,n)=P(m-1,n)+P(m,n-1)$ when both $m$ and $n$ are $>1$.

share|improve this answer
2  
The same hint in different language: Tilt the rectangles/squares 45 degrees, so that the (1,1) position is at the top. Do you see Pascal's triangle forming? –  Jyrki Lahtonen Jul 26 '11 at 18:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.