\documentclass[11pt]{article}
\usepackage{amsmath}
%\usepackage{graphics}
\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\textbf{Solution}: \quad #1}

\newcommand{\numb}[1]{\#\mbox{#1}}

\begin{document}

\tutn{9}{4/9/99}{April 8, 1999}

\section{Poker hands}
A poker hand consists of five cards from a standard 52 card deck.

\subsection{Hands with a Full House}
A \emph{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 \ \mbox{J} \clubsuit \ \mbox{J} \heartsuit
\ \mbox{J} \diamondsuit
\]
is a full house because there are three jacks and two sevens.

How many different full houses 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 $\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 $\binom{4}{2} = 6$ ways.

So the total number of full house hands is therefore $13 \cdot 4 \cdot 12
\cdot 6 = 3744$.  A full house is worth less in poker than four-of-a-kind
because it is six times more common than four-of-a-kind---we saw in
lecture that the number of hands with a four-of-a-kind was 624.

\subsection{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 $\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 $\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.  Alltogether 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 can {\em not} be any one of the 48 remaining cards; in
particular, it can not have the same value as a card already selected.
(Otherwise, there would be a 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:

\[
\numb{hands with two pairs} = \frac{13 \cdot 6 \cdot 12 \cdot 6 \cdot 44}{2}
       =  123,552
\]

Why did this factor of 2 arise in counting pairs, but not in counting
full houses?  The reason is that pairs are interchangable, 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 very 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 $\binom{13}{2}$.  We can choose suits for
each pair in $\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!


\section{Stars and Bars}
A shelf holds 12 books in a row.  How many ways are there to choose 
five books so that no two adjacent books are chosen?

There are five bars (chosen books), and therefore there are six slots
where the seven stars (non-chosen books) can fit---one place before the
first bar, five places between adjacent bars, and one place after the
fifth bar.  Each of the second through fifth of these slots must have at
least one star in it, so that adjacent books are not chosen.  Once we have
placed these four stars, there are three stars left to be placed anywhere
in the six slots.  We know from lecture that the number of ways to do this
is $\binom{6+3-1}{3}=\binom{8}{3}=56$.


\section{Paths and Matching Parentheses}
In lecture we described the \emph{well-matched} strings of parentheses in
which left and right parentheses properly match up in pairs.  These are
the strings of parentheses one could obtain by erasing all the symbols
except parentheses from a parenthesized arithmetic expression.
For example, erasing everything but parentheses from the arithmetic
expression
\[
((1+2)*((-(3*4))+(5 + 6))* (7-9))
\]
yields the well-matched string:
\[
\texttt{(()((())())())}
\]


On the other hand, no string that begins with a right parenthesis or ends
with a left parenthesis can be well-matched; neither can any proper prefix
of a well-matched string be well-matched.

We want to compute the number, $S_n$, of such well-matched parenthesis
strings of length $2n$.  Counting them turns out to be useful because such
strings correspond to trees---which \emph{are} important in many
applications\footnote{Remember that we described in lecture bijections between
\begin{itemize}
\item the well-matched strings of $2n$ parentheses,
\item the ordered, rooted trees with $n$ vertices,
\item the ordered, rooted, complete binary trees with $2n-1$ vertices.
\end{itemize}}.

Now it's easy to check that $S_1=1$, $S_2=1$, $S_3=2$.

\textbf{Class exercise}:  What is $S_4$?

\solution{With a little case analysis, we can conclude that the
well-matched strings of 8 parentheses are precisely:
\[\texttt{(()(())),\ (()()()),\ ((())()),\ (((()))),\ ((()()))},\]
so $S_4=5$.}

In order to count the number of well-matched strings, we note a simple,
efficient procedure---interesting in its own right---to determine if a
string of parentheses is well-matched: starting with zero, read the string
left-to-right, adding one for each left parenthesis and subtracting one
for each right parenthesis.  It's easy to see that any such count uniquely
determines a parenthesized string.  But what makes the count so valuable
is that a string is well-matched \emph{iff its count stays positive
exactly until the last parenthesis}.  For example, for the well-matched
string \texttt{(()((())())())} above, the successive values of the count
are:
\[0,1, 2, 1, 2,3,4,3,2,3,2,3,1,2,1,0.\]

A geometric way to describe the count values for any string of parentheses
is to consider \emph{count-paths} in the plane from an integer lattice
point $(x_1,y_1)$ to the point $(x_2,y_2)$.  Each step in a count-path is
at a $\pm 45$ degree angle, increasing the x-coordinate by 1 and the
y-coordinate by $\pm 1$.  For example, a count-path might start at $(1,1)$
and make seven steps to the successive points $(2,0)$, $(3,-1)$, $(4,0)$,
$(5,1)$, $(6,2)$, $(7,1)$, $(8,0)$ as in Figure~\ref{fig:path}.

\begin{figure}
\begin{center}
\begin{picture}(345,195)(-45,-45)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em A count-path from $(1,1)$ to $(8,0)$.}

\label{fig:path}

\end{figure}

So the sequence of count-values of a well-matched string of $2n$
parentheses is represented geometrically as a count-path from $(0,0)$ to
$(2n,0)$ \emph{which only touches the x-axis at its endpoints}.  In a
team problem, you will work out an elegant way to count the number of such
count-paths.

\section{Team Problems}
\begin{problems}

\problem
How many poker hands are there with no pairs?

\solution{
{\em First count. } 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 can not 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'', $\ldots$ are a
warning signal that we may be inadvertantly 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; that is, each hand is counted $5! = 120$ times!  We can
correct our initial answer by applying the Division Rule.  This gives:

\[
\numb{hands with no pairs}
 =  \frac{52 \cdot 48 \cdot 44 \cdot 40 \cdot 36}{120}
 =  1,317,888
\]

{\em Second count. } 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 possibilites.  Then we could choose
one of the four suits for each of the five cards.  This gives:

\[
\numb{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
\]

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 even have one
pair!
}

\problem

\bparts

\ppart

In lecture we demonstrated how to ``guess'' the fifth card in a poker hand
when a collaborator reveals the other four cards.  Describe a method for
guessing two hidden cards in a hand of nine cards, when your collaborator
reveals the other seven cards.

\solution{There must be $\ceil{9/4} = 3$ cards with the same suit, so our
collaborator chooses to hide two of them and then use the third one as the
first card to be revealed.  So this first revealed card fixes the suit of
the two hidden cards; it will also be used as the origin for the offset
position of the first hidden card.  This first hidden card will in turn be
used as the origin for the offset of the other hidden card.  There are six
cards to code the two offset positions.  These suffice to code two offsets
of size from one to six.  That is, our collaborator can choose one of the
$3! = 6$ orders in which to reveal the first three cards and thereby tell
us the offset position of the first hidden card.  Our collaborator can
then choose the order of the final three cards to describe the offset
position of the second hidden card from the first.  Note that the first
revealed card must be chosen so that both offsets are less $\leq 6$; since
the sum of the offsets between successive cars ordered in a cycle from Ace
to King is 13, it is not possible for more than one offset between
successive cards to exceed seven, so this is always possible.}

\ppart Show that there is no procedure for ``guessing'' a hidden card
among four when your collaborator reveals three. \hint Compare the number
of hands to the number of revealed three-card sequences.
~
\solution{
There are $\binom{52}{4}$ possible four-card hands.  There are $P(52,3)$
three-card sequences that can ever be revealed.  Since
\[
\frac{\binom{52}{4}}{P(52,3)}=
\frac{52\cdot 51\cdot 50 \cdot 49/4!}{52 \cdot 51 \cdot 50} = 49/24 > 1,
\]
there must, by pigeonholing, be two (actually three) hands for which the
collaborator reveals the same three cards.  Therefore the magician cannot
determine the hidden card, since these hands must have different hidden
cards.}

\eparts

\iffalse
\problem

A {\em derangement} is a permutation of $1,2,\dots,n$ where $i$ is not in
the $i^{th}$ position for $1\leq i\leq n$.  Let $D_n$ be the number of
derangements on $n$ elements.  For example, there are $D_n$ ways that $n$
items contributed to a charity auction could be distributed among $n$
contributors so that no one gets the item they contributed.  We claim

\begin{theorem}\label{numderange}
\[
D_n = n! \sum_{k=0}^n \frac{(-1)^k }{k!}
\]
\end{theorem}

\bparts
\ppart Conclude from Theorem~\ref{numderange} that the fraction of
permutations of $1,2,\dots,n$ which are derangements is close to $1/e$.
\hint The Taylor expansion of $e^{-1}$.

\solution{The Taylor expansion of $e^x$ is
\[
e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots
        = \sum_{k=0}^\infty \frac{x^k}{k!}
\]

For $x = -1$, we have
\[
 \frac{1}{e} = e^{-1} = \sum_{k=0}^\infty \frac{(-1)^k }{k!}
\]

This looks very close to our formula for derangements, which is $n!$ times
the first $n+1$ terms in this expansion.  Since the series approached
$1/e$, we csan conclude that $D_n \sim \frac{n!}{e}$.

In fact, with a little more work, we can prove that the number of
derangements always the nearest integer to $\frac{n!}{e}$.  To see this,
consider the difference $\frac{n!}{e} - D_n$.
\begin{eqnarray*}
\frac{n!}{e} - D_n & = & n! \sum_{k=n+1}^\infty \frac{(-1)^k}{k!}\\
     & = & (-1)^{n+1}(\frac{ 1}{n+1} - \frac{1}{(n+1)(n+2)} + \dots + 
  \frac{(-1)^{k+1}}{(n+1)(n+2)\ldots (n+k)} + \dots)
\end{eqnarray*}
So for $n \geq 1$,
\begin{eqnarray*}
\abs{\frac{n!}{e} - D_n} & = & \frac{ 1}{n+1} - \frac{1}{(n+1)(n+2)} + \dots + 
  \frac{(-1)^{k+1}}{(n+1)(n+2) \cdots (n+k)} + \dots\\
& \leq & \frac{1}{2} - \frac{1}{2.3} + \ldots + \frac{(-1)^{k+1}}{(k+1)!} = \frac{1}{e}.
\end{eqnarray*}
The last inequality can be explained by grouping the terms of the summation
into pairs (the first two, next two and so on) and then comparing.  The
difference between $n!/e$ and $D_n$ is at most $1/e < 1/2$, so the number
of derangements must be the integer closest to $n!/e$.}

\ppart Prove Theorem~\ref{numderange}.  \hint Let $A_i$ be the set of
permutations of $1,\ldots,n$ in which $i$ \emph{is} mapped to the $i^{th}$
position.  Use inclusion-exclusion.

\solution{
\begin{proof}
For $i = 1,\ldots,n$, let $A_i$ be the set of permutations of $1,\ldots,n$
in which $i$ is mapped to the $i^{th}$ position.  Then the set of
permutations that are \emph{not} derangements is
\[ A_1 \cup \ldots \cup A_n.\]
Now by inclusion-exclusion, the number of nonderangements is
\[
\card{A_1 \cup \ldots \cup A_n} =  \sum_{k=1}^{n} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k}
\card{\bigcap_{i \in S} A_i}
\]

In order to evaluate the Inclusion-Exclusion formula, we note that for any
set $S \subset \{ 1,\ldots,n\}$ such that $|S|=k$ we have
\[
\card{\bigcap_{i \in S} A_i} = (n-k)!
\]
since a permutation in $\bigcap_{i \in S} A_i$ is a permutation
that fixes the elements of $S$ and permutes in an arbitrary way
the other $n-k$ elements.  There are $(n-k)!$ ways to choose such a
permutation.  Considering that for any $k$ there
are $\binom{n}{ k}$ sets $S$ of size $k$, the sum evaluates to
\begin {eqnarray*}
\sum_{k=1}^n (-1)^{k+1} \binom{n}{k} (n-k)!
& = & \sum_{k=1}^n (-1)^{k+1} \frac{n!}{(n-k)!k!}  (n-k)!\\
& = & \sum_{k=1}^n (-1)^{k+1} \frac {n!}{k!}\\
& = & n! \sum_{k=1}^n \frac{(-1)^{k+1}}{k!}
\end {eqnarray*}
Since this gives us the number of permutations that are
not derangements, by subtracting this value from $n!$
we find the number of derangements:

\begin {eqnarray*}
D_n &= & n! -  n! \sum_{k=1}^n \frac{(-1)^{k+1}}{k!}\\
&= & n!(1 +  \sum_{k=1}^n  \frac{(-1)^{k}}{k!})\\
& = & n! \sum_{k=0}^n \frac{(-1)^{k}}{k!}
\end {eqnarray*}
\end {proof}
}
\eparts
\fi


\problem
\bparts

%Skip the first part in the future -- ARM, April, 1999.

\ppart What are necessary and sufficient conditions on the integer values
of $x_1,y_1,x_2,y_2$ for there to be a count-path---of any kind, not just
one corresponding to a well-matched string---from $(x_1,y_1)$ to
$(x_2,y_2)$?

\solution{$0 \leq \numb{moves} = x_2 - x_1$, i.e. $x_1\leq x_2$.  Also,
$y_2 - y_1 = \numb{up moves} - \numb{down moves}$, so $\abs{y_2 - y_1}
\leq \numb{moves} = x_2 - x_1$.  Also, the parity of $x_1+y_1$ is an
invariant on the path, so another necessary condition is $x_1+y_1 \equiv
x_2 + y_2 \bmod 2$.  It is not hard to verify that the required path can
be constructed whenever the coordinates satisfy these constraints.}

\ppart How many count-paths of any kind are there from $(x_1,y_1)$ to
$(x_2,y_2)$?  Express the answer as a binomial coefficient.

\textbf{Solution}:
\begin{align*}
\numb{moves}
    & = x_2 - x_1 \\
\numb{up moves} - \numb{down moves}
    & = y_2 - y_1 \\
\numb{up moves} + \numb{down moves}
    & = \numb{moves} = x_2 - x_1 \\
\numb{up moves}
    & = \frac{(x_2 + y_2) - (x_1 + y_1)}{2} ::= u \\
\numb{down moves}
    & = \frac{(x_2 - y_2) - (x_1 - y_1)}{2} ::= d \\
\numb{paths}
    & = \binom{u+d}{u} = \binom{u+d}{d}
\end{align*}

\ppart For $y_1,y_2 > 0$, show that the number count-paths from
$(x_1,y_1)$ to $(x_2,y_2)$ \emph{which touch or cross the x-axis} is equal
to the number of count-paths of any kind from $(x_1,-y_1)$ to $(x_2,y_2)$.

\textbf{Solution:} See Figure~\ref{fig:reflect}.

\begin{figure}

\begin{center}
\begin{picture}(345,205)(-45,-55)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\put(30,-30){\circle*{3}}
\put(32,-32){\makebox(0,0)[tl]{$(x_1, -y_1)$}}

\dottedline{2}(30,-30)(60,0)

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em Reflection of the initial part of a path.}

\label{fig:reflect}

\end{figure}

\ppart Conclude that the number of well-matched strings of $2n$ parentheses
is
\[\frac{1}{n} \binom{2n-2}{n-1}.\]
This number is called the $n-1$st \emph{Catalan number}.

\textbf{Solution:}

\begin{equation*}
\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \bigr)
        = \binom{2n-2}{n-1}
