 \documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}
 
 %\raggedbottom
 
 \input{macros-course}
 
 \newcommand{\recn}[3]
 {\setcounter{problemsetnum}{#1}
 \handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
 }
 
 \begin{document}
 
 \recn{8}{4/3}{April 8, 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}




\renewenvironment{proof}{{\noindent\em {Proof.}}}{}





\section{Binomial coefficients}
In lecture, we saw the {\em binomial coefficients} 
$${n \choose r} = \frac{n!}{r!(n-r)!}$$
These represent the number of ways to
choose $r$ elements from a set of $n$ elements, where the order does
not matter. Here we see more properties of binomial coefficients.

Binomial coefficients are related to Pascal's triangle.\footnote{%
A curiosity: 
Pascal's triangle is called ``Tartaglia's triangle'' in Italy.}

\subsubsection*{Pascal's Triangle}

\[ \begin{array}{c}
1\\
1 \ 1\\
1 \ 2 \ 1\\
1 \ 3 \ 3 \ 1\\
1\ 4 \ 6  \ 4 \ 1\\
1 \ 5 \ 10 \ 10 \ 5 \ 1\\
\ldots
\end {array} \]

Define $P_{n,r}$ as the $r$-th entry in the $n$-th row, where
$n \geq 0$ and $0 \leq r \leq n$ (so we count rows and entries
starting from the $0$-th.) Then, the inductive definition
of $P_{n,r}$ is as follows: for any $n \geq 0$,

\[ P_{n,r} = \left\{ \begin{array}{ll}
1 & \mbox{If } r=0\\
1 & \mbox{If } r=n\\
P_{n-1,r} + P_{n-1,r-1} & \mbox{If } 1 \leq r \leq n-1 \ .
\end {array} \right.  \]

\noindent We now show that binomial coefficients satisfy a
similar inductive property.

\begin {lemma} \label{lem1}
For $1 \leq r \leq n-1$, 
\[ {n \choose r} = {n-1 \choose r} + {n-1 \choose r-1} \]
\end {lemma}

\begin {proof} [Combinatorial]
${n \choose r}$ is the number of subsets of size $r$ chosen from a set
of size $n$. Fix some element $x$ in a set $S$ of size $n$.
There are ${n-1 \choose r}$ subsets of $S$ with $r$ elements
which contain $x$ and there are ${n-1 \choose r-1}$ subsets of
$S$ with $r$ elements which do not contain $x$.
Therefore, the total number of subsets of $S$ with $r$ elements
is ${n-1 \choose r-1} + {n-1 \choose r-1}$.
\qed
\end {proof}

\begin {proof} [Algebraic]
\begin {eqnarray*}
{n-1 \choose r} + {n-1 \choose r-1} &= &
\frac {(n-1)!}{(n-r-1)!r!} + \frac {(n-1)!}{(n-r)!(r-1)!}\\
& = & {(n-r)(n-1)!}{(n-r-1)!r!} + \frac {(n-1)!}{(n-r)!(r-1)!}\\
& =& \frac {((n-r)+r)(n-1)!}{(n-r)!r!}\\
& = & \frac {n!}{(n-r)!r!} \ . 
\end {eqnarray*}
\qed
\end {proof}

\noindent
It is now easy to prove by induction that $P_{n,r}$ is equal to ${n \choose r}$.

\begin {theorem}
$P_{n,r} = {n \choose r}$.
\end {theorem}

\begin {proof}
By induction on $n$. 

\smallskip

\noindent {\em Base Case.} For $n=0$, the only case to consider is $r=0$,
for which we have ${0 \choose 0} = 1 = P_{0,0}$.

\smallskip

\noindent {\em Inductive Step.} Assume that for all $0 \leq r \leq n-1$
it holds $P_{n-1,r} = {n-1 \choose r}$. We want to prove
that for all $0 \leq r \leq n$ it holds $P_{n,r} = {n \choose r}$.
We consider three cases.

\begin {enumerate}
\item If $r=0$, then $P_{n,0} = 1 = {n \choose 0}$.

\item If $r=n$, then $P_{n,n} = 1 = {n \choose n}$.

\item If $1 \leq r \leq n-1$, then we
have

\[ \begin{array}{rcll}
 P_{n,r} &=& P_{n-1,r} + P_{n-1,r-1} & \mbox{by definition
of $P_{n,r}$}\\
&=& {n-1 \choose r} + {n-1 \choose r-1} & \mbox{using the inductive
hypothesis}\\
&=& {n \choose r} & \mbox{by Lemma~\ref{lem1}}
\end {array}  \]\qed
\end {enumerate}
\end {proof}


Recall that 
for $0 \leq r \leq n$, 
$${n \choose r} = {n \choose n-r}.$$

The next theorem gives the ratio between successive binomial
coefficients (same $n$, successive $r$):

\begin{theorem}
Suppose $1 \leq r \leq n$. 
Then 
$${n \choose r} = {(n-r+1) \over r} {n \choose r-1}.$$
\end{theorem}

\begin {proof} [Combinatorial]
Consider the number of ways of choosing a committee of $r$ members
out of $n$ people, and  also choose a chairman for the committee.
There are ${n\choose r}$ ways of choosing the committee, and for each
such committee there are $r$ choices for the chair.
Alternatively, there are ${n \choose r-1}$ ways of choosing all the
members but the chair, and then $n-r+1$ ways to choose the chair among
the remaining people. It follows that
\[ r {n \choose r} = (n-r+1) {n \choose r-1} \]
\qed
\end {proof}

\begin {proof} [Algebraic]
\begin{eqnarray*} {n \choose r} / {n \choose r-1}
&=& \frac{n!}{r!(n-r)!} \times \frac{(r-1)!(n-(r-1))!}{n!} \\
&=& (n-r+1)/r.
\end {eqnarray*}
\qed
\end {proof}

Note that the ratio between successive binomial coefficients 
is $> 1$, which means the successive
coefficients are increasing, as long as $r < \frac{n+1}{2}$. 
Also, the ratio is $<1$, which means the coefficient are decreasing,
when $r > \frac{n+1}{2}$. 
This says that the coefficients increase, reach the maximum, 
then decrease, i.e., they
are {\em unimodal}. Here is another equation about binomial coefficients.

\begin{theorem}
Suppose $0 \leq r \leq m,n$. 
Then 
\[
{m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
\end{theorem}

{\em Proof. }
Suppose there are $m$ red balls and $n$ blue balls, all distinct.  
There are ${m+n \choose r}$ ways to choose $r$ balls from the two
sets combined.
This is the LHS of the identity.
Now decompose this collection of choices based on how many of the
chosen balls are blue and how many are red.
For any $k$, $0 \leq k \leq r$, there are ${m \choose r-k}$ ways to
choose $r-k$ red balls, and ${n \choose k}$ ways to choose $k$ blue
balls.
By the product rule, that makes ${m \choose r-k} {n\choose k}$
ways to choose $r$ balls such that $k$ of them are blue. 
Adding up these numbers for all $k$ we have that this is
$\sum_{k=0}^r {m \choose r-k}{n\choose k}$ which is the RHS. \qed


\section{Applications of the Binomial Theorem}

Recall that the Binomial Theorem states that

\[ (x+y)^n = \sum_{r=0}^n {n \choose r} x^r y^{n-r} \]
The Binomial Theorem has a couple of immediate corollaries.

\begin{corollary}
$\sum_{r=0}^n {n \choose r} = 2^n.$
\end {corollary}

\begin{proof}
Set $x=y=1$ in the Binomial Theorem.
\[ 2^n = (1+1)^n = \sum_{r=0}^n {n \choose r} 1^r 1^{n-r}
= \sum_{r=0}^n {n \choose r} \ . \]
\qed
\end {proof}

\noindent
There is also a combinatorial proof: $\sum_{r=0}^n {n \choose r}$
is equal to the total  number of subsets of a set of $n$ elements,
and we know that there are $2^n$ subsets.

\begin{corollary}\label{cor1}
$\sum_{r=0}^n (-1)^r {n \choose r} = 0.$
\end {corollary}

\begin{proof}
Set $x=-1$ and $y=1$ in the Binomial Theorem.
\[ 0 = ((-1)+1)^n = \sum_{r=0}^n {n \choose r} (-1)^r 1^{n-r}
= \sum_{r=0}^n (-1)^r {n \choose r} \ . \]
\qed
\end {proof}

\noindent Corollary~\ref{cor1} can be used to give a combinatorial
proof of the Inclusion-Exclusion formula.

\begin {theorem}[Inclusion-Exclusion] \mbox{}
\[ |A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k} | \bigcap_{i \in S} A_i |\right) \ . \]
\end {theorem}

\begin {proof} [Combinatorial]
For any element $x \in A_1 \cup \ldots \cup A_n$, we will
compute the contribution of $x$ to the RHS of the inclusion-exclusion
formula.

Let $m$ be the number of sets among $A_1,\ldots,A_n$ to whom
$x$ belongs. Then, since $x$ belongs to $m$ sets, $x$
contributes $m$ to the RHS when $k=1$; also, since $x$
belongs to ${m \choose 2}$ intersections of pairs of sets,
$x$ will contribute $-{m \choose 2}$ to the RHS when $k=2$.
In general, for $k \leq m$, $x$ belongs to ${m \choose k}$
intersections of $k$ sets.
Furthermore, $x$ will give no contribution when $k>m$, since
$x$ belongs to no intersection of $m+1$ sets or more. Overall
the contribution given by $x$ is

\begin{equation} \label{eq1}  \sum_{k=1}^m (-1)^{k+1} {m \choose k} \end {equation}
Since we know that 

\begin{equation} \label{eq2} \sum_{k=0}^m (-1)^{k+1} {m \choose k}
= -  \left( \sum_{k=0}^m (-1)^{k} {m \choose k} \right) = 0 \ ,  \end{equation}
we can subtract the LHS of (\ref{eq2}) from (\ref{eq1}) and
we conclude that the contribution given by $x$ is

\[ - (-1)^{0+1} {m\choose 0} = 1\]
So, each element of $A_1 \cup \cdots \cup A_n$ contributes
$1$ to the inclusion-exclusion formula, which means that
the inclusion-exclusion formula correctly computes the
cardinality of $A_1 \cup \cdots \cup A_n$.
\qed
\end {proof}


\begin {proof} [By Boring Induction]
We have already seen that for any two sets $A$ and $B$ it holds

\[ |A \cup B| = |A| + |B| - |A \cap B| \ . \]
We will use this fact to prove the correctness of the Inclusion-Exclusion
formula by induction on $n$.

{\noindent\em Base Case.} For $n=1$ the Inclusion-Exclusion formula
is just $|A_1| = |A_1|$.

{\noindent\em Inductive Step.} Assume that 

\[ |A_1 \cup \ldots \cup A_{n-1}| = \sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} A_i |\right) \ . \]
and consider an $n$-th set $A_{n}$. Using
Inclusion-Exclusion for two sets,  we
have

