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

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

%\hidesolutions
%\showsolutions

\begin{document}

\problemset{8}

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

\begin{problem}
In the game of seven-card stud, a hand consists of {\em seven} cards.
Solve the related counting problems below and show your work.  You may
leave binomial coefficients in your answers.

Note that 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.

\bparts

\ppart How many different hands are possible?

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

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

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

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

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

\ppart How many hands are there such that all the cards have
different values?

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

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

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

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

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

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

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

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

\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 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}
A cube is {\em colorful} if every face is painted either
red, orange, yellow, green, blue, or violet and no two faces are
painted the same color.  Two colorful cubes are considered the same if
one can be obtained from the other by rotation.  How many different
colorful cubes are possible?

\solution{There are 5 ways to select the face opposite the red face.
The number of ways to color the remaining four faces is equal to the
number of ways to seat four people at a circular table, which is $3!$.
Therefore, the number of different colorful cubes is:

\begin{equation*}
5 \cdot 3!  =  30
\end{equation*}
}
\end{problem}

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

\begin{problem}
On a set of $n$ elements how many of the following are there?

\begin{problemparts}

\ppart binary relations?
\solution{
$2^{n^2}$ since there are this many
  different $0-1$ matrices of order $n$.

}
\ppart symmetric binary relations?
\solution{
The matrix associated with a
  symmetric relation is symmetric.  Since there are $2^ {n+{n\choose
      2}}$ different symmetric matrices there are an equal number of
  symmetric relations.
}
\ppart reflexive binary relations 
\solution{
The matrix associated with a
  reflexive relation has $1$'s along the main diagonal . Hence the
  number of such matrices, and therefore reflexive relations, is
  $2^{n^2 - n}$ .
}

\ppart symmetric and reflexive binary relations

\solution{
The matrix
  associated with a symmetric and reflexive relation is symmetric and
  ha s $1$'s along the main diagonal. Hence the number of such
  relations is $2^{{n\choose 2} }$.
}
\ppart symmetric or reflexive binary relations 
\solution{

The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+{n\choose
      2}} - 2^{{n\choose 2}}$.
}
\end{problemparts}
\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?

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}
A number is {\em cube-free} if it is not divisible by a perfect cube
greater than 1.  For example, 36 is cube-free, but $54 = 3^3 \cdot 2$
is not.  Use inclusion-exclusion to count the cube-free integers in
the range from 1 to 999.

\solution{
Initially, we'll compute the size of the complementary set; that is,
we'll count the numbers from 1 to 999 that {\em are} divisible by a
perfect cube.

Let $S_q$ be the set of natural numbers from 1 to 999 that are
divisible by $q^3$.  Our goal is to compute:

\[
|S_2 \cup S_3 \cup S_4 \cup S_5 \cup S_6 \cup S_7 \cup S_8 \cup S_9|
\]

\noindent This would be a lot of work!  But notice that $S_4 \subseteq
S_2$; that is, every number divisible by $4^3$ is also divisible by
$2^3$.  Since $S_4$ adds nothing to the union above, we can forget
about it.  By similar reasoning, we can reduce the problem to
computing:

\[
|S_2 \cup S_3 \cup S_5 \cup S_7|
\]

This is more tractable.  We now compute the terms of the
inclusion-exclusion formula:

\[
\begin{array}{rcccl}
|S_2| & = & \lfloor \frac{999}{2^3} \rfloor & = & 124 \\
|S_3| & = & \lfloor \frac{999}{3^3} \rfloor & = & 37 \\
|S_5| & = & \lfloor \frac{999}{5^3} \rfloor & = & 7 \\
|S_7| & = & \lfloor \frac{999}{7^3} \rfloor & = & 2 \\
|S_2 \cap S_3| & = & \lfloor \frac{999}{2^3\ 3^3} \rfloor & = & 4
\end{array}
\]
All other terms are ZERO!  So we have:

\begin{eqnarray*}
|S_2 \cup S_3 \cup S_5 \cup S_7|
    & = & 124 + 37 + 7 + 2 - 4 \\
    & = & 166
\end{eqnarray*}

This means that 166 numbers in the range 1 to 999 are multiples of
perfect cubes.  Therefore, the number of cube-free numbers in this
range is:

\begin{equation*}
999 - 166  =  833
\end{equation*}
}

\end{problem}

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

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

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

\end{problem}]

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

\end{document}
