\documentclass[12pt,twoside]{article}
\usepackage{light}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{document}

\lecture{Counting III}{November 2, 2004}

Today we'll briefly review some facts you dervied in recitation on
Friday and then turn to some applications of counting.

\section{The Bookkeeper Rule}

In recitation you learned 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 is a special case of an exceptionally useful counting principle.

\begin{mathrule}[Bookkeeper Rule]
The number of sequences with $n_1$ copies of $l_1$, $n_2$ copies of
$l_2$, \ldots, and $n_k$ copies of $l_k$ is
%
\[
\frac{(n_1 + n_2 + \ldots + n_k)!}{n_1!\ n_2!\ \ldots\ n_k!}
\]
%
provided $l_1, \ldots, l_k$ are distinct.
\end{mathrule}

Let's review some applications and implications of the Bookkeeper Rule.

\subsection{20-Mile Walks}

I'm planning a 20 miles 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}
\]

\subsection{Bit Sequences}

How many $n$-bit sequences contain exactly $k$ ones?

Each such sequence also contains $n - k$ zeroes, so there are
%
\[
\frac{n!}{k!\ (n-k)!}
\]
%
by the Bookkeeper Rule.

\subsection{\textit{k}-element Subsets of an \textit{n}-element Set}

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}

There is a natural bijection between $k$-element subsets of an
$n$-element set and $n$-bit sequences with exactly $k$ ones.  For
example, here is a 3-element subset of $\set{x_1, x_2, \ldots, x_8}$
and the associated 8-bit sequence with exactly 3 ones:
%
\[
\begin{array}{rccccccccl}
\{ & x_1, &    &    & x_4, & x_5  &    &    &   & \} \\
(  &   1, & 0, & 0, &   1, &   1, & 0, & 0, & 0 & )
\end{array}
\]
%
Therefore, the answer to this problem is the same as the answer to the
earlier question about bit sequences.
%
\begin{mathrule}[Subset Rule]
\label{rule:subset}
The number of $k$-element subsets of an $n$-element set is:
%
\[
\frac{n!}{k!\ (n-k)!} = \binom{n}{k}
\]
\end{mathrule}
%
The factorial expression in the Subset Rule comes up so often that
there is a shorthand, $\binom{n}{k}$.  This is read ``$n$ choose $k$''
since it denotes the number of ways to choose $k$ items from among
$n$.  We can immediately knock off all three questions above using the
Sum Rule:

\begin{itemize}

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

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

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

\end{itemize}

The $k$-element subsets of an $n$-element set are sometimes called
\term{$k$-combinations}.  There are a great many similar-sounding
terms: permutations, $r$-permutations, permutations with repetition,
combinations with repetition, permutations with indistinguishable
objects, and so on.  For example, the Bookkeeper rule is elsewhere
called the ``formula for permutations with indistinguishable
objects''.  We won't drag you through all this terminology other than
to say that, broadly speaking, all the terms mentioning
\textit{permutations} concern sequences and all terms mentioning
\textit{combinations} concern subsets.

\subsection{An Alternative Derivation}

Let's derive the Subset Rule another way to gain an alternative
perspective.  The number of \textit{sequences} consisting of $k$
distinct elements drawn from an $n$-element set is
%
\[
n \cdot (n-1) \cdot (n-2) \cdots (n - k + 1) = \frac{n!}{(n-k)!}
\]
%
by the Generalized Product Rule.  Now suppose we map each sequence to
the set of elements it contains.  For example:
%
\[
(x_1, x_2, x_3) \qquad \to \qquad \set{x_1, x_2, x_3}
\]
%
This is a $k!$-to-1 mapping since each $k$-element set is mapped to by
all of its $k!$ permutations.  Thus, by the Quotient Rule, the number
of $k$-element subsets of an $n$-element set is:
%
\[
\frac{n!}{k!\ (n-k)!} = \binom{n}{k}
\]

\subsection{Word of Caution}

Someday you might refer to 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 just
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???}''

\section{Binomial Theorem}

