%  Counting
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Wednesday, March 24, 2010
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}
\topskip=20pt plus2pt

\def\abs#1{\mathopen|{#1}\mathclose|}
\def\nPr{{}_nP_r}

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Counting}
\smallskip
\centerline{Wednesday, March~24, 2010}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf The addition principle}

\nobreak\medskip

\noindent The addition principle, which is really just a formalization of the
common-sense idea of what addition means, says:

{\nobreak\medskip\narrower

\noindent If a task can be done using either of two different methods (but not
both methods simultaneously), the first of which can be done in $m$~ways and
the second of which can be done in $n$~ways, then there are $m+n$~different
ways of completing the task.

\medskip}

\noindent One application of the addition principle is in counting the number
of elements in the union of two disjoint sets, $A$~and~$B$. The ``task'' to be
performed is to choose an element from the union~$A\cup B$. This can be done in
either of two different methods: either choose an element of~$A$, or choose an
element of~$B$. If we let $m=\abs A$ and $n=\abs B$, then there are $m$~ways to
choose an element of~$A$ and $n$~ways to choose an element of~$B$, so the total
number of ways to choose an element of~$A\cup B$ (in other words, the number of
elements of~$A\cup B$) is $m+n$, or $\abs A+\abs B$. So:

{\nobreak\medskip\narrower

\noindent If $A$ and~$B$ are disjoint sets (that~is, $A\cap B=\emptyset$), then
$$\abs{A\cup B}=\abs A+\abs B.$$

\bigbreak} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf The principle of inclusion--exclusion}

\nobreak\medskip

\noindent If we attempt to use the addition principle to find $\abs{A\cup B}$
for two sets $A$ and~$B$ that are {\it not\/} disjoint, we will have
overcounted. This is because the elements in the intersection~$A\cap B$ will be
counted twice---once for being an element of~$A$ and once for being an element
of~$B$. To correct for this overcounting, we need to subtract $\abs{A\cap B}$.
This gives the following formula, which is often called the principle of
inclusion--exclusion:

{\nobreak\medskip\narrower

\noindent If $A$ and~$B$ are sets, then
$$\abs{A\cup B}=\abs A+\abs B-\abs{A\cap B}.$$

\nobreak\medskip}

\noindent We can also use this equation to get an expression
for~$\abs{A\cap B}$. Let's add the quantity $\abs{A\cap B}$ to both sides; this
gives us
$$\abs{A\cup B}+\abs{A\cap B}=\abs A+\abs B.$$
Now subtracting $\abs{A\cup B}$ from both sides produces the desired formula:
$$\abs{A\cap B}=\abs A+\abs B-\abs{A\cup B}.$$
Note that this is exactly the same as the formula for $\abs{A\cup B}$, except
that the symbols $\cup$ and~$\cap$ have been switched.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf The multiplication principle}

\nobreak\medskip

\noindent Like the addition principle, the multiplication principle is a
formalization of common sense. In this case, we are formalizing the
common-sense idea of what multiplication means. The multiplication principle
says:

{\nobreak\medskip\narrower

\noindent If a task can be broken up into two steps, the first of which can be
done in $m$~ways and the second of which can be done in $n$~ways (regardless of
how the first step is done), then there are $mn$~different ways of completing
the task.

\nobreak\medskip}

\noindent The multiplication principle can easily be extended to tasks that
require more than two steps. For example, if a task can be broken up into three
steps, the first of which can be done in $m$~ways, the second of which can be
done in $n$~ways (regardless of how the first step is done), and the third of
which can be done in $p$~ways (regardless of how the first and second steps are
done), then there are $mnp$~different ways of completing the task.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Choosing with replacement, order important}

\nobreak\medskip

\noindent Suppose we have a set of $n$~objects, and we want to repeatedly
choose an element of the set, $r$~times in all, with replacement (meaning that,
after we choose an element, we put it back into the set, so the same element
may be chosen more than once). Suppose also that the {\it order\/} in which we
choose the $r$~elements is important (so choosing the element~1 first and the
element~2 second should be considered to be different from choosing the
element~2 first and the element~1 second). For example, perhaps we are choosing
a six-digit identification number for a new product, where each of the digits
can be 0,~1, 2, 3, 4, 5, 6, 7, 8, or~9 (leading zeroes are allowed).

We can view this as a task to be performed, which is broken up into $r$~steps:
making the first choice, making the second choice, and so on. Since there are
$n$~objects in the set, each of these choices can be made in $n$~different
ways. By the multiplication principle, then, the number of ways to perform the
task is $n\times n\times n\times\cdots\times n$, with $r$~factors of~$n$; this
can also be written as~$n^r$. Hence:

{\nobreak\medskip\narrower

\noindent The number of ways to choose $r$~elements from a set of $n$~objects,
with replacement, when the order of the choices is important, is~$n^r$.

\bigbreak} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Permutations}

\nobreak\medskip

