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

%\renewcommand{\coursecopyrightnames}{Eric~Lehman}

%\hidesolutions
%\showsolutions

\begin{document}

%\renewcommand{\readingnote}{}

\renewcommand{\reading}{Sections 4.3 - 4.5 and 6.5 - 6.6 in Rosen, and
a short set of notes, which will be released on Tuesday, Oct. 30.}

\problemset{8}

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

\begin{problem}
In the game of seven-card stud, a hand consists of {\em seven} cards.
Each card has a {\em suit} ($\heartsuit$, $\spadesuit$,
$\diamondsuit$, or $\clubsuit$) and a {\em value} (A, 2, 3, 4, \ldots,
9, 10, J, Q, or K).  For this problem, the value of an ace is just
below the value of a 2.  The terms {\em pair}, {\em three-of-a-kind},
and {\em four-of-a-kind} refer to sets of two, three, and four cards
with the same value.

Solve the counting problems below and briefly explain your answers.
You may leave binomial coefficients and factorials in your solutions.

\bparts

\ppart How many different hands are possible?

\solution{Each hand is a 7-combination of the set of 52 cards.
Therefore, the number of hands is:

\[
\binom{52}{7}
\]
}

\ppart How many hands are there such that all seven cards are in
the same suit?

\solution{We can select the suit in 4 ways.  Then the hand is a
7-combination of the set of 13 cards in that suit.  Therefore, the
number of hands is:

\[
4 \cdot \binom{13}{7}
\]
}

\ppart How many hands are there such that all seven cards are in
the same suit and have consecutive values?

\solution{Again, we can select the suit in 4 ways.  The lowest card
must then be one of $A, 2, 3, \ldots, 7$.  These two things determine
all the remaining cards.  Therefore, the number of hands is:

\[
4 \cdot 7
\]
}

\ppart How many hands contain a four-of-a-kind?

\solution{The value of the four-of-a-kind can be chosen in 13 ways.
Then we must choose 3 more cards from the remaining 48.  Thus, the
number of hands is:

\[
13 \cdot \binom{48}{3}
\]
}

\ppart How many hands contain exactly one pair and no three- or
four-of-a-kind?

\solution{The value of the pair can be chosen in 13 ways.  The suits
of the pair can be chosen in $\binom{4}{2}$ ways.  The values of the
other 5 cards can be chosen in $\binom{12}{5}$ ways, and their suits
can be chosen in $5^4$ ways.  Therefore, the number of hands is:

\[
13 \cdot \binom{4}{2} \cdot \binom{12}{5} \cdot 5^4
\]
}

\ppart How many hands contain two three-of-a-kinds, but no
four-of-a-kind?

\solution{The values of the three-of-a-kinds can be chosen in
$\binom{13}{2}$ ways.  The suits in each three-of-a-kinds can be
chosen in $\binom{4}{3}$ ways.  There are 44 ways to choose the
remaining card.  Therefore, the number of hands is:

\[
\binom{13}{2} \cdot \binom{4}{3}^2 \cdot 44
\]
}

\eparts

\end{problem}

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

\begin{problem}
Solve the following counting problems and briefly explain your
answers.  You may leave factorials and binomial coefficients in your
solutions.

\bparts

\ppart How many ways are there to arrange the letters in the word
HULLABALOO?

\solution{If all 10 letters in the word HULLABALOO were distinct, then
there would be $10!$ arrangements.  However, this overcounts by a
factor of $2!\ 3!\ 2!$, because the two O's are indistinguishable, the
three L's are indistinguishable, and the two A's are indistinguishable.
Therefore, by the division rule, the number of arrangements is:


\[
\frac{10!}{2!\ 3!\ 2!}
\]

}

\ppart How many different paths are there from point $(0, 0, 0)$ to
point $(30, 40, 50)$ if every step increments one coordinate and
leaves the other two unchanged?