\begin{eqnarray*} |A_1 \cup \cdots \cup A_n | &= &
| (A_1 \cup \ldots \cup A_{n-1}) \cup A_n | \\
&= & |A_1 \cup \ldots \cup A_{n-1}| + |A_n| -
|(A_1 \cup \ldots \cup A_{n-1}) \cap A_n |\\
&= & |A_1 \cup \ldots \cup A_{n-1}| + |A_n| -
|(A_1 \cap A_n) \cup  \ldots \cup (A_{n-1} \cap A_n) |
\end {eqnarray*}

Using the inductive hypothesis we can compute
unions of $n-1$ sets.

\begin{eqnarray*} |A_1 \cup \ldots \cup A_{n-1}|
&=& \sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} A_i |\right) \\
& = & \sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \not\in S} 
| \bigcap_{i \in S} A_i |\right)
\end {eqnarray*}
\begin{eqnarray*}
 |(A_1 \cap A_n) \cup  \ldots \cup (A_{n-1} \cap A_n) |
& =& \sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} (A_i\cap A_n) |\right) \\
&=& \sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S\cup \{n \}} A_i |\right) \\
& = & - \sum_{k=2}^{n} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n\in S} 
| \bigcap_{i \in S} A_i |\right)
\end {eqnarray*}

Putting the pieces together, we have that
\begin{eqnarray*} |A_1 \cup \cdots \cup A_n | &= &
\sum_{k=1}^{n-1} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \not\in S} 
| \bigcap_{i \in S} A_i |\right)\\
&&+ |A_n|\\
&&+ \sum_{k=2}^{n} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \in S} 
| \bigcap_{i \in S} A_i |\right) \\
& = & \sum_{k=1}^{n} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k}
 | \bigcap_{i \in S} A_i |\right)\\
