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

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

\begin{document}
\lecturenotes{9}{Counting, I.}


{\scriptsize
\[
\begin{array}{rrrr}
  20480135385502964448038 &
3171004832173501394113017 &
5763257331083479647409398 &
8247331000042995311646021 \\
 489445991866915676240992 &
3208234421597368647019265 &
5800949123548989122628663 &
8496243997123475922766310 \\
1082662032430379651370981 &
3437254656355157864869113 &
6042900801199280218026001 &
8518399140676002660747477 \\
1178480894769706178994993 &
3574883393058653923711365 &
6116171789137737896701405 &
8543691283470191452333763 \\
1253127351683239693851327 &
3644909946040480189969149 &
6144868973001582369723512 &
8675309258374137092461352 \\
1301505129234077811069011 &
3790044132737084094417246 &
6247314593851169234746152 &
8694321112363996867296665 \\
1311567111143866433882194 &
3870332127437971355322815 &
6814428944266874963488274 &
8772321203608477245851154 \\
1470029452721203587686214 &
4080505804577801451363100 &
6870852945543886849147881 &
8791422161722582546341091 \\
1578271047286257499433886 &
4167283461025702348124920 &
6914955508120950093732397 &
9062628024592126283973285 \\
1638243921852176243192354 &
4235996831123777788211249 &
6949632451365987152423541 &
9137845566925526349897794 \\
1763580219131985963102365 &
4670939445749439042111220 &
7128211143613619828415650 &
9153762966803189291934419 \\
1826227795601842231029694 &
4815379351865384279613427 &
7173920083651862307925394 &
9270880194077636406984249 \\
1843971862675102037201420 &
4837052948212922604442190 &
7215654874211755676220587 &
9324301480722103490379204 \\
2396951193722134526177237 &
5106389423855018550671530 &
7256932847164391040233050 &
9436090832146695147140581 \\
2781394568268599801096354 &
5142368192004769218069910 &
7332822657075235431620317 &
9475308159734538249013238 \\
2796605196713610405408019 &
5181234096130144084041856 &
7426441829541573444964139 &
9492376623917486974923202 \\
2931016394761975263190347 &
5198267398125617994391348 &
7632198126531809327186321 &
9511972558779880288252979 \\
2933458058294405155197296 &
5317592940316231219758372 &
7712154432211912882310511 &
9602413424619187112552264 \\
3075514410490975920315348 &
5384358126771794128356947 &
7858918664240262356610010 &
9631217114906129219461111 \\
3111474985252793452860017 &
5439211712248901995423441 &
7898156786763212963178679 &
9908189853102753335981319 \\
3145621587936120118438701 &
5610379826092838192760458 &
8147591017037573337848616 &
9913237476341764299813987 \\
3148901255628881103198549 &
5632317555465228677676044 &
8149436716871371161932035 \\
3157693105325111284321993 &
5692168374637019617423712 &
8176063831682536571306791
\end{array}
\]
}

Two different subsets of the ninety 25-digit numbers shown above have
the same sum.  For example, maybe the sum of the numbers in the first
column is equal to the sum of the numbers in the second column.  Can
you find two such subsets?  This is a very difficult computational
problem.  But we'll prove that such subsets must exist!  This is the
sort of weird conclusion one can reach by tricky use of counting, the
topic of this chapter.

Counting seems easy enough: 1, 2, 3, 4, etc.  This explicit approach
works well for counting simple things, like your toes, and for
extremely complicated things for which there's no identifiable
structure.  However, subtler methods can help you count many things in
the vast middle ground, such as:

\begin{itemize}

\item The number of different ways to select a dozen doughnuts when
there are five varieties available.

\item The number of 16-bit numbers with exactly 4 ones.

\end{itemize}

Counting is useful in computer science for several reasons:

\begin{itemize}

\item Determining the time and storage required to solve a
computational problem--- a central objective in computer science---
often comes down to solving a counting problem.

\item Counting is the basis of probability theory, which in turn is
perhaps the most important topic this term.

\item Two remarkable proof techniques, the ``pigeonhole principle''
and ``combinatorial proof'', rely on counting.  These lead to a
variety of interesting and useful insights.

\end{itemize}

We're going to present a lot of rules for counting.  These rules are
actually theorems, but we're generally not going to prove them.  Our
objective is to teach you counting as a practical skill, like
integration.  And most of the rules seem ``obvious'' anyway.

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

\section{Counting One Thing by Counting Another}

How do you count the number of people in a crowded room?  We could
count heads, since for each person there is exactly one head.
Alternatively, we could count ears and divide by two.  Of course, we
might have to adjust the calculation if someone lost an ear in a
pirate raid or someone was born with three ears.  The point here is
that we can often \textit{count one thing by counting another}, though
some fudge factors may be required.  This is the central theme of
counting, from the easiest problems to the hardest.

In more formal terms, every counting problem comes down to determining
the size of some set.  The \term{size} or \term{cardinality} of a set
$S$ is the number of elements in $S$ and is denoted $\card{S}$.  In
these terms, we're claiming that we can often \textit{find the size of
one set $S$ by finding the size of a related set $T$.}  We already
have a mathematical tool for relating one set to another: relations.
Not surprisingly, a particular kind of relation is at the heart of
counting.

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

\subsection{The Bijection Rule}

If we can pair up all the girls at a dance with all the boys, then
there must be an equal number of each.  This simple observation
generalizes to a powerful counting rule:

\begin{mathrule}[Bijection Rule]
If there exists a bijection $f : A \to B$, then $\card{A} = \card{B}$.
\end{mathrule}

In the example, $A$ is the set of boys, $B$ is the set of
girls, and the function $f$ defines how they are paired.

The Bijection Rule acts as a magnifier of counting ability; if you
figure out the size of one set, then you can immediately determine the
sizes of many other sets via bijections.  For example, let's return to
two sets mentioned earlier:
%
\begin{align*}
A & = \text{all ways to select a dozen doughnuts when five varieties are available} \\
B & = \text{all 16-bit sequences with exactly 4 ones}
\end{align*}

Let's consider a particular element of set $A$:
%
\[
\underbrace{0\ 0}_{\text{chocolate}} \quad
\underbrace{}_{\text{lemon-filled}} \quad
\underbrace{0\ 0\ 0\ 0\ 0\ 0}_{\text{sugar}} \quad
\underbrace{0\ 0}_{\text{glazed}} \quad
\underbrace{0\ 0}_{\text{plain}}
\]
%
We've depicted each doughnut with a $0$ and left a gap between the
different varieties.  Thus, the selection above contains two chocolate
doughnuts, no lemon-filled, six sugar, two glazed, and two plain.  Now
let's put a 1 into each of the four gaps:
%
\[
\underbrace{0\ 0}_{\text{chocolate}} \quad 1 \quad
\underbrace{}_{\text{lemon-filled}} \quad 1 \quad
\underbrace{0\ 0\ 0\ 0\ 0\ 0}_{\text{sugar}} \quad 1 \quad
\underbrace{0\ 0}_{\text{glazed}} \quad 1 \quad
\underbrace{0\ 0}_{\text{plain}}
\]
%
We've just formed a 16-bit number with exactly 4 ones--- an element of
$B$!

