Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here is a puzzle about combinatorics.

Suppose you have a square grid with $n^2$ points. You want to go from the origin $(0, 0)$ to $(n-1, n-1)$. Assuming you can only go right or up, in how many ways can you reach destination?

share|cite|improve this question
Now that you know how to deal with squares, generalize. In how many ways can you get from $(0,0)$ to $(6,10)$ only going right or up, if you must follow grid lines? – André Nicolas Jun 15 '11 at 22:18
Are you restricted to moving one unit at a time or can you go directly to any point that is right and/or up from the current one? – Mitch Jun 16 '11 at 15:29
up vote 1 down vote accepted

Its a very common problem. Using google just for a bit would already have brought you very detailed answers:

share|cite|improve this answer

Hint: start filling in a piece of graph paper with the number of ways to get to points near (0,1). How many ways are there to get to (0,2)? to (1,1)? to (2,0)? Can you see a pattern?

share|cite|improve this answer

Hint: Since you can move either right or up at each step, you can encode a path from $(0,0)$ to $(n-1,n-1)$ using a sequence of letters R and U. For example, if you have a $4 \times 4$ grid, a sequence R,U,R,U,R,U will take you from $(0,0)$ to $(3,3)$. Now try and generalize to the $n \times n$ grid and count the number of possible strings.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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