\end {eqnarray*}
\qed
\end {proof}

\iffalse
\section{Derangements}

A {\em derangement} is a permutation of $1,2,\ldots,n$ where $i$ 
is not in the $i^{th}$ position. E.g. the
number of ways of addressing $n$ envelopes to $n$ people so that
all the envelopes are mailed to wrong addresses. Let us
represent the number of derangements on $n$ elements as $!n$.

\begin{theorem}
$$!n = n! \sum_{k=0}^n { (-1)^k \over k! } $$
\end{theorem}

\begin {proof}
Let $A_1$ be the set of permutations where the element $1$ is mapped to
 position  $1$. Similarly let $A_i$ for $i = 1,\ldots,n$ be
the set of permutations of $1,\ldots,n$ where $i$ is  mapped to the
$i^{th}$ position. Then the set of permutations that
are not derangements is

\[ A_1 \cup \ldots \cup A_n \]
and the number of such permutations is

\[ |A_1 \cup \ldots \cup A_n| =  \sum_{k=1}^{n} (-1)^{k+1} \left(
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k}
 | \bigcap_{i \in S} A_i |\right) \]
In order to evaluate the Inclusion-Exclusion formula, we
note that for any set $S \subset \{ 1,\ldots,n\}$ such that $|S|=k$
we have

