\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\newcommand{\ball}{$\ \circ \ $}
\newcommand{\str}{$\ \star \ $}

\begin{document}
\lecturenotes{8}{Permutations and Combinations}

% \reading Rosen 4.3, 4.6, 5.6

\section{The Division Rule}

The division rule is a common way to ignore ``unimportant'' differences
when you are counting things.  You can count distinct objects, and
then use the division rule to ``merge'' the ones that are not
significantly different.

We will state the Division Rule twice, once informally and then again
with more precise notation.  

\begin{theorem}[Division Rule]
If $B$ is a finite set and $f:A \mapsto B$ maps precisely $k$ items of
$A$ to every item of $B$, then $A$ has $k$ times as many items as $B$.
\end{theorem}

For example, suppose $A$ is a set of students, $B$ is a set of
tutorials, and $f$ defines the assignment of students to
tutorials.  If 12 students are assigned to every tutorial, then
the Division Rule says that there are 12 times as many students as
tutorials. 

The following two definitions permit a more precise statement of the
Division Rule.

\begin{definition}
If $f : A \mapsto B$ is a function, then $f^{-1}(b) = \{ a \in A \mid
f(a) = b \}$.
\end{definition}

That is, $f^{-1}(b)$ is the set of items in $A$ that are mapped to the
item $b \in B$.  In the preceding example, $f^{-1}(b)$ is the set of
students assigned to tutorial $b$.

This notation can be confusing, since $f^{-1}$ normally denotes the
inverse of the function $f$.  With our definition, however,
$f^{-1}(b)$ can be a set, not just a single value.  For example, if $f$
assigns no items in $A$ to some element $b \in B$, then $f^{-1}(b)$ is
the empty set.  In the special case where $f$ is a bijection,
$f^{-1}(b)$ is always a single value, and so $f^{-1}$ by our
definition is just the ordinary inverse of $f$.

%  Well, not really, since we define f^{-1} to be a SET...

\begin{definition}
A function $f:A \mapsto B$ is {\em $k$-to-1} if for all $b \in B$,
$|f^{-1}(b)| = k$.
\end{definition}

For example, if $f$ assigns exactly 12 students to each recitation,
then $f$ is 12-to-1.  Assuming $k$ is non-zero, a $k$-to-1 function is
always a surjection; every element of the range is mapped to by $k >
0$ elements of the domain.

We can now restate the Division Rule more precisely:

\begin{theorem*}[Division Rule, restatement]
If $B$ is a finite set and $f : A \mapsto B$ is $k$-to-1, then $|A| =
k |B|$.
\end{theorem*}

\begin{proof}
Since $B$ is finite, we can let $n = |B|$ and let $B = \{ b_1, b_2,
\dots, b_n \}$.  Then we have:

\[
A = f^{-1}(b_1) \cup f^{-1}(b_2) \cup \dots \cup f^{-1}(b_n)
\]
Equality holds because each side is contained in the other.  
The right side is contained in the left side because every set
$f^{-1}(b_i)$ is contained in $A$ by the definition of $f^{-1}(b_i)$.
The left side is contained in the right,
since every item in $A$ maps to some $b_i$, and therefore is contained
in the set $f^{-1}(b_i)$. 

Furthermore, all of the sets $f^{-1}(b_i)$ are disjoint.  
The proof is by contradiction.  Assume for the purpose of
contradiction that $a \in f^{-1}(b_i)$ and $a \in f^{-1}(b_j)$ for
some $i \neq j$.  The first inclusion implies $f(a) = b_i$, but the
second inclusion implies that $f(a) = b_j$.  This is a contradiction
since $f(a)$ denotes a unique item. 

Since the sets $f^{-1}(b_i)$ are disjoint, we can compute the
cardinality of their union with the Sum Rule.  Note that each set
$f^{-1}(b_i)$ has size $k$, since $f$ is $k$-to-1.

\begin{eqnarray*}
|A| & = & |f^{-1}(b_1)| + |f^{-1}(b_2)| + \dots + |f^{-1}(b_n)| \\
    & = & \underbrace{k + k + \dots + k}_{n = |B| \mbox{ terms}} \\
    & = & k |B|
\end{eqnarray*}
\end{proof}

\paragraph{Example: Seating at a Round Table}

In how many ways can King Arthur seat $n$ knights at his round table?
Two seatings are considered equivalent if one can be obtained from the
other by rotation.  For example, if Arthur has only four knights, then
there are six possibilities as shown in Figure~\ref{fig:knights}.
Hereafter, we denote a seating arrangement in text by listing knights
in square brackets in clockwise order, starting at an arbitrary point.
For example, $[1234]$ and $[4123]$ are equivalent.

As a sign that we should bring in the division rule, the question
points out that certain distinct seatings are equivalent, so should
only be counted once---that is, we want to count equivalence classes
instead of individual objects.  The division rule is a good way to do
this. 

\begin{figure}[htbp]
\centerline{\includegraphics[height=2.0in]{figures/knights}}
\caption{\em These are the 6 different ways that King Arthur can
seat 4 knights at his round table.  Two seatings differing only by
rotation are considered equivalent.  We denote a seating arrangement
in text by listing knights in square brackets in clockwise order,
starting at an arbitrary point.  For example, the seatings in the top
row can be denoted $[1234]$, $[2413]$, and $[3421]$.}
\label{fig:knights}
\end{figure}

\begin{claim}
Arthur can seat $n$ knights at his round table in $(n-1)!$ ways.
\end{claim}

In particular, the claim says that for $n = 4$ knights there are
$(4-1)! = 3! = 6$ orderings, which is consistent with the example in
Figure~\ref{fig:knights}.

\begin{proof}
The proof uses the Division Rule.  Let $A$ be the set of orderings of
$n$ knights in a line.  Let $B$ be the set of orderings of $n$ knights
in a ring.  Define $f: A \mapsto B$ by $f((x_1, x_2, \dots, x_n)) =
[x_1 x_2 \dots x_n]$. 

The function $f$ is $n$-to-1.  In particular:
\begin{eqnarray*}
f^{-1}([x_1 x_2 \dots x_n]) & = \{ &
        (x_1, x_2, x_3, \dots, x_n), \\
    & & (x_n, x_1, x_2, \dots, x_{n-1}) \\
    & & (x_{n-1}, x_n, x_1, \dots, x_{n-2}), \\
    & &  \dots \\
    & & (x_2, x_3, x_4, \dots, x_1) \}
\end{eqnarray*}
There are $n$ tuples in the list of tuples, because 
$x_1$ can appears in $n$ different places in a tuple. 
By the Division Rule, $|A| = n |B|$.  This gives:
\begin{eqnarray*}
|B| & = & \frac{|A|}{n} \\
    & = & \frac{n!}{n} \\
    & = & (n-1)!
\end{eqnarray*}

The second equality holds, because the number of orderings of $n$
items in a line is $n!$, as we showed previously.
\end{proof}

\section{Combinations}

We have seen a variety of techniques for counting elements in a finite
set.  These include setting up bijections, the
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}
{rule}{sum}{Sum Rule},
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}
{rule}{incl-excl}{Inclusion-Exclusion},
the Product Rule, Tree diagrams, and the Division Rule.  We now use the
Division Rule to find a formula for the number of \emph{combinations} of
elements from a set.  One common pitfall in counting problems is mixing up
combinations with permutations; try to keep track of which is which!

\subsection{Example: Students and prizes}

How many groups of $5$ students can be chosen from a 180-student class to
collaborate on a problem set?

Let $A$ be the set of $5$-permutations of the set of students.  This
number is $P(180,5) = 180 \times 179 \times 178 \times 177 \times 176$.
But that's not really what we want---order of the $5$ students in a group
doesn't matter.  So let $B$ be the set of $5$-student groups.  This is
what we want.  Let's define a map $f: A \Rightarrow B$ by ignoring the
order.  We claim that $f$ is $5!$ to $1$, in other words, $120$ to $1$.
This is based on the number of ways that $5$ students could be lined up.
So, by the Division Theorem, $\card{B} = \cfrac{\card{A}}{120} = \cfrac{180
\times 179 \times 178 \times 177 \times 176}{120}$.

\subsection{The \emph{r}-Combinations of a Set}

Generalizing the example that we just did, the Division Rule can be
used to count the number of $r$-combinations of a set.

\begin{definition}
An $r$-\emph{combination} of a set is a subset of size $r$.
\end{definition}

For example, for the set $\set{a, b, c}$, we have the following three
$2$-combinations: 
\[
\begin{array}{ccc}
\set{ a, b } & \set{ a, c } & \set{ b, c }
\end{array}
\]

Understanding the distinction between $r$-combinations and
$r$-permutations is important.  The $r$-combinations of a set are
different from $r$-permutations in that order does not matter.  For
example, the above set $\set{ a, b, c }$ has six 2-permutations:
\[
\begin{array}{cccccc}
(a, b) & (a, c) & (b, c) & (b, a) & (c, a) & (c, b)
\end{array}
\]

The collaboration groups of 5 students in previous example are the
$5$-combinations of the set of students in the class.

\subsection{The number of \emph{r}-Combinations}

The number of $r$-combinations of an $n$-element set comes up in many
problems.  The quantity is important enough to merit two notations.
The first is $C(n, r)$; this is analogous to the notation $P(n, r)$
from before for the number of $r$ permutations of an $n$-element
set.  The second notation is $\displaystyle \binom{n}{r}$, read ``$n$ choose $r$''.
The values $\displaystyle \binom{n}{r}$ or $C(n, r)$ are often called {\em binomial
coefficients} because of their prominent role in the Binomial Theorem,
which we will cover shortly. 

The following theorem gives a closed form for $\displaystyle \binom{n}{r}$.  This
theorem is used all the time; remember it!

\begin{theorem}\label{th:comb}
\[
\binom{n}{r} = \frac{n!}{(n-r)! \ r!}
\]
\end{theorem}
The theorem says, for example, that the number of 2-combinations of
the three element set $\set{ a, b, c }$ is $\cfrac{3!}{(3-2)!\, 2!} = 3$ as
we saw above. 

Also, for example, the number of $5$-combinations of the $180$ element
set of students is $\cfrac{180!}{175! 5!}$.

\begin{proof}
The proof uses the Division Rule.  Let $X$ be a set with $n$ elements.
Let $A$ be the set of $r$-permutations of $X$, and let $B$ be the set of
$r$-combinations of $X$.  Our goal is to compute $\card{B}$.  To this end,
let $f: A \mapsto B$ be the function mapping $r$-permutations to
$r$-combinations that is defined by:
\[
f(\underbrace{(x_1, x_2, \dots, x_r)}_{
\begin{array}{cc}
{\mbox{order matters}} \\
{\mbox{(permutation)}}
\end{array}
})
   = \underbrace{ \set{ x_1, x_2, \dots, x_r } }_{
\begin{array}{cc}
{\mbox{order does not matter}} \\
{\mbox{(combination)}}
\end{array}
}
\]
The function $f$ is $r!$-to-1.  In particular:
\begin{eqnarray*}
f^{-1}( \set{ x_1, x_2, \dots, x_r } )
& = & \{( x_1, x_2, x_3, x_4, \dots, x_r), \\
&   &  ( x_2, x_1, x_3, x_4, \dots, x_r), \\
&   &  \dots \mbox{all $r!$ permutations} \dots\}
\end{eqnarray*}

By the Division Rule, $\card{A} = r! \card{B}$.  Now we can compute the
number of $r$-combinations of an $n$-element set, $B$, as follows:
\begin{eqnarray*}
\card{B} & = & \frac{\card{A}}{r!} \\
         & = & \frac{P(n, r)}{r!} \\
         & = & \frac{n!}{(n-r)!\, r!}
\end{eqnarray*}
\end{proof}

