Number of ways for a king to move from the lower left corner to the upper right corner by moving one step right, one step up, or one step up-right

chessboardcombinatorics

There is a king in the lower left corner of the $n×n$ chessboard. The king can move one step right, one step up or one step up-right. How many ways are there for him to reach the upper right corner of the board?

Answer = the number of ways to reach upper right corner of $n×n$ board $modulo$ $1000003$ .

I cannot do so problems. I want to find a solution with combinatorics. I need help; I do not have combinatorial experience with these problems.

I have solution with loops but it is time limit.
$dp[i][j] += dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]$;

Problem link

Sorry for my English.
I do wrong something,sorry.

if I have mistake in something, please edit it

Best Answer

If there is no up-right move allowed, then you need n right moves and n up moves. Thus, it will be the number of ways to place n 'Us' and n 'Rs' next to each other. To achieve this, choose n places for 'Us' out of the 2n available places. The answer is given by $\frac{(2n)!}{n!n!}$.

Now, let's consider the number of ways to reach the top-right corner with exactly 1 diagonal move. In that case, there will be n-1 "Us" and n-1 "Ls" left to be placed which will add up to $ \frac{(2(n-1))!}{(n-1)!(n-1)!}$. After placing these moves, there will be $2 \times (n-1) + 1 $ places left to make our diagonal move. So the number of possible ways to achieve this with one diagonal move will add up to $(2 \times (n-1) +1) \times \frac{(2(n-1))!}{(n-1)!(n-1)!}.$

Continuing in a similar manner, consider the case where k diagonal moves have been made. Then there will be n-k "Us" and n-k "Ls" to be places. After calculating that, you need to choose k places out of 2(n-k) + 1 available places for your diagonal moves.

This method is a viable approach to derive the final answer, and it works effectively for computation.

Related Question