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

%\hidesolutions
\showsolutions

\begin{document}

\problemset{7}{March 29, 2005}{Monday, April 4 at 9 PM in Room 32-044}

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

\begin{problem}
Every function has some subset of these properties:
%
\begin{center}
injective \hspace{0.75in} surjective \hspace{0.75in} bijective
\end{center}
%
Determine the properties of the functions below, and briefly explain
your reasoning.

\bparts

\ppart The function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = e^x$.

\solution{This function is injective, since $e^x$ takes on each
nonnegative real value for exactly one $x$.  However, the function is
not surjective, because $e^x$ never takes on negative values.
Therefore, the function is not bijective either.}

\ppart The function $f : \mathbb{R} \to \mathbb{R}^+$ defined by $f(x)
= e^x$.

\solution{The function $e^x$ takes on every nonnegative value for
exactly one $x$, so it is injective, surjective, and bijective.}

\ppart The function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) =
(x + 1) x (x - 1)$.

\solution{This function is surjective, since it is continuous, it
tends to $+\infty$ for large positive $x$, and tends to $-\infty$ for
large negative $x$.  Thus, the function takes on each real value for
at least one $x$.  However, this function is not injective, since it
takes on the value 0 at $x = -1$, $x = 0$, and $x = 1$.  Therefore, the
function is not bijective either.}

\ppart Let $S$ be the set of all $20$-bit sequences.  Let $T$ be the
set of all $10$-bit sequences.  Let $f : S \to T$ map each 20-bit
sequence to its first 10 bits.  For example:
%
\[
f(\underline{1111011010}1101010010) = 1111011010
\]

\solution{This function is surjective since the sequence $b_1 b_2
\ldots b_{10}$ is mapped to by $b_1 b_2 \ldots b_{10} 0 0 \ldots 0$,
for example.  However, the function is not injective, because this
sequence is also mapped to by $b_1 b_2 \ldots b_{10} 1 1 \ldots 1$.
Consequently, the function is not bijective either.}

\eparts

\end{problem}

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

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

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

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

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

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

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

\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*}
\size{D_2 \cup D_3 \cup D_5}
    & = \size{D_2} + \size{D_3} + \size{D_5} \\
    & \quad - \size{D_2 \cap D_3} - \size{D_2 \cap D_5} - \size{D_3 \cap D_5}\\
    & \quad + \size{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}

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

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

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

\iffalse
\begin{problem}
A positive integer is called {\em cubish} if it is divisible by the
cube of any positive integer greater than 1.  For example, 54 is
cubish (since it is divisible by $3^3 = 27$), but 175 is not cubish.
Use the inclusion-exclusion formula to compute the number of cubish
integers in the set $\set{1, 2, 3, \ldots, 1000}$.
\end{problem}

\solution{Every cubish number less than 1000 must be a multiple of
$2^3$, $3^3$, $5^3$, or $7^3$.  The number of integers in $\set{1, 2,
3, \ldots, 1000}$ that are multiples of $c^3$ is $\lfloor 1000 / c^3
\rfloor$, which is equal to 0 if $c > 10$.  Therefore, by the
inclusion-exclusion formula, the number of cubish numbers is:
%
\[
\left\lfloor\frac{1000}{2^3}\right\rfloor
+ \left\lfloor\frac{1000}{3^3}\right\rfloor
+ \left\lfloor\frac{1000}{5^3}\right\rfloor
+ \left\lfloor\frac{1000}{7^3}\right\rfloor
- \left\lfloor\frac{1000}{2^3 \ 3^3}\right\rfloor
- \left\lfloor\frac{1000}{2^3 \ 5^3}\right\rfloor
\]

All other terms are 0.  This expression simplifies to 167.}
\fi

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

