Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Could the downvoter explain the reason for their downvote? This seems like a perfectly reasonable question to me. –  Chris Taylor Dec 1 '11 at 10:38
2  
The downvote (not by me) could be due to the uninformative title or due to the bad choice of starting coordinates or due to the wrong use of "down" or due to the missing definition of "turn". On the other hand, I certainly think that you should explain why you not upvote a question that you deem "perfectly reasonable". –  Phira Dec 1 '11 at 11:06
    
@Phira: I don't see what you mean by "bad" starting coordinates or wrong use of "down". People are perfectly free to start counting at $1$ (I personally always prefer $0$, but in this particular problem it makes little difference) or to index a grid as one would index the entries of a matrix (here my preferences actually coincide with those of the question). Being explicit about this would be better, but then I've seen many papers that talk about north, east etc. without pointing out the the reader should make sure to read it facing north. –  Marc van Leeuwen Dec 1 '11 at 11:29
1  
@Phira reasonable != great –  Chris Taylor Dec 1 '11 at 13:27
    
Is there any alternative way to solve this problem? Can this problem be solved using a multinomial theorem approach? –  user20622 Dec 4 '11 at 16:04

2 Answers 2

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.
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.