Binomial coefficients are important enough that some special values of
$\displaystyle \binom{n}{r}$ are worth remembering:
\[
\begin{array}{rccccll}
\displaystyle\binom{n}{0} & = & \cfrac{n!}{n! \, 0!} & = & 1 &
        \mbox{ There is a single size 0 subset of an $n$-set.}\\
\displaystyle\binom{n}{n} & = & \cfrac{n!}{0! \, n!} & = & 1 &
        \mbox{ There is a single size $n$ subset of an $n$-set.}\\
\displaystyle\binom{n}{1} & = & \cfrac{n!}{(n-1)! \, 1!} & = & n &
        \mbox{ There are $n$ size 1 subsets of an $n$-set.} \\
\displaystyle\binom{n}{n-1} & = & \cfrac{n!}{1! \, (n-1)!} & = & n &
        \mbox{ There are $n$ size $(n-1)$ subsets of an $n$-set.}
\end{array}
\]
Recall that $0!$ is defined to be 1, not zero.

\begin{theorem}\label{nnr}
For all $n \geq 1$, $0 \leq r \leq n$,
\[
\binom{n}{r} = \binom{n}{n-r}.
\]
\end{theorem}

Theorem~\ref{nnr} can be read as saying that the number of ways to choose
$r$ elements to form a subset of a set of size $n$ is the same as the
number of ways to choose the $n-r$ elements to exclude from the subset.
Put that way, it's obvious.  This is what is called a \emph{combinatorial
proof} of an identity: we write expressions that reflect different ways of
counting or constructing the same set of objects and conclude that the
expressions are equal.  All sorts of complicated-looking and apparently
obscure identities can be proved---and made clear---in this way.

Of course we can also prove Theorem~\ref{nnr} by simple algebraic manipulation:
\[
\binom{n}{r} = \frac{n!}{(n-r)!\, r!} = \frac{n!}{r!\, (n-r)!} =
\frac{n!}{(n-(n-r))!\, (n-r)!} = \binom{n}{n-r}.
\]

\subsection{Examples: Poker hands}

In the poker game Five-Card Draw, each player is dealt a hand
consisting of 5 cards from a deck of 52 cards.  Each
card in the deck has a suit (clubs $\clubsuit$, hearts $\heartsuit$,
diamonds $\diamondsuit$, or spades $\spadesuit$) and a value
($A , 2, \dots, 10, J, Q, K$).  The order in which cards are
dealt does not matter.  We will count various types of hands in
Five-Card Draw to show how to use the formula for $r$-combinations
given in Theorem~\ref{th:comb}.

It may not be clear why we want to count the number of types of hands.
The number of hands of a particular type tells us how ``likely'' we are to
encounter such a hand in a ``random'' deal of the cards.  Hands that are
less likely are ranked higher than those that are more likely, and so will
win over the more likely ones.  Knowing the likelihood (or the number) of
various hands can help us to figure out how to bet on the game.

\subsubsection{All Five-Card Hands}

How many different hands are possible in Five-Card Draw?  A hand is just a
5-card subset of the 52-card deck.  Therefore, the possible hands in
Five-Card Draw are exactly the 5-combinations of a 52-element set.  By
Theorem~\ref{th:comb}, there are $\displaystyle \binom{52}{5} = \cfrac{52!}{47! \, 5!} =
2,598,960$ possible hands.

Confusion between combinations and permutations is a common source of
error in counting problems.  For example, one might erroneously count
the number of 5-card hands as follows.  There are 52 choices for the
first card, 51 choice for the second card given the first, $\dots$,
and 48 choices for the fifth card given the first four.  This totals
$52 \cdot 51 \cdot 50 \cdot 49 \cdot 48$ possible hands.  The problem
with this way of counting is that a hand is counted once for every
ordering of the five cards; that is, each hand is counted $5! = 120$
times.  We accidentally counted $r$-permutations instead of
$r$-combinations!  To get the number of 5-combinations, we would have
to divide by 120.

\subsubsection{Hands with Four-of-a-Kind}

How many hands are there with four-of-a-kind?  For example, $9
\spadesuit \ 4 \diamondsuit \ 9 \clubsuit \ 9 \heartsuit \ 9 \diamondsuit$
has a four-of-a-kind, because there are four 9's.

First we must choose one value to appear in all four suits from the
set of 13 possible values (this follows the ``tree diagram'' approach
to exploring distinct cases).  There are 13 choices of this value, and
if we pick one we can't have any others (that would require 8 cards).
So the choice of value gives 13 disjoint cases to count.  After this
choice, we have to choose one more card from the remaining set of 48.
This can be done in $\displaystyle \binom{48}{1} = 48$ ways.  In total, there are
$13 \cdot 48 = 624$ hands with four-of-a-kind.  The situation is
illustrated by the tree diagram in Figure~\ref{fig:fourkind}.

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.0in]{figures/fourkind}}
\caption{\em This (incomplete) tree diagram counts the number of hands
with four-of-a-kind.  There are 13 choices for the value appearing in
all four suits.  The fifth card in the hand can be any of the 48 cards
remaining in the deck.  This gives a total of $13 \cdot 48 = 624$
possible hands.}
\label{fig:fourkind}
\end{figure}

Here is a way to interpret the result that uses probability.  If all
$\displaystyle \binom{52}{5}$ hands are equally likely, then the
probability that we are dealt a four-of-a-kind is
\[
\frac{624}{\binom{52}{5}} = \frac{1}{4165}.
\]
In other words, we can
only expect to get four-of-a-kind only once in every 4165 games of
Five-Card Draw!  (This is just a passing observation; we will talk about
probability ``for real'' in a few weeks.)

Mistakes are easy to make in counting problems.  It is a good idea to
check a result by counting the same thing in another way.  For
example, we could also count the number of hands with a four-of-a-kind
as follows.  First, there are 52 ways to choose the ``extra'' card.
Given this, there are 12 ways to choose the value that appears in all
four suits.  (We cannot choose the value of the first card.)  The
possibilities are illustrated by the tree diagram in
Figure~\ref{fig:fourkind2}.  By this method, we find that there are
$52 \cdot 12 = 624$ four-of-a-kind hands.  This is consistent with our
first answer (which is a good thing).

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.0in]{figures/fourkind2}}
\caption{\em This tree diagram shows another way to count the number of
hands with a four-of-a-kind.  There are 52 choices for the ``extra''
card and then 12 choices for the value appearing in all four suits.
This gives $52 \cdot 12 = 624$ hands, the same answer as before.}
\label{fig:fourkind2}
\end{figure}

\subsubsection{Hands with a Full House}

A full house is a hand with both a three-of-a-kind and a
two-of-a-kind.  For example, the hand $7 \spadesuit \ 7 \diamondsuit \
J \clubsuit \ J \heartsuit \ J \diamondsuit$ is a full house because
there are three jacks and two sevens.  How many full house hands are
there?

We can choose the value that appears three times in 13 ways.  Then we can
pick any three of the four cards in the deck with this value; this can be
done in $\displaystyle \binom{4}{3} = 4$ ways.  There are then 12
remaining choices for the value that appears two times.  We can pick any
two of the four cards with this value; this can be done in $\displaystyle
\binom{4}{2} = 6$ ways.

The total number of full house hands is therefore $13 \cdot 4 \cdot 12
\cdot 6 = 3744$.  This is 6 times greater than the number of
hands with a four-of-a-kind.  Since a four-of-a-kind is rarer, it
is worth more in poker!

\subsubsection{Hands with Two Pairs}

How many hands are there with two pairs, but no three- or
four-of-a-kind?

{\em Incorrect count. } There are 13 choices for the value of the cards in
the first pair.  There are then $\displaystyle \binom{4}{2} = 6$ ways to
choose two of the four cards in the deck that have this value.  Next,
there are 12 choices for the value of the cards in the second pair, and
$\displaystyle \binom{4}{2} = 6$ ways to choose two of the four cards with
this value.  Finally, the fifth card can be any one of the 48 cards
remaining in the deck.  Altogether there are $13 \cdot 6 \cdot 12 \cdot 6
\cdot 48$ hand with just two pairs.

There are actually {\em two} bugs in this argument.  The first is that
the fifth card {\em cannot} be any one of the 48 remaining cards; in
particular, it cannot have the same value as a card already selected.
(Otherwise, there would be three of a kind.)  This rules out 4 of
the 48 cards, leaving only 44 choices for the fifth card.

The second bug is that every hand has been counted twice!  For
example, a pair of kings and a pairs of queens is counted once with
the kings as the first pair and a second time with the queens as the
first pair.  The references in the argument to a ``first pair'' and a
``second pair'' signal danger; these terms imply an ordering that is
not part of the problem.  To fix the second bug, we can apply the
Division Rule.  There is a 2-to-1 mapping from the set of hands we
counted to the set of hands with two pairs.  Therefore, the set of
hands with two pairs is half as large as our initial count:

\begin{eqnarray*}
\mbox{hands with two pairs}
        & = & \frac{13 \cdot 6 \cdot 12 \cdot 6 \cdot 44}{2} \\
        & = & 123,552 \\
\end{eqnarray*}

Why did this factor of 2 arise in counting pairs, but not in counting
full houses?  The reason is that pairs are interchangeable, but a pair
and a triple are not.  For example, a pair of 2's and a pair of 9's is
the same as a pair of 9's and a pair of 2's.  On the other hand, a
pair of 2's and a triple of 9's is different from a pair of 9's
and a triple of 2's!

To check our result, we can count the number of hands with two pairs in a
completely different way.  The number of ways to choose the values for the
two pairs is $\displaystyle \binom{13}{2}$.  We can choose suits for each
pair in $\displaystyle \binom{4}{2} = 6$ ways, and we can choose the
remaining card in 44 ways as before.  This gives:

\[
\binom{13}{2} \cdot 6 \cdot 6 \cdot 44 = 123,552
\]

This is the same answer as before.  Two pairs turn out to be 33 times
more likely than a full house; as one would expect, a full house beats
two pairs in poker!

\subsubsection{Three of a kind, 2 different}

There are $\displaystyle \binom{13}{1}$ ways to choose the rank for the
three-of-a-kind, and once that is chosen, there are $\displaystyle
\binom{4}{3}$ ways to choose the three cards.  Once we have the
three-of-a-kind, there are $\displaystyle \binom{12}{2}$ ways to choose
the two ranks for the other two cards.  And then for each of these ranks,
there are $\displaystyle \binom{4}{1}$ ways to choose the single card of
that rank.  The total is:
\[
\binom{13}{1} \binom{4}{3} \binom{12}{2} \binom{4}{1} \binom{4}{1} = 54,912.
\]
Since this is fewer than the hands with two pairs, this is ranked higher.

\subsubsection*{1 pair, others all different}

There are $\displaystyle \binom{13}{1}$ ways to choose the rank for the
pair, and then $\displaystyle \binom{4}{2}$ ways to choose the two cards
of that rank.  Then there are $\displaystyle \binom{12}{3}$ ways to choose
the ranks of the remaining three cards, and for each of these ranks,
$\displaystyle \binom{4}{1}$ ways to choose the single card of that rank.
The total is:
\[
\binom{13}{1} \binom{4}{2} \binom{12}{3} \binom{4}{1} \binom{4}{1}
\binom{4}{1} = 1,098,240
\]

\subsubsection{Four different ranks}

We have analyzed all the actual poker hands based on the numbers of cards of
different ranks (4-1, 3-2, 3-1-1, 2-2-1, 2-1-1-1).

How many hands have all $5$ cards of different ranks?
That's the total number of hands minus the sum of the numbers of hands
of these five kinds, or
\[
2,598,960 - 1,098,240 - 123,552 - 54,912 - 3,744 - 624 = 1,317,888
\]

{\em Counted another way:}
There are 52 choices for the first card, 48
choices for the second card given the first, 44 choices for the third
given the first two, etc.  After each card, the number of remaining
choices drops by four, since we cannot subsequently pick the card
just taken or any of the other three cards with the same value.  This
gives $52 \cdot 48
\cdot 44
\cdot 40 \cdot 36$ hands with no pair.  Is this answer right?

The references to ``first card'', ``second card'', $\dots$ are a
warning signal that we may be inadvertently counting an ordered set.
To be sure, we can check how many times a particular hand is counted.
Consider the hand $A \heartsuit \ K \spadesuit \ Q \clubsuit \ J \clubsuit
\ 10 \heartsuit$.  We could have obtained this hand by drawing cards in
the order listed, but we could also have drawn them in another order.
In fact, we counted this hand once for every possible ordering of the
five cards, and in fact, every hand is counted $5! = 120$ times!  We can
correct our initial answer by applying the Division Rule.  This gives:

