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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{15}{November 3, 2004}

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

\begin{problem}
Learning to count takes practice!  Briefly justify your answers to the
following questions.  Not every problem can be solved with a cute
formula; you may have to fall back on case analysis, explicit
enumeration, or ad hoc methods.  Do as many problems as you can and
save the rest to study for Quiz II.  You may leave factorials and
binomial coefficients in your answers.

\bparts

\ppart How many different arrangements are there of the letters in
$BANANA$?

\solution[\vspace{1in}]{
By the Bookkeeper Rule, there are:
%
\[
\frac{6!}{1! \ 3! \ 2!} = 60
\]
}

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

\solution[\vspace{1in}]{There is a bijection between the set of all
such paths and the set of strings containing 10 X's, 20 Y's, and 30
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{60!}{10!\ 20!\ 30!}
\]

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

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

\solution[\newpage]{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 How many different nonnegative integer solutions are there to the
following equation?
%
\[
x_1 + x_2 + x_3 + \ldots + x_{10} = 1000
\]

A solution is a specification of the value of each variable $x_i$.
Two solutions are different if different values are specified for some
variable $x_i$.

\solution[\vspace{1in}]{There is a bijection between strings
containing 1000 stars and 9 bars and solutions to this equation.  The
9 bars divide the stars into 10 segments.  Let $x_i$ be the number of
stars in the $i$-th segment.  Therefore, the number of solutions is:

\[
\binom{1000+9}{9}
\]
}

\ppart How many different size $n$ subsets are there of a set $2n$
objects, given that $n$ of the $2n$ objects are identical and the other
$n$ are all unique?

\solution[\vspace{1in}]{We can select a size $n$ subset as follows.
First, take a subset of the unique objects.  Then take however many
identical elements are needed to bring the total to $n$.  The first step
can be done in $2^n$ ways, and the second can be done in only 1 way.
Therefore, there are $2^n$ ways to choose $n$ objects.
}

\ppart How many undirected graphs without self-loops are there
with vertices $v_1, v_2, \ldots, v_n$?

\solution[\vspace{1in}]{There are $\binom{n}{2}$ potential edges, each
of which may or may not appear in a given graph.  Therefore, the
number of graphs is:
%
\[
2^{\binom{n}{2}}
\]
}

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

\solution[\vspace{1in}]{There exists a bijection from 8-bit sequences
with exactly five 1's to valid book selections.  Map each zero to a
non-chosen book, each of the first four 1's to a chosen book followed
by a non-chosen book, and the last 1 to a chosen book.  For example,
the 8-bit sequence:
%
\[
(1, 0, 1, 1, 0, 1, 0, 1)
\]
%
maps to the book selection:
%
\[
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c\ n}_{1}\ 
\underbrace{n}_{0}\ 
\underbrace{c}_{1}
\]
%
where $c$ denotes a chosen book and $n$ denotes a non-chosen book.
Therefore, the number of valid book selections is $\binom{8}{5}$.}
\fi

\ppart Find the number of 5-card hands with exactly three aces.

\solution[\vspace{1in}]{We can choose the three aces in $\binom{4}{3}$
ways, and we can choose the remaining two cards in $\binom{48}{2}$
ways.  Thus, there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\ppart Find the number of 5-card hands in which every suit
appears at most twice.

\solution[\vspace{1in}]{There are two cases.  Either one suit appears
twice or else two suits appear twice.  The number of hands in which
one suit appears twice is $\binom{13}{2} \cdot 13^3 \cdot 4$, since
there are 4 ways to choose the doubly-represented suit,
$\binom{13}{2}$ ways to choose two values from this suit, and $13^3$
ways to choose values for cards in the three remaining suits.
Similarly, the number of hands in which two suits appear twice is
$\binom{13}{2}^2 \cdot 13 \cdot \binom{4}{2} \cdot 2$.  Therefore,
there are a total of
%
\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot \binom{4}{2} \cdot 2
\]
%
such hands.}

