Chess rook problem Determine the number of ways for a rook to get from left bottom corner to top right corner of table $3\times 7$, if the rook can only move top and right. (Two ways are different if rook stops at least at one place it didn't in the first way.) My idea was that rook has to move 8 squares but I don't know how to continue. Maybe there is something with on how many ways a natural number can be written as a sum of natural numbers. EDIT:Rook can move more than 1 space at one move

Given a particular cell, what places can you get to that cell from? Each cell can be reached in the sum of ways each cell you can reach it from can be reached.

Which is to say: $$X_{0,0} = 1$$ $$X_{j,k}=\sum_{m=0}^{j-1}X_{m,k}+\sum_{n=0}^{k-1}X_{j,n}$$

Using this, we get: $$\begin{array}{rrrrrrr} 2 & 5 & 14 & 37 & 94 & 232 & 560 \\\ 1 & 2 & 5 & 12 & 28 & 64 & 144 \\\ 1 & 1 & 2 & 4 & 8 & 16 & 32 \end{array} $$

This array is A035002 in OEIS.

So 560 ways to get to the top right.

**EDIT:** THere's some confusion how this works, so here's the 14 movesets that get you from (0,0) to (2,2):

* 2N 2E
* 1N 1N 2E
* 2N 1E 1E
* 1N 1N 1E 1E
* 1E 2N 1E
* 1E 1N 1N 1E
* 2E 2N
* 2E 1N 1N
* 1E 1E 2N
* 1E 1E 1N 1N
* 1N 2E 1N
* 1N 1E 1E 1N
* 1N 1E 1N 1E
* 1E 1N 1E 1N