\begin{eqnarray*}
\mbox{hands with no pairs}
        & = & \frac{52 \cdot 48 \cdot 44 \cdot 40 \cdot 36}{120} \\
        & = & 1,317,888
\end{eqnarray*}

{\em And still another way:} There is another way to count the hands with no
pairs that avoids this confusion.  Since there are no pairs, no two
cards have the same value.  This means that we could first choose 5
distinct values from the set of 13 possibilities.  Then we could choose
one of the four suits for each of the five cards.  This gives:

\begin{eqnarray*}
\mbox{hands with no pairs}
        & = & \binom{13}{5} \cdot 4^5 \\
        & = & \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}
                   {5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \cdot 4^5 \\
        & = & 1,317,888
\end{eqnarray*}

This is the same answer as before.  Notice that the number of hands
with no pairs is more than half of all the hands.  This means that in
more than half our games of Five-Card Draw, we will not have even one
pair!


\subsubsection{Hands with Every Suit}

How many hands contain one card of every suit?  Such a hand must
contain two cards from one suit and one card from each of the other
three suits.  Again, we can count in two ways.

{\em First count. } Pick one card from each suit.  This can be done in
$13^4$ ways.  Then pick any one of the remaining 48 cards.  This gives
a total of $13^4 \cdot 48$ hands.  However, we have overcounted by
two, since the two cards with the same suit could be picked in either
order.  Accounting for this, there are $\cfrac{13^4
\cdot 48}{2} = 685,464$ hands.

{\em Second count } First, we can pick the suit that contains two cards in
four ways.  Then we can pick values for these two cards in $\displaystyle
\binom{13}{2}$ ways.  Finally, we can pick a card from each of the other
three suits in $13$ ways.  This gives:
\begin{eqnarray*}
\mbox{hands with all suits}
        & = & 4 \binom{13}{2} \binom{13}{1}^3 \\
        & = & 4 \cdot \frac{13 \cdot 12}{2} \cdot 13 \cdot 13 \cdot 13 \\
        & = & 685,464
\end{eqnarray*}
More than a quarter of all Five-Card Draw hands contain all suits.

\subsubsection*{Reminders}

To make sure that you get the right answer when counting:

\begin{enumerate}

\item Look at a sample 5-card hand (or a sample of whatever you are
counting) and make sure that it is covered once and only once in your
count.

\item Try counting by two different ways and check that you get the same
answer.
\end{enumerate}

For example, when we first counted the number of hands with no pairs,
we discovered that we had massively overcounted; a sample hand was
actually covered 120 times by our count!  We corrected this answer by
applying the Division Rule, {\em and} we counted the same thing again in a
different way as a double-check.

\section{The Magic Trick}

Counting has many applications in Computer Science.  For example, we
have proved upper and lower bounds on the run time of algorithms,
proved that some functions are not computable, etc.  Counting also has
applications in information theory.  Here is a fun one!

There is a magician and an assistant.  The assistant goes into the
audience with a deck of 52 cards while the magician looks away.  Five
audience members are asked to select one card each from the deck.  The
assistant then gathers up the five cards and announces four of them to
the magician.  The magician thinks for a time and then correctly names
the secret, fifth card!

\subsection{How the Trick Works}

The assistant has somehow communicated the secret card to the magician
just by naming the other four cards.  In particular, the assistant has two
ways to communicate.  First, he can announce the four cards in any order.
The number of orderings of four cards is $4! = 24$, so this alone is
insufficient to identify which of the remaining 48 cards is the secret
one.  Second, the assistant can choose which four of the five cards to
reveal.  The amount of information that can be conveyed this way is harder
to pin down.  The assistant has $\displaystyle \binom{5}{4} = 5$ ways to
choose the four cards revealed, but the magician can not determine which
of these five possibilities the assistant selected, since he does not know
the secret card!  Nevertheless, these two forms of communication allow the
assistant to covertly reveal the secret card to the magician.

Here is an overview of how the trick works.  The secret card has the
same suit as the first card announced.  Furthermore, the value of the
secret card is offset from the value of the first card announced by
between 1 and 6.  See Figure~\ref{fig:cardcycle}.  This offset is
communicated by the order of the last three cards.

\begin{figure}[htbp]
\centerline{\includegraphics[height=2.5in]{figures/cardcycle}}
\caption{\em The 13 possible card values can be ordered in a cycle.  For
any two distinct values, one is offset between 1 and 6 clockwise steps
from the other.  In this diagram, $3$ is offset five steps from $J$.
In the card trick, the value of the secret card is offset between 1
and 6 steps from the first card announced.  This offset is
communicated by the order of the last three cards named by the
assistant.}
\label{fig:cardcycle}
\end{figure}

Here are the details.  The audience selects five cards and there are
only 4 suits in the deck.  Therefore, by the Pigeonhole Principle, the
assistant can always pick out two cards with the same suit.  One of
these will become the secret card, and the other will be the first
card that he announces.

Here is how he decides which is which.  Note that for any two card
numbers, one is at most six clockwise steps away from the other in
Figure~\ref{fig:cardcycle}.  For example, if the card numbers are $2$
and $Q$, then $2$ is three clockwise steps away from $Q$.  The
assistant ensures that the value of the secret card is offset between
1 and 6 clockwise steps from the first card he announces.

The offset is communicated by the order that the assistant announces
the last three cards.  The magician and assistant agree in advance on
an order for all 52 cards.  For example, they might use:

\[
A \ \clubsuit, 2 \ \clubsuit, \dots, K \ \clubsuit, A \ \diamondsuit,
\dots, K \ \diamondsuit, A \ \heartsuit, \dots, K \ \heartsuit, A \
\spadesuit, \dots, K \ \spadesuit
\]

With this order, one of the last three cards announced is the
smallest ($S$), one is largest ($L$), and the other is medium ($M$).
The offset is encoded by the order of these three:

\[
\begin{array}{ccc}
SML = 1 & SLM = 2 & MSL = 3 \\
MLS = 4 & LSM = 5 & LMS = 6
\end{array}
\]

For example, suppose that the audience selects $3 \heartsuit \ 8
\diamondsuit \ A \spadesuit \ J \heartsuit \ 6 \diamondsuit$.  The
assistant picks out two cards with the same suit, say $3 \heartsuit$
and $J \heartsuit$.  The $3 \heartsuit$ is five clockwise steps from
$J \heartsuit$ in Figure~\ref{fig:cardcycle}.  So the assistant makes
$3 \heartsuit$ the secret card, announces $J \heartsuit$ first, and
then encodes the number 5 by the order in which he announces the last
three cards: $A \spadesuit \ 6 \diamondsuit \ 8 \diamondsuit = LSM =
5$.

\subsection{Same Trick with 4 Cards?}

Could the same magic trick work with just 4 cards?  That is, if the
audience picks four cards, and the assistant reveals three, then can
the magician determine the fourth card?  The answer turns out to be
``no''.  The proof relies on the Pigeonhole Principle.

\begin{theorem}
The magic trick is not possible with 4 cards.
\end{theorem}

\begin{proof}
The audience can select any 4-combination of cards; let $A$ be the set
of all such 4-combinations.  The assistant can announce any
3-permutation of cards; let $B$ be the set of all such 3-permutations.
The formulas for $r$-combinations and $r$-permutations give the
following sizes for $A$ and $B$:

\begin{eqnarray*}
|A| & = & C(n, r) \\
    & = & \frac{52!}{48! \ 4!} \\
    & = & 270,725 \\
|B| & = & P(n, r) \\
    & = & \frac{52!}{49!} \\
    & = & 132,600
\end{eqnarray*}

The assistant sees a 4-combination of cards selected by the audience
and must announce a 3-permutation to the magician.  Let $f: A \mapsto
B$ be the function that the assistant uses in mapping one to the
other.  Since $|A| > |B|$, the Pigeonhole Principle implies that $f$
maps at least two 4-combinations to the same 3-permutation.  That is,
there are two different sets of four cards that the audience can pick
for which the assistant says exactly the same thing to the magician.

For these two sets of four cards, three cards must be the same (since
the assistant announces the same three cards in both cases) and one
card must be different (since the two sets are different).  For
example, these might be the two sets of four cards for which the
assistant says exactly the same thing to the magician:

\begin{eqnarray*}
3 \heartsuit \ 8 \diamondsuit \ A \spadesuit \ J \heartsuit \\
3 \heartsuit \ 8 \diamondsuit \ A \spadesuit \ K \diamondsuit
\end{eqnarray*}

In this case, the assistant announces $3 \heartsuit \ 8 \diamondsuit \
A \spadesuit$ in some order.  The magician is now stuck; he can not
determine whether the remaining card is $J \heartsuit$ or $K
\diamondsuit$.
\end{proof}

There are many variants of the magic trick.  For example, if the
audience picks 8 cards, then revealing 6 to the magician is enough to
let him determine the other two.  This sort of subtle transmission of
information is important in the security business where one wants to
prevent information from leaking out in undetected ways.  This is
actually a whole field of study, but this trick is all we'll see in
6.042.

\section{Properties of Binomial Coefficients}

There are infinitely many interesting identities involving binomial
coefficients.  We already seen a simple example in Theorem~\ref{nnr}.
These identities are important because of how often binomial coefficients
arise in analysis of algorithms (6.046) and probability (next week).  You
can't learn them all, but you can learn the basic ones and look others
up/derive them as needed.

You can prove them by algebra, or by combinatorial arguments that
establish combinatorial meanings for the left hand side (LHS) and right
hand side (RHS) of the equation as we did for Theorem~\ref{nnr}.

Let's begin with a formula for the ratio between successive binomial
coefficients---same $n$, successive $r$:
\begin{theorem}\label{bin-coeff-2}
  Suppose $1 \leq r \leq n$. 
  Then 
  \begin{displaymath}
    \binom{n}{r} \biggm/ \binom{n}{r-1} = \frac{n-r+1}{r}\,.
  \end{displaymath}
\end{theorem}

\begin{proof}[Algebraic proof]
  \begin{displaymath}
    \binom{n}{r} \biggm/ \binom{n}{r-1}
    =
    \frac{n!}{r!\, (n-r)!} \times \frac{(r-1)!\, (n-(r-1))!}{n!}
    =
    \frac{n-r+1}{r}.
  \end{displaymath}
\end{proof}

\begin{proof}[Combinatorial proof]
  Consider choosing a committee of size~$r$ and a leader, from
  $n$~people.  One way is to first pick the $r-1$ commons and then
  their leader; this can be done in $\displaystyle\binom{n}{r-1}(n-(r-1))$ ways.
  Another way is to pick the $r$ committee members first and then pick
  a leader from among them; this can be done in $\displaystyle\binom{n}{r}r$ ways.
  Thus,
  \begin{displaymath}
    \binom{n}{r-1}(n-r+1) = \binom{n}{r}r.
  \end{displaymath}
\end{proof}
This ratio is greater than 1 if $r < \cfrac{n+1}{2}$ and less than 1 if $r
> \cfrac{n+1}{2}$.  This says that the successive coefficients increase
until $r$ reaches $\cfrac{n+1}{2}$ and then decrease, \ie, they are {\em
unimodal} like the curve in Figure~\ref{fig:bell}.

\begin{figure}[htbp]
\centerline{\includegraphics[height=1.5in]{figures/bell}}
\caption{Bell Curve}
\label{fig:bell}
\end{figure}

In fact, the binomial coefficients form a real \emph{bell curve}.  These
arise on examinations in a natural way.  Suppose that a test has $n$
questions.  Then the bell curve describes, for every $r$, the number of
ways the student can get exactly $r$ of the questions right, namely
$\dbinom{n}{r}$.  If we suppose that each student taking the test is doing
random guessing, so is equally likely to get each of the $n$ questions
right or wrong, then these coefficients turn out to be proportional to the
number of students that get those numbers of questions right.  (We'll see
this when we do probability.)

Another identity: 
\begin{theorem} 
  Suppose $1 \leq r \leq n$. Then 
\[
    \binom{n}{r} = \frac{n}{r} \binom{n-1}{r-1}.
\]
\end{theorem}
\begin{proof}[Algebraic proof]
  \begin{align*}
    \binom{n}{r}
    &= \frac{n!}{r!(n-r)!} = \frac{n}{r}\frac{(n-1)!}{(r-1)!(n-r)!}\\
    &= \frac{n}{r}\frac{(n-1)!}{(r-1)!\, ((n-1)-(r-1))!}
    = \frac{n}{r}\binom{n-1}{r-1}.
  \end{align*}
\end{proof}

\begin{proof}[Combinatorial proof]
  Consider choosing a committee of size~$r$ and a leader, from
  $n$~people. One way is to first pick the leader and then his $r-1$
  subjects; this can be done in $n\binom{n-1}{r-1}$ ways.  Another way
  is to pick the $r$ committee members first and then pick a leader
  from among them; this can be done in $\displaystyle\binom{n}{r}r$ ways.  Thus,
  \begin{displaymath}
    n\binom{n-1}{r-1} = \binom{n}{r}r.
  \end{displaymath}
\end{proof}

Now an important theorem due to Pascal:
\begin{theorem}[Pascal]
Suppose $1 \leq r \leq n-1$. 
Then 
\[
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}.
\]
\end{theorem}
This is probably our most important identity, since it gives a kind of
recurrence for binomial coefficients.  {\bf Memorize it!}

