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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{14}{April 1, 2005}

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

\section*{Counting Rules}

\begin{mathrule}[Generalized Product Rule]
Let $S$ be a set of length-$k$ sequences.  If there are:
%
\begin{itemize}
\item $n_1$ possible first entries,
\item $n_2$ possible second entries for each first entry,
\item $n_3$ possible third entries for each combination of first and
second entries, etc.
\end{itemize}
%
then:
%
\[
\size{S} = n_1 \cdot n_2 \cdot n_3 \cdots n_k
\]
\end{mathrule}

A \term{$k$-to-1 function} maps exactly $k$ elements of the domain to
every element of the range.  For example, the function mapping each
ear to its owner is 2-to-1:

\begin{center}
\unitlength = 2pt
\begin{picture}(70,56)(-15,-3)
% \put(-15,-3){\dashbox(70,56){}} % bounding box
\put(-2,50){\makebox(0,3)[rt]{ear 1}}
\put(-2,40){\makebox(0,3)[rt]{ear 2}}
\put(-2,30){\makebox(0,3)[rt]{ear 3}}
\put(-2,20){\makebox(0,3)[rt]{ear 4}}
\put(-2,10){\makebox(0,3)[rt]{ear 5}}
\put(-2, 0){\makebox(0,3)[rt]{ear 6}}
\put(30,50){\makebox(0,3)[lt]{person A}}
\put(30,30){\makebox(0,3)[lt]{person B}}
\put(30,10){\makebox(0,3)[lt]{person C}}
\put(0,50){\vector(1,0){28}}
\put(0,40){\vector(3,-1){28}}
\put(0,30){\vector(3,2){28}}
\put(0,20){\vector(3,-1){28}}
\put(0,10){\vector(1,0){28}}
\put(0, 0){\vector(1,1){28}}
\end{picture}
\end{center}

\begin{mathrule}[Division Rule]
If $f : A \to B$ is $k$-to-1, then $\size{A} = k \cdot \size{B}$.
\end{mathrule}

\newpage

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

\section*{The Generalized Product Rule}

\begin{problem} Solve the following counting problems using the generalized
product rule.

\bparts

\ppart{Next week, I'm going to get really fit!  On day 1, I'll
exercise for 5 minutes.  On each subsequent day, I'll exercise 0, 1,
2, or 3 minutes more than the previous day.  For example, the number
of minutes that I exercise on the seven days of next week might be 5,
6, 9, 9, 9, 11, 12.  How many such sequences are possible?}

\solution[\vspace{1.5in}]{The number of minutes on the first day can
be selected in 1 way.  The number of minutes on each subsequent day
can be selected in 4 ways.  Therefore, the number of exercise
sequences is $1 \cdot 4^6$ by the extended product rule.}

\ppart An \term{$r$-permutation} of a set is a sequence of $r$
distinct elements of that set.  For example, here are all the
2-permutations of $\set{a, b, c, d}$:
%
\[
\begin{array}{ccc}
(a, b) & (a, c) & (a, d) \\
(b, a) & (b, c) & (b, d) \\
(c, a) & (c, b) & (c, d) \\
(d, a) & (d, b) & (d, c)
\end{array}
\]
%
How many $r$-permutations of an $n$-element set are there?  Express
your answer using factorial notation.

\solution[\vspace{1.5in}]{There are $n$ ways to choose the first
element, $n - 1$ ways to choose the second, $n - 2$ ways to choose the
third, \ldots, and there are $n - r + 1$ ways to choose the $r$-th
element.  Thus, there are:

\begin{eqnarray*}
n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1) & = & \frac{n!}{(n - r)!}
\end{eqnarray*}

$r$-permutations of an $n$-element set.
}

\ppart How many $n \times n$ matrices are there with \textit{distinct}
entries drawn from $\set{1, \ldots, p}$, where $p \geq n^2$?

\solution[\vspace{2in}]{There are $p$ ways to choose the first entry,
$p - 1$ ways to choose the second for each way of choosing the first,
$p - 2$ ways of choosing the third, and so forth.  In all there are
%
\[
p (p - 1) (p - 2) \cdots (p - n^2 + 1) = \frac{p!}{(p - n^2)!}
\]
%
such matrices.  Alternatively, this is the number of
$n^2$-permutations of a $p$ element set, which is $p! / (p - n^2)!$.}


