Definition 14.1. An $r$-permutation is a permutation of $r$ elements taken from a set of $n$ elements.
Theorem 14.2. If $P(n,r)$ denotes the number of $r$ permutations of an $n$-element set, then $$P(n,r) = n \cdot (n-1) \cdot \cdots \cdot (n-r+1).$$
We can think of this as an application of the product rule, where our first choice is from a set $S$ of size $n$, then we have a choice from $S \setminus \{a_1\}$ of size $n-1$, then a choice from $S \setminus \{a_1,a_2\}$ of size $n-2$ and so on.
Corollary 14.3. If $n$ is positive and $0 \leq r \leq n$, then $$P(n,r) = \frac{n!}{(n-r)!}.$$
Proof. Note that the total number of ways to order a set of $n$ elements is $n!$. From above, we have $P(n,r)$ ways to order $r$ out of $n$ elements. We are then left with $n-r$ elements to order, which we can do $(n-r)!$ ways. This gives us \begin{align*} n! &= P(n,r) \cdot (n-r)! \\ P(n,r) &= \frac{n!}{(n-r)!} \end{align*} $\tag*{$\Box$}$
Example 14.4. Suppose you are an old-timey travelling salesperson, going around selling knives or encyclopedia sets or what-not. You have a list of $n$ cities you need to hit up and obviously you would like to minimize the cost of travelling to these cities. The problem you have to solve is: what is the minimal cost route that allows you to visit all of these cities once, including your trip back?
We can try to solve this problem by checking each possible route. How many routes are there? This is the same as asking in which order we would like to travel to each city and how many total choices we have. So for $n$ cities, this is just $n!$. This doesn't seem so bad if you've only got four cities to go to, since $4! = 24$. However, if you're a bit more ambitious and want to go to 8 cities, then you're looking at $8! = 40320$ different routes to think about. This is not something you'd want to do by hand, but easily handled by a computer. Double the number of cities again, though, and we get $16! = 20922789888000$, which Wolfram|Alpha tells me is about the number of red blood cells in the human body or about 70 times the number of stars in our galaxy. This number clearly grows very quickly—on the order of $\sqrt{2\pi n} \left( \frac n e \right)^n$, by Stirling's approximation.
This problem is the Travelling Salesman Problem, one of the most famous problems for which we do not have an efficient algorithm for solving. The problem dates back as far as the 1800s although it wasn't formally stated in its current form until around the 1930s. One point of interest is that I said cost and not necessarily distance. If we assume that the costs are distances, then we impose a condition on our cost function: that the distances satisfy the triangle inequality, $d(x,y) \leq d(x,z) + d(z,y)$. This assumption makes the problem slightly (but not significantly) easier. However, not all cost functions necessarily behave that way and we have a very relevant example of one: flight prices.
Example 14.5. A single-occurrence word is a word in which each symbol appears at most once. Let $\Sigma = \{1,2,3,4,5,6,7,8,9\}$. How many single-occurrence words of length 6 are there that contain the substring $315$? What we do is we first choose a place for the string $315$ and in a word of length 6, there are four possible spots. Then there are three spots left in which we can place the six remaining symbols. This is just $P(6,3)$. Therefore, we have $4 \cdot P(6,3) = 4 \cdot \frac{6!}{3!} = 4 \cdot 6 \cdot 5 \cdot 4 = 480$ words in total.
Now, suppose that order is not so important and we are only concerned about the selection of $r$ objects from a set of $n$ objects.
Definition 14.6. An $r$-combination of a set $A$ with $n$ elements is a subset of $r$ elements from $A$. The number of $r$-combinations of a set with $n$ elements is denoted $C(n,r)$ or $\binom n r$. This is read "$n$ choose $r$".
What you'll find is that everyone introduces the notation for combinations as some variant of $C(n,r)$, because $C$ is a nice mnemonic for "choose" or "combination" but then this is almost immediately dropped for the $\binom n r$ notation. The $\binom n r$ are called binomial coefficients for reasons that we'll get to next class (see, I said we'd drop $C(n,r)$ almost immediately).
So when considering the number of $r$-combinations, we are basically counting the number of subsets of size $r$. Recall that sets are unordered so this differs from permutations in that all we care about is whether an element gets chosen at all.
Example 14.7. Thinking back to a three element set $A = \{1,2,3\}$, we observe that unlike permutations, there is only one 3-combination: $A$ itself. Then how many 2-combinations are there? Let's enumerate all of the subsets of $A$ of size 2: $$\begin{matrix} \{1,2\} & \{1,3\} & \{2,3\} \end{matrix}$$ Remember that since sets are not ordered, $\{1,2\}$ and $\{2,1\}$ are the same set.
So how many of these things are there?
Theorem 14.8. If $n \gt 0$ and $0 \leq r \leq n$, then $$C(n,r) = \frac{n!}{r!(n-r)!}.$$
Proof. We can make use of the number of $r$-permutations of a set. We know that the number of $r$-permutations of a set of size $n$ is simply the number of a subset of size $r$. So we can do the following: first, choose a subset of size $r$, and then compute the number of permutations of this subset. This gives us $$P(n,r) = C(n,r) \cdot P(r,r).$$ Then doing some algebra, we get $$C(n,r) = \frac{P(n,r)}{P(r,r)} = \frac{n!}{r!(n-r)!}.$$ $\tag*{$\Box$}$
Example 14.9. Let's return to our parking situation from last class. We wanted to know how many different parking arrangements there could be for you and six of your friends racing for three spots. Now, if the spots are noticeably different and there's a spot that's definitely better than the others, it makes sense to think about the possible arrangements. However, if all of spots are together, then all you really care about is getting a spot at all. In this case, it doesn't really matter who arrives first, second, and third, you just need to make sure not to be fourth. In this case, it makes sense to count the number of 3-combinations rather than 3-permutations. So we get $$C(7,3) = \frac{7!}{3!(7-3)!} = \frac{7!}{3! \cdot 4!} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$$ different ways where three people are happy and four people are stuck circling the parking lot.
Something you might have noticed when going through the previous example is that if we have $\binom 7 3 = \frac{7!}{3! \cdot 4!}$, then this looks the same as $\binom 7 4 = \frac{7!}{4! \cdot 3!}$. This is not a coincidence! First of all, this is very easy to verify.
Theorem 14.10. For all $n \gt 0$ and $0 \leq r \leq n$, $C(n,r) = C(n,n-r)$.
Proof. We have $$C(n,n-r) = \frac{n!}{(n-r)! (n - (n-r))!} = \frac{n!}{(n-r)! \cdot r!} = C(n,r).$$ $\tag*{$\Box$}$
Now, intuitively, what does this mean? Suppose we have a set of $n$ elements. We want to choose $r$ of these elements to form a subset. Then there are $n-r$ elements that weren't chosen. Alternatively, we can think of this as choosing $n-r$ elements to exclude from our subset, so that the remaining $r$ elements happen to form our subset. In both cases, we get the same result.
Example 14.11. We say a word over a binary alphabet, say $\{0,1\}$, is balanced if it contains exactly as many $0$s as it does $1$s. How many balanced words of length $n$ are there? First of all, if $n$ is odd, then there are no balanced words of length $n$. So $n$ has to be even. At first, we might approach this like previous string problems, where we place things sequentially. However, we know exactly how many $0$s and $1$s we need in our word: we want exactly $\frac n 2$ of each.
If we have $n$ spaces to fill, we first think about how to place our $0$s. We need to choose $\frac n 2$ of these spaces to fill. After we choose these spaces, we know the rest of the word must be filled with the $1$s. This gives us $C\left(n,\frac n 2\right) = \frac{n!}{\frac n 2! \left(n - \frac n 2\right)!} = \frac{n!}{\left(\frac n 2 !\right)^2}$ balanced words.
We can apply the same idea if we happen to be working in a larger alphabet. Suppose that we're working in a ternary alphabet $\{0,1,2\}$. Then a balanced word over this alphabet is one that has the same number of 0s, 1s, and 2s. Again, we would make sure that $3 \mid n$ but then our problem is solved in the following way:
First, we choose $\frac n 3$ spots for our 0s. However, we're left with $\frac 2 3 n$ spots for the 1s and 2s. We then choose half of these spots for the 1s and everything left over goes to the 2s. This gives us a total of $$C\left(n, \frac n 3\right) \cdot C\left(\frac{2n}3, \frac n 3\right) = \frac{n!}{\frac n 3! \cdot \left(n - \frac n 3\right)!} \cdot \frac{\frac{2n}3!}{\frac n 3! \cdot \left(\frac{2n}3 - \frac n 3\right)!} = \frac{n!}{\frac n 3! \cdot \frac{2n}3!} \cdot \frac{\frac{2n}3!}{\frac n 3! \cdot \frac n 3!} = \frac{n!}{\left(\frac n 3!\right)^3}.$$
One common question that comes up is when to count permutations and when to count combinations. It is very easy to turn a problem of one kind into a problem of the other, just like in our parking example. The key to look for is whether what you're counting has an element of ordering or arrangement or distinguishability.
Example 14.12. Suppose that there are 13 students thinking of choosing three out of them to run for Executive Slate. How many slates can they form? Here, they will have to decide who's running as President, VP Administration, and VP Student Affairs, so there can be two different slates with the same people in them. Here, we would use permutations, and the number of slates would be $P(13,3) = 13 \cdot 12 \cdot 11 = 1716$.
Now, suppose that there are 13 students from the same class running to be class representatives on the College Council. Since each class gets 4 representatives, how many different sets of represenatatives are there? Here, we would use combinations, because there is all of the positions are basically the same. In total, there would be $$C(13,4) = \binom{13}{4} = \frac{13!}{4!9!} = \frac{13 \cdot 12 \cdot 11 \cdot 10}{1 \cdot 2 \cdot 3 \cdot 4} = 715$$ possible ways to elect four representatives.