This example suggests a bijection from set $A$ to set $B$: map a dozen
doughnuts consisting of:
%
\[
\text{$c$ chocolate, $l$ lemon-filled, $s$ sugar, $g$ glazed, and $p$ plain}
\]
%
to the sequence:
%
\[
\underbrace{\ 0 \ldots 0\ }_{\text{$c$}} \quad 1 \quad
\underbrace{\ 0 \ldots 0\ }_{\text{$l$}} \quad 1 \quad
\underbrace{\ 0 \ldots 0\ }_{\text{$s$}} \quad 1 \quad
\underbrace{\ 0 \ldots 0\ }_{\text{$g$}} \quad 1 \quad
\underbrace{\ 0 \ldots 0\ }_{\text{$p$}}
\]

The resulting sequence always has 16 bits and exactly 4
ones, and thus is an element of $B$.  Moreover, the mapping is a
bijection; every such bit sequence is mapped to by exactly one order
of a dozen doughnuts.  Therefore, $\card{A} = \card{B}$ by the
Bijection Rule!

This demonstrates the magnifying power of the bijection rule.  We
managed to prove that two very different sets are actually the same
size--- even though we don't know exactly how big either one is.  But
as soon as we figure out the size of one set, we'll immediately know
the size of the other.

This particular bijection might seem frighteningly ingenious if you've
not seen it before.  But you'll use essentially this same argument
over and over, and soon you'll consider it boringly routine.

\subsection{Sequences}

The Bijection Rule lets us count one thing by counting another.  This
suggests a general strategy: get really good at counting just a
\textit{few} things and then use bijections to count \textit{everything
else}.  This is the strategy we'll follow.  In particular, we'll get
really good at counting \textit{sequences}.  When we want to determine the
size of some other set $T$, we'll find a bijection from $T$ to a set of
sequences $S$.  Then we'll use our super-ninja sequence-counting skills to
determine $\card{S}$, which immediately gives us $\card{T}$.  We'll need
to hone this idea somewhat as we go along, but that's pretty much the
plan!


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

\section{Two Basic Counting Rules}

We'll harvest our first crop of counting problems with two basic
rules.

\subsection{The Sum Rule}

Linus allocates his big sister Lucy a quota of 20 crabby days, 40
irritable days, and 60 generally surly days.  On how many days can
Lucy be out-of-sorts one way or another?  Let set $C$ be her crabby
days, $I$ be her irritable days, and $S$ be the generally surly.  In
these terms, the answer to the question is $\card{C \cup I \cup S}$.
Now assuming that she is permitted at most one bad quality each day,
the size of this union of sets is given by the Sum Rule:

\begin{mathrule}[Sum Rule]
If $A_1, A_2, \ldots, A_n$ are disjoint sets, then:
%
\[
\card{A_1 \cup A_2 \cup \ldots \cup A_n}
    = \card{A_1} + \card{A_2} + \ldots + \card{A_n}
\]
\end{mathrule}

Thus, according to Linus' budget, Lucy can be out-of-sorts for:
%
\begin{align*}
\card{C \cup I \cup S}
    & = \card{C} \cup \card{I} \cup \card{S} \\
    & = 20 + 40 + 60 \\
    & = 120 \text{ days}
\end{align*}

Notice that the Sum Rule holds only for a union of {\em disjoint}
sets.  Finding the size of a union of intersecting sets is a more
complicated problem that we'll take up later.

\subsection{The Product Rule}

The product rule gives the size of a product of sets.  Recall that if
$P_1, P_2, \ldots, P_n$ are sets, then
%
\[
P_1 \times P_2 \times \ldots \times P_n
\]
%
is the set of all sequences whose first term is drawn from $P_1$,
second term is drawn from $P_2$ and so forth.

\begin{mathrule}[Product Rule]
If $P_1, P_2, \ldots P_n$ are sets, then:
%
\begin{align*}
\card{P_1 \times P_2 \times \ldots \times P_n}
    & = \card{P_1} \cdot \card{P_2} \cdots \card{P_n}
\end{align*}
\end{mathrule}

Unlike the sum rule, the product rule does not require the sets $P_1,
\ldots, P_n$ to be disjoint.  For example, suppose a {\em daily diet}
consists of a breakfast selected from set $B$, a lunch from set $L$,
and a dinner from set $D$:
%
\begin{align*}
B & = \set{\text{pancakes},
      	   \text{bacon and eggs},
           \text{bagel},
           \text{Doritos}} \\
L & = \set{\text{burger and fries},
           \text{garden salad},
           \text{Doritos}} \\
D & = \set{\text{macaroni},
           \text{pizza},
           \text{frozen burrito},
           \text{pasta},
           \text{Doritos}}
\end{align*}
%
Then $B \times L \times D$ is the set of all possible daily diets.
Here are some sample elements:
%
\begin{gather*}
(\text{pancakes}, \text{burger and fries}, \text{pizza}) \\
(\text{bacon and eggs}, \text{garden salad}, \text{pasta}) \\
(\text{Doritos}, \text{Doritos}, \text{frozen burrito})
\end{gather*}
%
The Product Rule tells us how many different daily diets are possible:
%
\begin{align*}
\card{B \times L \times D}
    & = \card{B} \cdot \card{L} \cdot \card{D} \\
    & = 4 \cdot 3 \cdot 5 \\
    & = 60
\end{align*}

\subsection{Putting Rules Together}

Few counting problems can be solved with a single rule.  More often, a
solution is a flury of sums, products, bijections, and other methods.
Let's look at some examples that bring more than one rule into play.

\subsubsection*{Passwords}

The sum and product rules together are useful for solving problems
involving passwords, telephone numbers, and license plates.  For
example, on a certain computer system, a valid password is a sequence
of between six and eight symbols.  The first symbol must be a letter
(which can be lowercase or uppercase), and the remaining symbols must
be either letters or digits.  How many different passwords are
possible?

Let's define two sets, corresponding to valid symbols in the first and
subsequent positions in the password.
%
\begin{align*}
F & = \set{ a, b, \ldots, z, A, B, \ldots, Z } \\
S & = \set{ a, b, \ldots, z, A, B, \ldots, Z, 0, 1, \ldots, 9 }
\end{align*}
%
In these terms, the set of all possible passwords is:
%
\[
(F \times S^5) \cup (F \times S^6) \cup (F \times S^7)
\]
%
Thus, the length-six passwords are in set $F \times S^5$, the
length-seven passwords are in $F \times S^6$, and the length-eight
passwords are in $F \times S^7$.  Since these sets are disjoint, we
can apply the Sum Rule and count the total number of possible
passwords as follows:
%
\begin{align*}
\card{(F \times S^5) \cup (F \times S^6) \cup (F \times S^7)}
    & = \card{F \times S^5} + \card{F \times S^6} + \card{F \times S^7}
        & \text{Sum Rule} \\
    & = \card{F} \cdot \card{S}^5 +
          \card{F} \cdot \card{S}^6 +
          \card{F} \cdot \card{S}^7
        & \text{Product Rule} \\
    & = 52 \cdot 62^5 + 52 \cdot 62^6 + 52 \cdot 62^7 \\
    & \approx 1.8 \cdot 10^{14} \text{ different passwords}