\end{equation*}
because
\begin{align*}
    u   &= \frac{2n-2}{2}     = n-1, \\
    d   &= \frac{(2n-2)-0}{2} = n-1.
\end{align*}

\begin{align*}
\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ touching
    x-axis}\bigr)
    &= \numb{paths}\bigl( (1, -1) \to (2n-1, 1) \bigr) \\
    &= \binom{2n-2}{n} = \binom{2n-2}{n-2}
\end{align*}
because
\begin{align*}
    u &= \frac{2n - 0}{2} = n\\
    d &= \frac{(2n - 2) - 2}{2} = n - 2
\end{align*}

\begin{align*}
\lefteqn{\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ above x-axis}\bigr)} \qquad&\\
    &= \numb{paths}\bigl( (1, 1) \to (2n-1, 1) \bigr)
        - \numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ touching} \bigr)\\
    &= \binom{2n-2}{n-1} - \binom{2n-2}{n}\\
    &= \binom{2n-2}{n-1}
        - \frac{(2n-2)!}{n! \, (n-2)!}\\
    &= \binom{2n-2}{n-1}
        - \frac{(2n-2)!(n-1)}{n(n-1)! \, (n-1)!}\\
    &= \binom{2n-2}{n-1} - \frac{n-1}{n}\binom{2n-2}{n-1}\\
    &= \binom{2n-2}{n-1} \cdot \frac{1}{n}
\end{align*}

\eparts

\end{problems}

\end{document}
