3. $[\mathbf{2 0}]$ Let $n>4$ be a positive integer. Determine the number of ways to walk from $(0,0)$ to $(n, 2)$ using only up and right unit steps such that the path does not meet the lines $y=x$ or $y=x-n+2$ except at the start and at the end.
Answer: $\quad \frac{1}{2}\left(n^{2}-5 n+2\right)$
Solution: It is easy to see the the first two steps and the last two steps must all be right steps. So we need to compute the number of walks from $(2,0)$ to $(n-2,0)$ that does not pass through $(2,2)$ and $(n-2,0)$. There are $\binom{n-2}{2}$ paths from $(2,0)$ to $(n-2,0)$, and exactly two of them are invalid. So the answer is $\binom{n-2}{2}-2=\frac{1}{2}(n-2)(n-3)-2=\frac{1}{2}\left(n^{2}-5 n+2\right)$.