\[ | \bigcap_{i \in S} A_i | = (n-k)! \]
since a permutation in $\bigcap_{i \in S} A_i$ is a permutation
that fixes the elements of $S$ and permutes in an arbitrary way
the other $n-k$ elements. There are $(n-k)!$ ways to choose such a
permutation. Considering that for any $k$ there
are ${n \choose k}$ sets $S$ of size $k$, the sum evaluates to

\begin {eqnarray*}
 \sum_{k=1}^n (-1)^{k+1} {n \choose k} (n-k)!
& = & \sum_{k=1}^n (-1)^{k+1} \frac{n!}{(n-k)!k!}  (n-k)!\\
& = & \sum_{k=1}^n (-1)^{k+1} \frac {n!}{k!}
\end {eqnarray*}
Since this gives us the number of permutations that are
not derangements, by subtracting this value from $n!$
we find the number of derangements:

\begin {eqnarray*}
!n &= & n! -  \sum_{k=1}^n (-1)^{k+1} \frac {n!}{k!}\\
&= & n! \left( 1 +  \sum_{k=1}^n (-1)^{k} \frac {1}{k!} \right)\\
& = & n! \sum_{k=0}^n (-1)^{k} \frac {1}{k!}
\end {eqnarray*}
\qed
\end {proof}


The Taylor expansion of $e^x$ is
$$e^x = 1 + x + {x^2 \over 2!} + {x^3 \over 3!} + \ldots $$
That is, $$e^x = \sum_{k=0}^\infty {x^k \over k!}$$
For $x = -1$, we have
$$e^{-1} = 1/e = \sum_{k=0}^\infty {(-1)^k  \over k!}$$

This looks very close to our formula for derangements which 
is $n!$ times the first $n+1$ terms in this expansion.
In fact, we can observe that the number of derangements is the nearest
integer to $n!/e$. To see this, consider the difference $n!/e - !n$.
$$n!/e - !n = n! \left(\sum_{k=n+1}^\infty {(-1)^k \over k!}\right) $$
$$ = (-1)^{n+1}\left({ 1 \over n+1} - {1 \over (n+1)(n+2)} + \ldots + 
  {(-1)^{k+1} \over (n+1)(n+2)\ldots (n+k)} + \ldots \right)$$
So for $n \geq 1$, 
$$|n!/e - !n| = { 1 \over n+1} - {1 \over (n+1)(n+2)} + \ldots + 
  {(-1)^{k+1} \over (n+1)(n+2)\ldots (n+k)} + \ldots$$
$$ \leq {1 \over 2} - {1 \over 2.3 } + \ldots + {(-1)^{k+1} \over (k+1)!} = 1/e$$

The last inequality can be observed by grouping the terms of the
summation into pairs (the first two, next two and so on) and then
comparing.
The difference between $n!/e$ and $!n$ is at most $1/e < 1/2$, so the number of 
derangements must be the integer closest to $n!/e$.
\fi

\section {Balls and Bins}

\subsection{Identical vs Distinguishable Balls and Bins}

In lecture we saw two results on the number of ways of
putting balls into bins under different assumptions.

\begin {enumerate}

\item  There are $n^r$ ways to put $r$ {\em distinct}
balls into $n$ {\em distinct} bins. 

\item There are

\[ {n + r  - 1 \choose r}  \]
ways to put $r$ balls into $n$ bins when the balls are {\em identical}
and the bins are {\em distinct}. 

\end {enumerate}

\iffalse
For example, 20 people vote to elect 
a representative out of 3 candidates. If each voter announces its vote
publicly, there are $3^{20}$ possible outcomes of the vote. If votes
are secret and only the number of votes received by each candidate
is disclosed, then there are ${20 + 3 -1 \choose 20}$ possible outcomes.
\fi

