\documentclass[11pt]{article}
\usepackage{precalc}
\begin{document}
\assigntitle{20}{The Art of Counting, Part I}
Up until now, we have been exploring \term{continuous} mathematics,
dealing with real numbers and measurement. This week we will begin
the second half of the course, focusing on \term{discrete}
mathematics, dealing with pattern and structure.
This week, we begin with counting. What's that? You already know how
to count? Aha, that's what \emph{you} think! Counting is about much
more than just saying ``one, two, three, \dots'' For example, suppose
someone showed you a rectangular grid of dots and asked you how
many dots there were. Would you just point to each and every dot and
literally count them? Or would you cleverly realize that it was a
\emph{rectangular} grid, count how many dots were along each edge, and
multiply to get the total number of dots? The mathematical study of
counting---called \term{combinatorics}---takes this idea of counting
things in clever ways (``counting without actually counting'') to
whole new levels.
\section{Basic counting techniques}
\label{sec:basic}
\subsection{Alternatives = addition}
\label{sec:addition}
For the most part, this is intuitively obvious, but it's worth
stating: if the things you are trying to count can be separated into
disjoint groups (\term{disjoint} means that the groups do not
overlap), and you know how to count each group, then the total number
of things is just the sum of the number of things in each group.
\begin{problem}
A petting zoo has sixteen rabbits, fourteen snails, and thirty-nine
lemurs. How many animals are in the petting zoo?
\end{problem}
\begin{problem}
How many animals are in the petting zoo now?
\end{problem}
\subsection{Independent choices = multiplication}
\label{sec:multiplication}
Often when counting things it is useful to think about how you could
\emph{choose} one of the things you are counting. If choosing one of
them involves making two \emph{independent} choices, then the total
number of things is the number of ways of making the first choice,
\emph{times} the number of ways of making the second choice.
For example, if you are counting the number of dots in a rectangular
grid, you could choose any particular dot by first choosing a row, and
then choosing a column. Since these choices are independent (you
could choose any column no matter which row you pick, and vice versa),
the total number of ways to choose a dot is the number of ways to
choose a row (that is, the number of rows) times the number of ways to
choose a column (that is, the number of columns).
\begin{problem}
How many seconds are there in a day?
\end{problem}
\begin{problem}
A company is trying to decide on a logo for a new product. They
have narrowed things down to four different colors, three different
designs, and six different names for the product. Assuming these
choices are independent, how many possible logos are there?
\end{problem}
\begin{problem}
How many red face cards are in a standard deck of cards?
\end{problem}
You have to be careful, though: if the choices are not independent,
you can't just multiply! You have to be a bit more clever.
\begin{problem}
At the Tastie-Freeze Ice Cream Store, you can choose any one of
their thirty delicious ice cream flavors, and, optionally, any one
of their four delicious toppings, \emph{unless} you have vanilla, in
which case you may have two toppings, or if you have Super-Chunky
Peanut Butter Cup Fudge Raisin Mint Coffee Cookie Surprise, in which
case you don't get a topping. How many different things can you
order?
\end{problem}
\section{Permutations}
\label{sec:permutations}
\term{Permutation} is just a fancy mathematical name for \term{order}:
to make a permutation of some objects, you just put them in some
particular order. For example, if we have the letters `A', `B', and
`C', one permutation of them is ``ACB''; another permutation is
``BAC'', another is ``ABC'', and so on.
\begin{problem}
How many permutations of `A', `B' and `C' are there?
\end{problem}
Permutations come up in lots of places, so it's nice to know how to
count them. Suppose we have $n$ objects, and we want to know how many
permutations of the $n$ objects there are. It's useful to again think
in terms of \emph{choosing} a permutation: how many ways can we choose
a particular permutation?
Well, the permutation has to start with one of the $n$ objects, right?
So we have $n$ choices for the first object. After that, there are $n
- 1$ objects left, and we are free to choose any of them to be the
second object in the permutation. Since this choice is independent of
the first, there are a total of $n \cdot (n-1)$ ways to choose the
first two objects. Of course, that leaves $n-2$ choices for the third
object, and so on\dots until we are down to the last object and there
is only one thing left to choose. So, there are \[ n \cdot (n-1)
\cdot (n-2) \cdots 2 \cdot 1 = n! \] permutations of $n$ objects.
\begin{problem}
A group of seven tourists is having their picture taken in front of
the Scottsbluff, Nebraska Municipal Water Tower. They are unsure
what the optimal order is for them to stand in (shortest to tallest?
tallest to shortest? alternating?) so they decide to take one
picture with them standing in every possible order. Assuming they
can take one picture every thirty seconds, how long will this take?
\end{problem}
\begin{problem}
After looking at the pictures, the tourists realize that only four
of them fit in the picture frame at once, so they go back to take
more pictures. This time, they want to take a picture of every
possible group of four of them in every possible order. How many
pictures will they take?
\end{problem}
\section{Practice problems}
\label{sec:more-problems}
\begin{problem}
The country of West Mathistan issues license plates with four letters
and three numbers (for example, my car's license plate is
``NERD-123''). Every car must have a different license plate. What
is the maximum number of cars that can be registered in West
Mathistan?
\end{problem}
\begin{problem}
You have two normal six-sided dice, except that one is red and one
is blue, and you roll them both.
\begin{subproblems}
\item How many different outcomes are there?
\item In how many different ways can you roll a total of 7?
\item In how many different ways can you roll a total larger than 7?
\end{subproblems}
\end{problem}
\begin{problem}
How many seconds are in a century? (You may ignore leap seconds,
and assume that exactly $24$ out of $100$ years are leap years.)
\end{problem}
\begin{problem}
How many seconds were there between 12:00 AM on January 1, 1970, and
11:31:30 PM on February 13, 2009?
\end{problem}
\begin{problem}
How many squares (of \emph{any} size!) are there on a chess board?
\end{problem}
\begin{problem}
\pref{fig:triangular} below illustrates the first four
\term{triangular numbers}; the $n$th triangular number is the number
of dots in a triangle of size $n$. As you can see by counting the
dots below, the first four triangular numbers are $1$, $3$, $6$,
$10$. What is the $100$th triangular number?
\begin{figure}[htp]
\centering
\includegraphics{diagrams/triangles}
\caption{Triangular numbers}
\label{fig:triangular}
\end{figure}
\end{problem}
\begin{problem}
If Ronnie has six pairs of basketball shoes, nineteen pairs of
special lucky basketball socks, three pairs of basketball shorts,
and five basketball jerseys, how many different basketball outfits
can he wear? Give as many possible answers as you can think of, by
interpreting the question in different ways. (For example, is Ronnie
allowed to mix and match his shoes? What about his socks? Can he
wear more than one jersey at a time? etc.)
\end{problem}
\begin{problem}
Fred (shown in blue in \pref{fig:grid}) lives at the intersection of
1st and A streets. Every day he walks to school (shown in red),
which is at the intersection of 5th and E streets. How many
different ways can Fred walk to school (assuming he only walks east
and north)?
\begin{figure}[htp]
\centering
\includegraphics{diagrams/grid}
\caption{The streets of Manhattan}
\label{fig:grid}
\end{figure}
\end{problem}
\end{document}