\end{align*}

\subsubsection*{Subsets of an $n$-element Set}

How many different subsets of an $n$ element set $X$ are there?  For
example, the set $X = \set{x_1, x_2, x_3}$ has eight different subsets:
%
\[
\begin{array}{cccc}
\set{} & \set{x_1} & \set{x_2} & \set{x_1, x_2} \\
\set{x_3} & \set{x_1, x_3} & \set{x_2, x_3} & \set{x_1, x_2, x_3}
\end{array}
\]

There is a natural bijection from subsets of $X$ to $n$-bit sequences.
Let $x_1, x_2, \ldots, x_n$ be the elements of $X$.  Then a particular
subset of $X$ maps to the sequence $(b_1, \ldots, b_n)$ where $b_i =
1$ if and only if $x_i$ is in that subset.  For example, if $n = 10$,
then the subset $\set{x_2, x_3, x_5, x_7, x_{10}}$ maps to a 10-bit
sequence as follows:
%
\[
\begin{array}{rrrrrrrrrrrrr}
\text{subset:} &
\{ &    & x_2, & x_3, &    & x_5, &   & x_7, &    &    & x_{10} & \} \\
\text{sequence:} &
(  & 0, &   1, &   1, & 0, &   1, & 0, &   1, & 0, & 0, &        1 & )
\end{array}
\]
%
We just used a bijection to transform the original problem into a
question about sequences--- \textit{exactly according to plan!}  Now
if we answer the sequence question, then we've solved our original
problem as well.

But how many different $n$-bit sequences are there?  For example,
there are 8 different 3-bit sequences:
%
\[
\begin{array}{ccccccc}
(0,0,0) & \quad & (0,0,1) & \quad & (0,1,0) & \quad & (0,1,1) \\
(1,0,0) & \quad & (1,0,1) & \quad & (1,1,0) & \quad & (1,1,1)
\end{array}
\]

Well, we can write the set of all $n$-bit sequences as a product of
sets:
%
\[
\underbrace{\set{0,1} \times \set{0,1} \times
        \ldots \times \set{0,1}}_{\text{$n$ terms}} = \set{0,1}^n
\]
%
Then Product Rule gives the answer:
%
\begin{align*}
\card{\set{0,1}^n}
    & = \card{\set{0,1}}^n \\
    & = 2^n
\end{align*}

This means that the number of subsets of an $n$-element set $X$ is
also $2^n$.  We'll put this answer to use shortly.

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

\section{More Functions: Injections and Surjections}

Bijections are both injective and surjective, which makes them a powerful
tool for exact counting.  We've observed in earlier Notes that surjections and
injections by themselves imply certain size relationships between sets:

\begin{mathrule}[Mapping Rule] \mbox{}
\begin{enumerate}

\item If $f : X \to Y$ is surjective, then $\card{X} \geq \card{Y}$.

\item\label{in<} If $f : X \to Y$ is injective, then $\card{X} \leq \card{Y}$.

\item If $f : X \to Y$ is bijective, then $\card{X} = \card{Y}$.

\end{enumerate}
\end{mathrule}

\subsection{The Pigeonhole Principle}

Here is an old puzzle:

\begin{quotation}
A drawer in a dark room contains red socks, green socks, and
blue socks.  How many socks must you withdraw to be sure that you have
a matching pair?
\end{quotation}

For example, picking out three socks is not enough; you might end up with
one red, one green, and one blue.  The solution relies on the Pigeonhole
Principle, which is a friendly name for the contrapositive of
part~\eqref{in<} of the Mapping Rule.  Let's write it down:

\begin{quotation}
If $\card{X} > \card{Y}$, then no function $f : X \to Y$ is
injective.
\end{quotation}

And now rewrite it again to eliminate the word ``injective.''

\begin{mathrule}[Pigeonhole Principle]
If $\card{X} > \card{Y}$, then for every function $f : X \to Y$, there
exist two different elements of $X$ that are mapped to the same
element of $Y$.
\end{mathrule}

Perhaps the relevance of this abstract mathematical statement to
selecting footwear under poor lighting conditions is not obvious.
However, let $A$ be the set of socks you pick out, let $B$ be the set
of colors available, and let $f$ map each sock to its color.  The
Pigeonhole Principle says that if $\card{A} > \card{B} = 3$, then at
least two elements of $A$ (that is, at least two socks) must be mapped
to the same element of $B$ (that is, the same color).  For example,
one possible mapping of four socks to three colors is shown below.

\begin{center}
\begin{picture}(145,100)(0,-10)
%\put(0,-10){\dashbox(145,100){}}
\put(24,80){\makebox(0,0){$A$}}
\put(80,80){\makebox(0,0){$f$}}
\put(125,80){\makebox(0,0){$B$}}
\put(48,60){\makebox(0,6)[tr]{1st sock}}
\put(48,40){\makebox(0,6)[tr]{2nd sock}}
\put(48,20){\makebox(0,6)[tr]{3rd sock}}
\put(48,0){\makebox(0,6)[tr]{4th sock}}
\put(110,60){\makebox(0,6)[tl]{red}}
\put(110,40){\makebox(0,6)[tl]{green}}
\put(110,20){\makebox(0,6)[tl]{blue}}
\put(50,60){\vector(1,0){58}}
\put(50,40){\vector(1,0){58}}
\put(50,20){\vector(1,0){58}}
\put(50,0){\vector(3,2){58}}
\end{picture}
\end{center}

Therefore, four socks are enough to ensure a matched pair.

Not surprisingly, the pigeonhole principle is often described in terms
of pigeons:
\begin{quote}
\emph{If every pigeon flies into a pigeonhole, and there are more pigeons
than holes, then at least two pigeons must fly into some hole.}
\end{quote}
In this case, the pigeons form set $A$, the pigeonholes are set $B$, and
$f$ describes which hole each pigeon flies into.

Mathematicians have come up with many ingenious applications for the
pigeonhole principle.  If there were a cookbook procedure for
generating such arguments, we'd give it to you.  Unfortunately, there
isn't one.  One helpful tip, though: when you try to solve a problem
with the pigeonhole principle, the key is to clearly identify three
things:

\begin{enumerate}

\item The set $A$ (the pigeons).

\item The set $B$ (the pigeonholes).

\item The function $f$ (the rule for assigning pigeons to pigeonholes).

\end{enumerate}

\subsection*{Hairs on Heads}

There are a number of generalizations of the pigeonhole principle.
For example:

\begin{mathrule}[Generalized Pigeonhole Principle]
If $\card{X} > k \cdot \card{Y}$, then every function $f : X \to Y$
maps at least $k+1$ different elements of $X$ to the same element of
$Y$.
\end{mathrule}