\solution{There is a bijection between the set of all such paths and
the set of strings containing 30 X's, 40 Y's, and 50 Z's.  In
particular, we obtain a path by working through a string from left to
right.  An $X$ corresponds to a step that increments the first
coordinate, a $Y$ increments the second coordinate, and a $Z$
increments the third.  The number of such strings is:

\[
\frac{100!}{30!\ 40!\ 50!}
\]

\noindent Therefore, this is also the number of paths.
}

\ppart How many different sequences are there that consist of 99 stars
and 7 bars?

\solution{We must choose 7 of the $99 + 7 = 106$ positions in the
sequence to contain bars.  Therefore, the number of such sequences is:

\[
\binom{99 + 7}{7}
\]
}

\ppart In how many different ways can $2n$ students be paired up?

\solution{Pair up students by the following procedure.  Line up the
students and pair the first and second, the third and fourth, the
fifth and sixth, etc.  The students can be lined up in $(2n)!$ ways.
However, this overcounts by a factor of $2^n$, because we would get
the same pairing if the first and second students were swapped, the
third and fourth were swapped, etc.  Furthermore, we are still
overcounting by a factor of $n!$, because we would get the same
pairing even if pairs of students were permuted, e.g. the first and
second were swapped with the ninth and tenth.  Therefore, the number
of pairings is:

\[
\frac{(2n)!}{2^n \cdot n!}
\]
}

\ppart In how many different ways can 100 identical balls be arranged
in 10 different bins, if every bin must receive at least 3 balls?

\solution{First, we place 3 balls in each bin.  The number of ways to
place the remaining 70 balls into the 10 bins is equal to the number
of strings containing 9 bars and 70 stars, which is:

\[
\binom{79}{9}
\]
}

\ppart In how many different ways can 100 identical balls be arranged
in 10 different bins, if every bin must receive an even number of
balls?

\solution{This is equal to the number of strings with 50 stars and 9
bars, where we regard each star as a {\em pair} of balls.  Therefore,
the number of ways is:

\[
\binom{59}{9}
\]
}

\ppart How many different solutions over the {\em nonnegative}
integers are there to the following equation?

\begin{eqnarray*}
x_1 + x_2 + \ldots + x_{12} & = & 100
\end{eqnarray*}

\ppart How many different solutions over the {\em positive} integers
are there to the following equation?

\begin{eqnarray*}
x_1 + x_2 + \ldots + x_{12} & = & 100
\end{eqnarray*}

\ppart How many nondecreasing sequences of 7 integers in the range
from 0 to 99 are there?

\solution{There is a bijection between these nondecreasing sequences
and strings containing 7 bars and 99 stars.  In particular, the $k$-th
number in the nondecreasing sequence is the number of stars preceding
the $k$-th bar.  For example:

\[
\star \mid \star \star \star \mid \mid \star \star \mid \star \ldots
\quad \leftrightarrow \quad
(1, 4, 4, 6, \ldots)
\]

Therefore, the number of such nondecreasing sequences is:

\[
\binom{99 + 7}{7}
\]
}

\ppart In how many different ways can one choose $n$ out of $2n$
objects, given that $n$ of the $2n$ objects are identical and the
other $n$ are all unique?

\eparts
\end{problem}

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

\begin{problem}
On an island, everyone is healthy, wealthy, or wise.  There are
exactly 1000 people with each property.  There are exactly 200 people
with each pair of properties.  And there are exactly 50 people with
all three properties.  How many people are on the island?

\solution{
Let $H$ be the set of healthy people, $\$$ be the set of wealthy
people, and $W$ be the set of wise people.  By the inclusion-exclusion
formula, we have:

\begin{eqnarray*}
|H \cup \$ \cup W|
    & = & |H| + |\$| + |W| - |H \cap \$| - |H \cap W| - |\$ \cap W|
          + |H \cap \$ \cap W| \\
    & = & 3 \cdot 1000 - 3 \cdot 200 + 50 \\
    & = & 2450
\end{eqnarray*}
}

\end{problem}

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

