More Discrete Mathematicsvia Graph Theory

Subsection2.3.1The Quotient Principle

In Activity 93, you showed proved the algebraic formula \(\binom{n}{k} = \frac{n!}{(n-k)!k!}\text{.}\) However, this was done rather indirectly. First you proved the binomial identity \(P(n,k) = \binom{n}{k}k!\) and then wrote \(P(n,k) = \frac{n!}{(n-k)!}\) and solved for \(\binom{n}{k}\text{.}\)

This approach has the advantage of illustrating the connection between combinations and permutations, but the combinatorial argument that both sides of the identity are equal asked you to count the number of permutations in two ways. It is instructive to think of this equation in terms of combinations instead. Let's start with a concrete example.

Let's look carefully at what we did above. We had a set of permutations (all 60 of the 3-permutations of the set \(\{a,b,c,d,e\}\)). Then we noticed that some of these permutations corresponded the the same subset. Saying that these permutations were related like this feels like defining a equivalence relation.

This suggests a general approach to solving a counting problem. Say we want to count the number of elements in a set \(S\text{.}\) Suppose we can count the size of some set \(T\text{,}\) perhaps containing many more elements than we are actually interested in counting. Then define an equivalence relation \(\sim\) on \(T\) so that there is a bijection between \(S\) and the set of equivalence classes \(T/\sim\text{.}\) Then if we know the size of \(T/\sim\text{,}\) we have the size of \(S\text{.}\)

Look at the notation \(T/\sim\) that we used to denote the set of equivalence classes of \(T\) under \(\sim\text{.}\) This set is sometimes called the quotient set or quotient space of \(T\) by \(\sim\text{.}\) This is a good name, as you are dividing up a set into parts. It is also a good name because sometimes we can conclude

where \(A\) is one of the equivalence classes under \(\sim\text{.}\) When can you do this?

Note this is exactly what we did when we counted subsets: we divided the number of permutations by the number of permutations equivalent to each other. That worked precisely because all the equivalence classes had the same size!

This justifies the quotient principle we now state.

Like the product principle, the quotient principle is really just a statement about how division works. Here are a few examples of how you can use it in counting. In each of the following activities, make sure you can say exactly how the quotient principle could be used.

Subsection2.3.2When does Order Matter?

One way to distinguish combinations from permutations is by asking whether “order matters”. Both \(\binom{n}{k}\) and \(P(n,k)\) count the number of ways to select \(k\) objects from \(n\) objects without repeats, but you use the combination \(\binom{n}{k}\) when “order doesn't matter” and the permutation \(P(n,k)\) when “order matters”. Despite the presence of the scare quotes, this is not a false statement, but we must understand what we mean when we say “order matters”.

Understanding the role of order in distinguishing outcomes often suggests the use of the quotient principle. You might say we arrive at combinations by counting permutations and modding out by the order. Each block that corresponds to a single combination is a group of permutations that are only different because of their order. Let's see if we can apply this to other counting questions.

The previous activity illustrates that you cannot always simply apply the quotient principle to eliminate order mattering. What we are after in the 3-scoop shakes with possibly repeated flavors is a multiset, which is just like a set only we allow for elements to be in the set multiple times, but we still do not care in what order the elements are listed. So an example of an \(4\)-element multiset of \([7]\) is \(\{1,3,3,6\}\text{,}\) which is the same multiset as \(\{1,6,3,3\}\) but different from the multiset \(\{1,3,6\}\) (in particular, this multiset only has three elements).

What we tried to do above was to count multisets by first counting sequences with possibly repeated elements, and then divide out by the number of sequences that just differ by the arrangement of a particular multiset. But this didn't work, because the size of each block was not the same.

However, we would still like to be able to count the number of multisets. How can we do this? Is it an application of the quotient principle after all? To start, let's establish some notation. The number of \(k\)-element subsets of \([n]\) was given by \(n\) choose \(k\) (written \(\binom{n}{k}\)), so we will say that the number of \(k\)-element multisets of \([n]\) will be \(n\) multichoose \(k\), and write \(\mchoose{n}{k}\text{.}\) From what we have seen above, we can say,

despite the obvious allure of this possibility.

Our question now is, what should be in the numerator if not \(n^k\text{?}\) First let's get more comfortable with thinking of multisets as a model for counting questions.

The problems in Activity 121 are sometimes referred to as “distribution problems”, since we are asking for the number of ways to distribute some objects to some recipients. This is a useful model for the other counting techniques we have seen as well. For example, a permutation \(P(n,k)\) gives the number of ways to distribute \(n\) distinct objects to \(k\) distinct recipients, so that each recipient gets exactly one object.