\begin{proof}
\begin{description}

\item[Algebraic:]
\begin{eqnarray*}
\binom{n-1}{r} + \binom{n-1}{r-1} & = & \frac{(n-1)!}{r!(n-1-r)!} +
 \frac{(n-1)!}{(r-1)!(n-r)!} \\
&= &(n-r)\frac{(n-1)!}{r!(n-r)!} + r\frac{(n-1)!}{r!(n-r)!}\\
&= &n\frac{(n-1)!}{r!(n-r)!}\\
&= &\frac{n!}{r!(n-r)!}\\
&= &\binom{n}{r}
\end{eqnarray*}

\item[Combinatorial:]   We use case analysis (a tree diagram) and the
  sum rule.
Let $S \eqdef \set{1,\dots,n}$.\\
Let $A$ be the set of $r$-element subsets of $S$.\\
Let $B$ be the set of $r$-element subsets of $S$ that contain $n$.\\
Let $C$ be the set of $r$-element subsets of $S$ that don't contain $n$. 

Then $A = B \cup C$, and $B$ and $C$ are disjoint.  So $|A| = |B| + |C|$,
by the Sum Rule.  But now we can get expressions for $|A|$, $|B|$ and
$\card{C}$ as numbers of combinations:
\begin{itemize}

\item 
$\card{A} = \dbinom{n}{r}$. 

\item 
$|B| = \dbinom{n-1}{r-1}$.  This is because, in addition to $n$, another
$r-1$ elements must be chosen from $\set{1,\dots,n-1}$.

\item 
$|C| = \dbinom{n-1}{r}$. 
This is because $r$ elements must be chosen from $\set{1,\dots,n-1}$. 

\end{itemize}
So (by the Sum Rule)
\[
\binom{n}{r} = |A| = |B| + |C| = \binom{n-1}{r-1} + \binom{n-1}{r}.
\]
\end{description}
\end{proof}

Pascal's theorem has a nice pictorial representation: The row
represents $n$, starting with $0$ in the top row.  Successive elements
in the row represent $r$, starting with $0$ at the left.