\begin{problem}
A \textit{balanced parentheses string} is a sequence of left and right
parentheses such that
%
\begin{itemize}
\item the total number of left and right parentheses is equal, and
\item the number of left parentheses is greater than or equal to the number of right parentheses in every prefix.
\end{itemize}
%
For example:
%
\begin{center}
\begin{tabular}{c|cl}
Balanced & \multicolumn{2}{c}{Not Balanced} \\ \hline
(()) & ((() & \text{more left than right}\\
()(()) & ())()( & \text{fewer left than right in prefix ())}
\end{tabular}
\end{center}

Let $C_n$ be the number of balanced parentheses strings with $2n$
parentheses.  The values $C_0, C_1, C_2, \ldots$ are the
\textit{Catalan numbers}, which come up in dozens of different
counting problems.  Here are the first few Catalan numbers:
%
\[
\begin{array}{c|ccccccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline
C_n & 1 & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & 16796 & 58786 & 208012
\end{array}
\]

\bparts

\ppart Verify the first four entries by listing all balanced
parentheses strings with at most 6 parentheses.  (Don't forget the
empty string!)

\solution{
Here are all the balanced parentheses strings with at most 6 parentheses:
%
\begin{align*}
\text{empty} && () && ()() && (()) \\
()(()) && (())() && (()()) && ((())) && ()()()
\end{align*}
%
Therefore, $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, and $C_3 = 5$ as claimed
in the table.}

\ppart A path from $(0,0)$ to $(n,n)$ consisting of unit steps upward
or rightward is \textit{safe} if it does not cross the diagonal
boundary of the Flaming Chasm of Hideous Death.
%
\begin{center}
\begin{picture}(200,220)(0,-20)
\thinlines
\multiput(0,0)(20,0){11}{\line(0,1){200}}
\multiput(0,0)(0,20){11}{\line(1,0){200}}
\thicklines
\put(10,0){\line(1,1){190}}
\put(100,50){\colorbox{white}{\parbox{52pt}{Flaming Chasm of Hideous Death}}}
\linethickness{2pt}
\put(0,0){\line(0,1){20}}
\put(0,20){\line(1,0){20}}
\put(20,20){\line(0,1){40}}
\put(20,60){\line(1,0){20}}
\put(40,60){\line(0,1){60}}
\put(40,120){\line(1,0){40}}
\put(80,120){\line(0,1){20}}
\put(80,140){\line(1,0){60}}
\put(140,140){\line(0,1){60}}
\put(140,200){\line(1,0){60}}
\put(100,-10){\makebox(0,0){A Safe Path}}
\end{picture}
\quad
\begin{picture}(200,220)(0,-20)
\thinlines
\multiput(0,0)(20,0){11}{\line(0,1){200}}
\multiput(0,0)(0,20){11}{\line(1,0){200}}
\thicklines
\put(10,0){\line(1,1){190}}
\put(100,50){\colorbox{white}{\parbox{52pt}{Flaming Chasm of Hideous Death}}}
\linethickness{2pt}
\put(0,0){\line(0,1){20}}
\put(0,20){\line(1,0){60}}
\put(60,20){\line(0,1){100}}
\put(60,120){\line(1,0){20}}
\put(80,120){\line(0,1){20}}
\put(80,140){\line(1,0){60}}
\put(140,140){\line(0,1){40}}
\put(140,180){\line(1,0){20}}
\put(160,180){\line(0,1){20}}
\put(160,200){\line(1,0){40}}
\put(100,-10){\makebox(0,0){An Unsafe Path}}
\end{picture}
\end{center}
%
Show that there are exactly $C_n$ safe paths by describing a bijection
with balanced parentheses strings.

\ppart Many computational geometry algorithms begin by partitioning
polygons into triangles with the same vertices.  For example, here are
all the possible triangulations of a pentagon:
%
\begin{center}
\begin{picture}(72,72)
\put(0,48){\line(5,-4){60}}
\put(60,0){\line(-1,3){24}}
\thicklines
\put(12,0){\line(1,0){48}}
\put(12,0){\line(-1,4){12}}
\put(60,0){\line(1,4){12}}
\put(36,72){\line(-3,-2){36}}
\put(36,72){\line(3,-2){36}}
\end{picture}
%
\begin{picture}(72,72)
\put(0,48){\line(5,-4){60}}
\put(0,48){\line(1,0){72}}
\thicklines
\put(12,0){\line(1,0){48}}
\put(12,0){\line(-1,4){12}}
\put(60,0){\line(1,4){12}}
\put(36,72){\line(-3,-2){36}}
\put(36,72){\line(3,-2){36}}
\end{picture}
%
\begin{picture}(72,72)
\put(12,0){\line(1,3){24}}
\put(60,0){\line(-1,3){24}}
\thicklines
\put(12,0){\line(1,0){48}}
\put(12,0){\line(-1,4){12}}
\put(60,0){\line(1,4){12}}
\put(36,72){\line(-3,-2){36}}
\put(36,72){\line(3,-2){36}}
\end{picture}
%
\begin{picture}(72,72)
\put(12,0){\line(5,4){60}}
\put(0,48){\line(1,0){72}}
\thicklines
\put(12,0){\line(1,0){48}}
\put(12,0){\line(-1,4){12}}
\put(60,0){\line(1,4){12}}
\put(36,72){\line(-3,-2){36}}
\put(36,72){\line(3,-2){36}}
\end{picture}
%
\begin{picture}(72,72)
\put(12,0){\line(5,4){60}}
\put(12,0){\line(1,3){24}}
\thicklines
\put(12,0){\line(1,0){48}}
\put(12,0){\line(-1,4){12}}
\put(60,0){\line(1,4){12}}
\put(36,72){\line(-3,-2){36}}
\put(36,72){\line(3,-2){36}}
\end{picture}
\end{center}
%
Show that there are $C_n$ different ways to triangulate a convex
$(n+2)$-gon by describing a bijection from triangulations to balanced
parentheses strings.  (This problem is challenging; ask your TA for
help if you're stuck!)

\solution{Note that every nonempty balanced parentheses string has the
form $(\alpha)\beta$ since the first symbol must be $($ and there must
be a matching $)$.  Thus, every balanced parentheses string can be
decomposed into two smaller strings $\alpha$ and $\beta$.  We'll
exploit this fact to recursively map a balanced parentheses string to
a triangulation.

Suppose we have a not-yet-triangulated $(n+2)$-gon and a balanced
parentheses string $(\alpha)\beta$.  We must map the parentheses
string to a triangulation.

Select two consecutive vertices $x$ and $y$ and denote the remaining
vertices $v_0$, \ldots, $v_{n-1}$.  It must be that $\alpha$ contains
$j$ pairs of parentheses and $\beta$ contains the remaining $(n-1)-j$
pairs for some $j$ between 0 and $n-1$.  Draw a triangle with the
vertices $x$, $y$, and $v_j$.

\begin{center}
\includegraphics{triangulation}
\end{center}

This triangle partitions the polygon into a $(j+2)$-gon and a
$(n-j+1)$-gon.  Triangulate these polygons recursively using the
balanced parentheses strings $\alpha$ and $\beta$.  (Let $x$ and $v_j$
play the role of $x$ and $y$ in triangulation one side, and let $v_j$
and $y$ play the role of $x$ and $y$ on the other.)}

\eparts

\end{problem}

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

\begin{problem}
A \textit{derangement} is a permutation $(x_1, x_2, \ldots, x_n)$ of
the set $\set{1, 2, \ldots, 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.

\bparts

\ppart Let's first work on counting permutations of $\set{1, 2,
\ldots, n}$ that are \textit{not} derangements.  Let $S_i$ be the set
of all permutations $(x_1, x_2, \ldots, x_n)$ of the set $\set{1, 2,
\ldots, n}$ such that $x_i = i$.  Use the inclusion-exclusion formula
to express the number of non-derangements in terms of sizes of
intersections of the sets $S_1, \ldots, S_n$.

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

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

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

\ppart What is $\size{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, \ldots, n} - \set{i, j}$,
and so $\size{S_i \cap S_j} = (n-2)!$.}

\ppart What is $\size{S_{i_1} \cap S_{i_2} \cap \ldots \cap S_{i_k}}$
where $i_1, i_2, \ldots, i_k$ are all distinct?

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

\ppart How many terms in the expression in part (a) have the form
$\size{S_{i_1} \cap S_{i_2} \cap \ldots \cap S_{i_k}}$?

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

\ppart Combine your answers to the preceding parts to get a (messy)
expression for the number of \textit{non}-derangements.

\solution{
\begin{align*}
\lefteqn{\sum_i \size{S_i}
- \sum_{i,j} \size{S_i \cap S_j}
+ \sum_{i,j,k} \size{S_i \cap S_j \cap S_k}
- \ldots
\pm \size{S_1 \cap S_2 \cap \ldots \cap S_n}} \quad \\
    & = \binom{n}{1} \cdot (n-1)!
      - \binom{n}{2} \cdot (n-2)!
      + \binom{n}{3} \cdot (n-3)!
      - \ldots
      \pm \binom{n}{n} \cdot 0! \\
    & = n! \paren{\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \ldots \pm \frac{1}{n!}}
\end{align*}
}

\ppart Now give an expression for the number of derangements.

\solution{
\[
n! \paren{1 - \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \ldots \pm \frac{1}{n!}}
\]
}

\ppart As $n$ goes to infinity, this expression approaches a constant
fraction of all permutations.  What is that constant?  Recall that:
%
\[
e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots
\]

\solution{$1/e$}

\eparts

\end{problem}

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

\end{document}
