 \documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}
 
 %\raggedbottom
 
 \input{macros-course}
 
 \newcommand{\recn}[3]
 {\setcounter{problemsetnum}{#1}
 \handout{teamprobs#1}{Problem for Recitation #1 (#2/98)}{#3}
 }
 
 \begin{document}
 
 \recn{8}{10/30}{October 30, 1998}
 
 


\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}





\begin {problems}

\problem

In a company there are $n$ engineers and $m$ projects (and, thankfully,  there
are more engineers than projects.) Each engineer works on exactly one
project, and each project must have at least one engineer assigned to it.
In how many ways can the boss assign
projects to the engineers?

The above problem is equivalent to the problem of counting the
number of surjective functions $f : A \rightarrow B$ between two non-empty sets
$A$ and $B$ 
such that $|A|=n$ (engineers) and $|B|=m$ (projects). 

\bparts

\ppart Find the number of functions $f: A \rightarrow B$.

\ppart Use Inclusion-Exclusion to derive a formula expressing the
number of non-surjective functions $f:A \rightarrow B$ in terms of
binomial coefficients.

\ppart Use the previous steps to prove  that the number of
surjections $f:A \rightarrow B$ is

\[\sum_{k=0}^{m} (-1)^{k} {m \choose k} (m-k)^n \]
where $n=|A|$ and $m=|B|$.

\eparts

\end {problems}
\end {document}