\ppart There are 15 sidewalk squares in a row.  Suppose that a ball is
thrown down the row so that it bounces on 0, 1, 2, or 3 distinct sidewalk
squares.  How many different throws are possible?

\solution[\vspace{1in}]{
\[
\binom{15}{0} + \binom{15}{1} + \binom{15}{2} + \binom{15}{3}
\]
}

\ppart Find the number of 7-card hands with three pairs and no three-
or four-of-a-kind.

\solution[\vspace{1in}]{We can select the values of the three pairs in
$\binom{13}{3}$ ways, the suits for the three pairs in
$\binom{4}{2}^3$ ways, and the final card in 40 ways.  This gives:

\[
40 \binom{13}{3} \binom{4}{2}^3
\]

hands in all.}

\ppart In how many different ways can the numbers shown on a red
die, a green die, and a blue die total up to 15?  Assume that these
are ordinary, 6-sided dice.

\solution[\vspace{1in}]{We fall back on explicit enumeration.  Let
$R$, $G$, and $B$ be the values shown on the three dice.
\[\begin{array}{rlrlcl}
R & = 1, & B + G & = 14 & \rightarrow  0 \ \text{ways} \\
R & = 2, & B + G & = 13 & \rightarrow  0 \ \text{ways} \\
R & = 3, & B + G & = 12 & \rightarrow  1 \ \text{ways} \\
R & = 4, & B + G & = 11 & \rightarrow  2 \ \text{ways} \\
R & = 5, & B + G & = 10 & \rightarrow  3 \ \text{ways} \\
R & = 6, & B + G & = 9 & \rightarrow   4 \ \text{ways}
\end{array}\]
A total of 10 ways.

Another approach (suggested by a student in recitation) begins by
observing that the number of ways the dice can sum to 15 is the same as
the number of positive integer solutions to the equation
\[
x_1 + x_2 + x_3 = 15
\]
such that $x_i\leq 6$.  In general, counting solutions with inequality
constraints on the variables involves a tedious case analysis, but in this
case there's a trick to remove the constraints: let $y_i = 6 - x_i$.  Now
the number of desired $x_i$ solutions is the same as the number of
nonnegative integer solutions to
\begin{equation}\label{y3}
y_1 + y_2 + y_3 = 3
\end{equation}
such that $y_i \leq 5$.  But since the sum of the $y_i$'s must be three,
the constraint that $y_i \leq 5$ will be met by every nonnegative integer
solution to~\eqref{y3}.  So we need only count the number of nonnegative
integer solutions to~\eqref{y3}, which we already know is the same as the
number of sequences of two bars and three stars, namely
\[
\binom{2+3}{3} =10.
\]
}

\ppart In how many ways can 20 indistinguishable pre-frosh be stored
in four different crates if each crate must contain an \textit{even}
number of pre-frosh?

\solution[\vspace{1in}]{There is a bijection from 13-bit strings with
exactly 3 ones. In particular, the string $0^a10^b10^c10^d$
corresponds to to storing $2a$ prefrosh in the first crate, $2b$ in
the second, $2c$ in the third, and $2d$ in the fourth.  Therefore, the
number of ways to store the pre-frosh is equal to the number of 13-bit
strings with exactly 3 ones, which is $\binom{13}{3}$.}

\ppart How many paths are there from point $(0, 0)$ to $(50, 50)$ if
every step increments one coordinate and leaves the other unchanged
and there are impassable boulders sitting at points $(10, 10)$ and
$(20, 20)$?

\solution[\vspace{1.5in}]{We use inclusion-exclusion.  The total
number of paths is $\binom{100}{50}$, but we must subtract off the
obstructed paths.  There are $\binom{20}{10} \cdot \binom{80}{40}$
paths through the first boulder, since there are $\binom{20}{10}$
paths from the start to the boulder and $\binom{80}{40}$ paths from
the boulder to the finish.  Similarly, there are $\binom{40}{20} \cdot
\binom{60}{30}$ paths through the second boulder.  However, we must
subtract off paths going through both boulders, and there are
$\binom{20}{10} \cdot \binom{20}{10} \cdot \binom{60}{30}$ of those.
Therefore, the total number of paths is:
%
\[
\binom{100}{50}
- \binom{20}{10} \cdot \binom{80}{40}
- \binom{40}{20} \cdot \binom{60}{30}
+ \binom{20}{10} \cdot \binom{20}{10} \cdot \binom{60}{30}
\]
}