There are other two cases that could be of interest: when the balls
are {\em distinct} and the bins are {\em identical}, and when
both balls and bins are {\em identical}. In these two cases there
is no simple formula, and in general the problem has to be
solved by case analysis (see Figure~\ref{fig}.)

\begin {figure}
\begin {center}
\begin {tabular}{|l|l|l|}
\hline
                   & Bins are distinct & Bins are identical\\
\hline
Balls are distinct & $n^r$ & case analysis\\
\hline
Balls are identical    & ${n+r-1 \choose r}$ & case analysis\\
\hline
\end {tabular}
\caption{Number of ways of putting $r$ balls into $n$ bins.}
\label{fig}
\end {center}
\end {figure}

For example, consider the problem of putting $5$ different
balls into $3$ identical bins (i.e. the problem of dividing
$5$ distinct object into at most $3$ groups). The partition
of balls into bins can have one of the following patterns:


\begin {itemize}
\item $(5,0,0)$: all the balls are in the same bin. This case arises only once.
\item $(4,1,0)$: a bin is empty, a bin gets one ball, the other bin
gets the remaining $4$ balls. There are 5 ways to get this case (corresponding
to the number of ways to choose the ball that goes alone in one bin).
\item $(3,2,0)$: this case arises ${5 \choose 3} = 10$ times (corresponding
to the number of ways to choose the three balls that go together in one bin).
\item $(3,1,1)$: this case arises ${5 \choose 3} = 10$ times. 
\item $(2,2,1)$: this case arises $4 \cdot {4 \choose 2} \cdot \frac 12  = 
12$ times. This is
the  trickier case.
There are $5$ ways to choose the ball that goes alone
in one bin, and then there are ${4 \choose 2} \cdot \frac 12 = 3$ 
ways to partition the remaining 4 balls into two indistinguishable bins
so that there are two balls in every bin.
We have to divide by two since ${4 \choose 2}$ counts the number of
subsets of size 2 of a set of 4 elements, which is also the number
of ways to arrange 4 distinct balls into 2 {\em distinct} bins.
\end {itemize}

Thus, there are $1 + 5 + 10 + 10 + 15 = 41$ ways to put
$5$ different balls into $3$ identical bins.

What is  the number of ways to put $5$ identical balls
into $3$ identical bins? We have to repeat the previous case analysis, however
now each of the previous cases can occur only once, so the answer
is simply $5$.




\subsection{At Least a Ball in Each Bin, at Most $k$ Balls in Each Bin}

In how many ways can we put $r$ identical balls into $n$ distinct bins
so that there is at least a ball in any bin (assuming $r > n$)? 
This is equivalent
to look for a positive integer 
solution of the equation $x_1 + x_2 + \ldots + x_r = n$.

\begin {theorem}
Assume $r>n$; the number of ways of putting $r$ identical
balls into $n$ distinct bins so that each bin gets at least
one ball is
\[  {r-1 \choose n-1} \]
\end {theorem}

\begin {proof} [Combinatorial]
Since the balls are identical, and we want at least one of them
in every bin, we can  start by putting one ball in every bin.
Then, any way of putting  the remaining $r-n$ balls into the $n$
bins gives a legal solution. Therefore, the  answer is given by the number of
ways of putting $r-n$ identical balls into $n$ distinct bins, that is

\[ {n + (r-n) -1 \choose r-n} = {r-1 \choose r-n} = {r-1 \choose n-1} \]
where the last equality is due to the fact that ${n \choose k} = {n \choose n-k}$.
\qed
\end {proof}

If, instead of having a lower bound on the number of balls to put in any
bin, we have an upper bound, then there is again no simple formula.
Suppose that we want to count the ways of putting 5 identical balls
into 3 distinct bins so that each bin gets at most 3 balls. It turns
out that it is easier to count the number of illegal ways of putting
the balls into the bins (i.e. the ways in which a bin gets 4 balls or more)
and then subtract this number from the total. 

The total number
of ways of putting the 5 identical balls into 3 distinct bins
is ${5 +3 -1 \choose 2} = {7 \choose 2}=21$. 

Illegal ways of putting
the balls are to put  all the 5 balls in one bin (this
arises 3 times) and to put 4 balls in one bin and 1 ball in another
(this arises 6 times, since there are 3 choices for the bin
that receives 4 balls and 2 choices for the bin that receives
1 ball). Thus, there are 9 illegal cases, and therefore 12 legal cases.

