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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.csail.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document}
\lecturenotes{10}{Counting, II.}

\newcommand{\spa}{\spadesuit}
\newcommand{\hea}{\heartsuit}
\newcommand{\dia}{\diamondsuit}
\newcommand{\clu}{\clubsuit}

\section{Counting Subsets}

How many $k$-elements subsets of an $n$-element set are there?  This
question arises all the time in various guises:

\begin{itemize}

\item In how many ways can I select 5 books from my collection of 100
to bring on vacation?

\item How many different 13-card Bridge hands can be dealt from a
52-card deck?

\item In how many ways can I select 5 toppings for my pizza if there
are 14 available?

\end{itemize}

This number comes up so often that there is a special notation for it:
\[
\binom{n}{k} \eqdef \text{ the number of $k$-element subsets of an $n$-element set.}
\]

The expression ``$\dbinom{n}{k}$'' is read ``$n$-choose-$k$.''  Now we can
immediately express the answers to all three questions above:

\begin{itemize}

\item I can select 5 books from 100 in $\binom{100}{5}$ ways.

\item There are $\dbinom{52}{13}$ different Bridge hands.

\item There are $\dbinom{14}{5}$ different 5-topping pizzas, if 14
toppings are available.

\end{itemize}

\subsection{The Subset Rule}

We can derive a simple formula for $n$-choose-$k$ number using the
Division Rule.  We do this by mapping any permutation of an $n$-element
set $\set{a_1,\dots, a_n}$ into a $k$-element subset simply by taking the
first $k$ elements of the permutation.  That is, the permutation
$a_1a_2\dots a_n$ will map to the set $\set{a_1,a_2,\dots,a_k}$.

Notice that any other permutation with the same first $k$ elements
$a_1,\dots,a_k$ \emph{in any order} and the same remaining elements $n-k$
elements \emph{in any order} will also map to this set.  What's more, a
permutation can only map to $\set{a_1,a_2,\dots,a_k}$ if its first $k$
elements are the elements $a_1,\dots,a_k$ in some order.  Since there are
$k!$ possible permutations of the first $k$ elements and $(n-k)!$
permutations the remaining elements, we conclude from the Product Rule
that exactly $k!(n-k)!$ permutations of the $n$-element set map to the the
particular subset, $S$.  In other words, the mapping from permutations to
$k$-element subsets is $k!(n-k)!$-to-1.

But we know there are $n!$ permutations of an $n$-element set, so by the
Division Rule, we conclude that
\[
n!= k!(n-k)!\binom{n}{k}
\]
which proves:
\begin{mathrule}[Subset Rule]
\label{rule:subset}
The number,
\[
\binom{n}{k},
\]
of $k$-element subsets of an $n$-element set is
\[
\frac{n!}{k!\ (n-k)!}.
\]
\end{mathrule}

Notice that this works even for 0-element subsets: $n!/0!n! = 1$.  Here we
use the fact that $0!$ is a \emph{product} of 0 terms, which by convention
equals 1.  (A \emph{sum} of zero terms equals 0.)

\subsection{Bit Sequences}

How many $n$-bit sequences contain exactly $k$ ones?  We've already seen
the straightforward bijection between subsets of an $n$-element set and
$n$-bit sequences.  For example, here is a 3-element subset of $\set{x_1,
x_2, \ldots, x_8}$ and the associated 8-bit sequence:
%
\[
\begin{array}{rccccccccl}
\{ & x_1, &    &    & x_4, & x_5  &    &    &   & \} \\
(  &   1, & 0, & 0, &   1, &   1, & 0, & 0, & 0 & )
\end{array}
\]
Notice that this sequence has exactly 3 ones, each corresponding to an
element of the 3-element subset.  More generally, the $n$-bit sequences
corresponding to a $k$-element subsets will have exactly $k$ ones.  So by
the Bijection Rule,
\begin{quote}
The number of $n$-bit sequences with exactly $k$ ones is $\dbinom{n}{k}$.
\end{quote}

\section{Magic Trick}

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 each select one card from the deck.  The Assistant then
gathers up the five cards and holds up four of them so the Magician can
see them.  The Magician concentrates for a short time and then correctly
names the secret, fifth card!

Since we don't really believe the Magician can read minds, we know the
Assistant has somehow communicated the secret card to the Magician.  Since
real Magicians and Assistants are not to be trusted, we can expect that
the Assistant would illegitimately signal the Magician with coded phrases
or body language.  But this need not happen.  In fact, the Magician and
Assistant could be kept out of sight of each other with the Assistant
designating some audience member to hold up the 4 cards he selects.

But there is an obvious, legitimate way the Assistant can communicate to
the Magician: he can choose any of the $4! = 24$ permutations of the 4
cards as the order in which to hold up the cards.  However, this alone
won't quite work: there are 48 cards remaining in the deck, so the
Assistant doesn't have enough choices of orders to indicate exactly what
the secret card is (though he could narrow it down to two cards).

\subsection{The Secret}

The method the Assistant can use to communicate the fifth card exactly is
a nice application of what we know about counting and matching.

The Assistant really has two legitimate ways to communicate.  He can not
only announce the four cards in any order, but he can also choose
\emph{which four of the five cards to reveal}.  Of course, the Magician
can not determine which of these five possibilities the Assistant
selected, since he does not know the secret card.

