\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions -- Problem Set 2}
\centerline{February 14, 2005}
\bigskip
\noindent
Chapter 3/7.  a)  To count the full houses, there are
13 choices for the rank of the three of a kind, and 
${4\choose 3}$ choices for the suits of the three cards.
Similarly, once the three of a kind are chosen,
there are 12 choices for the rank of the pair, and 
${4\choose 2}$ choices for the suits in the pair.  By the
multiplication rule, this gives
$$13\cdot {4\choose 3} \cdot 12 \cdot {4\choose 2}$$
of this type of hand.
\bigskip
\noindent
b)  As described on the course homepage, a straight
can be either ace-low, or ace-high.  This means that
there are 10 possible sets of ranks for straights.
There are 4 possible suits for each of the 5 cards,
so the total number of ``straight'' hands is 
$10\cdot 4^5$.
But we want to leave out the straight and royal flushes
here.  Those are the straights in which all cards
have the same suit, so there are $10\cdot 4$ of them 
leaving a total of 
$$10\cdot 4^5 - 10\cdot 4$$
actual straights.
\bigskip
\noindent
c)  A flush is composed of five cards of the same suit,
but that is not also a straight.  This means the ranks must be distinct,
so there are ${13\choose 5}$ combinations of ranks, 
and $4$ possible suits.  Leaving out the straight and
royal flushes, this leaves
$${13\choose 5}\cdot 4 - 10\cdot 4$$
flushes.
\bigskip
\noindent
d)  A straight flush is a flush where all cards are
from the same suit, but the ranks are not 
$10,J,Q,K,A$ (i.e. not a royal flush).  There
are $10\cdot 4 - 4 = 9\cdot 4 = 36$ of these.
\bigskip
\noindent
e)  There are two distinct ranks for the pairs, so ${13\choose 2}$
different possible combinations of ranks and 
${4\choose 2}$ combinations of suits for each of the pairs.  
Then, the last (fifth) card can be any one of the 44 cards
not of the ranks appearing in the pairs.  This gives
$${13\choose 2}{4\choose 2}{4\choose 2}\cdot 44$$
two-pair hands.
\bigskip
\noindent
There are 13 possible ranks for the pair and 
${4\choose 2}$ combinations of suits in the pair.
The other three cards must come from 3 different
ranks that are also different from the rank of 
the pair.  Each of those cards can be from 
any of the four suits.  This means there are
${12\choose 3}\cdot 4^3$ ways to chose the three
cards not in the pair, and 
$$13\cdot {4\choose 2} \cdot {12\choose 3}\cdot 4^3$$
total hands of this type.
\bigskip
\noindent
{\it Note:} The most common mistakes on this question involved
counting the hands in parts e and f multiple times.
For instance if your answer to e was
$$13\cdot 12\cdot {4\choose 2}{4\choose 2}\cdot 44$$
because you thought the two ranks of the pairs could
be chosen in $13\cdot 12$ ways, 
then you're counting every two-pair hand {\it twice}
(once for each ordering of the 2 ranks).  Similarly
in f, you need to take ${12\choose 3}$ (or divide
by $3!=6$) to account for the fact that the three
ranks of the single cards can come in any order).
\bigskip
\noindent
Chapter 3/28. a) Each route from home to the office corresponds
to an ordered string of $9$ E's and $8$ N's giving the directions 
of which way to turn at the intersections.  (For example the
string `E,E,E,E,E,E,E,E,E,N,N,N,N,N,N,N,N' would correspond
to the route that goes directly east for 9 blocks, then north
for 8 blocks, along the bottom and right edges of the rectangle 
in the figure accompanying the problem.)  There are 
$${17! \over 9!8!} = {17\choose 9}$$
of these ``direction strings''.  (Note: This is 
the same as counting
permutations of the multiset $\{9\cdot E, 8\cdot N\}$, 
{\it or} counting the combinations of locations where the E's can occur.)

\bigskip
\noindent
b)  The block that is under water is the eastward block 
4 blocks east and 3 blocks north of home.  To count the number
of routes avoiding that block, we will use the Subtraction Rule.
The number of routes that {\it do} use that block is the number
of routes from home to point A to the figure below, then
from A to B along the flooded block, then from B to the office.
By the same reasoning as in part a, there are
${7\choose 4}$ routes from home to point A, and 
${9\choose 4}$ routes from point B to the office. 
\vglue 1.5truein
\noindent
The total
number of routes from home to the office using the block
from A to B comes from the Multiplication Rule. (Each route
from home to A can be combined with each of the routes from 
B to the office):  ${7\choose 4}\cdot {9\choose 4}$.  Then,
the number of routes {\it not} using the flooded block is
$${17\choose 9} - {7\choose 4}{9\choose 4}.$$
\bigskip
\noindent
Chapter 3/48.  First method (the ``direct way''):  We can partition the collection
of permutations according to how many B's actually occur.
This is some $j$ with $0\le j \le n$.  If there are exactly
$j$ B's, then we apply the formula for permutations of a multiset
and obtain ${m + j \choose j}$.  By the Addition Rule, the 
total number is 
$$\sum_{j=0}^n {m + j \choose j}\leqno(1)$$
Now the rest of the problem is to show that that sum of binomial
coefficients is equal to the single term given in the problem.
In other words, we want to show that 
$$\sum_{j=0}^n {m + j \choose j} = {m+n+1\choose m+1} = {m+n+1\choose n}$$
(where the last equality comes from the result of problem 16).  
We can do that by using the Pascal's Triangle identity repeatedly.
First note that
$${m+n+1\choose n} = {m+n\choose n} + {m+n\choose n-1}$$
The first term on the right is one of the terms in the sum (1), so
we're ``looking good!''.  The other term can be broken down into 
a sum by Pascal's triangle again:
$${m+n+1\choose n} = {m+n\choose n} + {m+n-1\choose n-1} + {m+n-1\choose n-2}.$$
We repeat the same argument $n+1$ times in all to get
$${m+n+1\choose n} = \sum_{j=0}^n {m+j\choose j},$$
which is what we wanted to show.

\bigskip
\noindent
Second method (the ``clever way''):  Given any permutation of 
$m$ A's and at most $n$ B's, place a ``divider'' at the end of 
the ordered list, then append enough B's at the right to make $n$ 
B's in all.  For example,
with $m = 3$ and $n = 5$, and the permutation of 3 A's and 2 B's
given by $ABAAB$ we place the divider $|$ at the end, then add
three more B's to make $ABAAB|BBB$.   What we have is then 
a string of $m + n + 1$ characters in all, in which $m+1$ locations
are either A's or the divider.  Conversely, if we 
\medskip
\item{$\bullet$} start with 
a ``blank'' row of $m+n+1$ spaces, 
\item{$\bullet$} select any $m+1$ locations
out of the $m+n+1$,
\item{$\bullet$} fill those in with $m$ A's and a divider
in the rightmost position among the $m+1$, then
\item{$\bullet$} fill in the rest of the locations with
B's, 
\medskip
\noindent
then {\it the part to the left of the divider} will be a permutation
of $m$ A's and at most $n$ B's.  For example, 
placing $m=3$ A's and a divider in 9 slots as follows (with
${}_\sqcup$ indicating a blank space),
$A{}_\sqcup {}_\sqcup A {}_\sqcup A {}_\sqcup | {}_\sqcup$
then the locations of the B's are completely determined:
$ABBABAB|B$ and we taking the part to the left of the divider
we have $ABBABAB$, a permutation of $3$ A's and $4 \le 5$ B's.  
It is not difficult to see that the permutations we want to count
are in one-to-one correspondence with the possible placements
of the A's and the divider.  Since the divider always comes 
to the right of the last A, there are 
$${m + n + 1\choose m+1}$$
ways to place the A's and the divider.  (If you find this
proof pretty neat, then you're a combinatorialist at heart!
Otherwise, there's still hope, of course!)

\bye
