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

\newcommand{\rem}{\textup{ rem }}

\begin{document} 
\inclassproblems{11, Fri.}

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

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

\bparts

\ppart How many $n \times n$ matrices are there with entries drawn
from $\set{1, \ldots, p}$?

\solution[\vspace{1in}]{There are $p$ ways to choose the first entry,
$p$ ways to choose the second for each way of chosing the first, $p$
ways to choose the third for each way of choosing the first two, etc.
Therefore, there are $p^{n^2}$ matrices.}

\ppart In how many ways can a rook, a queen, and a king be placed on
an $8 \times 8$ chessboard so that no two share a row or column?

\solution[\vspace{1.5in}]{There are:

\begin{itemize}
\item 8 ways to choose the row of the rook
\item 8 ways to choose the column of the rook
\item 7 ways to choose the row of the queen
\item 7 ways to choose the column of the queen
\item 6 ways to choose the row of the king
\item 6 ways to choose the column of the king
\end{itemize}

Therefore, there are $8 \cdot 8 \cdot 7 \cdot 7 \cdot 6 \cdot 6$
matrices in all.}

\ppart \textbf{(Important.)}\quad A \textbf{\textit{permutation}} of a
set $S$ is a sequence containing every element of $S$ exactly once.
For example, here are all the permutations of the set $\set{a, b, c}$:

\[
\begin{array}{ccc}
(a, b, c) & (a, c, b) & (b, a, c) \\
(b, c, a) & (c, a, b) & (c, b, a)
\end{array}
\]

How many permutations of an $n$-element set are there?  Express your
answer using factorial.

\solution[\newpage]{There are $n$ ways to choose the first element, $n
- 1$ ways to choose the second, $n - 2$ ways to choose the third, and
so forth.  In all, there are

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

permutations of an $n$-element set.
}

\ppart \textbf{(Important.)}\quad An \textbf{\textit{$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{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{How many bijective functions are there from set $A$ to set $B$,
if $|A| = |B| = n$?}

\solution[\vspace{1.25in}]{Let $a_1, \ldots, a_n$ denote the elements
of $A$.  There are $n$ ways to map $a_1$, $n - 1$ way to map $a_2$, $n
- 2$ ways to map $a_n$ and so forth.  Therefore, there are $n!$
bijective functions from $A$ to $B$ in total.}

\ppart A function $f: A \to B$ is \textbf{\textit{injective}} if every
element of $B$ is mapped to at most once.  How many injective
functions $f: A \to B$ are there if $\card{A} = n$, $\card{B} = m$,
and $n \leq m$?

\solution{Let $a_1, \ldots, a_n$ denote the elements of $A$.  There
are $m$ ways to map $a_1$, $m - 1$ way to map $a_2$, $m - 2$ ways to
map $a_n$, \ldots, and $m - n + 1$ ways to map $a_n$.  Therefore,
there are $m! / n!$ injective functions from $A$ to $B$ altogether.}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem} \textbf{(Tao of Bookkeeper)}  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.)}\quad 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{1in}

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

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

\end{problem}

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

\instatements{\newpage}

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

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

\textbf{Solution.}  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}$.

\bparts 

\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[\vspace{1.5in}]{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 \textbf{(Important.)}\quad How many $k$-element subsets of
$\set{x_1, x_2, \ldots, x_n}$ are there?

\solution[\vspace{1.5in}]{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 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[\newpage]{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!--- chidren
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[\vspace{1.5in}]{The number 104-entry sequences containing 2
of each card is $104! / (2!)^{52}$.}

\ppart In how many different ways can three indistinguishable rooks be
arranged on a chessboard so that no two share a row or column?

\solution[\vspace{1.5in}]{There is a $3!$-to-1 mapping from ways to
arrange a rook, a queen, and a king to ways of arranging the three
rooks: replace each of the original three pieces with a rook.  This
mapping is $3!$-to-1 because each of the $3!$ permutations of the
original pieces yields the same configuration of rooks.  Therefore,
the number of arrangements is $8 \cdot 8 \cdot 7 \cdot 7 \cdot 6 \cdot
7 / 3!$.}

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

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

\eparts

\end{problem}

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

\end{document}
