\documentclass[12pt]{article}

\addtolength{\voffset}{-.5in}
\addtolength{\textheight}{1in}
\addtolength{\hoffset}{-.5in}
\addtolength{\textwidth}{1in}

\begin{document}

\begin{center}
{\bf \LARGE Permutations/Combinations}
\end{center}

To do most of combinatorics, you need to understand the {\em multiplication principle.}  If you have $x$ choices of dinner and $y$ choices of dessert, and you have to pick one of each, then there are $xy$ combinations you can pick.  This isn't hard to see.

The multiplication principle can be modified slightly:  suppose there are $x$ dinners, and each dinner comes with a choice of $y$ different desserts (not necessarily the same as what's offered with other dinners).  You still can make $xy$ combinations.

Notation:  $n!$ is ``$n$ factorial,'' and is written $$n! = (n)\cdot(n-1)\cdot(n-2)\cdot\cdots\cdot2\cdot1.$$  (For example, $5!=5\cdot4\cdot3\cdot2\cdot1 = 120$.)

\begin{itemize}
 \item {\bf Permutations:}  How many ways can you choose $k$ books from $n$ books, and arrange them on a shelf?  (Order matters)
 \item {\bf Combinations:}  How many ways can you choose $k$ books from a group of $n$ books?  (Order does not matter)
\end{itemize}

Permutations are written $_nP_k$, and you can represent the calculation as $n! \over (n-k)!$.  In practice, you will almost never need that formula unless you're doing a proof.  Instead, what you need to remember concerns choices.

Say you have 10 books and you want to put three of them on a shelf (so order matters).  You have 10 choices for the first book.  {\em No matter what book you chose,} you have 9 choices for the second.  {\em Whatever your first two choices,} you have 8 choices for the third.  (This is like the revised multiplication principle.)  So the answer is $10\cdot9\cdot8=720$ choices.

The formula above, $\frac{10!}{(10-3)!}$, simply cancels the last seven terms of 10!, leaving $10 \cdot 9 \cdot 8$, which is exactly what you want.  But if you don't put $7 \cdot 6 \cdot \cdots \cdot 1$ there in in the first place, it's no matter.

Combinations are written $_nC_k$, for consistency, but almost everyone writes them $n \choose k$, essentially like a fraction but always with parenthesis and never with a horizontal line.  (It's really hard to break yourself of the habit of drawing that line.)  $_nC_k = {n \choose k} = {n! \over k!(n-k)!}$.  Again, in practice the formula is only useful for proofs.

How do you choose 3 books from 10, if order doesn't matter?  Well, start by choosing 3 books from 10 if order {\em does} matter.  You get 720 --- it's a permutation.  But {\em for any group of three books on the shelf,} you could have them in a number of different orders.  In this case, six orderings:  ABC, ACB, BAC, BCA, CAB, CBA.  The key thing there is that there are six orderings for every group of 3 books.  You can put the 720 permutations into 120 piles of 6, and each pile represents one combination.  So if order doesn't matter, you have to divide by 6.  $720 \div 6 =120$, and 120 is your answer.

So to calculate a combination, calculate a permutation and divide by the number of orderings of the objects (which is the number of objects, factorial.  In this case, $3!=6$).

\bigskip

Those are the basics.  Past that there are a lot of wonderful, sometimes subtle, applications.

{\bf Examples}

\begin{enumerate}
 \item How many ways can you pick six of 35 numbers for the lottery?  $${35 \choose 6} = \frac{35 \cdot 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}$$
 \item How many ways can you deal a poker hand?  \fbox{$52 \choose 5$}
 \item How many ways can you deal a full house?  \fbox{${13 \choose 1}{4 \choose 3}{12 \choose 1}{4 \choose 2}$}.  (Choose a rank.  Choose which three cards of that rank are in your hand.  Choose a different rank.  Choose which two cards of that rank are in your hand.)
 \item How many ways can you deal two of a kind?  \fbox{${13 \choose 1}{4 \choose 2}{48 \choose 3}$}.  Choose a rank for your pair, and choose two of the four cards of that rank.  Then choose three more cards from the 48 not of that rank.  (You can make up card problems all day long.)
 \item How many ways can you distribute 10 apples to 3 people?  Order matters (if A gets 6 and B gets 1, it's not the same as if A gets 1 and B gets 6).  Imagine 12 numbered buckets --- place them in order in a row.  Distribute the 10 apples into the buckets.  Every apple until the first empty bucket goes to the first person, everything between the empty buckets goes to the second person, and everything after the second empty bucket goes to the third person.  Thus the answer is \fbox{$12 \choose 2$}.
 
 How do you know this really works?  Every way you can distribute the apples can be represented in one way with the buckets; every way you can put the apples into the buckets corresponds to one distribution of apples to the three people.  This establishes that the number of ways you can put apples into buckets is the same as the number of ways you can distribute the apples.
 
 Notice that in general, if you want to distribute $n$ things to $k$ people, the formula is $n+k-1 \choose k-1$.
 
 \item How many ways can 7 people sit on a bench if three must sit together?  Imagine that persons 1, 2, and 3 are glued together, so there are five ``people'' to be seated:  (123), (4), (5), (6), and (7).  There are $_5P_5=5!=120$ ways for the five ``people'' to sit on the bench.  But once the group works itself free of the glue, there are six ways that 1, 2, and 3 can sit together ($3!=6$).  So there are $120\cdot6 = \mbox{\fbox{720}}$ ways for the seven people to sit.
 
 \item How many ways can 13 people sit in a ring of chairs if location doesn't matter, only who sits to the left or right of whom?  There are 13! ways to seat the people in the chairs, but {\em for every seating arrangement,} there are 12 other seating arrangements (13 total) that are the same.  So you can put the seating arrangements into piles of 13, leaving you with $13!/13=\mbox{\fbox{12!}}$ arrangements.
 
 An easier way to think about this:  tell one person to sit down.  It doesn't matter where.  The other 12 people sit in relation to him/her, giving $12!$ arrangements.
 
 If left and right don't matter, then the answer would be \fbox{$\frac{12!}{2}$}, since for every ordering you could take its mirror image.

 \item How many ways can you arrange the letters in ELLIPSE?  There are 7! ways to arrange seven letters, but the duplicate E's and L's mean that each arrangement will come up four times.  (Imagine ${\rm E}_1$, ${\rm E}_2$, ${\rm L}_1$ and ${\rm L}_2$.  You could have ${\rm E}_1{\rm L}_1{\rm L}_2{\rm IPSE}_2$, but the E's or L's could switch and give an identical ``word.'' Hence the answer is \fbox{$\frac{7!}{2!2!}$} and in general, the top numerator comes from the number of letters, and the denominator accounts for letter repetition.

\end{enumerate}

\bigskip

{\bf Problems}

\begin{enumerate}

\item Without expanding the product $$(a+b+c)(d+e+f)(p+q+r+s)(x+y+u+v+w),$$ calculate how many terms there will be.

\item In how many ways can ten persons be seated in a row so that a certain two of them are not next to each other?

\item In how many ways can ten A's, six B's, and five C's be lined in a row so that no two B's are adjacent?

\item In how many ways can all of $n$ distinct objects be put in $k$ distinct boxes, not more than one in each box, if there are more boxes than things?

\item There are nine different books on a shelf; four are red and five are blue.  In how many different orders is it possible to arrange the books on the shelf if
 \begin{enumerate}
  \item there are no restrictions;
  \item the red books must be together and the green books together;
  \item the red books must be together whereas the green books may be, but need not be, together;
  \item the colors must alternate, i.e., no two books of the same color may be adjacent?
 \end{enumerate}
 
\item How many of the first 10,000 positive integers have distinct digits?

\item You have a box containing four red socks, three blue socks, and two green socks.  You pick out three socks at random; what is the most likely outcome?

\item If 9 students are separated onto three ARML relay teams, what is the probability that a specific two of them are on the same team?  What is the probability that a specific three of them are completely separated, one on each team?
\item A man has a large supply of wooden regular tetrahedra (a solid with four equilateral triangles as faces), all the same size.  If he paints each triangular face in one of four colors, how many different painted tetrahedra can he make, allowing all possible combiantions of colors?  (Two colorings are the same if one tetrahedron could be rotated to match the other's coloring.)

\item A child has a set of 96 distinct blocks.  Each block is one of 2 materials ({\em plastic, wood}), 3 sizes ({\em small, medium, large}), 4 colors ({\em blue, green, red, yellow}), and 4 shapes ({\em circle, hexagon, square, triangle}).  How many blocks in the set are different from the ``{\em plastic medium red circle}'' in exactly two ways?  (The ``{\em wood medium red square}'' is such a block).

\item How many differently colored blocks of a fixed cubical shape can be made if six colors are available, and a block is to have a different color on each of its six faces?

\item Prove that ${n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}$, both algebraically and with a non-algebraic explanation.

\item Determine a closed form for $\sum_{k=0}^n {n \choose k}$, and prove that your closed form is correct.  (For example, what is ${6 \choose 0} + {6 \choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}$?)

\end{enumerate}

\end{document}