2
$\begingroup$

How many ways can we move on an $N \times N$ grid with the following constraints:

  • Our start state is $(1,1)$
  • End state is $(N,N)$
  • The only moves allowed are right and down moves
  • Your path should have exactly $K$ turns in it.

For example, I worked out that for $N = 4, K = 2$, the answer is $4$, but I am not able to generalize the results.

Thanks in advance.

  • 0
    Is there any alternative way to solve this problem? Can this problem be solved using a multinomial theorem approach?2011-12-04

2 Answers 2

7

It seems to me that the final answer should be $2 \binom{N-2}{\left\lfloor \frac{k}{2} \right\rfloor } \binom{N-2}{\left\lfloor \frac{k-1}{2} \right\rfloor }$.

I won't give away the entire proof, but note the following:

  • The options of starting going down and starting going right are symmetric, so just worry about one, and double your answer.
  • You'll have to worry about whether $k$ is even or odd, since this will determine (together with your starting direction) whether the last turn is on the bottom row or the rightmost column. Since this last turn is determined, only $k-1$ turns are free choices, whilst avoiding the bottom row and rightmost column. Together with the starting direction this will determine the number of free choices for down-to-right turns and right-to-down turns. So now look at where the down-to-right turns can be made, and where the right-to-down turns can be made.
  • You can't turn as your very first move.
5

You may count the paths starting horizontally, and multiply the end result by 2 by symmetry. Now consider the sets $S_r,S_c$ of rows and columns that contain at least one turning point, or the start or end point. In general there will be exactly two such points in the row or column as soon as there is one, the exceptions being the first column, and depending on whether $K$ is odd or even the last row or column (these have only one such point). The first and last rows are uninteresting, as they are always in the sets $S_r,S_c$, it suffices to choose the remainder of these sets among the remaining $N-2$ columns/rows.

Now you should be able to figure out why the result is twice $\binom{N-2}i\binom{N-2}{i-1}$ when $K=2i$, and twice $\binom{N-2}i\binom{N-2}i=\binom{N-2}i^2$ when $K=2i+1$. Don't forget the factors 2.