Nevertheless, these legitimate forms of communication allow the Assistant
to covertly reveal the secret card to the Magician.

Our counting tools give a lot of insight into the magic trick.  Put
all the \textit{sets} of 5 cards in a collection $X$ on the left.  And
put all the sequences of 4 distinct cards in a collection $Y$ on the
right.

\begin{center}
\begin{picture}(450,155)(0,25)
%\put(0,25){\framebox(450,155){}} % bounding box

\put(50,164){\makebox(0,0){$X = $}}
\put(50,150){\makebox(0,0){all sets of}}
\put(50,136){\makebox(0,0){5 cards}}

\put(100,172){\makebox(0,0){$\bullet$}}
\put(100,154){\makebox(0,0){$\bullet$}}
\put(100,136){\makebox(0,0){$\bullet$}}
\put(100,118){\makebox(0,0){$\bullet$}}
\put(100,100){\makebox(0,0){$\set{8 \hea, K \spa, Q \spa, 2 \dia, 6 \dia}$}}
\put(100,82){\makebox(0,0){$\bullet$}}
\put(100,64){\makebox(0,0){$\bullet$}}
\put(100,46){\makebox(0,0){$\set{8 \hea, K \spa, Q \spa, 9 \clu, 6 \dia}$}}
\put(100,28){\makebox(0,0){$\bullet$}}

\put(410,172){\makebox(0,0){$Y = $ all}}
\put(410,158){\makebox(0,0){sequences of 4}}
\put(410,144){\makebox(0,0){distinct cards}}

\put(350,172){\makebox(0,0){$\bullet$}}
\put(350,154){\makebox(0,0){$\bullet$}}
\put(350,136){\makebox(0,0){$\bullet$}}
\put(350,118){\makebox(0,0){$(8 \hea, K \spa, Q \spa, 2 \dia)$}}
\put(350,100){\makebox(0,0){$(K \spa, 8 \hea, Q \spa, 2 \dia)$}}
\put(350,82){\makebox(0,0){$(K \spa, 8 \hea, 6 \dia, Q \spa)$}}
\put(350,64){\makebox(0,0){$\bullet$}}
\put(350,46){\makebox(0,0){$\bullet$}}
\put(350,28){\makebox(0,0){$\bullet$}}

\put(165,100){\line(3,1){60}}
\put(165,100){\line(1,0){125}}
\put(165,100){\line(6,-1){125}}
\put(165,100){\line(3,-1){60}}

\put(165,50){\line(3,1){60}}
\put(165,50){\line(1,0){60}}

\thicklines
\put(165,100){\line(6,1){125}}
\put(165,50){\line(5,1){125}}

\end{picture}
\end{center}

For example, $\set{ 8 \hea, K \spa, Q \spa, 2 \dia, 6 \dia }$ is an
element of $X$ on the left.  If the audience selects this set of 5 cards,
then there are many different 4-card sequences on the right in set $Y$
that the Assistant could choose to reveal, including $(8 \hea, K \spa, Q
\spa, 2 \dia)$, $(K \spa, 8 \hea, Q \spa, 2 \dia)$, and $(K \spa, 8 \hea,
6 \dia, Q \spa)$.

Let's think about this problem in terms of graphs.  Regard the
elements of $X$ and $Y$ as the vertices of a bipartite graph.  Put an
edge between a set of 5 cards and a sequence of 4 if every card in the
sequence is also in the set.  In other words, if the audience selects
a set of cards, then the Assistant must reveal a sequence of cards
that is adjacent in the bipartite graph.  Some edges are shown in the
diagram above.

What we need to perform the trick is a \textit{matching} for the $X$
vertices; that is, we need a subset of edges that join every vertex on
the left to exactly one, distinct vertex on the right.  If such a
matching exists, then the Assistant and Magician can agree one in
advance.  Then, when the audience selects a set of 5 cards, the
Assistant reveals the corresponding sequence of 4 cards.  The Magician
translates back to the corresponding set of 5 cards and names the one
not already revealed.

For example, suppose the Assistant and Magician agree on a matching
containing the two bold edges in the diagram above.  If the audience
selects the set $\set{8 \hea, K \spa, Q \spa, 9 \clu, 6 \dia}$, then
the Assistant reveals the corresponding sequence $(K \spa, 8 \hea, 6
\dia, Q \spa)$.  The Magician names the one card in the corresponding
set not already revealed, the $9 \clu$.  Notice that the sets must be
matched with \textit{distinct} sequences; if the Assistant revealed
the same sequence when the audience picked the set $\set{8 \hea, K
\spa, Q \spa, 2 \dia, 6 \dia}$, then the Magician would be unable to
determine whether the remaining card was the $9 \clu$ or $2 \dia$!

The only remaining question is whether a matching for the $X$ vertices
exists.  This is precisely the subject of Hall's Theorem.  Regard the
$X$ vertices as girls, the $Y$ vertices as boys, and each edge as an
indication that a girl likes a boy.  Then a matching for the girls
exists if and only if the marriage condition is satisfied:

\begin{center}
\textit{Every subset of girls likes at least as large a set of boys.}
\end{center}

Let's prove that the marriage condition holds for the magic trick
graph.  We'll need a couple preliminary facts:

