2. a $W e g$ in the plane leads from the point $(0,0)$ to the point $(6,6)$, whereby in each step you can either go 1 to the right or 1 upwards. How many paths are there that contain neither the point $(2,2)$ nor the point $(4,4)$?

## Solution:
For $a, b \geq 0$, the number of paths from the point $(x, y)$ to the point $(x+a, y+b)$, in which one moves 1 to the right or upwards in each step, is generally equal to $\binom{a+b}{a}=$ $\binom{a+b}{b}$. This is because such a path is defined by specifying the positions of the $a$ steps to the right (or, equivalently, the positions of the $b$ steps upwards) in the sequence of $a+b$ steps required.

There are therefore a total of $\binom{12}{6}$ paths from $(0,0)$ to $(6,6)$. Of these, exactly $\binom{4}{2}\binom{8}{4}$ contain the point $(2,2)$ and just as many contain the point $(4,4)$. Finally, exactly $\binom{4}{2}^{3}$ of these contain both points. According to the switch-on/switch-off formula, the required number of paths is therefore

$$
\binom{12}{6}-\left[2\binom{8}{4}\binom{4}{2}-\binom{4}{2}^{3}\right]=300
$$