Similarly, it is possible to deal with the case of putting $r$ balls
in $n$ bins so that each bin receives at least one and no more
than $k$ balls. We first put one ball in each bin, and then
we have to put $r-n$ balls into $n$ bins in such a way that no
bin gets more than $k-1$ balls. This reduces to the previous case.


\section{Team 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). 

\begin {enumerate}

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

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

\item 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|$.

\end {enumerate}

\subsection*{Solution}

Let $n = |A|$, $m = |B|$. 
We compute the total number of functions $f:A \rightarrow B$.

\begin {lemma}
The total number of functions $f:A \rightarrow B$ is $m^n$.
\end {lemma}

\begin {proof} [Inductive]
By induction on  $n$. 

{\noindent\em Base Case.} 
$n=1$. Let $A = \{ a \}$. Then a function $f : \{a\} \rightarrow B$
is totally specified by the value $f(a)$. There are $m$  choices.

{\noindent\em Inductive Step.} Assume that for all $A'$ such that $|A'| = n-1$
it is true that there are $m^{n-1}$ functions $f' : A' \rightarrow B$.
Fix an element $a \in A$ and consider the set $A' = A - \{ a\}$.
By the inductive hypothesis, there are $m^{n-1}$ functions
$f': A' \rightarrow B$. For any such function, and for any $b \in B$,
we can define a function $f: A \rightarrow B$ as follows

\[ f(x) = \left\{ \begin{array}{ll} b &  \mbox{If } x=a;\\
f'(x) &  \mbox{otherwise.} \end {array} \right.  \]
Indeed, there is a bijection between functions $f : A \rightarrow B$
and pairs $(f',b)$ where $f' : A' \rightarrow B$ and $b \in B$.
By the product rule, the number of such pairs
is $m^{n-1} \cdot m = m^n$, therefore there are $m^n$ functions
$f:A \rightarrow B$.
\qed
\end {proof}

\begin {proof}[Combinatorial]
Functions $f: A \rightarrow B$ are in $1-1$ correspondence with
sequences in $B^{|A|}$. By the product rule, the size of
$B^{|A|}$ is $m^n$.
\qed
\end {proof}

Recall that for a function $f: A \rightarrow B$, the {\em range} of $f$
is defined as
\[ range(f) = \{ b \in B : \exists a \in A. f(a)=b \}\ .  \]
We say that $f$  is not surjective when
$range(f) \neq B$, meaning that there exists a $b \in B$
such that $b \not\in range(f)$. Let $F_b$ be the set
of functions $f: A \rightarrow B - \{ b\}$.
Clearly the set of non-surjective functions is given
by $\bigcup_{b \in B} F_b$.
The number of non-surjective functions can now be computed
using inclusion-exclusion

\begin {equation} \label{eqie} | \bigcup_{b \in B} F_b | =
\sum_{k=1}^{|B|} (-1)^{k+1} \sum_{S \subseteq B, |S| =k}
| \bigcap_{b \in S} F_b | \end {equation}
It remains to compute the cardinality of the intersections.
Observe that $\bigcap_{b \in S} F_b$ is just the set
of functions $f:A \rightarrow B-S$, and there are
$(m-|S|)^n$ such functions. The number of non-surjective
functions is thus
\begin{eqnarray*}
 \sum_{k=1}^{|B|} (-1)^{k+1} \sum_{S \subseteq B, |S| =k}
| \bigcap_{b \in S} F_b | &=&
  \sum_{k=1}^{m} (-1)^{k+1} \sum_{S \subseteq B, |S| =k}
(m-k)^n\\
& = &  \sum_{k=1}^{m} (-1)^{k+1} {m \choose k} (m-k)^n \ . 
\end {eqnarray*}
The number of surjective functions is 
\[ m^n - \sum_{k=1}^{m} (-1)^{k+1} {m \choose k} (m-k)^n
= m^n + \sum_{k=1}^{m} (-1)^{k} {m \choose k} (m-k)^n
= \sum_{k=0}^{m} (-1)^{k} {m \choose k} (m-k)^n
\] % \end{eqnarray*}

In the special case where $|A|=|B|=n$, a function $f : A\rightarrow B$
is a surjection if and only if it is a bijection. The number of
bijections between two sets of size $n$ is $n!$. Therefore we
have the remarkable equation

\[ n! = \sum_{k=0}^{n} (-1)^{k} {n \choose k} (n-k)^n \]

\end{document}