\eparts

\end{problem}

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

\newpage

\section*{The Tao of BOOKKEEPPER}

\begin{problem} In this problem, we seek enlightenment through contemplation
of the word $BOOKKEEPER$.

\bparts

\ppart In how many ways can you arrange the letters in the word
$POKE$?

\solution[\vspace{0.5in}]{There are $4!$ arrangments corresponding to
the $4!$ permutations of the set $\set{P, O, K, E}$.}

\ppart In how many ways can you arrange the letters in the word
$BO_1O_2K$?  Observe that we have subscripted the O's to make them
distinct symbols.

\solution[\vspace{0.5in}]{There are $4!$ arrangments corresponding to
the $4!$ permutations of the set $\set{B, O_1, O_2, K}$.}

\ppart Suppose we map arrangements of the letters in $BO_1O_2K$ to
arrangements of the letters in $BOOK$ by erasing the subscripts.
Indicate with arrows how the arrangements on the left are mapped to
the arrangements on the right.

\[
\begin{array}{lcl}
\begin{array}{l}
O_2BO_1K \\
KO_2BO_1 \\
O_1BO_2K \\
KO_1BO_2 \\
BO_1O_2K \\
BO_2O_1K \\
\ldots
\end{array}
& \hspace{2in} &
\begin{array}{l}
BOOK \\
OBOK \\
KOBO \\
\ldots
\end{array}
\end{array}
\]

\ppart What kind of mapping is this, young grasshopper?

\solution[\vspace{0.5in}]{2-to-1}

\ppart In light of the Division Rule, how many arrangements are there
of $BOOK$?

\solution[\vspace{0.5in}]{$4! / 2$}

\ppart Very good, young master!  How many arrangements are there of
the letters in $KE_1E_2PE_3R$?

\solution[\vspace{0.5in}]{$6!$}

\ppart Suppose we map each arrangement of $KE_1E_2PE_3R$ to an
arrangement of $KEEPER$ by erasing subscripts.  List all the different
arrangements of $KE_1E_2PE_3R$ that are mapped to $REPEEK$ in this way.

\solution[\vspace{0.75in}]{$RE_1PE_2E_3K$, $RE_1PE_3E_2K$,
$RE_2PE_1E_3K$, $RE_2PE_3E_1K$, $RE_3PE_1E_2K$, $RE_3PE_2E_1K$}

\ppart What kind of mapping is this?

\solution[\vspace{0.75in}]{3!-to-1}

\ppart So how many arrangements are there of the letters in $KEEPER$?

\solution[\vspace{0.5in}]{$6! / 3!$}

\ppart {\em Now you are ready to face the BOOKKEEPER!}

How many arrangements of $BO_1O_2K_1K_2E_1E_2PE_3R$ are there?

\solution[\vspace{0.5in}]{$10!$}

\ppart How many arrangements of $BOOK_1K_2E_1E_2PE_3R$ are there?

\solution[\vspace{0.5in}]{$10! / 2!$}

\ppart How many arrangements of $BOOKKE_1E_2PE_3R$ are there?

\solution[\vspace{0.5in}]{$10! / (2! \cdot 2!)$}

\ppart How many arrangements of $BOOKKEEPER$ are there?

\solution[\vspace{0.5in}]{$10! / (2! \cdot 2! \cdot 3!)$}

\ppart How many arrangements of $VOODOODOLL$ are there?

\solution[\vspace{0.5in}]{$10! / (2! \cdot 2! \cdot 5!)$}

\ppart \textbf{(IMPORTANT) } How many $n$-bit sequences contain $k$
zeros and $(n-k)$ ones?

\solution[\vspace{0.75in}]{$n! / (k! \cdot (n-k)!)$}

This quantity is denoted $\binom{n}{k}$ and read ``$n$ choose $k$''.
You will see it almost every day in 6.042 from now until the end of
the term.

\eparts

\vspace{0.5in}

\begin{center}
\textit{Remember well what you have learned: subscripts on, subscripts off.}

\textit{This is the Tao of Bookkeeper.}
\end{center}