\begin{itemize}

\item Each vertex on the left has degree $5 \cdot 4! = 120$, since
there are five ways to select the card kept secret and there are $4!$
permutations of the remaining 4 cards.  In terms of the marriage
metaphor, every girl like 120 boys.

\item Each vertex on the right has degree 48, since there are 48
possibilities for the fifth card.  Thus, every boy is liked by 48
girls.

\end{itemize}
Now let $S$ be an arbitrary set of vertices on the left, which we're
regarding as girls.  There are $120 \card{S}$ edges incident to vertices
in this set.  Since each boy is liked by at most 48 girls, this set of
girls likes at least $120 \card{S} / 48 \geq \card{S}$ different boys.
Thus, the marriage condition is satisfied, a matching exists by Hall's
Theorem.  In fact, this reasoning show that the Magician could still pull
off the trick if 120 cards were left instead of 48, that is the trick
would work with a deck as large as 124 different cards --- without any
magic!

\subsection{The Real Secret}

You might not find the preceding answer very satisfying.  After all,
as a practical matter, the Assistant and the Magician can not memorize
a matching containing $\binom{52}{5} = 2,598,960$ edges!  The
remaining challenge is to choose a matching that can be readily
computed on the fly.  We'll describe one approach.  As an running
example, suppose that the audience selects:
%
\[
10 \hea \quad 9 \dia \quad 3 \hea \quad Q \spa \quad J \dia
\]

\begin{itemize}

\item The Assistant picks out two cards of the same suit.  In the
example, the assistant might choose the $3 \hea$ and $10 \hea$.

\item The Assistant locates the values of these two cards on the cycle
shown below:

\begin{center}
\begin{picture}(120,120)(-60,-60)
% \put(-60,-60){\framebox(120,120){}} % bounding box
\put(0.000000,50.000000){\makebox(0,0){$A$}}
\put(23.236159,44.272801){\makebox(0,0){$2$}}
\put(41.149193,28.403237){\makebox(0,0){$\mathbf{3}$}}
\put(49.635444,6.026834){\makebox(0,0){$4$}}
\put(46.750812,-17.730244){\makebox(0,0){$5$}}
\put(33.156133,-37.425537){\makebox(0,0){$6$}}
\put(11.965783,-48.547091){\makebox(0,0){$7$}}
\put(-11.965783,-48.547091){\makebox(0,0){$8$}}
\put(-33.156133,-37.425537){\makebox(0,0){$9$}}
\put(-46.750812,-17.730244){\makebox(0,0){$\mathbf{10}$}}
\put(-49.635444,6.026834){\makebox(0,0){$J$}}
\put(-41.149193,28.403237){\makebox(0,0){$Q$}}
\put(-23.236159,44.272801){\makebox(0,0){$K$}}
\end{picture}
\end{center}

For any two distinct values on this cycle, one is always between 1 and
6 hops clockwise from the other.  For example, the $3 \hea$ is 6 hops
clockwise from the $10 \hea$.

\item The more counterclockwise of these two cards is revealed first,
and the other becomes the secret card.  Thus, in our example, the $10
\hea$ would be revealed, and the $3 \hea$ would be the secret card.
Therefore:

\begin{itemize}

\item The suit of the secret card is the same as the suit of the first
card revealed.

\item The value of the secret card is between 1 and 6 hops clockwise
from the value of the first card revealed.

\end{itemize}

\item All that remains is to communicate a number between 1 and 6.
The Magician and Assistant agree beforehand on an ordering of all the
cards in the deck from smallest to largest such as:
%
\[
A \clu\ 2 \clu\ \ldots\ K \clu\ 
A \dia\ 2 \dia\ \ldots\ Q \dia\ 
A \hea\ 2 \hea\ \ldots\ Q \hea\ 
A \spa\ 2 \spa\ \ldots\ Q \spa
\]
%
The order in which the last three cards are revealed communicates the
number according to the following scheme:
%
\[
\begin{array}{rcccll}
(&\text{small},&\text{medium},&\text{large}&) & = 1 \\
(&\text{small},&\text{large},&\text{medium}&) & = 2 \\
(&\text{medium},&\text{small},&\text{large}&) & = 3 \\
(&\text{medium},&\text{large},&\text{small}&) & = 4 \\
(&\text{large},&\text{small},&\text{medium}&) & = 5 \\
(&\text{large},&\text{medium},&\text{small}&) & = 6
\end{array}
\]
%
In the example, the Assistant wants to send 6 and so reveals the
remaining three cards in large, medium, small order.  Here is the
complete sequence that the Magician sees:
%
\[
10 \hea \quad Q \spa \quad J \dia \quad 9 \dia
\]

\item The Magician starts with the first card, $10 \hea$, and hops 6
values clockwise to reach $3 \hea$, which is the secret card!

\end{itemize}

Note that while Hall's Theorem ensures that the Magician and Assistant
could perform the trick with a deck of up to 120 cards providing they had
access to a computer database containing an appropriate matching, we know
of no practical method to perform the trick with a deck of more than 52
cards without use of a computer.

\subsection{Same Trick with Four Cards?}

Suppose that the audience selects only \textit{four} cards and the
Assistant reviews a sequence of \textit{three} to the Magician.  Can
the Magician determine the fourth card?