\noindent A {\it permutation\/} of a set of $n$~objects is a particular
rearrangement or ordering of the elements of the set. For example, the
permutations of the set~$\{1,2,3\}$ are $1,2,3$;~$1,3,2$; $2,1,3$; $2,3,1$;
$3,1,2$; and~$3,2,1$.

To count the number of permutations of a set of $n$~objects, we again view it
as a task to be performed and use the multiplication principle. The task can be
broken up into $n$~steps: choosing the first element of the permutation,
choosing the second element of the permutation, and so on. Note that once we
have chosen an element, we cannot choose it again, because each element appears
only once in the permutation. So there are $n$~different ways to make the first
choice, $n-1$~different ways to make the second choice, $n-2$~different ways to
make the third choice, and so on; there will be only 2~ways to make the
second-to-last choice, and only 1~way to make the last choice. Therefore:

{\nobreak\medskip\narrower

\noindent The number of permutations of a set of $n$~objects is
$$n!=n(n-1)(n-2)\cdots3\cdot2\cdot1.$$

\nobreak}

\noindent Note that $0!$ is defined to be~1. (There are good reasons for this.)

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Choosing without replacement, order important}

\nobreak\medskip

\noindent Suppose we have a set of $n$~objects, and we want to choose $r$~of
them, without replacement (so no element can be chosen twice). Suppose also
that the order in which the elements are chosen is important. For example,
perhaps we are judging submissions to an essay contest and must choose the
first place winner, the second place winner, and the third place winner.

Viewing this as a task to be performed, and breaking it up into $r$~steps
(making the first choice, making the second choice, and so on), we see that
there are $n$~different ways to make the first choice, $n-1$~different ways
to make the second choice, and so on, just as before when we were counting
permutations. The difference is that here we are only making $r$~choices in
all, so there are only $r$~factors in the multiplication. The last factor will
be $n-r+1$ (not $n-r$; why?). Therefore:

{\nobreak\medskip\narrower

\noindent The number of ways to choose $r$~elements from a set of $n$~objects,
without replacement, when the order of the choices is important, is
$$n(n-1)(n-2)\cdots(n-r+1)={n!\over(n-r)!}.$$

\nobreak}

\noindent This is sometimes called ``the number of permutations of $n$~objects
taken $r$~at a time,'' and is written with the symbol $\nPr$ or~$P(n,r)$.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Combinations (choosing without replacement, order not important)}

\nobreak\medskip

\noindent Suppose, as above, that we have a set of $n$~objects from which we
want to choose $r$~elements without replacement, but this time suppose that the
order in which the elements are chosen is {\it not\/} important. For example,
perhaps we are dealing a poker player a hand of five cards from a 52-card deck.
Or perhaps, in more abstract terms, we are choosing a subset of size~$r$ from a
larger set of size~$n$.

We know that $\nPr$ is the number of ways to do this if order is important.
However, each individual subset of size~$r$ has $r!$~permutations, so
$\nPr$~will count it $r!$~times. Therefore, if we don't care about the order of
the choices, we must divide $\nPr$ by~$r!$ to correct for the overcounting. So:

{\nobreak\medskip\narrower

\noindent The number of ways to choose $r$~elements from a set of $n$~objects,
without replacement, when the order of the choices is not important, is
$${\nPr\over r!}={n!\over r!(n-r)!}.$$

\nobreak}

\noindent This number comes up so frequently that it has a special notation:
${n\choose r}$,~which is read ``$n$~choose~$r$.'' The formula
for~${n\choose r}$ is, as noted above,
$${n\choose r}={n!\over r!(n-r)!}.$$

This is sometimes called ``the number of combinations of $n$~objects taken
$r$~at a time,'' and is sometimes written with the symbol~${}_nC_r$.

The formula for~${n\choose r}$ provides one good reason for the definition that
$0!=1$. Consider the expression~${n\choose n}$. This is the number of ways to
choose $n$~elements from a set of size~$n$, where the order in which the
elements are chosen does not matter. Clearly there is only one way to do
this---choose all $n$~elements of the set. So ${n\choose n}$ should be~1. If we
plug in $n=5$ and $r=5$ into the formula above, we get $0!$ as part of the
denominator; the only way the formula will give us the ``right'' answer is if
$0!=1$.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Choosing with replacement, order not important}

\nobreak\medskip

\noindent We have seen that, when counting the number of ways to make a
sequence of choices, it is essential to know whether replacement is or is not
allowed and whether the order in which the elements are chosen is or is not
important. We have covered three of the possibilities above; the last
possibility is that the choices are made with replacement and the order is not
important. This is somewhat subtler than the other three cases, and will be
explored in a problem on Homework~6.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf The pigeonhole principle}

\nobreak\medskip

\noindent The pigeonhole principle, like the other ``principles'' described
above, is just a formalization of a common-sense idea. However, despite its
apparent obviousness, the pigeonhole principle is often a very useful tool, so
it is worthwhile to state it explicitly. The pigeonhole principle says:

{\nobreak\medskip\narrower

\noindent If we are placing objects in boxes and there are more objects than
boxes, then at least one of the boxes must receive at least two objects.

}

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

\bye
