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.

Suppose that we have a cheespiece that can move either to the left or upwards. How many possibilities are there on a $n^2$ board to come from the bottom right square to the upper left square of the board.

I tried to show that this in fact is $2^{2n-1}$ but I don't get the induction right.

share|improve this question
2  
If there are only single steps allowed, then the number is $2n-2\choose n-1$ as you choose $n-1$ left steps out of $2(n-1)$ steps in total. –  Hagen von Eitzen Jan 22 '13 at 21:03
1  
Do you mean travelling from the "bottom right" square to the "upper left" square? –  orlandpm Jan 22 '13 at 21:05
    
Thanks :) and yes it is travelling from bottom right to upper left. –  random guy Jan 22 '13 at 21:08

2 Answers 2

Consider the fact that no matter which path the piece takes, it must go left $n$ times and up $n$ times. Thus the number of all possible paths is all the possible permutations of the multiset $\{n \cdot \operatorname{up},n \cdot \operatorname{left}\}$ which has a closed form formula.

share|improve this answer

Added: This assumed that the piece could start on any square on the right and end on any square on the left, including moving up as many spaces along the left edge as desired. It appears this is not what was wanted.

If the piece starts in the top row, there is only $1$ way to get there-always go left. If it starts one row below the top, it can go up in any column, or not at all, for a total of $n+1$ paths. If it starts two rows below the top, you can choose any two rows to go up in with replacement, $\frac 12 n(n+1)$, go up only once, $n+1$, or not at all, $1$, for a total of $1+n+{n+1 \choose 2}$. For row $i$, we have $\sum_{j=1}^i{n+j-1\choose j-1}$, so summing over all rows we have $$\sum_{i=1}^n \sum_{j=1}^i{n+j-1\choose j-1}=\sum_{i=1}^n \frac i{n+1}{n+i \choose i}=\frac n{n+2} {2n+1 \choose n+1}=\frac n{2(n+1)^2}\frac {(2n+2)!}{(n+1)!^2}$$

with the sum evaluations done by Alpha 1 and Alpha 2

share|improve this answer

Your Answer

 
discard

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.