CMSC 27100 — Lecture 16

Counting arrangements

Suppose we have a set of items. How many ways are there to arrange these items? 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.

Suppose you are given a set of integers $\{a_1, a_2, \cdots, a_n\}$. We would like to arrange them from least to greatest. You may recognize this as the sorting problem. Assuming that the integers are distinct, we know there is one sorted arrangement, but how many possible arrangements are there in total?

Such arrangements are called permutations.

A permutation of a set $A$ is a sequence that contains every element of $A$ exactly once.

Consider a set $A = \{1,2,3\}$. What are the permutations of $A$? How many of them are there? One way of looking at it is that we are trying to fill in the following spots. $$\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 apply some of the counting rules we’ve already seen.

If $A$ is a set containing $n$ elements, then the number of permutations of $A$ is $n!$.

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.

Let’s think about sorting a set of $n$ integers again. It is well known that comparison-based sorting can be done in $O(n \log n)$ time. Because of this, it is often said that $O(n^2)$ algorithms like bubble sort are “brute-force” algorithms.

However, brute-force algorithms simply search the solution space and test all possible solutions. Since we are looking for an optimal arrangement, the solution space for sorting is the set of all $n$-item permutations. In other words, there are $n!$ possible solutions. To check whether a solution is in sorted order, we need to perform $O(n)$ comparisons. This means that a true brute force algorithm for sorting, which checks all possible permutations, has running time $O(n \cdot n!)$.

This suggests that while algorithms like bubble sort are not optimal, they do much better than brute force. To accomplish this, they must exploit some aspect of the structure of the problem and are more clever than we typically give credit for.

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.

But what if we didn’t want to go to every city, but instead wanted to go to some subset of them. How many ways are there to do this? We can think about this informally: we carry out the same process as before, but stop when we reach our desired number of choices. this lead to the following definition and result.

An $r$-permutation is a permutation of $r$ elements taken from a set of $n$ elements.

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).$$

If $n$ is positive and $0 \leq r \leq n$, then $$P(n,r) = \frac{n!}{(n-r)!}.$$

Note that the total number of ways to order a set of $n$ elements is $n!$. By definition, $P(n,r)$ is the number of 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*}

It is very common to immediately view this as an algebraic problem—after all, it’s not too hard to manipulate the two factorials into our desired form. However, this doesn’t really tell us much about how to obtain the value $P(n,r)$. This is another example of combinatorial proof. This is a proof that relies on arguments about the construction and enumeration of the objects in question.

Notice that we relate the quantity that we’re computing with the process by which we’re constructing the associated object. This offers more insight into how we’re enumerating or constructing the object than a direct algebraic proof. This kind of information is useful, particularly for computer scientists who are often interested in using this information to literally enumerate or construct solutions.

Counting equivalent objects

We also snuck in a new rule: the division rule. Here’s what we did: we said that the total number of permutations on $n$ objects is $n!$, which is the same as counting permutations on $r$ objects, which is $P(n,r)$, and then counting permutations on the rest of the $n-r$ objects, which is $(n-r)!$. Then we conclude algebraically that $P(n,r) = \frac{n!}{(n-r)!}$.

Implicitly, what this says is that the number of $r$-permutations can be found by counting all $n$-permutations and tossing out the last $n-r$ elements—since they don’t matter, we can treat all of them as equivalent. This is essentially what the division rule says.

Since the division rule is really about process (i.e. the number of equivalent ways to do something), we’ll frame the rule in terms of functions.

If there exists a function $f : A \to B$ such that for every $b \in B$, there are exactly $k$ elements $a_1, \dots, a_k \in A$ such that $f(a_i) = b$ (i.e. $|\{a \in A \mid f(a) = b\}| = k$), then $|A| = k \cdot |B|$.

As a result, we can conclude that $|B| = \frac{|A|}k$.

