\documentclass[11pt]{article}
\usepackage{precalc}
\begin{document}
\assigntitle{21}{The Art of Counting, Part II}
\section{Permutations, revisited}
\label{sec:permutations}
\topic{permutations} In last week's assignment, we studied
\term{permutations}, noting that there are $n \cdot (n-1) \cdot (n-2)
\dots 2 \cdot 1 = n!$ ($n$ factorial) different ways to put $n$
objects in order.
\begin{problem}
How many ways are there to put zero objects in order? What does
this suggest the definition of $0!$ should be?
\end{problem}
In general, there are
\begin{equation} \label{eq:perm}
P(n,k) = n \cdot (n-1) \dots (n - k + 1)
\end{equation}
permutations of $k$ out of $n$ things (that is, the number of ways to
put $k$ out of $n$ things in some order). That $n - k + 1$ may seem a
little mysterious, but if you think about it for a bit, you'll see
that all we're doing is taking $k$ numbers, starting from $n$ and
counting down by $1$ each time. So, the first number starting from
$n$ is $n - 1 + 1$ (that is, $n$); the second number is $n - 2 + 1$;
the third number is $n - 3 + 1$, \dots and the $k$th number is $n - k
+ 1$. So, for example, there are twelve ways to put two out of four
things in some order: there are $4$ possibilities for the first thing,
and $3$ for the second thing, for a total of $4 \cdot 3 = 12$
permutations.
\begin{problem}
What is $P(21,6)$? That is, how many permutations are there of $6$
out of $21$ things?
\end{problem}
\begin{problem}
Which problem from last week's assignment had to do with this
general permutations formula?
\end{problem}
\begin{problem}
Calculate $1!$, $2!$, $3!$, \dots, $7!$. Since factorials come up
so often in combinatorics, it's useful to be familiar with the
factorials of small numbers.
\end{problem}
\begin{problem}
The number of permutations of $k$ out of $n$ things can also be
written as
\begin{equation} \label{eq:perm2}
P(n,k) = \frac{n!}{(n-k)!}.
\end{equation}
Explain why \pref{eq:perm2} is equal to
\pref{eq:perm}. (\emph{Hint:} write out the factorials and see what cancels\dots)
\end{problem}
\topic{nPr} The number of permutations of $k$ out of $n$ things is
implemented on many calculators (probably including yours) as a
function called \texttt{nPr}. For example, \texttt{6 nPr 3} tells you
how many ways there are to put three out of six things in some order,
that is, the number of permutations of three out of six objects.
\section{Combinations}
\label{sec:combinations}
\topic{combinations} What if we just want to know the number of ways
of choosing a certain number of things from a bigger set of
possibilities, but we \emph{don't care} about the order? For example,
suppose you are at the store and there are six kinds of fruit to
choose from (apples, bananas, cherries, dates,
eggplants\footnote{Eggplant \emph{is} a fruit. Go look up the
definition of fruit if you don't believe me. Botanically speaking,
a fruit is anything which is the seed-bearing portion of a plant,
regardless of whether it tastes sweet or you could use it to make
ice cream. Other ``vegetables'' which are actually fruits include
tomato, squash, pumpkin, corn, cucumber, and zucchini.}, and figs),
but you only have enough money to buy exactly three, and you want to
know how many different choices you can make. In this case, the
\emph{order} in which you buy your three fruits doesn't make any
difference; the only thing that matters is which three fruits you get.
A set of objects chosen from some larger set, where we \emph{don't}
care about the order of the objects, is called a \term{combination}.
\begin{problem} \label{prob:fruit-combs}
\topic{fruity goodness}
So, how many ways \emph{are} there to buy three out of the six
fruits? For now, just list the different possibilities (you can
abbreviate the fruits using just their first letter). Which three
would you buy?
\end{problem}
\begin{problem} \label{prob:fruit-perms}
How many \term{permutations} of three out of six fruits are there?
(For example, maybe you plan to buy the fruits one at a time instead
of all at once, on Monday, Wednesday, and Friday, so now you care
about which order you buy them in.)
\end{problem}
\begin{problem}
Is your answer to \pref{prob:fruit-perms} bigger or smaller than
your answer to \pref{prob:fruit-combs}? Why? How much bigger or
smaller is it?
\end{problem}
\topic{counting combinations}
Let's think about how to count the number of ways to choose $k$ out of
$n$ things, when we don't care about the order. We already know how
to count them when we \emph{do} care about the order, and want to
count each ordering separately, but this is \emph{too many}. For
example, if we're trying to count the number of ways to choose two out
of three things, we could list all the \emph{permutations} of two out
of three things---AB, BA, AC, CA, BC, CB---but this is too many, we've
listed each combination of things twice! Since we don't care about
the order, AB is really the same as BA, AC is the same as CA, and BC
is the same as CB, so there are three ways to choose two out of three
things, not six.
\topic{combinations from permutations}
But herein lies the key. Suppose we are choosing $k$ out of $n$
things. We already know how to count the permutations of $k$ out of
$n$ things; as we have noted, this overcounts the combinations, but we
can figure out exactly by how much it overcounts. If we count
permutations, we count every possible order of each group of $k$
things, but we instead want to just count this group once. Well, how
many possible orders are there of $k$ things? Easy---there are $k!$
(that's $k$ factorial, not me being excited about how easy it is).
So if we just take the number of permutations and divide by $k!$, we
get the number of combinations.
\begin{equation}
\label{eq:combinations}
C(n,k) = \binom n k = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}.
\end{equation}
\topic{binomial coefficients}
Combinations come up so often that they have a special notation:
$\binom n k$, pronounced ``$n$ choose $k$'', denotes the number of
combinations of $k$ out of $n$ things. $\binom n k$ is also often
called a ``binomial coefficient'' (for reasons we will see later). You
can write it in \LaTeX\ as \verb|\binom{n}{k}|. Your calculator
probably has a function to compute combinations called \texttt{nCr}.
\begin{problem} \label{prob:comb-table} Compute $\binom{n}{k}$ for
every value of $n$ from $0$ to $7$ and every value of $k$ from $0$
to $n$ (that is, compute $\binom 0 0$; $\binom 1 0$ and $\binom 1
1$; $\binom 2 0$, $\binom 2 1$, and $\binom 2 2$; and so on). Make
a table with $n$ down the side and $k$ along the top. What patterns
do you notice? Can you explain any of the patterns?
\end{problem}
\begin{problem} \label{prob:ten-choose-5}
Compute $\binom{10}{5}$.
\end{problem}
\begin{problem}
Go back and look at Problem 17 from last week's assignment, and
compare it with your table from \pref{prob:comb-table}, and your
answer to \pref{prob:ten-choose-5}. What do you notice? Can
you explain the relationship?
\end{problem}
\section{More problems}
\label{sec:more-problems}
\begin{problem}
How many different poker hands are there? (A poker hand is five cards.)
\end{problem}
\begin{problem}
Remember Fred from Problem 17 in last week's assignment? What if
his school was at 7th and K streets? How many ways could he walk to
school then?
\end{problem}
\begin{problem}
Fred likes going to Joe's Pizza Parlor, where you can get a Small,
Medium, Large, or Ridiculous pizza with your choice of any three
toppings. In fact, he likes it so much that he goes once every day
and eats an entire pizza. Out of principle, however, Fred never
orders a pizza that he has ordered before. (Fred likes Trying New
Things.) If Joe's has seventeen toppings to choose from, how long
will Fred be able to go to Joe's before he is forced to
order a pizza that he has ordered before?
\end{problem}
\begin{problem}
Each day, after his daily pizza, Fred also likes going to the
Tastie-Freeze Ice Cream Store and getting a banana split. A banana
split consists of three scoops of ice cream (each of the three
scoops must be a \emph{different} kind of ice cream) and any two
different toppings. Recall that Tastie-Freeze has thirty kinds of
ice cream and four toppings. How many different banana splits could
Fred order?
\end{problem}
\begin{problem}
What if the three scoops in a banana split do not necessarily have
to be different (Fred could get three scoops of the same kind of ice
cream, or two of one kind and one of another)? How many different
banana splits are there now? (\emph{Hint:} break the types of
banana splits down into splits with three different kinds of ice
cream, with two kinds, and with one kind, and count each sort of
split separately. Keep in mind that the order of the scoops doesn't matter---but
getting two scoops of chocolate and one of vanilla IS different than
getting two vanilla and one chocolate!)
\end{problem}
%% save these for next week's assignment. Pascal's triangle extravaganza!
%% Pascal's triangle. connections with "streets" problem in part I.
%% Binomial theorem. (?)
%% provide links to blog posts about this stuff.
\end{document}