Exploring Combinatorial Mathematics

Subsection 1.3.1 The Quotient Principle

In Exercise 29, you proved the algebraic formula \(\binom{n}{k} = \frac{n!}{(n-k)!k!}\text{.}\) However, this was done rather indirectly. First you proved the identity \(P(n,k) = \binom{n}{k}k!\text{,}\) then wrote \(P(n,k) = \frac{n!}{(n-k)!}\text{,}\) and finally 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.

Subsection 1.3.2 When 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 54 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 \(k\) distinct objects to \(n\) distinct recipients, so that each recipient gets at most one object.

The claim implicit in Activity 54 is that the number of ways to distribute \(k\) identical objects to \(n\) 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 54 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.

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.²

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.

It is interesting that the number of \(k\)-element multisets of \([n]\) can be expressed as a binomial coefficient. This suggests there should be a way to describe a multiset as choosing \(k\) things from a collection of \(n-1+k\) things. Or perhaps thinking about each multiset as a \((n-1+k)\)-bit string of weight \(k\text{.}\)

There is a standard interpretation for this. We call this approach stars and bars (others use balls and wall or dashes and slashes; the important thing is that it rhymes). The idea is that we represent each multiset as a string of \(k\) “stars” and \(n-1\) “bars”. These are really just bit strings in disguise, so the binomial coefficient becomes clear. The only question is how do multisets correspond to the strings?

Thinking of these distribution problems as “stars and bars problems” can make solving them very quick. The key step is deciding what part of the problem the stars correspond to, and what the bars correspond do. The remaining exercises here should give you some practice with this.

Subsection 1.3.3 More 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. Just like we did with 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 2 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 Exercise 66. 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 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 Exercise 66, 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?”