\begin{figure}[htbp]
\centerline{
%\psfig{figure=pascal.ps,height=2in}
\includegraphics[height=2in]{figures/pascal}
}
\caption{Pascal's triangle.}
\label{fig:pascal}
\end{figure}
(Notice that it's just the double-induction matrix ``reshaped''.)

This triangle has lots of nice properties.  Experiment with it.  For
example, what happens if we add the coefficients in one row?
\begin{theorem}
  Suppose $n$ is any natural number.  Then
\[
\sum_{r=0}^n \binom{n}{r} = 2^n.
\]
\end{theorem}

\begin{proof} 
\begin{description}
\item[Algebraic:] This proof demonstrates an induction and Pascal's
identity.  The proof is by induction on $n$.  Let $P(n)$ be:
\[
\sum_{r=0}^n \binom{n}{r} = 2^n.
\]

BASE: $n=0$.
\[
\sum_{r=0}^0 \binom{0}{r} = \binom{0}{0} = 1 =  2^0
\]

INDUCTIVE STEP: Assume $P(n)$, show $P(n+1)$, where $n \geq 0$.
\begin{align*}
\sum_{r=0}^{n+1} \binom{n+1}{r} & = \binom{n+1}{0} + \sum_{r=1}^{n}\binom{n+1}{r} + \binom{n+1}{n+1} \\
&= 2 + \sum_{r=1}^n\binom{n+1}{r} \\
&= 2 + \sum_{r=1}^n \left(\binom{n}{r} + \binom{n}{r-1}\right) & \text{ by
Pascal's identity} \\
&= 2 + 2 \sum_{r=1}^{n-1} \binom{n}{r} + \binom{n}{0} + \binom{n}{n} \\
&= 2 \sum_{r=0}^{n} \binom{n}{r} \\
&= 2 \cdot 2^n & \text{ by inductive hypothesis}, \\
&= 2^{n+1}.
\end{align*}

\item[Combinatorial:] Again, we use case analysis and the sum rule for
disjoint unions.  There are $2^n$ different subsets of a set of $n$
elements.  Decompose this collection based on the sizes of the subsets.
That is, let $A_r$ be the collection of subsets of size $r$.  Then the set
of all subsets is the disjoint union $\cup_r A_r$.  There are
$\displaystyle\binom{n}{r}$ subsets of size $r$, for $r=0,1,\dots,n$.
Hence the theorem follows.
\end{description}
\end{proof}

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

\begin{proof}
\begin{description}
\item[Combinatorial:] Again we use case analysis with the sum and
  product rules.  Suppose there are $m$ red balls and $n$ blue balls,
  all distinct.  There are $\displaystyle\binom{m+n}{r}$ ways to choose $r$ balls
  from the two sets combined.  That's the LHS.  Now decompose this
  collection of choices based on how many of the chosen balls are
  blue.  For any $k$, $0 \leq k \leq r$, there are $\displaystyle\binom{m}{r-k}$
  ways to choose $r-k$ red balls, and $\displaystyle\binom{n}{k}$ ways to choose
  $k$ blue balls.  By the product rule, that makes $\displaystyle\binom{m}{r-k}
  \binom{n}{k}$ ways to choose $r$ balls such that $k$ of them are
  blue.  Adding up these numbers for all $k$ gives the RHS.
\end{description}
\end{proof}

We can also give an algebraic proof using induction on $n$.
However, to do this, it's useful to generalize the notion of binomial
coefficient a little:
\begin{definition}
If $r > n$, define $\displaystyle\binom{n}{r}$ to be $0$.  
\end{definition}
This makes some kind of sense informally, because there aren't any ways to
choose more elements than there are in a set!  Many of the usual binomial
identities are still correct with this extension.  In particular, Pascal's
theorem is still true if $r \geq n$ (it reduces trivially).  So we will
prove Vandermonde's theorem without the restriction $r \leq m,n$.  This
means that some of the terms in the statement of the theorem could be
trivial terms, \eg, $\displaystyle\binom{n}{k}$ could occur, where $k >
n$.  But these terms have value 0, so don't really matter.

\begin{proof}
\begin{description}
\item[Algebraic:]
Induction using generalized Pascal's identity: 
Let $P(n)$ be 
\[
\forall m, r \binom{m+n}{r} = \sum_{k=0}^r \binom{m}{r-k}\binom{n}{k}
\]
This is the generalization of Vandermonde to remove any restrictions
on the relative sizes of $m$, $n$, and $r$. 

BASE: $n =0$.  Then
\[
\binom{m+0}{r} = \binom{m}{r} = \sum_{k=0}^r \binom{m}{r-k}\binom{0}{k}.
\]
This latter equation is true because the only value of $k$ for which
the second factor isn't $0$ is $k = 0$. 
Hence $P(0)$ is true.

INDUCTIVE STEP: Assume $P(n)$ is true, show $P(n+1)$.  We have:
\begin{align*}
\binom{m+(n+1)}{r} & = \binom{m+n}{r} + \binom{m+n}{r-1} \quad 
\lefteqn{\text{ by generalized Pascal's identity}} \\
& = \sum_{k=0}^r \binom{m}{r-k}\binom{n}{k} 
  + \sum_{k=0}^{r-1} \binom{m}{r-1-k}\binom{n}{k} & \text{ by the
inductive hypothesis}\\
& = \sum_{k=0}^r \binom{m}{r-k}\binom{n}{k} 
  + \sum_{k=1}^r \binom{m}{r-k}\binom{n}{k-1}  &\text{ by change of vars}\\
& = \binom{m}{r}\binom{n}{0} + \sum_{k=1}^r \binom{m}{r-k}(\binom{n}{k} +
\binom{n}{k-1}) \\
& =  \binom{m}{r}\binom{n}{0} 
  + \sum_{k=1}^r \binom{m}{r-k}\binom{n+1}{k}  
& \mbox{ by Pascal's identity}\\ 
& =  \binom{m}{r}\binom{n+1}{0} 
  + \sum_{k=1}^r \binom{m}{r-k}\binom{n+1}{k} \\ 
& = \sum_{k=0}^r \binom{m}{r-k}\binom{n+1}{k} 
\end{align*}
Hence, $P(n+1)$ is true. So $P(n)$ is true for all $n$.
\end{description}
\end{proof}

\section{The Binomial Theorem}

An important theorem gives the coefficients in the expansion of powers
of binomial expressions.  It turns out they are binomial
coefficients---thus the name!  

\subsection{The Theorem}

\begin{theorem}
Suppose $n \in \naturals$. 
Then
$$ (x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k} .$$
\end{theorem}

\begin{example}
$(x+y)^4 = 1x^4+4x^3y+6x^2y^2+4xy^3+1y^4$
\end{example}

\begin{proof}
\begin{description}
\item[Algebraic:] By induction, using Pascal's identity.
\item[Combinatorial:]
Consider the product
\[
(x+y)^n = (x+y)(x+y)(x+y)(x+y)\dots
\]
This product has $n$ factors.  To expand this product, we generate
individual terms of the sums by selecting (in all possible ways) one
of the two variables inside each factor to get an $n$-variable
product.  If we select $k$ ``$x$'' variables and $n-k$ ``$y$''
variables, we get a term of the form $x^ky^{n-k}$.  Then we gather all
those terms together.  So how many ways do we get such a term?  Each
$x^ky^{n-k}$ term selects $x$ from $k$ of the factors and $y$ from the
other $n-k$.  So there are $\displaystyle\binom{n}{k}$ ways of choosing which
factors have $x$.
\end{description}
\end{proof}

%[[[Pset question:  Prove the Binomial Theorem algebraically.]]]

\subsection{Identities via Binomial Theorem }

The binomial theorem can be used to give slick proofs of some binomial
identities, \eg: 
\begin{theorem}
\[
\sum_{k=0}^n \binom{n}{k} = 2^n.
\]
\end{theorem}
\begin{proof}
  Plug $x = 1$, $y = 1$ into binomial theorem.
\end{proof}
\begin{theorem}\label{bin-coeff-3}
\[
\sum_{k=0}^n (-1)^k\binom{n}{k} = 0.
\]
\end{theorem}
\begin{proof}
  Plug $x = -1$, $y=1$ into binomial theorem.
\end{proof}
The combinatorial interpretation is as follows: the number of ways of
selecting an even number of elements from a set of $n$ equals the
number of ways of selecting an odd number. This works for both even
and odd $n$.
\begin{example}
Consider $n = 5$.  We can choose an odd-size set
\[
\binom{5}{1} + \binom{5 }{3} + \binom{5}{5} = 5 + 10 + 1 = 16
\]
ways.  We can choose an even-size set
\[
\binom{5}{0} + \binom{5}{2} + \binom{5}{4} = 1 + 10 + 5 = 16
\]
ways.
\end{example}

\begin{example}
$n = 6$: 
There are $6 + 20 + 6 = 32$ odd sets. 
There are $1 + 15 + 15 + 1 = 32$ even sets.
\end{example}

For odd $n$, this is intuitive (choosing an even set leaves an odd
set).  For even $n$, it may be somewhat surprising---there is no
obvious bijection between the even and odd sets.
%[[[HW:  Set up such a bijection.  I think this was on the final last
%term.  Or maybe it was the second quiz.]]]
Theorem~\ref{bin-coeff-3} can also be proven using
inclusion\slash exclusion in a tricky way.
\begin{proof}[Combinatorial proof of Theorem~\ref{bin-coeff-3}]
  Let $A_1 = A_2 = \cdots = A_n = \{1\}$. Obviously
  \begin{displaymath}
    |A_1 \cup A_2 \cup \cdots \cup A_n| = 1.
  \end{displaymath}
  Now compute the size of this intersection using inclusion\slash
  exclusion. The first term in this expansion is
  \begin{displaymath}
    \sum_{i=1}^n |A_i| = n,
  \end{displaymath}
  the second---the sum over all unordered pairs---is
  \begin{displaymath}
    \sum_{i=1}^n \sum_{j=i+1}^n |A_i \cap A_j| = \binom{n}{2}
  \end{displaymath}
  since there are $\displaystyle\binom{n}{2}$ unordered pairs and the size of every
  $A_i \cap A_j$ is~$1$. Continuing in the same way, the $k$th term is
  $\displaystyle\binom{n}{k}$. Therefore,
  \begin{displaymath}
    |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{k=1}^n (-1)^{k-1}\binom{n}{k},
  \end{displaymath}
  which is equivalent to
  \begin{displaymath}
    \sum_{k=0}^n (-1)^{k}\binom{n}{k} = 0
  \end{displaymath}
  since $|A_1 \cup A_2 \cup \cdots \cup A_n| = 1 = \binom{n}{0}$.
\end{proof}
\begin{theorem}
\[
\sum_{k=0}^{\floor{\frac{n}{2}}} \binom{n}{2k} = 2^{n-1}.
\]
\end{theorem}
\begin{proof}
\begin{description}
\item[Algebraic:] Add the equations in the two previous theorems.  We
  get
\begin{align*}
\sum_{k=0}^n \left(\binom{n}{k} + (-1)^k\binom{n}{k}\right) &= 2^n.
\intertext{%
The terms with $k$ odd cancel out, while the even terms double, so we
get:}
2 \sum_{k=0}^{\floor{\frac{n}{2}}} \binom{n}{2k} &= 2^n.
\end{align*}
Then divide by 2.
\item[Combinatorial:] The LHS represents the number of ways to pick an
  even number of elements from a set of $n$ elements.  The number of
  ways to pick an even number is equal to the number of ways to pick
  an odd number of elements.  Since the total number of ways is $2^n$,
  the number of ways to pick even is half this, or $2^{n-1}$.
\end{description}
\end{proof}
The Binomial Theorem also provides a new proof of Pascal's identity:
\begin{proof}
  We know that $(x+y)^n = x(x+y)^{n-1} + y(x+y)^{n-1}$.  Consider the
  coefficient of $x^r y^{n-r}$.  On the LHS this coefficient is $\displaystyle\binom{n
}{r}$ by the Binomial Theorem. On the RHS this coefficient
  is obtained by adding the coefficient of $x^{r-1} y^{n-r}$ in the first
  term, plus the coefficient of $x^r y^{n-1-r}$ in the second term.
  These are $\displaystyle\binom{n-1}{r-1}$ and $\displaystyle\binom{n-1}{r}$, respectively
  (again by the Binomial Theorem).
\end{proof}
It also gives a new proof of Vandermonde's identity:
\begin{proof}
  We know $(1+t)^{m+n} = (1+t)^m(1+t)^n$.  Consider the coefficient of
  $t^r$.  On the LHS this is $\displaystyle\binom{m+n}{r}$ by the binomial
  theorem.  On the RHS, it is obtained by adding up, for all $k$, the
  product of the coefficient of $t^k$ in the second factor and the
  coefficient of $t^{r-k}$ in the first factor.  This is
\[
\sum_{k=0}^r \binom{n}{k} \binom{m}{r-k}.
\]
\end{proof}

\iffalse

\subsection{The General Binomial Theorem}

We can generalize binomial coefficients once again, allowing the first
argument to be any real number:

\begin{definition}
  {\bf The Generalized binomial coefficient} $\displaystyle\binom{\alpha}{k}$ for
  $\alpha \in \reals$ and $k\in \naturals$:
  \begin{eqnarray*}
    \binom{\alpha}{k} &= &\frac{1}{k!}\prod_{j=0}^{k-1}(\alpha-j)\\ 
    & =    &\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!} \\
    \binom{\alpha}{0} &= &1
  \end{eqnarray*}
\end{definition}

This doesn't have the same kinds of combinatorial meaning as
before---for example, some of the terms in the product can now be
negative if $k>\alpha$---but it works out nice mathematically.  In
particular, a version of the binomial theorem holds:

\begin{theorem}
Let $\alpha \in \reals$ and $\abs{\cfrac{x}{y}} <1$. Then
\[
(x+y)^\alpha=\sum_{k=0}^\infty \binom{\alpha}{k}x^ky^{\alpha - k}
\]
\end{theorem}

\begin{proof}
Calculus.
\end{proof}

\begin{example}
Approximate $\sqrt{2}$ using binomial theorem. 
\[
\sqrt{2} = (x+y)^{\frac{1}{2}}, \; \mbox{where} \; x=1,y=1.
\]
However, we can't use the binomial theorem directly, because
\[
\left| \frac{x}{y} \right| \not < 1.
\]

However,
\[\sqrt{2} = 2\frac{\sqrt{2}}{2}=2\sqrt{\frac12}=2(1-\frac12)^{\frac12}=2(x+y)^{\frac12},
  \; \mbox{where} \; x=1, y=-\frac12
\]
\[(1-\frac12)^{\frac12} = \sum_{k=0}^\infty \binom{\frac12}k
  \left(-\frac12 \right)^k
\]
\[\binom{\frac12}0=1, \binom{\frac12}1=\frac12,
    \binom{\frac12}2=\frac{\left( \frac12 \right)\left(-\frac12
    \right)}{2!}=-\frac18, \binom{\frac12}3=\frac{\left( \frac12
  \right)\left(-\frac12\right)\left(-\frac32\right)}{3!}=\frac1{16},
etc.
\]
\begin{eqnarray*}
  \sqrt{2} &= 2\left(
  1+\frac12\left(-\frac12\right)+\left(-\frac18\right)
  \left(\frac14\right)+\left(\frac1{16}\right)
    \left(-\frac18\right)+\cdots\right) \\
&= 2\left(1-\frac14-\frac1{32}-\frac{1}{128}-\cdots\right) \\
&\approx 2(.7109375) = 1.421875
\end{eqnarray*} 
\end{example}
\fi

\section{Principle of Inclusion and Exclusion}

Now we return to the Principle of Inclusion-Exclusion from last
week.  Our binomial coefficient identities give us a way to prove
this theorem, via our alternating sum identity (proved by binomial
theorem).  Recall the Inclusion-Exclusion theorem:

\begin{theorem}
  $\card{\bigcup_i A_i} = 
  \sum\limits_{i} |A_i| 
  - \sum\limits_{i <j} \card{A_i \cap A_j}
  + \sum\limits_{i<j<k} \card{A_i \cap A_j \cap A_k} - \cdots$
\end{theorem}

The theorem can be proved by induction on the number of sets, but this
approach is messy \iffalse, so LTTR\fi.  Instead we will give a
combinatorial proof using binomial coefficients.

\begin{proof}
Each term in the summation counts certain elements in $\lgunion_i A_i$.  We
prove that every element of this union is counted exactly once.  So,
consider any particular element $a$, and suppose it is in exactly $r$ of
the sets $A_i$.  We see how many times $a$ is counted by each term.

In the first term, $a$ is counted $r = \binom{r}{1}$ times, once for each
of the sets that contains it.  In the second term, $a$ is counted
$\displaystyle\binom{r}{2}$ times, once for each of the pairs of sets that
contain it.  In the third term, $a$ is counted $\displaystyle\binom{r}{3}$
times, $\dots$, and in the $r$th term, $a$ is counted
$\displaystyle\binom{r}{r} = 1$ times.  The terms alternate signs, so the
total number of times $a$ is counted is:
\[
\binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \dots - (-1)^r\binom{r}{r}.
\]
But Theorem \ref{bin-coeff-3} implies that 
\[
\sum_{k=0}^r (-1)^k\binom{n}{k} = 0.
\]
This implies that the sum above is equal to $\displaystyle\binom{r}{0} = 1$. 
That is, $a$ is counted exactly once, as needed.
\end{proof}


\section{\emph{r}-Permutations with Repetition}

We now turn to permutations and combinations where elements are allowed to
repeat.  An {\em $r$-permutation with repetition} of a set $S$ is the
number of ways to choose $r$ elements from $S$ with repetition allowed and
where order matters.  For example, there are nine 2-permutations with
repetition of the set $S = \{A, B, C \}$, which are listed below.

\[
\begin{array}{ccc}
(A, A) & (A, B) & (A, C) \\
(B, A) & (B, B) & (B, C) \\
(C, A) & (C, B) & (C, C)
\end{array}
\]

\subsection{Counting \emph{r}-Permutations with Repetition}

Fortunately, $r$-permutations with repetition are easy to count.

\begin{theorem}
The number of $r$-permutations with repetition of an $n$-element set
is $n^r$.
\end{theorem}

For example, the theorem says that the number of 2-permutations with
repetition of the 3-element set $S = \{A, B, C \}$ is $3^2 = 9$, which
checks with our previous answer.

\begin{proof}
Let $S$ be a set with $n$ elements.  The $r$-permutations with
repetition of $S$ are precisely the elements of:

\[
\underbrace{S \times S \times \dots \times S}_{\text{$r$ terms}}
\]

By the Product Rule, this set has cardinality $|S|^r = n^r$.
\end{proof}

\subsection{Permutations with Limited Repetition}

We might want to count the number of $r$-permutations where each
element can be repeated a limited number of times.  In general, this
leads to some hairy analysis and no closed-form answer.  Therefore, we
will consider only a special case, the number of $r$-permutations
where each element is repeated a precisely specified number of times.

For example, in how many ways can we arrange the letters in the word
$PEPPER$?  This is equal to the number of 6-permutations of the set
$\{ P, E, R \}$ where $P$ is repeated 3 times, $E$ is repeated 2
times, and $R$ is repeated 1 time.  (Since the total number of
repetitions defines $r$, we will use the term ``permutations'' in
place of ``$r$-permutations'' for the remainder of the section.)

Initially, suppose that we make all the letters distinct by adding
subscripts.  That is, we want the number of ways to arrange the
letters $P_1E_1P_2P_3E_2R$.  In this case, there are $6! = 720$
arrangements because there are six choices for the first letter, five
choices for the second letter, etc.

Next, suppose that we erase the subscripts on the $E$'s.  This maps
each arrangement of the letters $P_1E_1P_2P_3E_2R$ to an arrangement of
the letters $P_1EP_2P_3ER$.  Since $E_1$ and $E_2$ could be ordered in
$2!$ ways before the erasure, the mapping is 2!-to-1.  For example, we
have:

\begin{eqnarray*}
P_1E_1P_2P_3E_2R & \rightarrow & P_1EP_2P_3ER \\
                 & \text{and}  & \\
P_1E_2P_2P_3E_1R & \rightarrow & P_1EP_2P_3ER
\end{eqnarray*}

Therefore, by the Division Rule there are $\frac{6!}{2!} = 360$
arrangement of the letters in $P_1EP_2P_3ER$.

Finally, suppose that we erase the subscripts on the $P$'s.  This maps
each arrangement of the letters $P_1EP_2P_3ER$ to an arrangement of
the letters $PEPPER$.  Since $P_1$, $P_2$, and $P_3$ could be ordered
in $3!$ ways before the erasure, this mapping is 3!-to-1.  Therefore,
by the Division Rule, the number of arrangements of the letters
$PEPPER$ is $\frac{6!}{2!\ 3!} = 60$.

We can prove a general theorem using the same argument as in the
$PEPPER$ problem.

\begin{theorem}
\label{th:multinomial}
Let $A$ be the set $\{ a_1, a_2, \dots, a_n \}$, and let $r_1, r_2,
\dots, r_n$ be non-negative integers.  The number of permutations of the
set $A$ where each element $a_i$ is repeated exactly $r_i$ times is:

\[
\frac{(r_1 + r_2 + \dots + r_n)!}{r_1! \ r_2! \ \dots \ r_n!}
\]
\end{theorem}

For example, the theorem says that the number of permutations of $\{
P, E, R \}$ where $P$ is repeated 3 times, $E$ is repeated 2 times,
and $R$ is repeated 1 time is $\frac{(3 + 2 + 1)!}{3!\ 2!\ 1!} = 60$.
This is the answer we found before.

\begin{proof}[Proof sketch]
We initially make $r_i$ distinct copies of each element $a_i$.  Then
the number of permutations where each element is repeated exactly once
is $(r_1 + r_2 + \dots + r_n)!$.  We then ``erase the subscripts'' on
the distinct copies of element $a_1$.  This defines an $r_1!$-to-1
mapping from old permutations to permutations where $a_1$ is
repeated $r_1$ times and all other elements are repeated once.
Therefore the number of new permutations is $\frac{(r_1 + r_2 + \dots
+ r_n)!}{r_1!}$.  Continuing this way with $a_2, a_3, \dots$, we
find that the number of permutations where each element $a_i$ is
repeated exactly $r_i$ times is $\frac{(r_1 + r_2 + \dots +
r_n)!}{r_1!\ r_2! \ \dots \ r_n!}$.
\end{proof}

\subsection{Multinomial Coefficients}

What is the number of permutations of the set $A = \{a_1, a_2\}$ where
$a_1$ is repeated $r_1$ times and $a_2$ is repeated $r_2$ times?
According to Theorem~\ref{th:multinomial}, the answer is:

\[
\frac{(r_1 + r_2)!}{r_1!\ r_2!} = \binom{r_1 + r_2}{r_1}
\]

We can restate the question as follows.  How many strings contain $r_1$
copies of the symbol $a_1$ and $r_2$ copies of the symbol $a_2$?  This
is equal to the number of ways to choose $r_1$ distinct positions for
the $a_1$'s from the set of all $r_1 + r_2$ positions, which is
$\displaystyle\binom{r_1 + r_2}{r_1}$.  This is the same as the previous answer.

By shifting from ``permutations'' to ``strings'' in this way, we can
give an alternative proof of Theorem~\ref{th:multinomial}.

\begin{proof}[Alternative proof of Theorem~\ref{th:multinomial}]
There is a bijection between permutations of the set $A = \{ a_1, a_2,
\dots, a_n \}$ where each element $a_i$ appears exactly $r_i$ times
and strings where each symbol $a_i$ appears exactly $r_i$ times.
Therefore, we can count permutations by counting strings as follows.

The number of ways to choose $r_1$ distinct positions for the $a_1$'s
from the set of all $r_1 + r_2 + \dots + r_n$ positions is
$\displaystyle\binom{r_1 + r_2 + \dots + r_n}{r_1}$.  Then the number of ways to
choose $r_2$ distinct positions for the $a_2$'s from the set of all
$r_2 + \dots + r_n$ remaining positions is $\displaystyle\binom{r_2 +
\dots + r_n}{r_2}$, and so forth.  The total number of strings is
therefore:

\begin{eqnarray*}
&   &   \binom{r_1 + r_2 + \dots + r_n}{r_1} \cdot
        \binom{r_2 + \dots + r_n}{r_2} \cdot
        \binom{r_3 + \dots + r_n}{r_3} \cdot
        \cdots
        \binom{r_n}{r_n} \\*[2ex]
& = &   \frac{(r_1 + r_2 + \dots + r_n)!}{r_1!\ (r_2 + \dots + r_n)!} \cdot
        \frac{(r_2 + \dots + r_n)!}{r_2!\ (r_3 + \dots + r_n)!} \cdot
        \frac{(r_3 + \dots + r_n)!}{r_3!\ (r_4 + \dots + r_n)!} \cdot
        \cdots
        \frac{r_n!}{r_n!\ 0!} \\*[2ex]
& = &   \frac{(r_1 + r_2 + \dots + r_n)!}{r_1!\ r_2!\ \dots\ r_n!}
\end{eqnarray*}

The first equality uses the definition of binomial coefficients, and
the second follows by cancelling terms.
\end{proof}

The quantity $\frac{(r_1 + r_2 + \dots + r_n)!}{r_1!\ r_2!\ \dots\
r_n!}$ is called a {\em multinomial coefficient} and is denoted
$\displaystyle\binom{r_1 + r_2 + \dots + r_n}{r_1, r_2, \dots, r_n}$.  Given a
set with $r_1 + r_2 + \dots + r_n$ elements, the multinomial
coefficient $\displaystyle\binom{r_1 + r_2 + \dots + r_n}{r_1, r_2, \dots, r_n}$
represents the number of ways to choose $r_1$ elements, then $r_2$ of
the remaining elements, and so forth.

Multinomial coefficients also arise in the Multinomial Theorem, a
generalization of the Binomial Theorem.  The result is stated below,
but not proved.

\begin{theorem}[Multinomial Theorem]
\[
(x_1 + x_2 + \dots + x_n)^r =
        \sum_{r_1 + r_2 + \dots + r_n = r} \binom{r}{r_1, r_2, \dots, r_n}
        x^{r_1} x^{r_2} \dots x^{r_n}
\]
\end{theorem}

\section{Combinations with Repetition}

Now we move from permutations with repetition to combinations with
repetition.  Let $S$ be the set $\{ A, B, C \}$.  As we saw in the
previous lecture, this set has three 2-combinations.  That is, there
are three ways to choose two distinct elements of $S$ where order does
not matter.  The three 2-combinations of $S$ are shown below.

\[
\{ A, B \} \quad \{ A, C \} \quad \{ B, C \}
\]

Suppose that we are not required to choose distinct elements of $S$,
but rather can choose the same element repeatedly.  The resulting sets
are called the {\em $r$-combinations with repetition} of the set $S$.
Listed below are the six $2$-combinations with repetition of $S$.

\[
\{ A, B \} \quad \{ A, C \} \quad \{ B, C \} \quad
\{ A, A \} \quad \{ B, B \} \quad \{ C, C \}
\]

Strictly speaking, these are multisets (bags), not sets, since an element may
appear multiple times.

\subsection{Counting \emph{r}-Combinations with Repetition}

The following theorem gives a nice formula for the number of
$r$-combinations with repetition of an $n$-element set.

\begin{theorem}
\label{th:comb-rep}
The number of $r$-combinations with repetition of an $n$-element set
is

\[
\binom{n + r - 1}{r}.
\]
\end{theorem}

In the example above, we found six ways to choose two elements from
the set $S = \{ A, B, C \}$ with repetition allowed.  Sure enough, the
theorem says that the number of 2-combinations of a 3-element set is
$\displaystyle\binom{3 + 2 - 1}{2} = 6$.

For comparison, recall that the number of ordinary $r$-combinations of
an $n$-element set is $\displaystyle\binom{n}{r}$.  Every ordinary $r$-combination
is also a valid $r$-combination with repetition.  So, as one would
expect, the number of $r$-combinations with repetition is greater if
$r > 1$.

The proof of this theorem uses an important trick called ``stars and
bars''.

\begin{proof}
Let $S$ be a set with $n$ elements that are ordered in some way.  We
will establish a bijection between $r$-combinations with repetition of
the set $S$ and strings of stars and bars.

Let $R$ be a particular $r$-combination with repetition of $S$.  Write
down $n-1$ bars.  These $n-1$ bars divide the line into $n$ regions.

\[
\underbrace{\quad \mid \quad \quad \mid \quad \quad \mid \quad \quad
        \dots \quad \quad \mid \quad}_{\text{$n-1$ bars define $n$ regions}}
\]

Put one star in the $i$-th region for each time that the $i$-th
element of $S$ appears in $R$.  This procedure maps each
$r$-combination with repetition to a string with $r$ stars and $n-1$
bars.

(For example, let $S$ be the set $\{ A, B, C, D, E \}$, with elements
ordered alphabetically.  Let $R$ be the $7$-combination with
repetition $\{ A, B, B, B, D, E, E \}$.  The stars-and-bars string
corresponding to $R$ is shown below.

\[
\underbrace{\star}_{A} \ \mid \
\underbrace{\star \ \star \ \star}_{B, B, B} \ \mid \ \ \mid \ 
\underbrace{\star}_{D} \ \mid \ 
\underbrace{\star \ \star}_{E, E}
\]

The two bars with no stars between indicate that element $C$ never
appears in $R$.)

This mapping is a bijection because it has an inverse.  That is, given
any stars-and-bars string, we can construct the corresponding
$r$-combination with repetition.  The number of stars in the first
region determines the number of times that the first element of $S$
appears in the $r$-combination, the stars in the second region
determine the number of times that the second element appears, etc.

Since the mapping is a bijection, the number of $r$-combinations with
repetition of an $n$-element set is equal to the number of strings
containing $n-1$ bars and $r$ stars.  The number of such strings is
equal to the number of ways to choose $r$ distinct positions for the
stars in a string of $n + r - 1$ stars and bars.  This is the number
of ordinary $r$-combinations of a set with $n + r -1$ elements, which
is $\displaystyle\binom{n + r - 1}{r}$.
\end{proof}

\subsection{Triple-Scoop Ice Cream Cones}

Baskin-Robbins is an ice cream store that has 31 different flavors.
How many different triple-scoop ice cream cones are possible at
Baskin-Robbins?  Two ice cream cones are considered the same if one
can be obtained from the other by reordering the scoops.  Of course,
we are permitted to have two or even three scoops of the same flavor.

Of course, the best solution to this problem is to go to the
Baskin-Robbins in Harvard Square and explicitly construct all possible
combinations.  This is called the {\em consumption method}.  However,
there is also a purely mathematical approach.

The number of triple-scoop ice cream cones is precisely the number of
3-combinations with repetition of the set of 31 flavors.  Therefore,
we can count the number of ice creams cones with the formula in
Theorem~\ref{th:comb-rep} where $n=31$ and $r=3$.  This gives:

\[
\binom{31 + 3 - 1}{3} = \binom{33}{3} =
\frac{33 \cdot 32 \cdot 31}{3 \cdot 2 \cdot 1} = 5456
\]

On Thursdays the Harvard Square Baskin-Robbins is run by an irritating
woman who refuses to serve a cone with two or three scoops of the same
flavor.  How many different triple-scoop ice cream cones are possible
on Thursday?

Now we must select an ice cream cone by choosing 3 {\em distinct}
flavors from the complete set of 31.  Therefore, the number of
different cones is the number of ordinary 3-combinations of a
31-element set.  This is:

\[
\binom{31}{3} = \frac{31 \cdot 30 \cdot 29}{3 \cdot 2 \cdot 1} = 4495
\]

As we would expect, the number of combinations with repetition is
greater than number of combinations without repetition.
Permitting scoops of the same flavor gives an extra $5456 - 4495 =
961$ options.

\subsection{Dozens of Dunkin Donuts}

Suppose we next stagger down to the Dunkin Donuts in Central Square.
We want a box of a dozen doughnuts and there are 21 varieties
available.  How many options do we have?

We select our box of doughnuts by pointing out 12 varieties from the
complete set of 21 where repetition is allowed.  Therefore, the number
of options is the number of 12-combinations with repetition of a 21
element set.  Applying Theorem~\ref{th:comb-rep} with $n=21$ and
$r=12$, we find that number of different boxes of doughnuts is:

\[
\binom{21 + 12 - 1}{12} = \binom{32}{12} = 225,792,840
\]

\subsection{Balls and Bins}

Suppose that we have $r$ identical balls and $n$ distinct bins.  In
how many ways can we arrange the balls in the bins?  There are six
possibilities for the case of two balls and three bins, as shown
below.

\[
\begin{array}{c}
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball \ball & & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & \ball \ball & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & & \ball \ball \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball & \ball & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball & & \ball \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & \ball & \ball \\ \hline \end{array}
\end{array}
\]

\begin{claim}
\label{clm:balls}
There are $\displaystyle\binom{n + r - 1}{r}$ ways to arrange $r$ identical balls
in $n$ distinct bins.
\end{claim}

\begin{proof}
Each arrangement of the $r$ balls corresponds to an $r$-combination
with repetition of the set of $n$ bins.  Specifically, if the $i$-th
bin contains $a_i$ balls, then the corresponding $r$-combination with
repetition contains the $i$-th bin $a_i$ times.  Therefore, the number
of arrangement of balls is equal to the number of $r$-combinations of
an $n$-element set, which is $\displaystyle\binom{n + r - 1}{r}$ by
Theorem~\ref{th:comb-rep}.
\end{proof}

There is another way to prove the claim that uses a cute bijection
between balls-and-bins arrangements and stars-and-bars strings.  The
six arrangements in the preceding example are redrawn below with some
lines erased and the balls replaced by stars.

\[
\begin{array}{c}
\begin{array}{p{3em}|p{3em}|p{3em}} \str \str & & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & \str \str & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & & \str \str \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} \str & \str & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} \str & & \str \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & \str & \str \end{array}
\end{array}
\]

Now each balls-and-bin diagram has become a stars-and-bars string.
The number of ways to place $r$ balls in $n$ bins is therefore equal
to the number of strings with $r$ stars and $n-1$ bars, which is
\[
\binom{n + r - 1}{r}.
\]

\subsection{\emph{r}-Combinations with at Least One of Each Item}

Suppose that Kaybee Toys carries balls in three delightful colors: red,
blue, and green.\footnote{I bet you're wondering if the 6.042 staff has
discovered a lucrative scam involving product promotion in lecture notes.
No comment.} In how many ways can we choose five balls so that we get at
least one ball of each color?

We might as well start by choosing one ball of each color.  Then we
can choose the last two balls however we like.  Remember that we are
counting combinations, so the order in which we choose the balls does
not matter.

Under this interpretation, the number of options is equal to the number
of ways to choose two balls from the set of three colors with
repetition allowed.  Therefore, by Theorem~\ref{th:comb-rep} there are
$\displaystyle\binom{3 + 2 - 1}{2} = 6$ possibilities.  Here they are:

\[
\begin{array}{ccc}
\{R,G,B,\ R,R\} & \{R,G,B,\ R,G\} & \{R,G,B,\ R,B\} \\
\{R,G,B,\ G,G\} & \{R,G,B,\ G,B\} & \{R,G,B,\ B,B\}
\end{array}
\]

This argument generalizes to give the theorem below.

\begin{theorem}
\label{th:comb-rep-min}
The number of $r$-combinations with repetition of an $n$-element set
that contain every element in the set at least once is:

\[
\binom{r - 1}{n - 1}
\]
\end{theorem}

For example, in the colored balls problem, we have $r = 5$ and $n =
3$.  The theorem says that there are $\displaystyle\binom{5 - 1}{3 - 1} = 6$
possibilities, which is consistent with our previous answer.

\begin{proof}
Every such $r$-combination consists of the entire $n$-element set
together with an $(r-n)$-combination with repetition of the
$n$-element set.  By Theorem~\ref{th:comb-rep} the number of such
combinations is:

\[
\binom{n + (r-n) - 1}{r-n} = \binom{r - 1}{r - n} = \binom{r-1}{n-1}
\]

The last equality uses the identity $\displaystyle\binom{m}{k} = \binom{m}{m-k}$.
\end{proof}

How many $n$-combinations with repetition of an $n$-element set are
there that contain every element in the set?  In this case,
Theorem~\ref{th:comb-rep-min} gives $\displaystyle\binom{n-1}{n-1} = 1$.  This
makes sense; the only such combination is the set $S$ itself!

In how many ways can we arrange $r$ identical balls in $n$ distinct
bins so that no bin is empty?  If we first put one ball in each bin,
then we can arrange the remaining $r-n$ balls in $\displaystyle\binom{n + (r-n) -
1}{r-n} = \binom{n-1}{r-1}$ ways.

\subsection{\emph{r}-Combinations with Limited Repetition}

Suppose that we want to count $r$-combinations where an element can be
repeated only a limited number of times.  For example, in how many
ways can we arrange 10 identical balls in 4 distinct bins such no bin
gets more than 7 balls?  A good way to solve such problems is first to
count the number of arrangements without a limit on repetition and
then to subtract off the illegal arrangements.

The number of ways to arrange 10 identical balls in 4 distinct bins
without a limit on repetition is $\displaystyle\binom{4 + 10 - 1}{10} = 286$.

Now we must count the illegal arrangements; that is, arrangements in
which some bin contains 8 or more balls.  Since there are only 10
balls in total, at most one bin can be overloaded with 8 or more
balls.  We can count the number of ways to overload the first bin by
putting 8 balls into the first bin and then observing that the last
two balls can be placed in $\displaystyle\binom{4 + 2 - 1}{2} = 10$ ways.  Since
any one of the four bins could be overloaded, the total number of
illegal arrangement is $4 \cdot 10 = 40$.

Overall, there are $286 - 40 = 246$ ways to arrange 10 balls in 4 bins
so that no bin gets more than 7 balls.

Sometimes when there are limits on repetition, the number of illegal
arrangements can itself be difficult to compute.  In such cases, a
messy inclusion-exclusion calculation may be necessary.

\subsection{Data Compression}

Stars and bars can help solve a data compression problem.  How many
bits are needed to specify a multiset of $n$ arbitrary integers in the
range $[0, 2n]$?  For example, how much disk space do we need to store
one million numbers in the range zero to two million?

\subsubsection*{A Simple Scheme}

One simple scheme is store each number in binary.  With this approach,
storing each number requires $\left\lceil \log_2(2n +1) \right\rceil$
bits.  Storing all $n$ numbers requires $n \left\lceil \log_2(2n +1)
\right\rceil$ bits.  In the case of a million numbers, we need 21 bits
to store each number and therefore 21 million bits to store all of the
numbers.

\subsubsection*{A Better Approach Using Stars and Bars}

There is a more clever scheme that uses stars and bars.  We can regard
the multiset of numbers that we want to store as an $n$-combination with
repetition of the $(2n+1)$-element set $[0,2n]$.  The proof of
Theorem~\ref{th:comb-rep} shows that such $n$-combinations with
repetition correspond to strings of $n$ stars and $2n$ bars.  If we
represent a star with a 0 and a bar with a 1, then we can store such a
stars-and-bars string using $n + 2n = 3n$ bits.

To make the scheme clear, suppose that we are storing a multiset of $n = 5$
numbers in the range $[0, 10]$.  In particular, suppose that the
numbers are $\{ 2, 4, 4, 6, 7 \}$.  We can represent this multiset as
a stars-and-bars string and then with $3n = 15$ bits as follows.

\begin{eqnarray*}
\{ 2, 4, 4, 6, 7 \}     & \rightarrow &
        \mid \ \ \mid \ \star \ \mid \ \ \mid \ \star \ \star \ \mid \ \ 
        \mid \ \star \ \mid \ \star \ \mid \ \ \mid \ \ \mid \\
        & \rightarrow & 1\ 1\ 0\ 1\ 1\ 0\ 0\ 1\ 1\ 0\ 1\ 0\ 1\ 1\ 1
\end{eqnarray*}

As another example, we could store a million numbers in the range zero
to two million using only 3 million bits, a factor of 7 improvement
over the simple scheme.  It is rather surprising that we need only 3
bits per number on average, no matter how large $n$ becomes!

\subsubsection*{An Optimal Scheme}

The stars-and-bars approach is simple and efficient, but not quite
optimal.

In any scheme, we must associate every multiset of $n$ numbers with a
distinct binary string.  From the stars-and-bars interpretation, we
know that there are $\displaystyle\binom{3n}{n}$ possible sets of $n$ numbers.
Therefore, we must be prepared to store any one of $\displaystyle\binom{3n}{n}$
distinct binary strings.  Using $k$ bits, we can store at most $2^k$
different binary strings.  This means that we need at least $k$ bits
where $2^k \geq \binom{3n}{n}$.  This inequality is satisfied provided
$k \geq \left\lceil \log_2 \binom{3n}{n} \right\rceil$.  Therefore, as
a lower bound, we need at least $\left\lceil \log_2 \binom{3n}{n}
\right\rceil$ bits.

How far from optimal is the stars-and-bars scheme?  To answer this
question, we must rewrite the lower bound in a more familiar form.  To
this end, we can use Stirling's Formula to approximate $\displaystyle\binom{3n}{n}$
as follows.

\begin{eqnarray*}
\binom{3n}{n}
        & = & \frac{(3n)!}{(2n)! \ n!} \\
        & \sim & \frac{\sqrt{2 \pi (3n)} \left( \frac{3n}{e} \right)^{3n}}
                   {\sqrt{2 \pi (2n)} \left( \frac{2n}{e} \right)^{2n}
                    \sqrt{2 \pi n}    \left( \frac{ n}{e} \right)^{ n}} \\
        & = & \sqrt{\frac{3}{4 \pi n}} \left( \frac{3^{3n}}{2^{2n}} \right)\\
        & = & \sqrt{\frac{3}{4 \pi n}} \left( \frac{27}{4} \right)^n \\
\end{eqnarray*}

With this formula, we can approximate the lower bound.

\begin{eqnarray*}
\left\lceil \log_2 \binom{3n}{n} \right\rceil
        & \sim & n \log_2 \frac{27}{4} -
                \underbrace{\frac{1}{2} \log_2{\frac{4 \pi n}{3}}}_{
                \text{low-order term}} \\
        & \sim & 2.755\dots \cdot n
\end{eqnarray*}

The stars-and-bars approach uses $3n$ bits, which is slightly more
than the lower bound of about $2.755n$ bits.

This lower bound is actually not hard to achieve, though we will not
cover the details.  The idea is to order all of the multisets of $n$
numbers in the range $[0,2n]$ and then index them $0, 1, 2, \dots$.
We then store a multiset by storing its index.  The index is a number
in the range $0$ to $\displaystyle\binom{3n}{n} - 1$, which we can store in exactly
$\left\lceil \log_2 \binom{3n}{n} \right\rceil$ bits.  Of course, the
hard part is efficiently mapping a multiset to an index and vice
versa.  Nevertheless, we can store a million numbers in the range zero
to two million with only 2.755 million bits.


\iffalse
\section{Counting with Generating Functions}

Generating functions can be used to solve counting problems of the
type we encountered in the last two weeks.  Problems involving
choosing items from a set often lead to nice generating functions.
When generating functions are used in this way, the coefficient of
$x^n$ is the number of ways to choose $n$ items from a set.

\subsection{Choosing Items from a Set Without Repetition}

The generating function for binomial coefficients follows directly
from the Binomial Theorem:

\begin{eqnarray*}
< \binom{k}{0}, \binom{k}{1}, \binom{k}{2}, \dots, \binom{k}{k},
        0, 0, 0, \dots > & \leftrightarrow & \binom{k}{0} +
        \binom{k}{1} x + \binom{k}{2} x^2 + \dots + \binom{k}{k} x^k \\
& = & (1 + x)^k
\end{eqnarray*}

This is the generating function for choosing items from a $k$-element
set without repetition.  More precisely, the coefficient of $x^n$ is
the number of ways to chose $n$ items from a $k$-element set with
without repetition.  For example, the coefficient of $x^2$ is the
number of ways to choose 2 items from a $k$-element set, which is
$\displaystyle\binom{k}{2}$.  Similarly, the coefficient of $x^{k+1}$ is the number
of ways to choose $k+1$ items from a $k$-element set, which is zero.

Often we can find the generating function for such a counting problem
with very little work.  In fact, we could find the generating function
above without worrying about the Binomial Theorem or even binomial
coefficients!

Here is how.  First, consider a single-element set $\{ a_1 \}$.  The
generating function for the number of ways to choose $n$ elements from
this set is simply $1 + x$; we have one way to choose zero elements,
one way to choose one element, and zero ways to choose more than one
element.  Similarly, the number of ways to choose $n$ elements from
the set $\{ a_2 \}$ is also given by the generating function $1 + x$;
the fact that the element differs is irrelevant.

Here is the main trick.  The generating function for choosing
elements from the union of disjoint sets is the product of the
generating functions for choosing from each set.  For example, the
generating for the number of ways to choose $n$ elements from the set
$\{ a_1, a_2 \}$ is:

\[
\underbrace{(1 + x)}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1 \}$}
\end{array}}
\underbrace{(1 + x)}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_2 \}$}
\end{array}}
=
\underbrace{(1 + x)^2}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1, a_2 \}$}
\end{array}}
= 1 + 2x + x^2
\]