Counting gives insight into one of the basic theorems of algebra.  A
\textit{binomial} is a sum of two terms, such as $a + b$.  Now let's
consider a postive, integral power of a binomial:
%
\[
(a + b)^n
\]
%
Suppose we multiply out this expression completely for, say, $n = 4$:
%
\begin{align*}
(a + b)^4
& = aaaa + aaab + aaba + aabb \\
& \quad + abaa + abab + abba + abbb \\
& \quad + baaa + baab + baba + babb \\
& \quad + bbaa + bbab + bbba + bbbb
\end{align*}
%
Notice that there is one term for every sequence of $a$'s and $b$'s.
Therefore, 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}

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

\iffalse % not enough time!
\subsection{Multinomials}

Our reasoning about binomials extends nicely.  For example, suppose we
have a positive, integral power of a \textit{trinomial}:
%
\[
(a + b + c)^n
\]
%
Multiplying out, we get one term for every length-$n$ sequence of
$a$'s, $b$'s, and $c$'s.  For example:
%
\begin{align*}
(a + b + c)^2 & = aa + ab + ac + ba + bb + bc + ca + cb + cc
\end{align*}
%
Now let's group equivalent terms as before.  Then the coefficient of
$a^i b^j c^k$ (where $i + j + k = n$) is equal to the number of
sequences with exactly $i$ copies of $a$, $j$ copies of $b$ and $k$
copies of $c$.  The number of such sequences is
%
\[
\frac{n!}{i!\ j!\ k!} = \binom{n}{i, j, k}
\]
%
by the Bookkeeper Rule.  The expression above on the left is sometimes
called a ``multinomial coefficient''.  And the expression on the right
is a shorthand.  Generalizing this reasoning to $m$ variables gives
the Multinomial Theorem:

\begin{theorem}[Multinomial Theorem]
For all $n \in \mathbb{N}$ and $z_1, \ldots z_m \in \mathbb{R}$:
%
\[
(z_1 + z_2 + \ldots + z_m)^n =
   \sum_{\substack{k_1, \ldots, k_m \in \mathbb{N} \\
                   k_1 + \ldots + k_m = n}}
   \binom{n}{k_1, k_2, \ldots, k_m} z_1^{k_1} z_2^{k_2} \ldots z_m^{k_m} 
\]
\end{theorem}

\noindent It's ugly, but its mother still loves it.
\fi

\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{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 reveals four of them to the
Magician, one at a time.  The Magician concentrates for a short time
and then correctly names the secret, fifth card!

\subsection{The Secret}

The Assistant somehow communicated the secret card to the Magician
just by naming the other four cards.  In particular, the Assistant has
two ways to communicate:

\begin{enumerate}

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

\item The Assistant can choose 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.

\end{enumerate}

\noindent Nevertheless, these two 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}

\noindent For example, $\{ 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 correspoding 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}

\noindent Now let $S$ be an arbitrary set of vertices on the left,
which we're regarding as girls.  There are $120 \size{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 \size{S} / 48 \geq
\size{S}$ different boys.  Thus, the marriage condition is satisfied,
a matching exists by Hall's Theorem, and the trick can be done without
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}

\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
%
\[
\size{X} = \binom{52}{4} = 270,725
\]
%
by the Subset Rule.  On the other hand, we have
%
\[
\size{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!

\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}

Flo, 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}?!''  Flo figures that $n$ people (including himself) are
competing for spots on the team and only $k$ will be selected.  Thus,
there are two cases to consider:

\begin{itemize}

\item Flo 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 Flo is 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 Flo, 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}
\]

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

Claire and Flo each correctly counted the number of possibly 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 $\size{S} = n$ by counting one way.

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

\item Conclude that $n = m$.

\end{enumerate}
%
In the preceding example, $S$ was the set of all possible United
States Olympic boxing teams.  Flo computed $\size{S} =
\binom{n-1}{k-1} + \binom{n-1}{k}$ by counting one way, and Claire
computed $\size{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, invented story.  (You probably realized
this was invention; after all, Flo is a French citizen and thus
wouldn't be \textit{eligible} for the US team.)  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
%
\[
\size{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:
%
\[
\size{S} = \sum_{r=0}^n \binom{n}{r} \binom{2n}{n-r}
\]
%
Equating these two expressions for $\size{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}

