A way to calculate all the paths there are through a chessboard with combinatory.

Question

I am looking to a way to calculate all the paths there are from (1,1) to (8,8) but you can only move the piece one square up, one square to the right and diagonally one square up to the right. I know the solution is 48639, i am looking for a way to do this through combinatory.

Answer 1

For some $k$ between $0$ and $7$ you need to make $k$ moves right, $k$ up and $7-k$ diagonally up. For a given $k$ the number of sequences of such moves is the multinomial coefficient $$\binom{k+7}{k,k,7-k}=\frac{(k+7)!}{k!^2(7-k)!}.$$ The total number of paths is thus $$\sum_{k=0}^7\binom{k+7}{k,k,7-k}=\sum_{k=0}^7\frac{(k+7)!}{k!^2(7-k)!}.$$

Answer 2

Say you go by diagonal $n$ times.

If $n=0$: then you must go 8 times up and 8 times right, that is if you want to describe your path you use 8 times $U$ (for up) and 8 times $R$ (for right). Say one such parh is $$URUUUURRRRUURURR$$ so you have ${16 \choose 8}$ paths in this case.

If $n=1$ you have ${14 \choose 7}\cdot {8\choose 1}$ paths (you use 7 U and 7 R and you must choose once when you will by diagonal).

If $n=2$ you have ${12 \choose 6}\cdot {8\choose 2}$ paths.

If $n=3$ you have ${10 \choose 5}\cdot {8\choose 3}$ paths

...

So the total number of paths is $$\sum _{n=0}^8 {16-2n \choose 8-n}\cdot {8\choose n}$$