1. [20] Determine the number of ways of walking from $(0,0)$ to $(5,5)$ using only up and right unit steps such that the path does not pass through any of the following points: $(1,1),(1,4),(4,1),(4,4)$.
Answer:
34
Solution: In the following figure, each lattice point (with the bottom-left-most point $(0,0)$ ) is labeled with the number of ways of reaching there from $(0,0)$. With the exception of the forbidden points, the labels satisfy the recursion formula $f(x, y)=f(x-1, y)+f(x, y-1)$. We see from the diagram that there are 34 ways to reach $(5,5)$.