In our discussion of the number of $r$-permutations, we can consider the function that maps permutations of $n$ things to the permutations of $r$ things. One such function is the one that simply takes the first $r$ elements of each permutation. For example, suppose our salesman from earlier is considering a list of itineraries containing permutations like \[(\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{CTS}, \mathrm{YUL}, \mathrm{MSP})\] but they realize they only have time for a trip to three cities. Then they would consider a a mapping from 6-permutations to 3-permutations by simply taking the “front” of the permutation: \begin{align*} (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{CTS}, \mathrm{MSP}, \mathrm{YUL}) &\mapsto (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}) \\ (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{MSP}, \mathrm{CTS}, \mathrm{YUL}) &\mapsto (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}) \\ (\mathrm{CTS}, \mathrm{HND}, \mathrm{YYZ}, \mathrm{MSP}, \mathrm{ORD}, \mathrm{YUL}) &\mapsto (\mathrm{CTS}, \mathrm{HND}, \mathrm{YYZ}) \\ \end{align*}

More abstractly, we would have something like \[(3,1,5,2,4,6) \mapsto (3,1,5)\] We see then that for each 3-permutation, there are $6 = 3!$ possible 6-permutations that map to it: \[(3,1,5) \leftarrow \begin{cases} (3,1,5,2,4,6) \\ (3,1,5,2,6,4) \\ (3,1,5,4,2,6) \\ (3,1,5,4,6,2) \\ (3,1,5,6,2,4) \\ (3,1,5,6,4,2) \end{cases} \] So when framed via the Division Rule, we have $|A| = n!$, $|B| = P(n,r)$, and $k = (n-r)!$. That is, for each $r$-permutation of $n$ things, we can associate it with $(n-r)!$ different $n$-permutations.

Counting subsets

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.

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 $\binom n r$. This is read “$n$ choose $r$”.

Sometimes you’ll see this denoted as $C(n,r)$, but that notation really only exists in a first discrete math or combinatorics class—everyone ends up dropping it sooner or later in favour of $\binom n r$.

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.

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?

If $n \gt 0$ and $0 \leq r \leq n$, then $$\binom n r = \frac{n!}{r!(n-r)!}.$$

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) = \binom n r \cdot r!.$$ However, the ordering of the $r$ elements doesn’t matter—every permutation containing the same items is considered equivalent. So we apply the Division Rule to remove all such equivalent items, of which there are $r!$. This gives us $$\binom n r = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}.$$

Suppose you and six of your friends decide to go somewhere for dinner and like fools, you all drive your own cars. This is foolish because when you get there, there are only three parking spots left. How many possible parking situations are there? 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 $$\binom 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.

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.

Here is an example where we have to consider carefully which setting our problem is in.

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.

A common line of thinking is that since we are constructing strings, we must be counting permutations, since the ordering of a string matters. However, we need to check this against the set that is being permuted or chosen from. If we have a length $n$ permutation, this must be drawn from a set of $n$ items. But our string is a binary string:the set of items is $\{0,1\}$. This suggests that the set under consideration is not the set of symbols.

Consider the problem statement again: we want exactly $\frac n 2$ 0’s and 1’s in our string. What varies about all possible strings is the positions of the 0’s and 1’s. In other words, the set under consideration is the set of positions in the string. Since the ordering of the positions doesn’t matter (i.e., the order in which they are assigned), this is a combination problem.

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 $\binom n {\frac n 2} = \frac{n!}{\frac n 2! \left(n - \frac n 2\right)!} = \frac{n!}{\left(\frac n 2 !\right)^2}$ balanced words.

Recall that combinations are really about counting subsets, while this suggests that there’s a correspondence between how to arrange or select spots in a binary string. This makes sense—after all, we proved that the subsets of an $n$-element set are in correspondence with binary strings of length $n$.

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 $$\binom n {\frac n 3} \cdot \binom {\frac{2n}3} {\frac n 3} = \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}.$$