
Problem 11.3. The plane is divided into unit squares by lines parallel to coordinate axes of an orthogonal coordinate system. Find the number of paths of length $n$ from the point with coordinates $(0 ; 0)$ to the point with coordinates $(a ; b)$ moving along the sides of the unit squares.


Solution: Divide the path into unit paths, i.e. paths between two neighbouring points of integer coordinates. Denote the number of moves up by $x_{1}$, down by $y_{1}$, right by $x_{2}$ and left by $y_{2}$. The condition of the problem gives $x_{1}+x_{2}+y_{1}+y_{2}=n, x_{1}-y_{1}=b, x_{2}-y_{2}=a$. Thus, $y_{1}=x_{1}-b ; x_{2}=\frac{n+a+b}{2}-x_{1} ; y_{2}=\frac{n-a+b}{2}-x_{1}$. Since $|a|+|b|=\left|x_{2}-y_{2}\right|+\left|x_{1}-y_{1}\right| \leq x_{1}+x_{2}+y_{1}+y_{2}=n$ we obtain that it is necessary to have $a+b \leq n$ and $a+b \equiv n(\bmod 2)$. Let
us first fix the moves up and rigth. This can be done by $\binom{n}{\frac{n+a+b}{2}}$ ways. After that in these already fixed $\frac{n+a+b}{2}$ positions fix the moves up and finally, in the remaining $\frac{n-a-b}{2}$ positions fix the moves left. We obtain

$$
\binom{n}{\frac{n+a+b}{2}} \sum_{i=b}^{\frac{n+a-b}{2}}\binom{\frac{n+a+b}{2}}{i}\binom{\frac{n-a-b}{2}}{\frac{n-a+b}{2}-i}
$$

The sum $\sum_{i=b}^{\frac{n+a-b}{2}}\binom{\frac{n+a+b}{2}}{i}\binom{\frac{n-a-b}{2}}{\frac{n-a+b}{2}-i}$ equals to the coefficient in front of $x^{\frac{n-a+b}{2}}$ in the expansion of $(1+x)^{\frac{n+a+b}{2}}(1+x)^{\frac{n-a-b}{2}}=(1+x)^{n}$. Therefore the sum equals $\binom{n}{\frac{n-a+b}{2}}$. The number of paths is:

$$
\binom{n}{\frac{n+a+b}{2}}\binom{n}{\frac{n-a+b}{2}}
$$

Answer: If $|a|+|b|>n$ or $a+b \not \equiv n(\bmod 2)$, the number of paths is 0 , otherwise the number of paths is $\binom{n}{\frac{n+a+b}{2}}\binom{n}{\frac{n-a+b}{2}}$.

## Spring mathematics tournament Kazanlak, 30 March - 1 April 2001
