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