Number of way to move form $(1,1)$ to $(n,n)$ in a square grid taking exactly $k$ turns Given a square grid of size $n \times n (n>2)$, find the number of ways to move form $(1,1)$ to $(n,n)$ using only right and down direction and taking exactly $k$ turns( a turn is a right move followed immediately by a down move, or a down move followed immediately by a right move $0 < k < 2n-2$).
If we remove "exactly $k$ turn" clause then the problem is easy but we have to take care of turns also. A turn can be uniquely identified by coordinates so we can choose $k/2$ row and column indices but still there are some problems.
Can somebody please help me to solve this question.
 A: Hint: If there are $k$ turns, how many horizontal segments are there? How many vertical segments are there? (WLOG, the direction of the first move is horizontal.)
Hint: How many ways are there to write $n$ as the sum of $l$ positive integers, where $l\leq n$?
A: Suppose you start in direction $d \in \{\text{right}, \text{down}\}$, and $d'$ is the other direction.
Then, $k$ turns means that there are $1 + \lfloor k/2 \rfloor$ contiguous segments in direction $d$, and $\lceil k/2 \rceil$ segments in direction $d'$. The entire sequence of moves is specified if we specify how many moves there are in each of these segments. That is, let $x_1, x_2, \dots, x_{1+\lfloor k/2 \rfloor}$ be the numbers of moves in the segments in direction $d$, and each of $y_1, y_2, \dots, y_{\lceil k/2 \rceil}$ be the number of moves in the segments in direction $d'$. Then the entire path is completely determined by the $x_i$s and $y_j$s.
As the number of total number of moves in each direction is $n-1$, we are looking (for each choice of $d$) for the number of positive integer solutions to
$$\begin{align}
x_1 + x_2 + \dots + x_{1 + \lfloor k/2 \rfloor} &= n-1 \\
y_1 + y_2 + \dots + y_{\lceil k/2 \rceil} &= n-1
\end{align}
$$
This gives the final answer as $$2\binom{n-2}{\lfloor k/2 \rfloor}\binom{n-2}{\lceil k/2 \rceil - 1}.$$