Sure enough, for the set $\{ a_1, a_2 \}$ we have one way to choose
zero elements, two ways to choose one element, one way to choose two
elements, and zero ways to choose more than two elements.

\begin{rul}
Let $A(x)$ and $B(x)$ be ordinary generating functions for the number
of ways to choose items from disjoint sets ${\cal A}$ and ${\cal B}$,
respectively.  The generating function for the number of ways to
choose objects from the union ${\cal A} \cup {\cal B}$ is the product
$A(x) \cdot B(x)$.
\end{rul}

For example, by repeated application of this rule, we find that the
generating function for choosing $n$ items from a $k$-element set $\{
a_1, a_2, \dots, a_k \}$ is:

\[
\underbrace{(1 + x)}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1 \}$}
\end{array}}
\underbrace{(1 + x)}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_2 \}$}
\end{array}}
\dots
\underbrace{(1 + x)}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_k \}$}
\end{array}}
=
\underbrace{(1 + x)^k}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1, a_2, \dots, a_k\}$}
\end{array}}
\]

This is the same generating function that we obtained by using the
Binomial Theorem.

\begin{proof}
Let $A(x) = \sum_{n=0}^\infty a_n x^n$, let $B(x) = \sum_{n=0}^\infty
b_n x^n$, and let $C(x) = A(x) \cdot B(x) = \sum_{n=0}^\infty c_n
x^n$.

