# “chess” problem

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.

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

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