\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\coursecopyrightnames}
{\href{http://theory.csail.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}
\renewcommand{\coursecopyrightyear}{2005}

\renewcommand{\reading}{Counting, Notes I.\ \& II.\S 1--3.}

\newcommand{\rem}{\operatorname{\,rem\,}}

\begin{document}
\problemset{7}

%S05, ps7

\begin{problem}
There are 20 books arranged in a row on a shelf.

\bparts

\ppart Describe a bijection between ways of choosing 6 of these books
so that no two adjacent books are selected and $15$-bit sequences with
exactly 6 ones.

\solution{There is a bijection from 15-bit sequences with exactly six
1's to valid book selections: given such a sequence, map each zero to
a non-chosen book, each of the first five 1's to a chosen book
followed by a non-chosen book, and the last 1 to a chosen book.  For
example, here is a configuration of books and the corresponding binary
sequence:
%
\fboxsep=0pt
\fboxrule=1pt
\definecolor{lightgray}{gray}{0.8}
\newsavebox{\selected}
\newsavebox{\unselected}
\savebox{\selected}
    {\fcolorbox{black}{lightgray}{\rule{15pt}{0pt}\rule{0pt}{40pt}}}
\savebox{\unselected}
    {\fcolorbox{black}{white}{\rule{15pt}{0pt}\rule{0pt}{40pt}}}
\newcommand{\sbk}{\usebox{\selected}}
\newcommand{\ubk}{\usebox{\unselected}}
%
\[
\overbrace{\sbk\ubk}^{1}\overbrace{\ubk}^{0}\overbrace{\ubk}^{0}\overbrace{\sbk\ubk}^{1}\overbrace{\sbk\ubk}^{1}\overbrace{\ubk}^{0}\overbrace{\ubk}^{0}\overbrace{\ubk}^{0}\overbrace{\sbk\ubk}^{1}\overbrace{\ubk}^{0}\overbrace{\ubk}^{0}\overbrace{\sbk\ubk}^{1}\overbrace{\ubk}^{0}\overbrace{\ubk}^{0}\overbrace{\sbk}^{1}\]
%
Selected books are darkened.  Notice that the first fives ones are
mapped to a chosen book \textit{and} an non-chosen book in order to
ensure that the binary sequence maps to a valid selection of books.}

\ppart How many ways are there to select 6 books so that no two
adjacent books are selected?

\solution{By the Bijection Rule, this is equal to the number of 15-bit
sequences with exactly 6 ones, which is equal to
%
\[
\frac{15!}{6!\ 9!} = \binom{15}{6}
\]
%
by the Bookkeeper Rule.}

\eparts

\end{problem}

%S05, ps7

\begin{problem}
Answer the following questions and provide brief justifications.  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.

You may leave factorials and binomial coefficients in your answers.

\bparts

\ppart In how many different ways can the letters in the name of the
popular 1980's band $BANANARAMA$ be arranged?

\solution{There are 5 $A$'s, 2 $N$'s, 1 $B$, 1 $R$, and 1 $M$.
Therefore, the number of arrangements is
%
\[
\frac{10!}{5!\ 2!\ 1!\ 1!\ 1!}
\]
%
by the Bookkeeper Rule.
}

\ppart How many different paths are there from point $(0, 0, 0)$ to
point $(12, 24, 36)$ 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 12 X's, 24 Y's, and 36 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{72!}{12!\ 24!\ 36!}
\]
%
Therefore, this is also the number of paths.
}

