\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial7}{Problems for Tutorial 7}{November 4, 1996}

\section {Derangements}

$N$ people leave their hats in a coatroom. On the way out the person
in charge of the coatroom hands their hats back to them in an arbitrary
order. Use inclusion-exclusion to count the total number of ways in
which the hats can be handed back to them such that no person gets
his/her own hat back.



\section {Counting Paths}

\begin{itemize}

\item Find the number of paths from $(0,0)$ to $(m,n)$, where $m,n \in
  \cal N$, such that each path is made up of a series of steps,
  where each step is either a step one unit to the right or one unit
  forwards.


\item Prove that $\sum_{k=0}^{r} C(n+k, k) = C(n+r+1, r)$, where $n,r \in
  \cal Z^+$.


 
\end{itemize}

\end{document}