\end{problem}

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

\newpage

\begin{problem}
Solve the following counting problems.  Define an appropriate mapping
(bijective or $k$-to-1) between a set whose size you know and the set
in question.

\bparts 

\ppart \textbf{(IMPORTANT) } In how many ways can $k$ elements be
chosen from an $n$-element set $\set{x_1, x_2, \ldots, x_n}$?

\solution[\vspace{2in}]{There is a bijection from $n$-bit sequences
with $k$ ones.  The sequence $(b_1, \ldots, b_n)$ maps to the subset
that contains $x_i$ if and only if $b_i = 1$.  Therefore, the number
of such subsets is $\binom{n}{k}$.}

\ppart How many different ways are there to select a dozen donuts if
four varieties are available?

\solution[\vspace{2in}]{There is a bijection from selections of a
dozen donuts to 15-bit sequences with exactly 3 ones.  In particular,
suppose that the varieties are glazed, chocolate, lemon, and Boston
creme.  Then a selection of $g$ glazed, $c$ chocolate, $l$ lemon, and
$b$ Boston creme maps to the sequence:
%
\[
(g\ 0's)\ 1\ (c\ 0's)\ 1\ (l\ 0's)\ 1\ (b\ 0's)
\]
%
Therefore, the number of selections is equal to the number of 15-bit
sequences with exactly 3 ones, which is:
%
\[
\frac{15!}{3!\ 12!} = \binom{15}{3}
\]
}

\ppart How many paths are there from $(0, 0)$ to $(10, 20)$ consisting
of right-steps (which increment the first coordinate) and up-steps
(which increment the second coordinate)?

\solution[\newpage]{There is a bijection from 30-bit sequences
with 10 zeros and 20 ones.  The sequence $(b_1, \ldots, b_{30})$ maps
to a path where the $i$-th step is right if $b_i = 0$ and up if $b_i =
1$.  Therefore, the number of paths is equal to $\binom{30}{10}$.}

\ppart An independent living group is hosting eight pre-frosh,
affectionately known at $P_1, \ldots, P_8$ by the permanent residents.
Each pre-frosh must must be assigned a task: 2 must wash pots, 2 must
clean the kitchen, 1 must clean the bathrooms, 1 must clean the common
area, and 2 must serve dinner.  In how many ways can $P_1, \ldots,
P_8$ be put to productive use?

\solution[\vspace{1.5in}]{There is a bijection from sequences containing two
$P$'s, two $K$'s, a $B$, a $C$, and two $D$'s.  In particular, the
sequence $(t_1, \ldots, t_8)$ corresponds to assigning $P_i$ to
washing pots if $t_i = P$, to cleaning the kitchen if $t_i = K$, to
cleaning the bathrooms if $t_i = B$, etc.  Therefore, the number of
possible assignments is:
%
\[
\frac{8!}{2!\ 2!\ 1!\ 1!\ 2!}
\]
}

\ppart In how many ways can Mr. and Mrs. Grumperson distribute 13
indistinguishable pieces of coal to their two--- no, three!--- children
for Christmas?

\solution[\vspace{1.5in}]{There is a bijection from 15-bit strings
with two ones.  In particular, the bit string $0^a10^b10^c$ maps to
the assignment of $a$ coals to the first child, $b$ coals to the
second, and $c$ coals to the third.  Therefore, there are
$\binom{15}{2}$ assignments.}

\ppart How many solutions over the natural numbers are there to the
equation:

\begin{eqnarray*}
x_1 + x_2 + \ldots + x_{10} & \leq & 100
\end{eqnarray*}

\solution[\vspace{1.5in}]{There is a bijection from 110-bit sequences
with 10 ones to solutions to this equation.  In particular, $x_i$ is
the number of zeros before the $i$-th one but after the $(i-1)$-st one
(or the beginning of the sequence).  Therefore, there are
$\binom{110}{10}$ solutions.}

\ppart (Quiz 2, Fall '03) Suppose that two identical 52-card decks of
are mixed together.  In how many ways can the cards in this
double-size deck be arranged?

\solution{The number of sequences of the 104 cards containing 2 of each
card is $104! / (2!)^{52}$.}

\eparts

\end{problem}

\end{document}