\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 How many different solutions over the natural numbers are
there to the following equation?
%
\[
x_1 + x_2 + x_3 + \ldots + x_{8} = 100
\]
%
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{There is a bijection between sequences containing 100 zeros
and 7 ones.  Specifically, the 7 ones divide the zeros into 8
segments.  Let $x_i$ be the number of zeros in the $i$-th segment.
Therefore, the number of solutions is:
%
\[
\binom{100+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?

\solution{We can select $n$ objects 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 are there with vertices $v_1, v_2,
\ldots, v_n$ if self-loops are permitted?

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

\[
2^{\binom{n}{2} + n}
\]
}

\iffalse
\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{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 $\frac{4!}{2!\ 2!} = 6$ ways to do this.  All cases are
listed below:

\[
\begin{array}{cc}
\text{distribution of balls} & \text{\# of ways} \\
3, 3, 0, 0 & \frac{4!}{2!\ 2!} = 6\\
3, 2, 1, 0 & \frac{4!}{1!\ 1!\ 1!\ 1!} = 24 \\
3, 1, 1, 1 & \frac{4!}{3!\ 1!} = 4 \\
2, 2, 2, 0 & \frac{4!}{3!\ 1!} = 4 \\
2, 2, 1, 1 & \frac{4!}{2!\ 2!} = 6\\
\end{array}
\]

Thus, there are $6 + 24 + 4 + 4 + 6 = 44$ ways in all.
}\fi


\ppart There are 15 sidewalk squares in a row.  Suppose that a ball
can be thrown so that it bounces on 0, 1, 2, or 3 distinct sidewalk
squares.  Assume that the ball always moves from left to right.  How
many different throws are possible?  As an example, a two-bounce throw
is illustrated below.
%
\begin{center}
\begin{picture}(310,40)
\thinlines
\multiput(0,0)(20,0){16}{\line(1,2){10}}
\put(0,0){\line(1,0){300}}
\put(10,20){\line(1,0){300}}
\thicklines
\put(0,30){\vector(1,0){75}}
\put(75,30){\vector(1,-1){20}}
\put(95,10){\vector(1,1){20}}
\put(115,30){\vector(1,0){60}}
\put(175,30){\vector(1,-1){20}}
\put(195,10){\vector(1,1){20}}
\put(215,30){\vector(1,0){95}}
\end{picture}
\end{center}

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

\iffalse

\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{We fall back on explicit enumeration.  Let $R$, $G$, and $B$
be the values shown on the three dice.
%
\begin{eqnarray*}
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{way} \\
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{eqnarray*}
}
\fi

\ppart The working days in the next year can be numbered 1, 2, 3,
\ldots, 300.  I'd like to avoid as many as possible.
%
\begin{itemize}
\item On even-numbered days, I'll say I'm sick.
\item On days that are a multiple of 3, I'll say I was stuck in traffic.
\item On days that are a multiple of 5, I'll refuse to come out from
under the blankets.
\end{itemize}
%
In total, how many work days will I \textit{avoid} in the coming year?

\solution{Let $D_2$ be the set of even-numbered days, $D_3$ be the
days that are a multiple of 3, and $D_5$ be days that are a multiple
of 5.  The set of days I can avoid is $D_2 \cup D_3 \cup D_5$.  By the
Inclusion-Exclusion Rule, the size of this set is:
%
\begin{align*}
\card{D_2 \cup D_3 \cup D_5}
    & = \card{D_2} + \card{D_3} + \card{D_5} \\
    & \quad - \card{D_2 \cap D_3} - \card{D_2 \cap D_5} - \card{D_3 \cap D_5}\\
    & \quad + \card{D_2 \cap D_3 \cap D_5} \\
    & = \frac{300}{2} + \frac{300}{3} + \frac{300}{5}
        - \frac{300}{2 \cdot 3} - \frac{300}{2 \cdot 5} - \frac{300}{3 \cdot 5}
        + \frac{300}{2 \cdot 3 \cdot 5} \\
    & = 220
\end{align*}
}

\eparts

\end{problem}

%S05 ps7

\begin{problem}
Use the pigeonhole principle to solve the following problems.

\bparts

\ppart Prove that among any $n^2 + 1$ points within an $n \times n$
square there must exist two points whose distance is at most
$\sqrt{2}$.

\solution{ Partition the $n \times n$ into $n^2$ unit squares.  Each
of the $n^2 + 1$ points lies in one of these $n^2$ unit squares.  (If
a point lies on the boundary between squares, assign it to a square
arbitrarily.)  Therefore, by the pigeonhole principle, there exist two
points in the same unit square.  And the distance between those two
points can be at most $\sqrt{2}$.}

\ppart Jellybeans of 6 different flavors are stored in 5 jars.  There
are 11 jellybeans of each flavor.  Prove that some jar contains at
least three jellybeans of one flavor and also at least three
jellybeans of some other flavor.

\solution{We use the pigeonhole principle twice.  Since there are 11
beans of a given flavor and there are only 5 jars, some jar must get
at least $\rceil 11/5 \lceil = 3$ beans of that flavor.  Since there
are 6 flavors and only 5 jars, some jar must get two pairs of
same-flavored beans.}

\ppart Prove that among every set of 30 integers, there exist two
whose difference \textit{or} sum is a multiple of 51.

\solution{Regard the 30 integers as pigeons.  Regard the 26 sets
$\set{0}$, $\set{1, 50}$, $\set{2, 49}$, $\ldots$, $\set{25, 26}$ as
pigeonholes.  Map integer $n$ to the set containing $n \rem 51$.  By
the pigeonhole principle, some two pigeons (integers $a$ and $b$) are
mapped to the same pigeonhole.  Thus, either:
%
\begin{itemize}

\item $a \rem 51 = b \rem 51$ and so the difference of $a$ and $b$ is
a multiple of 51.

\item $a \rem 51 + b \rem 51$ is either 0 or 51 and so the sum of $a$
and $b$ is a multiple of 51.

\end{itemize}
}

\eparts
\end{problem}

% revised by ARM from S05 ps8

\begin{problem}
Suppose you have seven dice--- each a different color of the rainbow;
otherwise the dice are standard, with six faces numbered 1 to 6.  A
\emph{roll} is a sequence specifying a value for each die in rainbow
(ROYGBIV) order.  For example, one roll is $(3,1,6,1,4,5,2)$ indicating
that the red die showed a 3, the orange die showed 1, the yellow 6, the
green 1, the blue 4, the indigo 5, and the violet 2.

For the problems below, describe a bijection between the specified set of
rolls and another set that is easily counted using the Product,
Generalized Product, and similar rules.  Then write a simple numerical
expression for the size of the set of rolls.  You do not need to prove
that the correspondence between sets you describe is a bijection, and you
do not need to simplify the expression you come up with.

For example, let $A$ be the set of rolls where 4 dice come up showing the
same number, and the other 3 dice also come up the same, but with a
different number.  Let $R$ to be the set of seven rainbow colors and $S$
be the set $\set{1,\dots,6}$ of dice values.

Define $B \eqdef S_2 \cross \set{3,4} \cross R_3$, where $S_2$ is the set
of size 2 subsets of $S$, and $R_3$ is the set of size 3 subsets of $R$.
Then define a bijection from $A$ to $B$ by mapping a roll in $A$ to the
sequence in $B$ whose first element is the set of two numbers that came
up, whose second element is the number of times the smaller of the two
numbers came up in the roll, and whose third element is the set of colors
of the three matching dice.

For example, the roll
\[
(4,4,2,2,4,2,4) \in A
\]
maps to the triple
\[
(\set{2,4},3,\set{\text{yellow,green,indigo}}) \in B.
\]

Now by the bijection Rule $\card{A} = \card{B}$, and by the Product rule,
\[
\card{B} = \binom{6}{2} \cdot 2 \cdot \binom{7}{3}.
\]

\bparts

\ppart For how many rolls is the value on every die different?

\solution{None, by the Pigeonhole Principle.}

\ppart\label{66} For how many rolls do two dice have the value 6 and the
remaining five dice all have different values?

Example: $(6, 2, 6, 1, 3, 4, 5)$ is a roll of this type, but $(1, 1, 2, 6,
3, 4, 5)$ and $(6, 6, 1, 2, 4, 3, 4)$ are not.

\solution{As in the example, map a roll into an element of $B \eqdef R_2
\cross P_5$ where $P_5$ is the set of permutations of $\set{1,\dots,5}$.  A roll
maps to the pair whose first element is the set of colors of the two dice
with value 6, and whose second element is the sequence of values of the
remaining dice (in rainbow order).  So $(6, 2, 6, 1, 3, 4, 5)$ above maps
to $(\set{\text{red,yellow}}, (2,1,3,4,5))$.  By the Product rule,
\[
\card{B} = \binom{7}{2}\cdot 5!.
\]}

\ppart For how many rolls do two dice have the same value and the
remaining five dice all have different values?

Example: $(4, 2, 4, 1, 3, 6, 5)$ is a roll of this type, but $(1, 1, 2, 6,
1, 4, 5)$ and $(6, 6, 1, 2, 4, 3, 4)$ are not.  

\solution{Map a roll into a triple whose first element is in $S$,
indicating the value of the pair of matching dice, whose second element is
set of colors of the two matching dice, and whose third element is the
sequence of the remaining five dice values (in rainbow order).

So $(4, 2, 4, 1, 3, 6, 5)$ above maps to $(4, \set{\text{red,yellow}},
(2,1,3,6,5))$.  Notice that the number of choices for the third element of
a triple is the number of permutations of the remaining five values,
namely, $5!$.  This mapping is a bijection, so the number of such rolls
equals the number of such triples.
By the Generalized Product rule, the number of such triples is
\[
6 \cdot \binom{7}{2} \cdot 5!.
\]

Alternatively, we can define a map from this rolls in this part to the
rolls in part~\eqref{66}, by replacing the value of the duplicated values
with 6's and replacing any 6 in the remaining values by the value of the
duplicated pair.  So the roll $(4, 2, 4, 1, 3, 6, 5)$ would map to the
role $(6, 2, 6, 1, 3, 4, 5)$.  Now a type~\ref{66} role, $r$, is mapped to
by exactly the rolls obtainable from $r$ by exchanging occurrences of 6's
and $i$'s, for $i = 1,\dots,6$.  So this map is 6-to-1, and by the
Division Rule, the number of rolls here is 6 times the number of rolls in
part~\eqref{66}.

\iffalse

An useful variation of this idea is to map a roll into a triple in the set
$B \eqdef S cross R_2 \cross P_5$.  Again, the first element of a triple
in $B$ is the value of the matching dice, the second element is the set of
colors of the two matching dice, and the third element is the sequence of
\emph{rankings}\footnote{Given a set of $n$ numbers, the \emph{rank} of a
number in the set is its position when the numbers are listed in
increasing order.  So the rank of the smallest number is 1, the rank of
the second smallest is 2, \dots, and the rank of the largest is $n$.} of
the remaining five dice values (in rainbow order).

So now $(4, 2, 4, 1, 3, 6, 5)$ above maps to $(4, \set{\text{red,yellow}},
(2,1,3,5,4))$.  By the Product rule, $\card{B} = \binom{7}{2}\cdot 5!$.

The use of ranking let us define $B$ without having the possible values of
third elements in triples depend on the first elements.  This let us give
a simpler definition of the set, $B$, of triples corresponding to rolls.
With the simpler definition of $B$, we could calculate its size using the
Product rule instead of the Generalized Product rule.
\fi

}

\ppart For how many rolls do two dice have one value, two different dice
have a second value, and the remaining three dice a third value?

Example: $(6, 1, 2, 1, 2, 6, 6)$ is a roll of this type, but $(4, 4, 4, 4,
1,3,5)$ and $(5, 5, 5, 6, 6,1,2)$ are not.

\solution{Map a roll of this kind into a 4-tuple whose first element is
the set of two numbers of the two pairs of matching dice, whose second
element is the set of two colors of the pair of matching dice with the
smaller number, whose third element is the set of two colors of the larger
of the matching pairs, and whose fourth element is the value of the
remaining three dice.  For example, the roll $(6, 1, 2, 1, 2, 6, 6)$ maps
to the triple
$(\set{1,2},\set{\text{orange,green}},\set{\text{yellow,blue}}, 6)$.

There are $\binom{6}{2}$ possible first elements of a triple,
$\binom{7}{2}$ second elements, $\binom{5}{2}$ third elements since the
second set of two colors must be different from the first two, and 4 ways
to choose the value of the three dice since their value must differ from
the values of the two pairs.  So by the Generalized Product rule, there
are
\[
\binom{6}{2} \cdot \binom{7}{2} \cdot \binom{5}{2} \cdot 4
\]
possible rolls of this kind.}

\eparts

\end{problem}


%S05, ps7 slightly revised by ARM

\begin{problem}
A \textit{derangement} is a permutation $(x_1, x_2, \dots, x_n)$ of
the set $\set{1, 2, \dots, n}$ such that $x_i \neq i$ for all $i$.
For example, $(2, 3, 4, 5, 1)$ is a derangement, but $(2, 1, 3, 5, 4)$
is not because 3 appears in the third position.  The objective of this
problem is to count derangements.

It turns out to be easier to start by counting the permutations that are
\textit{not} derangements.  Let $S_i$ be the set of all permutations
$(x_1, x_2, \dots, x_n)$ that are not derangements because $x_i = i$.
So the set of non-derangements is
\[
\lgunion_{i=1}^n S_i.
\]

\bparts

\ppart What is $\card{S_i}$?

\solution{There is a bijection between permutations of $\set{1, 2,
\dots, n}$ with $i$ in the $i$-th position and unrestricted
permutations of $\set{1, 2, \dots, n} - i$.  Therefore, $\card{S_i} =
(n-1)!$.}

\ppart What is $\card{S_i \cap S_j}$ where $i \neq j$?

\solution{The set $S_i \cap S_j$ consists of all permutations with $i$
in the $i$-th position and $j$ in the $j$-th position.  Thus, there is
a bijection with permutations of $\set{1, 2, \dots, n} - \set{i, j}$,
and so $\card{S_i \cap S_j} = (n-2)!$.}

\ppart What is $\card{S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_k}}$
where $i_1, i_2, \dots, i_k$ are all distinct?

\solution{By the same argument, $(n - k)!$.}

\ppart\label{ie} Use the inclusion-exclusion formula to express the number of
non-derangements in terms of sizes of possible intersections of the sets
$S_1, \dots, S_n$.

\solution{
\[
\sum_i \card{S_i}
- \sum_{i,j} \card{S_i \cap S_j}
+ \sum_{i,j,k} \card{S_i \cap S_j \cap S_k}
- \cdots
\pm \card{S_1 \cap S_2 \cap \cdots \cap S_n}
\]
%
In each summation, the subscripts are distinct elements of $\set{1,
\dots, n}$.}

\ppart How many terms in the expression in part~\eqref{ie} have the form
$\card{S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_k}}$?

\solution{There is one such term for each $k$-element subset of the
$n$-element set $\set{1, 2, \dots, n}$.  Therefore, there are
$\binom{n}{k}$ such terms.}

\ppart Combine your answers to the preceding parts to prove the number of
non-derangements is:
\[
n! \paren{\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \cdots \pm \frac{1}{n!}}.
\]
Conclude that the number of derangements is
\[
n! \paren{1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!}}.
\]

\solution{
By Inclusion-Exclusion, the number of non-derangements is
\begin{align}
\lefteqn{\sum_i \card{S_i}
- \sum_{i,j} \card{S_i \cap S_j}
+ \sum_{i,j,k} \card{S_i \cap S_j \cap S_k}
- \cdots
\pm \card{S_1 \cap S_2 \cap \cdots \cap S_n}} \notag \\
    & = \binom{n}{1} \cdot (n-1)!
      - \binom{n}{2} \cdot (n-2)!
      + \binom{n}{3} \cdot (n-3)!
      - \cdots
      \pm \binom{n}{n} \cdot 0! \notag\\
    & = n! \paren{\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \cdots \pm \frac{1}{n!}}\label{nd}
\end{align}

Since there are $n!$ permutation, the number of derangements is $n!$ minus expression~\eqref{nd}.
}

\ppart As $n$ goes to infinity, the number of derangements approaches a constant
fraction of all permutations.  What is that constant?  \hint
%
\[
e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots
\]

\solution{$1/e$}

\eparts

\end{problem}


\end{document}