For example, if you pick two people at random, surely they are
extremely unlikely to have \textit{exactly} the same number of hairs
on their heads.  However, in the remarkable city of Boston,
Massachusetts there are actually \textit{three} people who have
exactly the same number of hairs!  Of course, there are many bald
people in Boston, and they all have zero hairs.  But we're talking about
non-bald people.

Boston has about 500,000 non-bald peole, and the number of hairs on a
person's head is at most 200,000.  Let $A$ be the set of non-bald
people in Boston, let $B = \set{1, \ldots, 200,000}$, and let $f$ map
a person to the number of hairs on his or her head.  Since $\card{A} >
2 \card{B}$, the Generalized Pigeonhole Principle implies that at
least three people have exactly the same number of hairs.  We don't
know who they are, but we know they exist!

\subsection*{Subsets with the Same Sum}

We asserted that two different subsets of the ninety 25-digit numbers
listed on the first page have the same sum.  This actually follows
from the Pigeonhole Principle.  Let $A$ be the collection of all
subsets of the 90 numbers in the list.  Now the sum of any subset of
numbers is at most $90 \cdot 10^{25}$, since there are only 90 numbers
and every 25-digit number is less than $10^{25}$.  So let $B$ be the
set of integers $\set{0, 1, \ldots, 90 \cdot 10^{25}}$, and let $f$
map each subset of numbers (in $A$) to its sum (in $B$).

We proved that an $n$-element set has $2^n$ different subsets.
Therefore:
%
\begin{align*}
\card{A}
    & = 2^{90} \\
    & \geq 1.237 \times 10^{27}
\end{align*}
%
On the other hand:
%
\begin{align*}
\card{B}
    & = 90 \cdot 10^{25} + 1 \\
    & \leq 0.901 \times 10^{27}
\end{align*}
%
Both quantities are enormous, but $\card{A}$ is a bit greater than
$\card{B}$.  This means that $f$ maps at least two elements of $A$ to
the same element of $B$.  In other words, by the Pigeonhole Principle,
two different subsets must have the same sum!

Notice that this proof gives no indication \textit{which} two sets of
numbers have the same sum.  This frustrating variety of argument is
called a \term{nonconstructive proof}.

\iffalse
\begin{quotation}
\textbf{CONTEST: There is a \$100 prize for being the first
6.042 student to actually \underline{find} two different subsets of
the ninety 25-digit numbers on the first page that have the same sum.
Send results to e\underline{\hspace{1ex}}lehman@mit.edu.  The contest
expires at the end of the 6.042 final.}
\end{quotation}
\fi

\begin{figure}[htbp]
\textbox{
\begin{center}
{\textbf {\Large Sets with Distinct Subset Sums}}
\end{center}

How can we construct a set of $n$ positive integers such that all its
subsets have {\em distinct} sums?  One way is to use powers of two:
\[
\set{1, 2, 4, 8, 16}
\]
This approach is so natural that one suspects all other such sets must
involve larger numbers.  (For example, we could safely replace 16 by
17, but not by 15.)  Remarkably, there are examples involving {\em
smaller} numbers.  Here is one:
\[
\set{6, 9, 11, 12, 13}
\]
One of the top mathematicans of the century, Paul Erd\H{o}s, conjectured
in 1931 that there are no such sets involving {\em significantly} smaller
numbers.  More precisely, he conjectured that the largest number must be
$> c2^n$ for some constant $c>0$.  He offered \$500 to anyone who could
prove or disprove his conjecture, but the problem remains unsolved.}
\end{figure}


\section{The Generalized Product Rule}

We realize everyone has been working pretty hard this term, and we're
considering awarding some prizes for \textit{truly exceptional}
coursework.  Here are some possible categories:

\begin{description}

\item[Best Administrative Critique] We asserted that the quiz was
closed-book.  On the cover page, one strong candidate for this award
wrote, ``There is no book.''

\item[Awkward Question Award] ``Okay, the left sock, right sock, and
pants are in an antichain, but how--- even with assistance--- could I
put on all three at once?''

\item[Best Collaboration Statement] Inspired by a student who wrote
``I worked alone'' on Quiz 1.

\end{description}

In how many ways can, say, three different prizes be awarded to $n$
people?  This is easy to answer using our startegy of translating the
problem about awards into a problem about sequences.  Let $P$ be the set
of $n$ people in 6.042.  Then there is a bijection from ways of awarding
the three prizes to the set $P^3 \eqdef P \times P \times P$.  In
particular, the assignment:
%
\begin{center}
``person $x$ wins prize \#1, $y$ wins prize \#2, and $z$ wins prize \#3''
\end{center}
%
maps to the sequence $(x, y, z)$.  By the Product Rule, we have
$\card{P^3}= \card{P}^3 = n^3$, so there are $n^3$ ways to award the
prizes to a class of $n$ people.

But what if the three prizes must be awarded to \textit{different}
students?  As before, we could map the assignment
%
\begin{center}
``person $x$ wins prize \#1, $y$ wins prize \#2, and $z$ wins prize \#3''
\end{center}
%
to the triple $(x, y, z) \in P^3$.  But this function is \textit{no longer
a bijection}.  For example, no valid assignment maps to the triple (Dave,
Dave, Becky) because Dave is not allowed to receive two awards.  However,
there \textit{is} a bijection from prize assignments to the set:
%
\[
S = \set{(x, y, z) \in P^3 \mid \text{$x$, $y$, and $z$ are different people}}
\]
%
This reduces the original problem to a problem of counting sequences.
Unfortunately, the Product Rule is of no help in counting sequences of
this type because the entries depend on one another; in particular,
they must all be different.  However, a slightly sharper tool does the
trick.

\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:
%
\[
\card{S} = n_1 \cdot n_2 \cdot n_3 \cdots n_k
\]
\end{mathrule}

In the awards example, $S$ consists of sequences $(x, y, z)$.  There
are $n$ ways to choose $x$, the recipient of prize \#1.  For each of
these, there are $n-1$ ways to choose $y$, the recipient of prize \#2,
since everyone except for person $x$ is eligible.  For each
combination of $x$ and $y$, there are $n-2$ ways to choose $z$, the
recipient of prize \#3, because everyone except for $x$ and $y$ is
eligible.  Thus, according to the Generalized Product Rule, there are
%
\[
\card{S} = n \cdot (n-1) \cdot (n-2)
\]
%
ways to award the 3 prizes to different people.

\subsection{Defective Dollars}

