Recall the following example from last class.
Example 7.10. Now consider the University of Chicago's CNetID password policy:
A standard password with a length of 12-18 characters can be used and must contain characters from three of the following categories:
- Uppercase letters
- Lowercase letters
- Numbers (1, 2, 3, etc)
- Symbols, including ! @ # $ % & * ( ) - + = _ | \ [ ] { } < > , . : ; /
Here, we have four distinct categories of symbols,
We know that we can make $$88^{12} = 215,671,155,821,681,003,462,656$$ possible passwords of length 12. However, this doesn't take into account any of the restrictions on what kinds of symbols must be included.
We need to consider the number of length 12 passwords that consist of symbols from only one or two categories. In other words, these are strings over the following: $$U,L,N,S,U \cup L, U \cup N, U \cup S, L \cup N, L \cup S, N \cup S.$$ However, we have to be careful, because these sets are not disjoint! For instance, $U \subseteq (U \cup L)$ and so $U^{12} \subseteq (U \cup L)^{12}$. Or, even more troublesome, we have $(U \cup L)^{12} \cap (U \cup S)^{12} = U^{12}$.
This leads us to the following theorem about the sizes of unions that are not disjoint which we saw earlier.
Theorem 2.18 (Inclusion-Exclusion). For all finite sets $A$ and $B$, $$|A \cup B| = |A| + |B| - |A \cap B|.$$
Example 7.11. Let's systematically go through our set of forbidden passwords. We can ignore those that come from a single category, since they are included in the union of passwords with symbols from two categories. Consider passwords from the sets $(U \cup L)^{12}$ and $(U \cup N)^{12}$. The passwords from $U^{12}$ appear in both sets, so if simply added their sizes, we would be double counting this quantity. Thus, \begin{align*} |(U \cup L)^{12} \cup (U \cup N)^{12}| &= |(U \cup L)^{12}| + |(U \cup N)^{12}| - |(U \cup L)^{12} \cap (U \cup N)^{12}| \\ &= |(U \cup L)^{12}| + |(U \cup N)^{12}| - |U^{12}| \\ &= 52^{12} + 36^{12} - 26^{12} \\ &= 395,519,958,867,910,127,616 \end{align*} Now, we can take this set and consider its union with $(U \cup S)^{12}$ and observe that again, we have an intersection of $U^{12}$, so we get \begin{align*} & 395,519,958,867,910,127,616 + |(U \cup S)^{12}| - |U^{12}| \\ =& 395,519,958,867,910,127,616 + 52^{12} - 26^{12} \\ =& 786,301,536,397,498,638,336 \end{align*} Now, things get a bit trickier if we want to add the passwords from $(L \cup N)^{12}$. The intersection of our new set with our set that we're building is $L^{12} \cup N^{12}$. \begin{align*} & 786,301,536,397,498,638,336 + |(L \cup N)^{12}| - |L^{12} \cup N^{12}| \\ =& 786,301,536,397,498,638,336 + 36^{12} - (26^{12} + 10^{12}) \\ =& 790,944,487,779,158,573,056 \end{align*} Luckily, things don't get much more complicated than this. If we skip to the end, after adding our final two sets of passwords, we'll see that we have a total of 1,186,273,587,733,745,336,320 forbidden passwords. To get the number of valid passwords of length 12, we simply subtract this number from our total to get $$215,671,155,821,681,003,462,656 - 1,186,273,587,733,745,336,320 = 214,484,882,233,947,258,126,336$$ which is still on the order of $2.14 \times 10^{23}$. Of course, remember that these are the shortest allowable passwords. The total number of allowed passwords is much larger; one can simply perform the same calculations on passwords of lengths 13 through 18 and sum up the results.
Informally, permutations are ordered arrangements of a set of objects. This seems similar to what we'd do with strings or tuples, but the difference is that rather than selecting one element from a particular set, we are arranging elements from the same set. Let's define this formally first.
Definition 8.1. A permutation of a set $A$ is a bijective function $\pi : A \to A$.
Example 8.2. Consider a set $A = \{1,2,3\}$. We can define the function $\pi$ by $\pi(1) = 3$, $\pi(2) = 1$, and $\pi(3) = 2$. Note that since a permutation is a bijection, we require that each element of $A$ get mapped to a unique element of $A$.
A natural question is how many such functions must exist. We can view such functions as filling in the following $$\begin{pmatrix} 1 & 2 & 3 \\ \_ & \_ & \_ \end{pmatrix}.$$ For something of this size, we can easily enumerate all of the possibilities: \begin{matrix} (1,2,3) & (1,3,2) & (2,1,3) & (2,3,1) & (3,1,2) & (3,2,1) \end{matrix} This suggests that we can view this as an ordered arrangement of the elements of a set and we can apply some of the counting rules we've already seen.
Theorem 8.3. If $A$ is a set containing $n$ elements, then the number of permutations of $A$ is $n!$.
We will give an argument for a more general definition later, since we can generalize permutations and ask the question of how many ways there are to arrange some subset of a set of elements.
Example 8.4. Suppose you and six of your friends decide to go somewhere for dinner and like fools, you all drive your own cars. When you get there, there are only three parking spots left. How many possible parking situations are there? For the first spot, any seven of you could get to it first. Once the first person to arrive parks, then only six of you are left to fight for it, and after the second person arrives, the remaining five of you fight for the last spot. That gets us $7 \cdot 6 \cdot 5 = 210$ possible ways to have parked your cars.
Definition 8.5. An $r$-permutation is a permutation of $r$ elements taken from a set of $n$ elements.
Theorem 8.5. 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 8.7. 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 8.8. Many TV shows are serials, in that there's a prescribed way to watch them, which is generally chronologically. However, once in a while, someone decides to get clever and propose that they've found the one true order in which you're really supposed to watch the show. How many possible different such "watch orders" are there for a 14-episode show? For the first episode, we can choose from any of the episodes. Once we make that choice, we have 13 episodes left to choose from for the second spot, then 12 for the third, and so on. What we get in the end is $$14 \cdot 13 \cdot 12 \cdots 2 \cdot 1 = 14!.$$
Example 8.9. 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 8.10. 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 8.11. 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 8.12. 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 8.13. 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 8.14. Let's return to our parking situation from before. 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 8.15. 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 8.16. 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.
Sometimes, rather than picking a bunch of things from a fixed set, we may want to choose some objects from a set of types of things.
Example 9.1. Suppose you've been tasked with gathering six donuts/muffins/scones/other pastry and there is a choice of four types, say chocolate, plain, strawberry, and green. How many different combinations can you make, with repetition? For an ordinary combination, we would only choose one of each type, but because we're concerned about classes of objects rather than single objects, we're able to choose multiples of a particular type.
Let's begin by considering one possible selection, $C,P,G,C,C,G$ (three chocolate, one plain, two green), assuming this is the order in which we chose our goods. However, since this is a combination and some of the elements are indistinguishable anyway, the order doesn't really matter, so let's group them together into $CCCPGG$. Now, let's separate these so they don't touch each other and cross contaminate the flavours or something, and we have something that looks like $CCC|P|GG$.
We can play with this analogy further and suppose that the box we have has a compartment for each type,regardless of the number that we end up choosing, so we have something like $CCC|P||GG$. Finally, we note that since each compartment contains a specific type, we don't need to specifically denote the type, and we can represent our choice by $***|*||**$.
Let's consider another possible choice: $*||*|****$, which is one chocolate, one strawberry, and four green. What we observe is that each choice of six items from four classes can be represented by an arrangement of six stars representing the items and three bars representing the division of classes of items.
But this is something we've already seen before: it's just a string problem over the alphabet $\{*,|\}$. Since we have six objects and four classes, we can view our possible selections as a string of length 9 with 6 $*$s and 3 $|$s and ask how many such strings there are. There are $$\binom 9 6 = \binom 9 3 = \frac{9!}{6!3!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 3 \cdot 4 \cdot 7 = 84$$ such strings.
This method of using stars and bars to denote the objects and categories was popularized by William Feller's An Introduction to Probability Theory and its Applications in 1950.
Theorem 9.2. There are $\binom{r+n-1} r = \binom{r+n-1}{n-1} = \frac{(r+n-1)!}{r!(n-1)!}$ $r$-combinations from a set $A$ of $n$ elements with repetition.
Proof. We can view each possible selection as a string of length $r+n-1$ over the alphabet $\{\star,|\}$. We know that each string contains exactly $r$ $\star$s and $n-1$ $|$s. Then there are $\binom{r+n-1}{r}$ possible ways to choose spots for the $r$ $\star$s. Since all remaining spots must be occupied by $|$s, this is the same as choosing spots for $n-1$ $|$s, and there are $\binom{r+n-1}{n-1}$ ways to do so. $\tag*{$\Box$}$
Example 9.3. How many solutions to $x+y+z = 13$ are there, where $x,y,z$ are non-negative integers? Here, we can think of $x,y,z$ as our types of objects, of which we want to choose 13 in some combination. For instance, one solution would be to choose 6 $x$s, 4 $y$s, and 3 $z$s, which would give us $6+4+3 = 13$. Then the number of solutions is just $$\binom{13+3-1}{13} = \frac{15!}{13!2!} = \frac{15 \cdot 14}{2} = 105.$$
Just like with generalizing combinations, we can also think about how to generalize permutations.
Example 9.4. How many distinguishable permutations of the word $ACGACGA$ are there? There are two approaches we can take. The first is something we've seen already, by counting the number of ways to choose positions in a word. Here, we have three $A$s, two $C$s, and two $G$s. So we can choose three of seven positions for the $A$s and there are $\binom 7 3$ ways to do so. This leaves four spots. We choose two for the $C$s and there are $\binom 4 2$ ways to do so, leaving two spots for the two $G$s with $\binom 2 2$ ways to place them. In total, we have $$\binom 7 3 \binom 4 2 \binom 2 2 = \frac{7!}{3!4!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{2!0!} = \frac{7!}{3!2!2!} = 210.$$
The other way to consider this problem is to suppose that each symbol of our word is distinguishable, by adding marks to each symbol in some way. So suppose we have $A_1 C_1 G_1 A_2 C_2 G_2 A_3$. It is clear that there are $7!$ permutations of this word. However, we know that these symbols aren't really distinguishable, so we treat each such permutation as equivalent. For instance, there are $P(3,3) = 3!$ permutations of $A_1 A_2 A_3$ and we know these are equivalent once we make these indistinguishable. By removing all the indistinguishable permutations for each symbol, we get $$\frac{7!}{3!2!2!}$$ as before.
Theorem 9.5. The number of different permutatiosn of $n$ objects, where there are $n_i$ indistinguishable objects of type $i$ for $1 \leq i \leq k$ is $$\frac{n!}{n_1! n_2! \cdots n_k!}.$$
These are called multinomial coefficients and are denoted $\binom{n}{n_1,n_2, \dots, n_k}$. As you might guess, these are the coefficients that we'd get if we generalized the binomial theorem to multinomial terms. In particular, $$\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}$$ is the coefficient for the term $(x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k})$ in $(x_1 + x_2 + \cdots + x_k)^n$.
(Metaphorical) Boxes and (metaphorically) putting things in boxes are a popular formulation for combinatorial problems. There are a few variations, depending on whether the objects or the boxes are distinguishable or indistinguishable. This gives us four different kinds of problems.
If our boxes are distinguishable, then we'll see that we can apply the generalized counting techniques we've seen today.
Example 9.6. Suppose you've narrowed down a list of courses you might want to take in the 2020-2021 year to 14. Assuming every course on your list is offered every quarter, how many different ways to take 3 courses per quarter are there? This is the case of distinguishable items (courses) into distinguishable boxes (quarters). In the autumn quarter, you take 3 and there are 14 courses to choose from, so there would be $\binom{14}{3}$. For the winter quarter, you'd have 11 courses left to choose from, giving you $\binom{11}{3}$ possibilities, leaving $\binom 8 3$ choices for the spring quarter. Then this gives us $$\binom{14}{3} \binom{11}{3} \binom 9 3 = \frac{14!}{11!3!} \frac{11!}{8!3!} \frac{8!}{5!3!} = \frac{14!}{3!3!3!5!}$$ possible choices in total. This looks suspiciously like a number of distinguishable permutations with repeated elements. One way to think about this is to play the same trick that we did with the stars and bars and think about strings. If we want to dispense 14 objects, we consider a string of length 14, with each spot corresponding to an object. Then we assign that position a symbol $A,W,S,N$ for autumn, winter, spring, or none. Then this becomes exactly our permutation with repetition problem from above, with 3 $A$s, $W$s, and $S$s and 5 $N$s.
Example 9.7. Suppose that you go to a canned tomato factory and grab six unlabelled cans off of the assembly line. How many different ways to brand your premium tomatoes if you have four types of labels? This is the case of indistinguishable items (cans of tomatoes) and distinguishable boxes (labels). This turns out to be identical to combinations with repetitions. We have six objects that we need to assign four types. Then this is just $$\binom{6+4-1}{6} = \frac{9!}{3!6!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 3 \cdot 4 \cdot 7 = 84.$$ In other words, we can think of the act of taking $n$ generic objects from $k$ distinct types in the same way as putting $n$ generic objects things into $k$ distinct boxes.
Now, if our boxes are indistinguishable, the problem is much harder and there aren't any "nice" ways to compute the following numbers except to enumerate the possibilities.
Example 9.8. Suppose you're moving and you pack a cast iron skillet, a saucepan, a stainless steel skillet, and an enameled cast iron dutch oven into three boxes but forgot to label them. How many possible ways could you have packed them? This is the case of distinguishable items (cookware) and indistinguishable boxes (unlabelled boxes). Essentially, what we would like to do is take our $n$ objects and distribute them into $k$ sets. So in our case, if we label our cookware by $1,2,3,4$, then some possible distributions include $\{\{1\},\{2\},\{3,4\}\}$, $\{\{1,2,3\},\{4\},\emptyset\}$, and $\{1,2,3,4\},\emptyset,\emptyset\}$. But, if you remember our definitions from set theory, you'd remember that the last one would be $\{\{1,2,3,4\},\emptyset\}$. This means we need to account for the number of empty/non-empty boxes when counting.
It turns out that the number of all of these sets can be described by using Stirling numbers of the second kind. The Stirling number of the second kind for $n$ and $j$ is defined by $$\genfrac\{\}{0pt}{} n j = \frac 1 {j!} \sum_{i=0}^{j-1} (-1)^i \binom j i (j-i)^n.$$ This number describes the number of ways to distribute $n$ objects into exactly $j$ non-empty boxes. Then the total number of ways to distribute $n$ distinguishable objects into $k$ boxes where boxes can be empty is $$\sum_{j=1}^k \genfrac\{\}{0pt}{} n j = \sum_{j=1}^k \frac 1{j!} \sum_{i=0}^{j-1} (-1)^i \binom j i (j-i)^n.$$ As you might expect/hope, this is not something we'll get into further.
Example 9.9. Suppose you're moving and you pack six black t-shirts into four identical suitcases. How many ways can you distribute the t-shirts? This is the case of indistinguishable objects (black t-shirts) into indistinguishable boxes (identical suitcases). Again, we can enumerate these. This problem is equivalent to asking to find solutions to $a_1 + a_2 + a_3 + a_4 = 6$, with $0 \leq a_1 \leq a_2 \leq a_3 \leq a_4 \leq 6$. This looks similar to the combination with repetitions problem above, but the difference here is that the "order" in which the coefficients are assigned doesn't matter (this is enforced by the ordering condition on the $a_i$'s). Such a choice for $a_1, a_2, a_3, a_4$ is called a partition of an integer $n$ (6) into at most $k$ (4) positive integers. These are described by the partition numbers and have no simple closed form.