Let $X$ be all the sets of four cards that the audience might select,
and let $Y$ be all the sequences of three cards that the Assistant
might reveal.  Now, one on hand, we have
\[
\card{X} = \binom{52}{4} = 270,725
\]
by the Subset Rule.  On the other hand, we have
\[
\card{Y} = 52 \cdot 51 \cdot 50 = 132,600
\]
by the Generalized Product Rule.  Thus, by the Pigeonhole Principle, the
Assistant must reveal the \textit{same} sequence of three cards for some
two \textit{different} sets of four.  This is bad news for the Magician:
if he hears that sequence of three, then there are at least two
possibilities for the fourth card which he cannot distinguish.  So there
is no legitimate way for the Assistant to communicate exactly what the
fourth card is!

\section{The Bookkeeper Rule}

\subsection{Sequences of Subsets}

Choosing a $k$-element subset of an $n$-element is the same as splitting
the set into a pair of subsets: the first subset of size $k$ and the
second subset consisting of the remaining $n-k$ elements.  So the Subset
Rule can be understood as a rule for counting the number of such splits
into pairs of subsets.

We can generalize this to splits into $m$ subsets.  Namely, let $A$ be an
$n$-element set and $k_1,k_2, \dots, k_m$ be nonnegative integers whose
sum is $n$.  A \term{$(k_1,k_2, \dots, k_m)$-split of $A$} is a sequence
\[
(A_1, A_2,\dots,A_m)
\]
where the $A_i$ are pairwise disjoint subsets of $A$ and $\card{A_i} =
k_i$ for $i=1,\dots,m$.

The same reasoning used to explain the Subset Rule extends directly to a
rule for counting the number of splits into subsets of given sizes.

\begin{mathrule}[Subset Split Rule]
The number of $(k_1,k_2, \dots, k_m)$-splits of an $n$-element set is
\[
\binom{n}{k_1,\dots,k_m} \eqdef \frac{n!}{k_1!\ k_2!\ \cdots k_m!}
\]
\end{mathrule}

The proof of this Rule is essentially the same as for the Subset Rule.
Namely, we map any permutation $a_1a_2\dots a_n$ of an $n$-element set,
$A$, into a $(k_1,k_2, \dots, k_m)$-split by letting the 1st subset in the
split be the first $k_1$ elements of the permutation, the 2nd subset of
the split be the next $k_1$ elements, \dots, and the $m$th subset of the
split be the final $k_m$ elements of the permutation.  This map is a
$k_1!\ k_2!\ \cdots\ k_k!$-to-1 from the $n!$ permutations to the
$(k_1,k_2, \dots, k_m)$-splits of $A$, and the Subset Split Rule now
follows from the Division Rule.

\subsection{Sequences over an alphabet}

We can also generalize our count of $n$-bit sequences with $k$-ones to
counting length $n$ sequences of letters over an alphabet with more than
two letters.  For example, how many sequences can be formed by permuting
the letters in the 10-letter word BOOKKEEPER?

Notice that there are 1 B, 2 O's, 2 K's, 3 E's, 1 P, and 1 R in
BOOKKEEPER.  This leads to a straightforward bijection between
permutations of BOOKKEEPER and (1,2,2,3,1,1)-splits of $\set{1,\dots,n}$.
Namely, map a permutation to the sequence of sets of positions where each
of the different letters occur.