We must show that $c_n$ is equal to the number of ways to choose $n$
items from ${\cal A} \cup {\cal B}$.  We can compute $c_n$ by
evaluating the product $A(x) \cdot B(x)$.  We can compute the number
of ways to choose $n$ items from ${\cal A} \cup {\cal B}$ by a
combinatorial argument.  The proof is completed by showing that these
two results are the same.

First, we compute $c_n$ by evaluating the product $A(x) \cdot B(x)$.
We can tabulate all of the terms in this product in a table like the
one shown below.

\[
\begin{array}{c|ccccc}
        & b_0 x^0 & b_1 x^1 & b_2 x^2 & b_3 x^3 & \dots \\
\hline
a_0 x^0 & a_0 b_0 x^0 & a_0 b_1 x^1 & a_0 b_2 x^2 & a_0 b_3 x^3 & \dots \\
a_1 x^1 & a_1 b_0 x^1 & a_1 b_1 x^2 & a_1 b_2 x^3 & \dots \\
a_2 x^2 & a_2 b_0 x^2 & a_2 b_1 x^3 & \dots \\
a_3 x^3 & a_3 b_0 x^3 & \dots \\
\dots & \dots \\
\end{array}
\]

Note that all terms containing a particular power of $x$ lie on a
/-sloped diagonal.  Collecting terms, we find that the coefficient of
$x^n$ in the product is:

\[
c_n = a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \dots a_n b_0
\]

Next, we compute the number of ways to choose $n$ items from ${\cal A}
\cup {\cal B}$.  We can break up the answer based on the number of
items chosen from set ${\cal A}$.  In particular, suppose we choose
$j$ items from ${\cal A}$ and $n-j$ items from ${\cal B}$.  The number
of ways to choose $j$ items from ${\cal A}$ is $a_j$, and the number
of ways to choose $n-j$ items from ${\cal B}$ is $b_{n-j}$.  By the
Product Rule, we can choose all $n$ items in $a_j b_{n-j}$ ways.
Since we could choose $j = 0, 1, \dots, n$ items from ${\cal A}$, the
total number of ways to choose $n$ items from ${\cal A} \cup {\cal B}$
is the sum:

\[
a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \dots a_n b_0
\]

This is equal to the value of $c_n$ computed above.
\end{proof}

In the above argument, we implicitly used the fact that ${\cal A}$ and
${\cal B}$ are disjoint sets when referring to the number of items
chosen from ${\cal A}$; were the sets intersecting, the number of
items drawn from ${\cal A}$ would not be well-defined, since the same
item might be in both sets.

The expression $c_n = a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \dots a_n
b_0$ may be familiar from a signal processing course; the sequence
$<c_0, c_1, c_2, \dots>$ is the {\em convolution} of sequences $<a_0,
a_1, a_2, \dots>$ and $<b_0, b_1, b_2, \dots>$.

\subsection{Choosing Items with Repetition}
\label{sec:rep}

We have seen that the number of ways to choose $n$~items \emph{with
  repetition} from a $k$-element set is $\displaystyle\binom{n + k - 1}{k}$.  We
can derive the same result using generating functions.  This will
introduce some new techniques that will be helpful when we do not know
the answer in advance!

\subsubsection{Finding a Generating Function}

Suppose we choose $n$ items with repetition from a set containing a
single item.  Then there is one way to choose zero items, one way to
choose one item, one way to choose a two items, etc.  The generating
function for choosing $n$ elements with repetition from a 1-element
set is therefore:

\begin{eqnarray*}
<1, 1, 1, 1, \dots> & \leftrightarrow & 1 + x + x^2 + x^3 + \dots
                      = \frac{1}{1-x}
\end{eqnarray*}

As before, the generating function for choosing items from a union of
disjoint sets is the product of the generating functions for choosing
from each set.

\[
\underbrace{\frac{1}{1-x}}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1 \}$}
\end{array}}
\underbrace{\frac{1}{1-x}}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_2 \}$}
\end{array}}
\dots
\underbrace{\frac{1}{1-x}}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_k \}$}
\end{array}}
=
\underbrace{\frac{1}{(1-x)^k}}_{
\begin{array}{cc}
\mbox{OGF for} \\
\mbox{$\{ a_1, a_2, \dots, a_k\}$}
\end{array}}
\]

The generating function for choosing $n$ items from a $k$-item set
with repetition allowed is $\frac{1}{(1-x)^k}$.

\subsubsection{Finding Coefficients}
\label{sec:find_coeff}

Now we need to find the coefficients of the generating function.  In
particular, the coefficient of $x^n$ in the generating function
$\frac{1}{(1-x)^k}$ gives the number of ways to choose $n$ items
from a $k$-item set with replacement.

Since the generating function is a ratio of polynomials, we could try
using partial fractions as before.  However, the partial fractions
expansion of $\frac{1}{(1-x)^k}$ actually {\em is} just
$\frac{1}{(1-x)^k}$; no progress there!

Another way to find coefficients of a generating function is by
repeatedly differentiating and then evaluating the result at 0.  Here
is how this technique can be used to find the first few coefficients
of a generating function $G(x)$.

\begin{eqnarray*}
G(x) = g_0 + g_1 x + g_2 x^2 + g_3 x^3 + g_4 x^4 + \dots
        & G(0) = g_0 \\
G'(x) = g_1 + 2 g_2 x + 3 g_3 x^2 + 4 g_4 x^3 + \dots
        & G'(0) = g_1 \\
G''(x) = 2 g_2 x + 3 \cdot 2 g_3 x + 4 \cdot 3 g_4 x^2 + \dots
        & G''(0) = 2 g_2 \\
G'''(x) = 3 \cdot 2 g_3 + 4 \cdot 3 \cdot 2 g_4 x + \dots
        & G'''(0) = 3 \cdot 2 g_3 \\
\end{eqnarray*}

In general, after $n$ derivatives we have $G^{(n)}(0) = n! g_n$.
Therefore, the coefficient of $x^n$ is $G^{(n)}(0) / n!$.

Recall that differentiating a generating function has two effects on
the corresponding sequence: terms are multiplied by their index and
then all terms are shifted left one place.  In this case, we intend to
left-shift $n$ times, but must cancel out the unwanted multiplication
by dividing by $n!$.

All that remains is to compute the $n$-th derivative of $G(x) =
\frac{1}{(1-x)^k}$.  This is not too hard:

\begin{eqnarray*}
G(x) & = & (1-x)^{-k} \\
G'(x) & = & k (1-x)^{-k-1} \\
G''(x) & = & k (k+1) (1-x)^{-k-2} \\
G^{(n)}(x) & = & k (k+1) \dots (k + n - 1)(1-x)^{-k-n}
\end{eqnarray*}

The coefficient of $x^n$ in the generating function is computed below.

\begin{eqnarray*}
G^{(n)}(0) / n! & = & \frac{k (k+1) \dots (k + n - 1)}{n!} \\
                & = & \frac{(k + n - 1)!}{n! \ (k-1)!} \\
                & = & \binom{k + n - 1}{n}
\end{eqnarray*}

Therefore, the number of ways to choose $n$ items from a $k$-element set
with repetition allowed is $\displaystyle\binom{k + n - 1}{n}$.

\section{An ``Impossible'' Counting Problem}

Here is an absurd counting problem.  In how many ways can we fill a
bag with $n$ fruits subject to the following constraints?

\begin{itemize}
\item The number of apples must be even.
\item The number of bananas must be a multiple of 5.
\item There can be at most four oranges.
\item There can be at most one pear.
\end{itemize}

For example, there are 7 ways to form a bag with 6 fruits:

\[
\begin{array}{c|ccccccc}
\mbox{Apples}  & 6 & 4 & 4 & 2 & 2 & 0 & 0 \\
\mbox{Bananas} & 0 & 0 & 0 & 0 & 0 & 5 & 5 \\
\mbox{Oranges} & 0 & 2 & 1 & 4 & 3 & 1 & 0 \\
\mbox{Pears}   & 0 & 0 & 1 & 0 & 1 & 0 & 1
\end{array}
\]

This problem appears utterly hopeless for an arbitrary number of
fruits, but we can actually use generating functions to find an
answer.

First, we need a generating function for the number of fruit bags.
Initially, we can consider each fruit separately.  That is, we can
count the number of fruit bags with just apples, then just bananas,
petc.  For example, the number of fruit bags with 0 apples is one (the
empty bag), the number of bags with 1 apple is zero (the number of
apples must be even), the number of bags with 2 apples is one (the bag
with two apples), etc.  The generating functions for the four types of
fruit are worked out below.

\begin{eqnarray*}
A(x) = & 1 + x^2 + x^4 + x^6 + \dots & =  \frac{1}{1-x^2} \\
B(x) = & 1 + x^5 + x^{10} + x^{15} + \dots & = \frac{1}{1-x^5} \\
O(x) = & 1 + x + x^2 + x^3 + x^4 & = \frac{1-x^5}{1-x} \\
P(x) = & 1 + x
\end{eqnarray*}

As in previous counting problems, the generating function for picking
$n$ items from a union of disjoint sets is the product of the
generating functions for picking from each set.  That is, all fruit
bags are counted by the generating function $A(x) B(x) O(x) P(x)$.
This function is computed below.

\begin{eqnarray*}
\mbox{OGF for fruit bags} & = & A(x) B(x) O(x) P(x) \\
& = & \frac{1}{1-x^2} \frac{1}{1-x^5} \frac{1-x^5}{1-x} (1 + x) \\
& = & \frac{1}{(1-x)^2} \\
& = & 1 + 2x + 3x^2 + 4 x^3 + \dots
\end{eqnarray*}

The coefficient of $x^n$ is simply $n+1$; that is, the number of ways
to form a bag of $n$ fruits is just $n+1$.  This is consistent with
the example we worked out, since there were 7 fruit bags with 6
fruits.  Amazing!

\section{Summary}

The table below summarizes the basic results from our lectures about
choosing $r$ elements from an $n$-element set:

\begin{eqnarray*}
\text{$r$-combinations without repetition} & = & \binom{n}{r} \\*[3ex]
\text{$r$-permutations without repetition} & = & \frac{n!}{(n-r)!} \\*[3ex]
\text{$r$-combinations with repetition} & = & \binom{n+r-1}{r} \\*[3ex]
\text{$r$-permutations with repetition} & = & n^r
\end{eqnarray*}
\fi

\end{document}