A dollar is \textit{defective} some digit appears more than once in
the 8-digit serial number.  If you check your wallet, you'll be sad to
discover that defective dollars are all-too-common.  In fact, how
common are \textit{nondefective} dollars?  Assuming that the digit
portions of serial numbers all occur equally often, we could answer
this question by computing:
%
\begin{align*}
\text{fraction dollars that are nondefective}
    & = \frac{\text{\# of serial \#'s with all digits different}}
             {\text{total \# of serial \#'s}}
\end{align*}
%
Let's first consider the denominator.  Here there are no restrictions;
there are are 10 possible first digits, 10 possible second digits, 10
third digits, and so on.  Thus, the total number of 8-digit serial
numbers is $10^8$ by the Product Rule.

Next, let's turn to the numerator.  Now we're not permitted to use any
digit twice.  So there are still 10 possible first digits, but only 9
possible second digits, 8 possible third digits, and so forth.  Thus, by
the Generalized Product Rule, there are
%
\begin{align*}
10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3
    & = \frac{10!}{2} \\
    & = 1,814,400
\end{align*}
%
serial numbers with all digits different.  Plugging these results into
the equation above, we find:
%
\begin{align*}
\text{fraction dollars that are nondefective}
    & = \frac{1,814,400}{100,000,000} \\
    & = 1.8144\%
\end{align*}

\subsection{A Chess Problem}

In how many different ways can we place a pawn ($p$), a knight ($k$),
and a bishop ($b$) on a chessboard so that no two pieces share a row
or a column?  A valid configuration is shown below on the left,
and an invalid configuration is shown on the right.
%
\[
\begin{array}{ccc}
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\ &\ &\ &\ &\ &\ &\ &\ \\ \hline
 & & & &k& & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 &b& & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & &p& & \\ \hline
 & & & & & & & \\ \hline
\end{array}
& \hspace{1in} &
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\ &\ &\ &\ &\ &\ &\ &\ \\ \hline
 & & & & & & & \\ \hline
 & & & &p& & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & &b& & &k& & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
\end{array} \\
\\
\text{valid} & & \text{invalid}
\end{array}
\]
%
First, we map this problem about chess pieces to a question about
sequences.  There is a bijection from configurations to sequences
%
\[
(r_p, c_p, r_k, c_k, r_b, c_b)
\]
%
where $r_p$, $r_k$, and $r_b$ are distinct rows and $c_p$, $c_k$, and
$c_b$ are distinct columns.  In particular, $r_p$ is the pawn's row,
$c_p$ is the pawn's column, $r_k$ is the knight's row, etc.  Now we
can count the number of such sequences using the Generalized Product
Rule:
%
\begin{center}
\begin{tabular}{l}
$\bullet$ $r_p$ is one of 8 rows \\
$\bullet$ $c_p$ is one of 8 columns \\
$\bullet$ $r_k$ is one of 7 rows (any one but $r_p$) \\
$\bullet$ $c_k$ is one of 7 columns (any one but $c_p$) \\
$\bullet$ $r_b$ is one of 6 rows (any one but $r_p$ or $r_k$) \\
$\bullet$ $c_b$ is one of 6 columns (any one but $c_p$ or $c_k$)
\end{tabular}
\end{center}
%
\noindent Thus, the total number of configurations is $(8 \cdot 7
\cdot 6)^2$.

\subsection{Permutations}

A \term{permutation} of a set $S$ is a sequence that contains 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?  Well, there
are $n$ choices for the first element.  For each of these, there are
$n - 1$ remaining choices for the second element.  For every
combination of the first two elements, there are $n - 2$ ways to
choose the third element, and so forth.  Thus, there are a total of
%
\[
n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1 = n!
\]
%
permutations of an $n$-element set.  In particular, this formula says
that there are $3! = 6$ permuations of the 3-element set $\set{a, b,
c}$, which is the number we found above.

Permutations will come up again in this course approximately 1.6
bazillion times.  In fact, permutations are the reason why factorial
comes up so often and why we taught you Stirling's approximation:
%
\[
n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\]


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

\section{The Division Rule}

We can count the number of people in a room by counting ears and
dividing by two.  Or we could count the number of fingers and divide
by 10.  Or we could count the number of fingers and toes and divide by
20.  (Someone is probably short a finger or has an extra ear,
%ERIC: maybe toe? -- maybe less funny, but more plausible
but let's not worry about that right now.)  These observations lead to an
important counting rule.

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}

\noindent Similarly, the function mapping each finger to its owner is
10-to-1.  And the function maping each each finger or toe to its owner
is 20-to-1.  Now just as a bijection implies two sets are the same
size, a $k$-to-1 function implies that the domain is $k$ times larger
than the domain:

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

Suppose $A$ is the set of ears in the room and $B$ is the set of
people.  Since we know there is a 2-to-1 mapping from ears to people,
the Division Rule says that $\card{A} = 2 \cdot \card{B}$ or,
equivalently, $\card{B} = \card{A} / 2$.  Thus, the number of people
is half the number of ears.

Now this might seem like a stupid way to count people.  But,
surprisingly, many counting problems are made much easier by initially
counting every item multiple times and then correcting the answer
using the Division Rule.  Let's look at some examples.

\subsection{Another Chess Problem}

In how many different ways can you place two identical rooks on a
chessboard so that they do not share a row or column?  A valid
configuration is shown below on the left, and an invalid configuration
is shown on the right.
%
\[
\begin{array}{ccc}
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\ &\ &\ &\ &\ &\ &\ &r \\ \hline
 & & & & & & &\ \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
r& & & & & & & \\ \hline
\end{array}
& \hspace{1in} &
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\ &\ &\ &\ &\ &\ &\ &\ \\ \hline
 & & & & & & & \\ \hline
 & & &r& & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & & & & & & \\ \hline
 & & &r& & & & \\ \hline
\end{array} \\
\\
\text{valid} & & \text{invalid}
\end{array}
\]

Let $A$ be the set of all sequences
%
\[
(r_1, c_1, r_2, c_2)
\]
%
where $r_1$ and $r_2$ are distinct rows and $c_1$ and $c_2$ are
distinct columns.  Let $B$ be the set of all valid rook
configurations.  There is a natural function $f$ from set $A$ to set
$B$; in particular, $f$ maps the sequence $(r_1, c_1, r_2, c_2)$ to a
configuration with one rook in row $r_1$, column $c_1$ and the other
rook in row $r_2$, column $c_2$.

But now there's a snag.  Consider the sequences:
%
\[
(1, 1, 8, 8) \qquad \text{ and } \qquad (8, 8, 1, 1)
\]
%
The first sequence maps to a configuration with a rook in the
lower-left corner and a rook in the upper-right corner.  The second
sequence maps to a configuration with a rook in the upper-right corner
and a rook in the lower-left corner.  The problem is that those are
two different ways of describing the \textit{same} configuration!  In
fact, this arrangement is shown on the left side in the diagram above.

More generally, the function $f$ map exactly two sequences to
\textit{every} board configuration; that is $f$ is a 2-to-1 function.
Thus, by the quotient rule, $\card{A} = 2 \cdot \card{B}$.
Rearranging terms gives:
%
\begin{align*}
\card{B}
    & = \frac{\card{A}}{2} \\
    & = \frac{(8 \cdot 7)^2}{2}
\end{align*}
%
On the second line, we've computed the size of $A$ using the General
Product Rule just as in the earlier chess problem.

\subsection{Knights of the Round Table}

In how many ways can King Arthur seat $n$ different knights at his
round table?  Two seatings are considered equivalent if one can be
obtained from the other by rotation.  For example, the following two
arrangements are equivalent:

\begin{center}
\begin{picture}(230,80)
%\put(0,0){\dashbox(230,80){}}
\put(0,0){
\begin{picture}(80,80)(-40,-40)
%\put(-40,-40){\dashbox(80,80){}}
\put(0,0){\circle{36}}
\put(0,26){\makebox(0,0){$k_1$}}
\put(26,0){\makebox(0,0){$k_2$}}
\put(0,-26){\makebox(0,0){$k_3$}}
\put(-26,0){\makebox(0,0){$k_4$}}
\end{picture}}
\put(150,0){
\begin{picture}(80,80)(-40,-40)
%\put(-40,-40){\dashbox(80,80){}}
\put(0,0){\circle{36}}
\put(0,26){\makebox(0,0){$k_3$}}
\put(26,0){\makebox(0,0){$k_4$}}
\put(0,-26){\makebox(0,0){$k_1$}}
\put(-26,0){\makebox(0,0){$k_2$}}
\end{picture}}
\end{picture}
\end{center}

Let $A$ be all the permutations of the knights, and let $B$ be the set
of all possible seating arrangements at the round table.  We can map
each permutaton in set $A$ to a circular seating arrangement in set
$B$ by seating the first knight in the permutation anywhere, putting
the second knight to his left, the third knight to the left of the
second, and so forth all the way around the table.  For example:
%
\begin{center}
\begin{picture}(200,80)(-160,-40)
%\put(-160,-40){\dashbox(200,80){}} % bounding box
\put(-120,0){\makebox(0,0){$(k_2, k_4, k_1, k_3)$}}
\put(-60,0){\makebox(0,0){$\implies$}}
\put(0,0){\circle{36}}
\put(0,26){\makebox(0,0){$k_2$}}
\put(26,0){\makebox(0,0){$k_4$}}
\put(0,-26){\makebox(0,0){$k_1$}}
\put(-26,0){\makebox(0,0){$k_3$}}
\end{picture}
\end{center}
%
This mapping is actually an $n$-to-1 function from $A$ to $B$, since
all $n$ cyclic shifts of the original sequence map to the same seating
arrangement.  In the example, $n = 4$ different sequences map to the
same seating arranement:
%
\begin{center}
\begin{picture}(200,80)(-160,-40)
% \put(-160,-40){\dashbox(200,80){}} % bounding box
\put(-120,24){\makebox(0,0){$(k_2, k_4, k_1, k_3)$}}
\put(-120,8){\makebox(0,0){$(k_4, k_1, k_3, k_2)$}}
\put(-120,-8){\makebox(0,0){$(k_1, k_3, k_2, k_4)$}}
\put(-120,-24){\makebox(0,0){$(k_3, k_2, k_4, k_1)$}}
\put(-60,0){\makebox(0,0){$\implies$}}
\put(0,0){\circle{36}}
\put(0,26){\makebox(0,0){$k_2$}}
\put(26,0){\makebox(0,0){$k_4$}}
\put(0,-26){\makebox(0,0){$k_1$}}
\put(-26,0){\makebox(0,0){$k_3$}}
\end{picture}
\end{center}
%
Therefore, by the division rule, the number of circular seating
arrangements is:
%
\begin{align*}
\card{B}
    & = \frac{\card{A}}{n} \\
    & = \frac{n!}{n} \\
    & = (n-1)!
\end{align*}
%
Note that $\card{A} = n!$ since there are $n!$ permutations of $n$
knights.

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

\section{Inclusion-Exclusion}

How big is a union of sets?  For example, suppose there are 60 Math
majors, 200 EECS majors, and 40 Physics majors.  How many students are
there in these three departments?  Let $M$ be the set of Math majors,
$E$ be the set of EECS majors, and $P$ be the set of Physics majors.  In
these terms, we're asking for $\card{M \cup E \cup P}$.

The Sum Rule says that the size of union of \textit{disjoint} sets is
the sum of their sizes:
%
\[
\card{M \cup E \cup P} = \card{M} + \card{E} + \card{P}
    \qquad \text{(if $M$, $E$, and $P$ are disjoint)}
\]
%
However, the sets $M$, $E$, and $P$ might \textit{not} be disjoint.  For
example, there might be a student majoring in both Math and
Physics.  Such a student would be counted twice on the right sides of this
equation, once as an element of $M$ and once as an element of $P$.  Worse,
there might be a triple-major
%ERIC how about: \footnote{\dots though not at MIT anymore.}
counting \textit{three} times on the right side!

Our last counting rule determines the size of a union of sets that are
not necessarily disjoint.  Before we state the rule, let's build some
intuition by considering some easier special cases: unions of just two
or three sets.

\subsection{Union of Two Sets}

For two sets, $S_1$ and $S_2$, the Inclusion-Exclusion rule is that the
size of their union is:
\begin{equation}\label{IE2}
\card{S_1 \cup S_2} = \card{S_1} + \card{S_2} - \card{S_1 \cap S_2}
\end{equation}
Intuitively, each element of $S_1$ is accounted for in the first term,
and each element of $S_2$ is accounted for in the second term.
Elements in \textit{both} $S_1$ and $S_2$ are counted
\textit{twice}--- once in the first term and once in the second.  This
double-counting is corrected by the final term.

We can prove equation~\eqref{IE2} rigorously by applying the Sum Rule to
some disjoint subsets of $S_1 \union S_2$.  As a first step, we observe
that given any two sets, $S,T$, we can decompose $S$ into the disjoint
sets consisting of those elements in $S$ but not $T$, and those elements
in $S$ and also in $T$.  That is, $S$ is the union of the disjoint sets
$S-T$ and $S \intersect T$.  So by the Sum Rule we have
\begin{align}
\card{S} & = \card{S-T} + \card{S \intersect T}, & \text{and so}\notag\\
\card{S-T} & = \card{S} - \card{S \intersect T}.\label{s-t}
\end{align}
Now we decompose $S_1 \union S_2$ into three disjoint sets:
\begin{equation}\label{sin3}
S_1 \cup S_2
     = (S_1 - S_2) \cup (S_2 - S_1) \cup (S_1 \cap S_2).
\end{equation}
Now we have
\begin{align*}
\card{S_1 \cup S_2}
    & = \card{(S_1 - S_2) \cup (S_2 - S_1) \cup (S_1 \cap S_2)}
        && \text{(by~\eqref{sin3})} \\
    & = \card{S_1 - S_2} + \card{S_2 - S_1} + \card{S_1 \cap S_2}
        && \text{(Sum Rule)} \\
    & = (\card{S_1} - \card{S_1 \cap S_2})
      + (\card{S_2} - \card{S_1 \cap S_2})
      + \card{S_1 \cap S_2}
        && \text{(by~\eqref{s-t})} \\
    & = \card{S_1} + \card{S_2} - \card{S_1 \cap S_2}
        && \text{(algebra)}
\end{align*}


\subsection{Union of Three Sets}

So how many students are there in the Math, EECS, and Physics
departments?  In other words, what is $\card{M \cup E \cup P}$ if:
%
\begin{align*}
\card{M} & = 60 \\
\card{E} & = 200 \\
\card{P} & = 40
\end{align*}
%
The size of a union of three sets is given by a more complicated
Inclusion-Exclusion formula:
%
\begin{align*}
\card{S_1 \cup S_2 \cup S_3} & = \card{S_1} + \card{S_2} + \card{S_3} \\
  & \quad - \card{S_1 \cap S_2} - \card{S_1 \cap S_3} - \card{S_2 \cap S_3} \\
  & \quad + \card{S_1 \cap S_2 \cap S_3}
\end{align*}
%
Remarkably, the expression on the right accounts for each element in the
union of $S_1$, $S_2$, and $S_3$ exactly once.  For example, suppose that
$x$ is an element of all three sets.  Then $x$ is counted three times (by
the $\card{S_1}$, $\card{S_2}$, and $\card{S_3}$ terms), subtracted off
three times (by the $\card{S_1 \cap S_2}$, $\card{S_1 \cap S_3}$, and
$\card{S_2 \cap S_3}$ terms), and then counted once more (by the
$\card{S_1 \cap S_2 \cap S_3}$ term).  The net effect is that $x$ is
counted just once.

So we can't answer the original question without knowing the sizes of
the various intersections.  Let's suppose that there are:
%
\begin{center}
\begin{tabular}{cl}
4 & Math - EECS double majors \\
3 & Math - Physics double majors \\
11 & EECS - Physics double majors \\
2 & triple majors
\end{tabular}
\end{center}
%
Then $\card{M \cap E} = 4 + 2$, $\card{M \cap P} = 3 + 2$, $\card{E
\cap P} = 11 + 2$, and $\card{M \cap E \cap P} = 2$.  Plugging all this
into the formula gives:
%
\begin{align*}
\card{M \cup E \cup P}
    & = \card{M} + \card{E} + \card{P}
      - \card{M \cap E} - \card{M \cap P} - \card{E \cap P}
      + \card{M \cap E \cap P} \\
    & = 60 + 200 + 40 - 6 - 5 - 13 + 2 \\
    & = 278
\end{align*}

\subsubsection{Sequences with 42, 04, or 60}

In how many permutations of the set $\set{0, 1, 2, \dots, 9}$ do
either 4 and 2, 0 and 4, or 6 and 0 appear consecutively?  For
example, none of these pairs appears in:
%
\[
(7, 2, 9, 5, 4, 1, 3, 8, 0, 6)
\]
%
The 06 at the end doesn't count; we need 60.  On the other hand, both
04 and 60 appear consecutively in this permutation:
%
\[
(7, 2, 5, \underline{6}, \underline{0}, \underline{4}, 3, 8, 1, 9)
\]
%
Let $P_{42}$ be the set of all permutations in which 42 appears; define
$P_{60}$ and $P_{04}$ similarly.  Thus, for example, the permutation above
is contained in both $P_{60}$ and $P_{04}$.  In these terms, we're looking
for the size of the set $P_{42} \cup P_{04} \cup P_{60}$.

First, we must determine the sizes of the individual sets, such as
$P_{60}$.  We can use a trick: group the 6 and 0 together as a single
symbol.  Then there is a natural bijection between permutations of
$\set{0, 1, 2, \dots 9}$ containing 6 and 0 consecutively and
permutations of:
%
\[
\set{60, 1, 2, 3, 4, 5, 7, 8, 9}
\]
%
For example, the following two sequences correspond:
%
\[
(7, 2, 5, \underline{6}, \underline{0}, 4, 3, 8, 1, 9)
\qquad \leftrightarrow \qquad
(7, 2, 5, \underline{60}, 4, 3, 8, 1, 9)
\]
%
There are $9!$ permutations of the set containing 60, so
$\card{P_{60}} = 9!$ by the Bijection Rule.  Similarly, $\card{P_{04}}
= \card{P_{42}} = 9!$ as well.

Next, we must determine the sizes of the two-way intersections, such
as $P_{42} \cap P_{60}$.  Using the grouping trick again, there is a
bijection with permutations of the set:
%
\[
\set{42, 60, 1, 3, 5, 7, 8, 9}
\]
%
Thus, $\card{P_{42} \cap P_{60}} = 8!$.  Similarly, $\card{P_{60} \cap
P_{04}} = 8!$ by a bijection with the set:
%
\[
\set{604, 1, 2, 3, 5, 7, 8, 9}
\]
%
And $\card{P_{42} \cap P_{04}} = 8!$ as well by a similar argument.
Finally, note that $\card{P_{60} \cap P_{04} \cap P_{42}} = 7!$ by a
bijection with the set:
%
\[
\set{6042, 1, 3, 5, 7, 8, 9}
\]

Plugging all this into the formula gives:
%
\begin{align*}
\card{P_{42} \cup P_{04} \cup P_{60}}
    & = 9! + 9! + 9! - 8! - 8! - 8! + 7!
\end{align*}

\subsection{Union of \emph{n} Sets}

The size of a union of $n$ sets is given by the following rule.

\begin{mathrule}[Inclusion-Exclusion]
\[
\card{S_1 \cup S_2 \cup \cdots \cup S_n} = 
\]
%
\centerline{\begin{tabular}[t]{rl}
 & the sum of the sizes of the individual sets \\
\textit{minus} & the sizes of all two-way intersections \\
\textit{plus} & the sizes of all three-way intersections \\
\textit{minus} & the sizes of all four-way intersections \\
\textit{plus} & the sizes of all five-way intersections, etc.
\end{tabular}}
\end{mathrule}

There are various ways to write the Inclusion-Exclusion formula in
mathematical symbols, but none are particularly clear, so we've just
used words.  The formulas for unions of two and three sets are special
cases of this general rule.

\subsubsection{Counting Primes}

How many of the numbers $1, 2, \dots, 100$ are prime?  One way to answer
this question is to test each number up to 100 for primality and keep a
count.  This requires considerable effort.  (Is 57 prime?  How about 67?)

Another approach is to use the Inclusion-Exclusion Principle.  This
requires one trick: to determine the number of primes, we will first count
the number of {\em non-primes}.  By the Sum Rule, we can then find the
number of primes by subtraction from 100.  This trick of ``counting the
complement'' is a good one to remember.

\subsubsection*{Reduction to a Union of Four Sets}

The set of non-primes in the range $1, \dots, 100$ consists of the set,
$C$, of composite numbers in this range: $4, 6, 8, 9, \dots, 99, 100$ and
the number 1, which is neither prime nor composite.  The main job is to
determine the size of the set $C$ of composite numbers.  For this purpose,
define $A_m$ to be the set of numbers in the range $m+1, \dots, 100$ that
are divisible by $m$:
\[
A_m \eqdef \set{x \leq 100 \suchthat x > m \text{ and } \paren{m \divides x}}
\]

For example, $A_2$ is all the even numbers from 4 to 100.  The following
Lemma will now allow us to compute the cardinality of $C$ by using
Inclusion-Exclusion for the union of four sets:

\begin{lemma}
\[
C = A_2 \cup A_3 \cup A_5 \cup A_7.
\]
\end{lemma}

\begin{proof}
We prove the two sets equal by showing that each contains the other.

To show that $A_2 \cup A_3 \cup A_5 \cup A_7 \subseteq C$, let $n$ be an
element of $A_2 \cup A_3 \cup A_5 \cup A_7$.  Then $n \in A_m$ for $m = 2,
3, 5$ or $7$.  This implies that $n$ is in the range $1, \dots, 100$ and
is composite because it has $m$ as a factor.  That is, $n \in C$.

Conversely, to show that $C \subseteq A_2 \cup A_3 \cup A_5 \cup A_7$, let
$n$ be an element of $C$.  Then $n$ is a composite number in the range $1,
\dots, 100$.  This means that $n$ has at least two prime factors.  Now if
both prime factors are $> 10$, then their product would be a number $>
100$ which divided $n$, contradicting the fact that $n<100$.  So $n$ must
have a prime factor $\leq 10$.  But 2, 3, 5, and 7 are the only primes
$\leq 10$.  This means that $n$ is an element of $A_2$, $A_3$, $A_5$, or
$A_7$, and so $n \in A_2 \cup A_3 \cup A_5 \cup A_7$.
\end{proof}

\subsubsection*{Computing the Cardinality of the Union}

Now it's easy to find the cardinality of each set $A_m$: every $m$th
integer is divisible by $m$, so the number of integers in the range $1,
\dots, 100$ that are divisible by $m$ is simply $\floor{100/m}$.  So
\[
\card{A_m} = \floor{\frac{100}{m}} - 1,
\]
where the $-1$ arises because we defined $A_m$ to exclude $m$ itself.
This formula gives:

\begin{eqnarray*}
\card{A_2} & = \lfloor\frac{100}{2}\rfloor - 1 = & 49 \\
\card{A_3} & = \lfloor\frac{100}{3}\rfloor - 1 = & 32 \\
\card{A_5} & = \lfloor\frac{100}{5}\rfloor - 1 = & 19 \\
\card{A_7} & = \lfloor\frac{100}{7}\rfloor - 1 = & 13
\end{eqnarray*}

Notice that these sets $A_2$, $A_3$, $A_5,$ and $A_7$ are not disjoint.
For example, 6 is in both $A_2$ and $A_3$.  Since the sets intersect, we
must use the Inclusion-Exclusion Principle:

\begin{align*}
\card{C}
  = & \card{A_2 \cup A_3 \cup A_5 \cup A_7} \\
  = & \card{A_2} + \card{A_3} + \card{A_5} + \card{A_7} \\
    & - \card{A_2 \cap A_3} - \card{A_2 \cap A_5} - \card{A_2 \cap A_7}
             - \card{A_3 \cap A_5} - \card{A_3 \cap A_7} - \card{A_5 \cap A_7} \\
    & + \card{A_2 \cap A_3 \cap A_5} + \card{A_2 \cap A_3 \cap A_7}
             + \card{A_2 \cap A_5 \cap A_7} + \card{A_3 \cap A_5 \cap A_7} \\
    & - \card{A_2 \cap A_3 \cap A_5 \cap A_7}
\end{align*}

There are a lot of terms here!  Fortunately, all of them are easy to
evaluate.  For example, $\card{A_3 \cap A_7}$ is the number of multiples
of $3 \cdot 7 = 21$ in the range 1 to 100, which is $\floor{100/21} = 4$.
\iffalse (Note that there is no reason to subtract 1 as we did when
evaluating $\card{A_m}$ above.)\fi Substituting such values for all of the
terms above gives:
\begin{align*}
\card{C}  = & 49 + 32 + 19 + 13 \\
            & - 16 - 10 - 7 - 6 - 4 - 2 \\
            & + 3 + 2 + 1 + 0 \\
            & - 0 \\
          = & 74
\end{align*}

This calculation shows that there are 74 composite numbers in the
range 1 to 100.  Since the number 1 is neither composite nor prime,
there are $100 - 74 - 1 = 25$ primes in this range.

At this point it may seem that checking each number from 1 to 100 for
primality and keeping a count of primes might have been easier than using
Inclusion-Exclusion.  However, the Inclusion-Exclusion approach used here
is asymptotically faster as the range of numbers grows large.\iffalse The
naive strategy requires $n$ runs of a primality test if the upper bound is
$n$.  The Inclusion-Exclusion approach seems to require summing an immense
number of terms, but fewer than $n$ of these are non-zero and the rest can
be ignored.\fi

\iffalse  FALL '05: THIS NEW SECTION ON EULER'S FUNCTION SHOULD HAVE BEEN INCLUDED.

\subsubsection{Computing Euler's Function}

For $n=p_1^{e_1}\cdots p_m^{e_m}$ for distinct primes $p_i$.  Let $C_i$
be the set of nonnegative integers less than $n$ that are divisible by
$p_i$.  So
\[
\lgunion_{i=1}^k C_i
\]
is the set of nonnegative integers less than $n$ that are not relatively
prime to $n$.  There are $n-\phi(n)$ such numbers, by definition of $\phi(n)$.
By Inclusion-Exclusion,
\begin{align*}
\card{\lgunion_{i=1}^m C_i} = & \sum_{i=1}^m \card{C_i} -
\sum_{1\leq i < j \leq m} \card{C_i \intersect C_j}
+ \sum_{1\leq i < j < k \leq m} \card{C_i \intersect C_j \intersect C_k} -
\cdots
\pm lgintersect_{i=1}^m C_i\\
= & \sum_{i=1}^m n/p_i -
\sum_{1\leq i < j \leq m} n/p_ip_j
+ \sum_{1\leq i < j < k \leq m} n/p_ip_jp_k} -
\cdots
\pm n/\prod_{i=1}^m p_i\\
= & n \paren{1- \prod_{i=1}^m \paren{1 - \frac{1}{p_i}}}
\end{align*}
So

\[
\phi(n) = n - \card{\lgunion_{i=1}^m C_i} = n\prod_{i=1}^m \paren{1 -
  \frac{1}{p_i}}.
\]

\begin{notesproblem}
Prove that
\[
\phi(ab) = \phi(a)\phi(b)
\]
for relatively prime nonnegative integers $a,b$.
\end{notesproblem}

\fi


\iffalse

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

\section{The Grand Scheme for Counting}

The rules and techniques we've covered to this point snap together
into an overall scheme for solving elementary counting problems.  Here
it is:

\textbox{
\begin{center}
{\Large \textbf{Grand Scheme for Counting}}
\end{center}

\begin{enumerate}

\item Learn to count sequences using two techniques:

\begin{itemize}

\item the General Product Rule

\item the BOOKKEEPER formula

\end{itemize}

\item Translate everything else to a sequence-counting problem via:

\begin{itemize}

\item bijections

\item $k$-to-1 functions

\end{itemize}

\item But for unions of sets, use Inclusion-Exclusion.

\end{enumerate}
}

Everything here should be familiar to you by now, except for the
BOOKKEEPER formula, which you'll see in recitation tomorrow.
\fi

\end{document}