\ppart In how many ways can the 90 students in 6.042 be divided into
18 groups of 5?

\solution[\vspace{1in}]{There is a $18!$-to-1 mapping from sequences
containing five $1$'s, five $2$'s, \dots, and five $18$'s.
Specifically, the sequence $(t_1, \dots, t_{90})$ corresponds to the
assignment where each student $i$ is placed in group $t_i$.  The
mapping is $18!$-to-1, because we can permute the team numbers (in
$18!$ different ways) without altering the way the class is
partitioned.  Therefore, the number of ways to divide the class into
teams is:
\[
\frac{90!}{(5!)^{18} 18!}
\]
}

\ppart In how many different ways can 10 indistinguishable balls be
placed in four distinguishable boxes, such that every box gets 1, 2,
3, or 4 balls?

\solution[\vspace{1.5in}]{First, we might as well put 1 ball in every
box.  Now the problem is to put the remaining 6 balls into 4 boxes so
that no box gets more than 3 balls.  Now we turn to case analysis.
For example, we could put 3 balls in two boxes and 0 balls in the
other two boxes.  There are $4!/(2!\ 2!) = 6$ ways to do this.  All
cases are listed below:
\[
\begin{array}{ccl}
\text{distribution of balls} & \text{\# of ways} \\
3, 3, 0, 0 & \dfrac{4!}{2!\ 2!} & = 6\\
3, 2, 1, 0 & \dfrac{4!}{1!\ 1!\ 1!\ 1!} & = 24 \\
3, 1, 1, 1 & \dfrac{4!}{3!\ 1!} & = 4 \\
2, 2, 2, 0 & \dfrac{4!}{3!\ 1!} & = 4 \\
2, 2, 1, 1 & \dfrac{4!}{2!\ 2!} & = 6\\
\end{array}
\]
}

\ppart In how many different ways can Blockbuster arrange 64 copies of
{\em Cat in the Hat}, 96 copies of {\em Matrix Revolutions}, and 1
copy of {\em Amelie} on 5 shelves?

\solution[\newpage]{This is the number of ways to arrange 64 $C$'s
(Cat in the Hat), 96 $M$'s (Matrix), 1 $A$'s (Amelie), and 4 $X$'s
(dividers between shelves).  This is equal to:
%
\[
\frac{(64 + 96 + 1 + 4)!}{64!\ 96!\ 1!\ 4!}
\]
}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem}
Give a combinatorial proof of the following theorem.  Remember the
basic plan for a combinatorial proof:

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

For this problem, let $S$ be the set of all sequences in $\set{0, 1, *}^n$
containing exactly one $*$.

\begin{theorem}
\[
n 2^{n-1} = \sum_{k=1}^n k \binom{n}{k}
\]
\end{theorem}

\solution{
\begin{proof}
We give a combinatorial proof.  Let $S$ be the set of all sequences in
$\set{0, 1, *}^n$ containing exactly one $*$.

On one hand, $\size{S} = n 2^{n-1}$, since the $*$ can appear in $n$
positions and there are $2^{n-1}$ settings for the remaining symbols.

On the other hand, every sequence in $S$ contains between 1 and $n$
nonzero entries since the $*$, at least, is nonzero.  The number of
sequences in $S$ with exactly $k$ nonzero entries is $k \binom{n}{k}$,
since there are $\binom{n}{k}$ ways to select the positions of the
nonzero entries and then $k$ ways to select one of those entries to be
the $*$.  Thus, by the Sum Rule:
%
\[
\size{S} = \sum_{k=1}^n k \binom{n}{k}
\]
%
Equating these two expressions for $\size{S}$ proves the theorem.
\end{proof}
}
\end{problem}

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

\end{document}