\begin{problem}
The ``engineering primes'' are 2, 3, 5, 7, and all larger natural
numbers that are not divisible by 2, 3, 5, or 7.

\bparts

\ppart What is the smallest engineering prime that is not a real
prime?

\solution{
\begin{eqnarray*}
11 \cdot 11 & = & 121
\end{eqnarray*}
}

\ppart Use inclusion-exclusion to count the number of
engineering primes that are less than a million.

\solution{We can use inclusion-exclusion to count numbers in the range
from 1 to million that are multiples of 2, 3, 5, or 7:

\begin{eqnarray*}
\left\lfloor\frac{10^6}{2}\right\rfloor
+ \left\lfloor\frac{10^6}{3}\right\rfloor
+ \left\lfloor\frac{10^6}{5}\right\rfloor
+ \left\lfloor\frac{10^6}{7}\right\rfloor \\
- \left\lfloor\frac{10^6}{2 \cdot 3}\right\rfloor
- \left\lfloor\frac{10^6}{2 \cdot 5}\right\rfloor
- \left\lfloor\frac{10^6}{2 \cdot 7}\right\rfloor
- \left\lfloor\frac{10^6}{3 \cdot 5}\right\rfloor
- \left\lfloor\frac{10^6}{3 \cdot 7}\right\rfloor
- \left\lfloor\frac{10^6}{5 \cdot 7}\right\rfloor \\
+ \left\lfloor\frac{10^6}{3 \cdot 5 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 5 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 5}\right\rfloor \\
- \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 5 \cdot 7}\right\rfloor
& = & 771429
\end{eqnarray*}

Therefore, there are $1000000 - 771429 - 228571$ numbers from 1 to a
million that are not multiples of 2, 3, 5, or 7.  Adding in the
numbers 2, 3, 5, and 7, we find that the number of engineering primes
less than a million is $228571 + 4 = 228575$.
}

\eparts

\end{problem}

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

\begin{problem}
Give combinatorial proofs of the following identities.  (Recall the
structure of a combinatorial proof: describe a set $S$, show that the
left side is equal to $|S|$, show that the right side is also equal to
$|S|$, and conclude that the two sides must be equal.)

\bparts

\ppart
\begin{eqnarray*}
n \cdot 2^{n-1} & = & \sum_{k=1}^n k \cdot \binom{n}{k}
\end{eqnarray*}

\solution{Suppose there are $n$ people.  Let $S$ be set of all
possible committees consisting of a chairperson and zero or more other
people.  Then the left side is equal to $|S|$, since we can choose the
chairperson in $n$ ways and then either include or exclude each of the
remaining $n - 1$ people.  Alternatively, suppose there are to be $k$
people on the committee.  Then we can select these people in
$\binom{n}{k}$ ways and select the chairperson from among them in $k$
ways.  Summing over all possible values of $k$ gives the expression on
the right.  Since both sides are equal to $|S|$, the equation must be
equal to each other.}


\ppart
\begin{eqnarray*}
\binom{4n + 1}{2n + 1}
         & = & \sum_{k=-n}^{n} \binom{2n-k}{n} \binom{2n+k}{n}
\end{eqnarray*}

\solution{Both sides count the number ways to choose $2n+1$ elements
from the set $\{1, 2, \ldots, 4n+1\}$.  On the left, we have the
standard formula for the number of $(2n+1)$-combinations of a
$(4n+1)$-element set.  Alternatively, note that the median chosen
element must be in the range from $n+1$ to $3n+1$, since there must be
$n$ elements below the median and $n$ elements above.  Therefore, we
can choose $k$ so that the median chosen element is $2n-k+1$.  The $n$
smaller elements can then be chosen in $\binom{2n-k}{n}$ ways, and the
$n$ larger elements can be chosen in $\binom{2n+k}{n}$ ways.  Summing
over all the possible values of $k$ gives the expression on the right.
Since both sides count the number of elements in the same set, they
must be equal.}

\eparts

\end{problem}

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

\end{document}