The claim implicit in Activity 121 is that the number of ways to distribute \(n\) identical objects to \(k\) distinct recipients (now allowing each recipient to receive any number of objects, including zero) is \(\mchoose{n}{k}\text{.}\) If this is the case, then we should be able to think of the set of \(k\)-element multisets of \([n]\) as a distribution.

Now let's consider a related distribution problem, where in some way, order now matters. In fact, how is it that saying the distribution problems as in Activity 121 are ones for which order doesn't matter? Look back at our standard example of order mattering or not:

Consider the case where the books are distinct instead of identical. Note also that in the next few activities, the usage of the variables \(k\) and \(n\) are reversed from above. As you work through these next activities, think about why that choice was made.

The assignment of which books go to which shelves of a bookcase is simply a function from the books to the shelves. But a function does not determine which book sits to the left of which others on the shelf, and this information is part of how the books are arranged on the shelves. In other words, the order in which the shelves receive their books matters. Our function must thus assign an ordered list of books to each shelf. We will call such a function an ordered function. More precisely, an ordered function from a set \(S\) to a set \(T\) is a function that assigns an (ordered) list of elements of \(S\) to some, but not necessarily all, elements of \(T\) in such a way that each element of \(S\) appears on one and only one of the lists.²The phrase ordered function is not a standard one, because there is as yet no standard name for the result of an ordered distribution problem.

We often think of functions as a rule that assigns an output to each input. However, we could equally well specify a function by giving the complete inverse image of each element of the codomain. That is, to define a (non-ordered) function \(f:S \to T\text{,}\) we could give the set \(f\inv(t) = \{s \in S \st f(s) = t\}\) for each \(t \in T\text{.}\) The set of elements sent to \(t\) is a set for a function, but for an ordered function, it is a sequence.

AHA! The previous activity suggests that to count multisets, which is the same as counting distributions of identical objects to distinct recipients, we should apply the quotient principle to ordered functions.

What should the equivalence relation be? Think about bookshelves. An ordered function is a distribution of distinct books to distinct shelves. A multiset is a distribution of identical books to distinct shelves. So we want two ordered functions to be equivalent if their corresponding shelves contain the same number of books (we no longer care what those books are, just how many there are).

Now, given any ordered function, how many ordered functions are in its equivalence class? We can get any other element in the class by permuting the books (but keeping the numbers in each shelf constant). There are \(k\) books, so there are \(k!\) ways to permute them. This is the same for every ordered function, so the equivalence classes all have the same size.

Applying the quotient principle, we arrive at the following.

Subsection2.3.3More Distribution Problems

Both multisets and ordered functions allowed some of the recipients to receive nothing (or for some elements of \([n]\) to not be included in the multiset). What if we didn't want to allow this?

The previous activity is an example of what we might call an ordered surjection. As for ordered functions, we can apply the quotient principle to count distributions where the objects being distributed are no longer distinct.

So far, we have only considered distribution problems in which the recipients are distinct. There are plenty of situations where we would want to consider recipients identical. For example, a problem we will take up in Chapter 3 is how many ways we can partition an integer. For example, we could partition 5 as \(4+1\) or \(3+1+1\text{,}\) but we would not want to also count \(1+4\) or \(1+3+1\) (doing so would be creating a composition, which we have already considered). We can think of the integer partition problem as distributing the 5 units that make up 5 into some number of identical bins.

Here is another example, which we already have the tools to address.

We can think of stacking books into identical boxes as partitioning the books and then ordering the blocks of the partition. This turns out not to be a useful computational way of visualizing the problem because the number of ways to order the books in the various stacks depends on the sizes of the stacks and not just the number of stacks. However this way of thinking actually led to the first hint in Activity 131. Instead of dividing a set up into non-overlapping parts, we may think of dividing a permutation (thought of as a list) of our \(k\) objects up into \(n\) ordered blocks. We will say that a set of ordered lists of elements of a set \(S\) is a broken permutation of \(S\) if each element of \(S\) is in one and only one of these lists.³The phrase broken permutation is not standard, because there is no standard name for the solution to this kind of distribution problem. The number of broken permutations of a \(k\)-element set with \(n\) blocks is denoted by \(L(k,n)\text{.}\) The number \(L(k,n)\) is called a Lah Number and, from our solution to Activity 131, is equal to \(k!\binom{k-1}{n-1}/n!\text{.}\)

The Lah numbers are the solution to the question “In how many ways may we distribute \(k\) distinct objects to \(n\) identical recipients if order matters and each recipient must get at least one?”