For example, in the permutation BOOKKEEPER itself, the B is in the 1st
position, the O's occur in the 2nd and 3rd positions, K's in 4th and 5th,
the E's in the 6th, 7th and 9th, P in the 8th, and R is in the 10th
position, so BOOKKEEPER maps to
\[
(\set{1}, \set{2,3}, \set{4,5}, \set{6,7,9}, \set{8}, \set{10}).
\]
From this bijection and the Subset Split Rule, we conclude that the
number of ways to rearrange the letters in the word BOOKKEEPER is:
\[
\frac{\overbrace{10!}^{\text{total letters}}}{
\underbrace{1!}_{\text{B's}}
\underbrace{2!}_{\text{O's}}
\underbrace{2!}_{\text{K's}}
\underbrace{3!}_{\text{E's}}
\underbrace{1!}_{\text{P's}}
\underbrace{1!}_{\text{R's}}}
\]

This example generalizes directly to an exceptionally useful counting
principle which we will call the
\begin{mathrule}[Bookkeeper Rule]
Let $l_1, \ldots, l_m$ be distinct elements.  The number of sequences with
$k_1$ occurrences of $l_1$, and $k_2$ occurrences of $l_2$, \dots, and
$k_m$ occurrences of $l_m$ is
\[
\frac{(k_1 + k_2 + \ldots + k_m)!}{k_1!\ k_2!\ \ldots\ k_m!}
\]
\end{mathrule}

\begin{example*} 20-Mile Walks.

I'm planning a 20-mile walk, which should include 5 northward miles, 5
eastward miles, 5 southward miles, and 5 westward miles.  How many
different walks are possible?

There is a bijection between such walks and sequences with 5 N's, 5
E's, 5 S's, and 5 W's.  By the Bookkeeper Rule, the number of such
sequences is:
\[
\frac{20!}{5!^4}
\]
\end{example*}

\subsection{A Word about Words}

Someday you might refer to the Subset Split Rule or the Bookkeeper Rule
in front of a roomful of colleagues and discover that they're all staring
back at you blankly.  This is not because they're dumb, but rather because
we made up the name ``Bookkeeper Rule''.  However, the rule is excellent
and the name is apt, so we suggest that you play through: ``You know?  The
Bookkeeper Rule?  Don't you guys know \textit{anything???}''

The Bookkeeper Rule is sometimes called the ``formula for permutations
with indistinguishable objects.''  The size $k$ subsets of an $n$-element
set are sometimes called \term{$k$-combinations}.  Other similar-sounding
descriptions are ``combinations with repetition, permutations with
repetition, $r$-permutations, permutations with indistinguishable
objects,'' and so on.  However, the counting rules we've taught you are
sufficient to solve all these sorts of problems without knowing this
jargon, so we'll skip it.

\section{Poker Hands}

There are 52 cards in a deck.  Each card has a \textit{suit} and a
\textit{value}.  There are four suits:
%
\[
\stackrel{\text{spades}}{\spadesuit} \qquad
\stackrel{\text{hearts}}{\heartsuit} \qquad
\stackrel{\text{clubs}}{\clubsuit} \qquad
\stackrel{\text{diamonds}}{\diamondsuit}
\]
%
And there are 13 values:
%
\[
2\ ,\ 3\ ,\ 4\ ,\ 5\ ,\ 6\ ,\ 7\ ,\ 8\ ,\ 9\ ,\ 
\stackrel{\text{jack}}{J},\ 
\stackrel{\text{queen}}{Q},\ 
\stackrel{\text{king}}{K},\ 
\stackrel{\text{ace}}{A}
\]
%
Thus, for example, $8 \heartsuit$ is the 8 of hearts and $A
\spadesuit$ is the ace of spades.  Values farther to the right in this
list are considered ``higher'' and values to the left are ``lower''.

Five-Card Draw is a card game in which each player is initially dealt
a \textit{hand}, a subset of 5 cards.  (Then the game gets
complicated, but let's not worry about that.)  The number of different
hands in Five-Card Draw is the number of 5-element subsets of a
52-element set, which is 52 choose 5:
%
\[
\text{total \# of hands} = \binom{52}{5} = 2,598,960
\]
%
Let's get some counting practice by working out the number of hands
with various special properties.

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

A \textit{Four-of-a-Kind} is a set of four cards with the same value.
How many different hands contain a Four-of-a-Kind?  Here a couple
examples:
%
\[
\begin{array}{rcccccl}
\{ & 8 \spa, & 8 \dia, & Q \hea, & 8 \hea, & 8 \clu & \} \\
\{ & A \clu, & 2 \clu, & 2 \hea, & 2 \dia, & 2 \spa * \} \\
\end{array}
\]
%
As usual, the first step is to map this question to a
sequence-counting problem.  A hand with a Four-of-a-Kind is completely
described by a sequence specifying:
%
\begin{enumerate}
\item The value of the four cards.
\item The value of the extra card.
\item The suit of the extra card.
\end{enumerate}
%
Thus, there is a bijection between hands with a Four-of-a-Kind and
sequences consisting of two distinct values followed by a suit.  For
example, the three hands above are associated with the following
sequences:
%
\[
\begin{array}{rccccclcl}
(8, Q, \hea) & \leftrightarrow &
  \{ & 8 \spa, & 8 \dia, & 8 \hea, & 8 \clu, & Q \hea & \} \\
(2, A, \clu) & \leftrightarrow &
  \{ & 2 \clu, & 2 \hea, & 2 \dia, & 2 \spa, & A \clu & \} \\
\end{array}
\]
%
Now we need only count the sequences.  There are 13 ways to choose the
first value, 12 ways to choose the second value, and 4 ways to choose
the suit.  Thus, by the Generalized Product Rule, there are $13 \cdot
12 \cdot 4 = 624$ hands with a Four-of-a-Kind.  This means that only 1
hand in about 4165 has a Four-of-a-Kind; not surprisingly, this is
considered a very good poker hand!

\subsection{Hands with a Full House}

A \textit{Full House} is a hand with three cards of one value and
two cards of another value.  Here are some examples:
%
\[
\begin{array}{rcccccl}
\{ & 2 \spa, & 2 \clu, & 2 \dia, & J \clu, & J \dia & \} \\
\{ & 5 \dia, & 5 \clu, & 5 \hea, & 7 \hea, & 7 \clu & \}
\end{array}
\]
%
Again, we shift to a problem about sequences.  There is a bijection
between Full Houses and sequences specifying:
%
\begin{enumerate}
\item The value of the triple, which can be chosen in 13 ways.
\item The suits of the triple, which can be selected in $\binom{4}{3}$ ways.
\item The value of the pair, which can be chosen in 12 ways.
\item The suits of the pair, which can be selected in $\binom{4}{2}$ ways.
\end{enumerate}
%
The example hands correspond to sequences as shown below:
%
\[
\begin{array}{rcrcccccl}
(2, \set{\spa, \clu, \dia}, J, \set{\clu, \dia}) & \leftrightarrow &
    \{ & 2 \spa, & 2 \clu, & 2 \dia, & J \clu, & J \dia & \} \\
(5, \set{\dia, \clu, \hea}, 7, \set{\hea, \clu}) & \leftrightarrow &
    \{ & 5 \dia, & 5 \clu, & 5 \hea, & 7 \hea, & 7 \clu & \}
\end{array}
\]
%
By the Generalized Product Rule, the number of Full Houses is:
%
\[
13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}
\]
%
We're on a roll--- but we're about to hit a speedbump.

\subsection{Hands with Two Pairs}

How many hands have \textit{Two Pairs}; that is, two cards of one
value, two cards of another value, and one card of a third value?
Here are examples:
%
\[
\begin{array}{rcccccl}
\{ & 3 \dia, & 3 \spa, & Q \dia, & Q \hea, & A \clu & \} \\
\{ & 9 \hea, & 9 \dia, & 5 \hea, & 5 \clu, & K \spa & \}
\end{array}
\]
%
Each hand with Two Pairs is described by a sequence consisting of:
%
\begin{enumerate}
\item The value of the first pair, which can be chosen in 13 ways.
\item The suits of the first pair, which can be selected $\binom{4}{2}$ ways.
\item The value of the second pair, which can be chosen in 12 ways.
\item The suits of the second pair, which can be selected in $\binom{4}{2}$ ways.
\item The value of the extra card, which can be chosen in 11 ways.
\item The suit of the extra card, which can be selected in $\binom{4}{1} = 4$ ways.
\end{enumerate}
%
Thus, it might appear that the number of hands with Two Pairs is:
%
\[
13 \cdot \binom{4}{2} \cdot 12 \cdot \binom{4}{2} \cdot 11 \cdot 4
\]
%
Wrong answer!  The problem is that there is \textit{not} a bijection
from such sequences to hands with Two Pairs.  This is actually a
2-to-1 mapping.  For example, here are the pairs of sequences that map
to the hands given above:
%
\[
\begin{array}{rcrcccccl}
(3, \set{\dia, \spa}, Q, \set{\dia, \hea}, A, \clu) & \searrow \\
 & & \{ & 3 \dia, & 3 \spa, & Q \dia, & Q \hea, & A \clu & \} \\
(Q, \set{\dia, \hea}, 3, \set{\dia, \spa}, A, \clu) & \nearrow \\
\\
(9, \set{\hea, \dia}, 5, \set{\hea, \clu}, K, \spa) & \searrow \\
& & \{ & 9 \hea, & 9 \dia, & 5 \hea, & 5 \clu, & K \spa & \} \\
(5, \set{\hea, \clu}, 9, \set{\hea, \dia}, K, \spa) & \nearrow \\
\end{array}
\]
%
The problem is that nothing distinguishes the first pair from the
second.  A pair of 5's and a pair of 9's is the same as a pair of 9's
and a pair of 5's.  We avoided this difficulty in counting Full Houses
because, for example, a pair of 6's and a triple of kings is different
from a pair of kings and a triple of 6's.

We ran into precisely this difficulty last time, when we went from
counting arrangements of \textit{different} pieces on a chessboard to
counting arrangements of two \textit{identical} rooks.  The solution
then was to apply the Division Rule, and we can do the same here.  In
this case, the Division rule says there are twice as many sequences
and hands, so the number of hands with Two Pairs is actually:
%
\[
\frac{13 \cdot \binom{4}{2} \cdot 12 \cdot \binom{4}{2} \cdot 11 \cdot 4}{2}
\]

\subsubsection*{Another Approach}

The preceding example was disturbing!  One could easily overlook the
fact that the mapping was 2-to-1 on an exam, fail the course, and turn
to a life of crime.  You can make the world a safer place in two ways:

\begin{enumerate}

\item Whenever you use a mapping $f : A \to B$ to translate one
counting problem to another, check the number elements in $A$ that are
mapped to each element in $B$.  This determines the size of $A$
relative to $B$.  You can then apply the Division Rule with the
appropriate correction factor.

\item As an extra check, try solving the same problem in a different
way.  Multiple approaches are often available--- and all had better
give the same answer!  (Sometimes different approaches give answers
that \textit{look} different, but turn out to be the same after some
algebra.)

\end{enumerate}

We already used the first method; let's try the second.  There is a
bijection between hands with two pairs and sequences that specify:
%
\begin{enumerate}
\item The values of the two pairs, which can be chosen in $\binom{13}{2}$ ways.
\item The suits of the lower-value pair, which can be selected in $\binom{4}{2}$ ways.
\item The suits of the higher-value pair, which can be selected in $\binom{4}{2}$ ways.
\item The value of the extra card, which can be chosen in $11$ ways.
\item The suit of the extra card, which can be selected in $\binom{4}{1} = 4$ ways.
\end{enumerate}
%
For example, the following sequences and hands correspond:
%
\[
\begin{array}{rcrcccccl}
(\set{3, Q}, \set{\dia, \spa}, \set{\dia, \hea}, A, \clu) & \leftrightarrow &
  \{ & 3 \dia, & 3 \spa, & Q \dia, & Q \hea, & A \clu & \} \\
(\set{9, 5}, \set{\hea, \clu}, \set{\hea, \dia}, K, \spa) & \leftrightarrow &
  \{ & 9 \hea, & 9 \dia, & 5 \hea, & 5 \clu, & K \spa & \}
\end{array}
\]
%
Thus, the number of hands with two pairs is:
%
\[
\binom{13}{2} \cdot \binom{4}{2} \cdot \binom{4}{2} \cdot 11 \cdot 4
\]
%
This is the same answer we got before, though in a slightly different
form.

\subsection{Hands with Every Suit}

How many hands contain at least one card from every suit?  Here is an
example of such a hand:
%
\[
\begin{array}{rcccccl}
\{ & 7 \dia, & K \clu, & 3 \dia, & A \hea, & 2 \spa & \}
\end{array}
\]
%
Each such hand is described by a sequence that specifies:

\begin{enumerate}

\item The values of the diamond, the club, the heart, and the spade,
which can be selected in $13 \cdot 13 \cdot 13 \cdot 13 = 13^4$ ways.

\item The suit of the extra card, which can be selected in 4 ways.

\item The value of the extra card, which can be selected in 12 ways.

\end{enumerate}

For example, the hand above is described by the sequence:
%
\[
\begin{array}{rcrcccccl}
(7, K, A, 2, \dia, 3) & \leftrightarrow &
    \{ & 7 \dia, & K \clu, & A \hea, & 2 \spa, & 3 \dia & \}
\end{array}
\]
%
Are there other sequences that correspond to the same hand?  There is
one more!  We could equally well regard either the $3 \dia$ or the $7
\dia$ as the extra card, so this is actually a 2-to-1 mapping.  Here
are the two sequences corresponding to the example hand:
%
\[
\begin{array}{rcrcccccl}
(7, K, A, 2, \dia, 3) & \searrow & \\
 && \{ & 7 \dia, & K \clu, & A \hea, & 2 \spa, & 3 \dia & \} \\
(3, K, A, 2, \dia, 7) & \nearrow &
\end{array}
\]
%
Therefore, the number of hands with every suit is:
%
\[
\frac{13^4 \cdot 4 \cdot 12}{2}
\]

\section{Binomial Theorem}

Counting gives insight into one of the basic theorems of algebra.  A
\term{binomial} is a sum of two terms, such as $a + b$.  Now consider its
4th power, $(a + b)^4$.

If we multiply out this 4th power expression completely, we get
\[\begin{array}{rccccccccc}
(a + b)^4
   & = &    & aaaa & + & aaab & + & aaba & + & aabb \\
   &   &  + & abaa & + & abab & + & abba & + & abbb \\
   &   &  + & baaa & + & baab & + & baba & + & babb \\
   &   &  + & bbaa & + & bbab & + & bbba & + & bbbb
\end{array}\]
Notice that there is one term for every sequence of $a$'s and $b$'s.  So
there are $2^4$ terms, and the number of terms with $k$ copies of $b$ and
$n - k$ copies of $a$ is:
\[
\frac{n!}{k!\ (n-k)!} = \binom{n}{k}
\]
by the Bookkeeper Rule.  Now let's group equivalent terms, such as
$aaab = aaba = abaa = baaa$.  Then the coefficient of $a^{n-k} b^k$ is
$\binom{n}{k}$.  So for $n = 4$, this means:
\[
(a + b)^4 =
    \binom{4}{0} \cdot a^4 b^0 + 
    \binom{4}{1} \cdot a^3 b^1 + 
    \binom{4}{2} \cdot a^2 b^2 + 
    \binom{4}{3} \cdot a^1 b^3 + 
    \binom{4}{4} \cdot a^0 b^4
\]
In general, this reasoning gives the Binomial Theorem:

\begin{theorem}[Binomial Theorem]
For all $n \in \mathbb{N}$ and $a, b \in \mathbb{R}$:
%
\[
(a + b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k
\]
\end{theorem}

The expression $\dbinom{n}{k}$ is often called a ``binomial
coefficient'' in honor of its appearance here.

This reasoning about binomials extends nicely to \term{multinomials},
which are sums of two or more terms.  For example, suppose we wanted
the coefficient of
%
\[
b o^2 k^2 e^3 p r
\]
%
in the expansion of $(b + o + k + e + p + r)^{10}$.  Each term in this
expansion is a product of 10 variables where each variable is one of
$b$, $o$, $k$, $e$, $p$, or $r$.  Now, the coefficient of $b o^2 k^2
e^3 p r$ is the number of those terms with exactly 1 $b$, 2 $o$'s, 2
$k$'s, 3 $e$'s, 1 $p$, and 1 $r$.  And the number of such terms is
precisely the number of rearrangments of the word BOOKKEEPER:
\[
\binom{10}{1,2,2,3,1,1} = \frac{10!}{1!\ 2!\ 2!\ 3!\ 1!\ 1!}.
\]
The expression on the left is called a ``multinomial coefficient.''  This
reasoning extends to a general theorem:

\begin{theorem}[Multinomial Theorem]
For all $n \in \mathbb{N}$ and $z_1, \ldots z_m \in \mathbb{R}$:
\[
(z_1 + z_2 + \cdots + z_m)^n =
   \sum_{\substack{k_1, \ldots, k_m \in \mathbb{N} \\
                   k_1 + \cdots + k_m = n}}
   \binom{n}{k_1, k_2, \ldots, k_m} z_1^{k_1} z_2^{k_2} \cdots z_m^{k_m} 
\]
\end{theorem}
You'll be better off remembering the reasoning behind the Multinomial
Theorem rather than this ugly formal statement.


\section{Combinatorial Proof}

Suppose you have $n$ different T-shirts only want to keep $k$.  You
could equally well select the $k$ shirts you want to keep or select
the complementary set of $n - k$ shirts you want to throw out.  Thus,
the number of ways to select $k$ shirts from among $n$ must be equal
to the number of ways to select $n - k$ shirts from among $n$.
Therefore:
%
\[
\binom{n}{k} = \binom{n}{n-k}
\]
%
This is easy to prove algebraically, since both sides are equal to:
%
\[
\frac{n!}{k!\ (n-k)!}
\]
%
But we didn't really have to resort to algebra; we just used counting
principles.

Hmm.

\subsection{Boxing}

Ishan, famed 6.042 TA, has decided to try out for the US Olympic
boxing team.  After all, he's watched all of the \textit{Rocky} movies
and spent hours in front of a mirror sneering, ``Yo, you wanna piece
a' \textit{me}?!''  Ishan figures that $n$ people (including himself)
are competing for spots on the team and only $k$ will be selected.  As
part of maneuvering for a spot on the team, he need to work out how
many different teams are possible.  There are two cases to consider:

\begin{itemize}

\item Ishan \textit{is} selected for the team, and his $k - 1$
teammates are selected from among the other $n - 1$ competitors.  The
number of different teams that be formed in this way is:
%
\[
\binom{n-1}{k-1}
\]

\item Ishan is \textit{not} selected for the team, and all $k$ team
members are selected from among the other $n - 1$ competitors.  The
number of teams that can be formed this way is:
%
\[
\binom{n - 1}{k}
\]

\end{itemize}

All teams of the first type contain Ishan, and no team of the second
type does; therefore, the two sets of teams are disjoint.  Thus, by
the Sum Rule, the total number of possible Olympic boxing teams is:
%
\[
\binom{n-1}{k-1} + \binom{n - 1}{k}
\]

Sayan, equally-famed 6.042 TA, thinks Ishan isn't so tough and so
he might as well try out also.  He reasons that $n$ people (including
himself) are trying out for $k$ spots.  Thus, the number of ways to
select the team is simply:
%
\[
\binom{n}{k}
\]

Sayan and Ishan each correctly counted the number of possible boxing
teams; thus, their answers must be equal.  So we know:
%
\[
\binom{n-1}{k-1} + \binom{n - 1}{k} = \binom{n}{k}
\]
%
This is called \term{Pascal's Identity}.  And we proved it
\textit{without any algebra!}  Instead, we relied purely on counting
techniques.

\subsection{Combinatorial Proof}

A \term{combinatorial proof} is an argument that establishes an
algebraic fact by relying on counting principles.  Many such proofs
follow the same basic outline:
%
\begin{enumerate}

\item Define a set $S$.

\item Show that $\card{S} = n$ by counting one way.

\item Show that $\card{S} = m$ by counting another way.

\item Conclude that $n = m$.

\end{enumerate}
%
In the preceding example, $S$ was the set of all possible Olympic boxing
teams.  Ishan computed $\card{S} = \binom{n-1}{k-1} + \binom{n-1}{k}$ by
counting one way, and Sayan computed $\card{S} = \binom{n}{k}$ by counting
another.  Equating these two expressions gave Pascal's Identity.

More typically, the set $S$ is defined in terms of simple sequences or
sets rather than an elaborate story.  Here is less-colorful example of
a combinatorial argument.

\begin{theorem}
\label{th:comb-ex}
\[
\sum_{r=0}^n \binom{n}{r} \binom{2n}{n-r} = \binom{3n}{n}
\]
\end{theorem}

\begin{proof}
We give a combinatorial proof.  Let $S$ be all $n$-card hands that can
be dealt from a deck containing $n$ red cards (numbered $1, \ldots,
n$) and $2n$ black cards (numbered $1, \ldots, 2n$).  First, note that
every $3n$-element set has
%
\[
\card{S} = \binom{3n}{n}
\]
%
$n$-element subsets.

From another perspective, the number of hands with exactly $r$ red
cards is
%
\[
\binom{n}{r} \binom{2n}{n - r}
\]
%
since there are $\binom{n}{r}$ ways to choose the $r$ red cards and
$\binom{2n}{n - r}$ ways to choose the $n - r$ black cards.  Since the
number of red cards can be anywhere from 0 to $n$, the total number of
$n$-card hands is:
%
\[
\card{S} = \sum_{r=0}^n \binom{n}{r} \binom{2n}{n-r}
\]
%
Equating these two expressions for $\card{S}$ proves the theorem.
\end{proof}

Combinatorial proofs are almost magical.  Theorem~\ref{th:comb-ex}
looks pretty scary, but we proved it without any algebraic
manipulations at all.  The key to constructing a combinatorial proof
is choosing the set $S$ properly, which can be tricky.  Generally, the
simpler side of the equation should provide some guidance.  For
example, the right side of Theorem~\ref{th:comb-ex} is
$\binom{3n}{n}$, which suggests choosing $S$ to be all $n$-element
subsets of some $3n$-element set.
\end{document}

