Combinatorics Through Guided Discovery

Subsection 1.2.1 The sum and product principles

These problems contain among them the kernels of many of the fundamental ideas of combinatorics. For example, with luck, you just stated the sum principle (illustrated in Figure 1.2.1), and product principle (illustrated in Figure 1.2.2) in Problems 9 and Problem 10. These two counting principles are the basis on which we will develop many other counting principles.

You may have noticed some standard mathematical words and phrases such as set, ordered pair, function and so on creeping into the problems. One of our goals in these notes is to show how most counting problems can be recognized as counting all or some of the elements of a set of standard mathematical objects. For example Problem 4 is meant to suggest that the question we asked in Problem 3 was really a problem of counting all the ordered pairs consisting of a bread choice and a filling choice. We use \(A\times B\) to stand for the set of all ordered pairs whose first element is in \(A\) and whose second element is in \(B\) and we call \(A\times B\) the Cartesian product of \(A\) and \(B\text{,}\) so you can think of Problem 4 as asking you for the size of the Cartesian product of \(M\) and \(N\text{,}\) that is, asking you to count the number of elements of this Cartesian product.

When a set \(S\) is a union of disjoint sets \(B_1, B_2, \ldots, B_m\) we say that the sets \(B_1, B_2, \ldots, B_m\) are a partition of the set \(S\text{.}\) Thus a partition of \(S\) is a (special kind of) set of sets. So that we don't find ourselves getting confused between the set \(S\) and the sets \(B_i\) into which we have divided it, we often call the sets \(B_1, B_2, \ldots, B_m\) the blocks of the partition. In this language, the sum principle says that

if we have a partition of a set \(S\text{,}\) then the size of \(S\) is the sum of the sizes of the blocks of the partition.

The product principle says that

if we have a partition of a set \(S\) into \(m\) blocks, each of size \(n\text{,}\) then \(S\) has size \(mn\text{.}\)

You'll notice that in our formal statement of the sum and product pinciple we talked about a partition of a finite set. We could modify our language a bit to cover infinite sizes, but whenever we talk about sizes of sets in what follows, we will be working with finite sets. So as to avoid possible complications in the future, let us agree that when we refer to the size of a set, we are implicitly assuming the set is finite. There is another version of the product principle that applies directly in problems like Problem 5 and Problem 6, where we were not just taking a union of \(m\) disjoint sets of size \(n\text{,}\) but rather \(m\) disjoint sets of size \(n\text{,}\) each of which was a union of \(m'\) disjoint sets of size \(n'\text{.}\) This is an inconvenient way to have to think about a counting problem, so we may rephrase the product principle in terms of a sequence of decisions:

The counting principle you gave in Problem 11 is called the general product principle. We will outline a proof of the general product pinciple from the original product principle in Problem 80. Until then, let us simply accept it as another counting principle. For now, notice how much easier it makes it to explain why we multiplied the things we did in Problem 5 and Problem 6.

The point of Problem 14 is that the general product principle can be stated informally, as we did originally, or as a statement about counting sets of standard concrete mathematical objects, namely functions.

There are a number of different notations for the number of \(k\)-element permutations of an \(n\)-element set. The one we shall use was introduced by Don Knuth; namely \(n^{\underline{k}}\text{,}\) read “\(n\) to the \(k\) falling” or “\(n\) to the \(k\) down”. In Problem 20 you may have shown that

It is standard to call \(n^{\underline{k}}\) the \(k\)-th falling factorial power of \(n\), which explains why we use exponential notation. Of course we call it a factorial power since \(n^{\underline{n}} = n(n-1)\cdots 1\) which we call \(n\)-factorial and denote by \(n!\text{.}\) If you are unfamiliar with the \(\Pi\) notation, or product notation we introduced for products in Equation (1.1), it works just like the \(\Sigma\) notation works for summations.

Subsection 1.2.2 Functions and directed graphs

As another example how standard mathematical language relates to counting problems, Problem 7 explicitly asked you to relate the idea of counting functions to the question of Problem 6. You have probably learned in algebra or calculus how to draw graphs in the Cartesian plane of functions from a set of numbers to a set of numbers. You may recall how we can determine whether a graph is a graph of a function by examining whether each vertical straight line crosses the graph at most one time. You might also recall how we can determine whether such a function is one-to-one by examining whether each horizontal straight line crosses the graph at most one time. The functions we deal with will often involve objects which are not numbers, and will often be functions from one finite set to another. Thus graphs in the cartesian plane will often not be available to us for visualizing functions.

However, there is another kind of graph called a directed graph or digraph that is especially useful when dealing with functions between finite sets. We take up this topic in more detail in Appendix A, particularly Subsection A.1.2 and Subsection A.1.3. In Figure 1.2.3 we show several examples of digraphs of functions.

If we have a function \(f\) from a set \(S\) to a set \(T\text{,}\) we draw a line of dots or circles, called vertices to represent the elements of \(S\) and another (usually parallel) line of circles or dots to represent the elements of \(T\text{.}\) We then draw an arrow from the circle for \(x\) to the circle for \(y\) if \(f(x) = y\text{.}\) Sometimes, as in part (e) of the figure, if we have a function from a set \(S\) to itself, we draw only one set of vertices representing the elements of \(S\text{,}\) in which case we can have arrows both entering and leaving a given vertex. As you see, the digraph can be more enlightening in this case if we experiment with the function to find a nice placement of the vertices rather than putting them in a row.

Notice that there is a simple test for whether a digraph whose vertices represent the elements of the sets \(S\) and \(T\) is the digraph of a function from \(S\) to \(T\text{.}\) There must be one and only one arrow leaving each vertex of the digraph representing an element of \(S\text{.}\) The fact that there is one arrow means that \(f(x)\) is defined for each \(x\) in \(S\text{.}\) The fact that there is only one arrow means that each \(x\) in \(S\) is related to exactly one element of \(T\text{.}\) (Note that these remarks hold as well if we have a function from \(S\) to \(S\) and draw only one set of vertices representing the elements of \(S\text{.}\)) For further discussion of functions and digraphs see Sections A.1.1 and Subsection A.1.2 of {Appendix A}.

Notice that there is a great deal of consistency between the use of the word permutation in Problem 27 and the use in Problem 20. If we have some way \(a_1,a_2,\ldots,a_n\) of listing our set, then any other list \(b_1,b_2,\ldots,b_n\) gives us the permutation of \(S\) whose rule is \(f(a_i) =b_i\text{,}\) and any permutation of \(S\text{,}\) say the one given by \(g(a_i)=c_i\) gives us a list \(c_1,c_2,\ldots,c_n\) of \(S\text{.}\) Thus there is really very little difference between the idea of a permutation of \(S\) and an \(n\)-element permutation of \(S\) when \(n\) is the size of \(S\text{.}\)

Subsection 1.2.3 The bijection principle

Another name for a one-to-one and onto function is bijection. The digraphs marked (a), (b), and (e) in Figure 1.2.3 are digraphs of bijections. The description in Problem 26.c of the digraph of a bijection from \(X\) to \(Y\) illustrates one of the fundamental principles of combinatorial mathematics, the bijection principle:

Two sets have the same size if and only if there is a bijection between them.

It is surprising how this innocent sounding principle guides us into finding insight into some otherwise very complicated proofs.

Subsection 1.2.4 Counting subsets of a set

Notice that the first question in Problem 8 asked you for the number of ways to choose a three element subset from a 12 element subset. You may have seen a notation like \(\binom{n}{k}\text{,}\) \(C(n,k)\text{,}\) or \(_nC_k\) which stands for the number of ways to choose a \(k\)-element subset from an \(n\)-element set. The number \(\binom{n}{k}\) is read as “\(n\) choose \(k\)” and is called a binomial coefficient for reasons we will see later on. Another frequently used way to read the binomial coefficient notation is ``the number of combinations of \(n\) things taken \(k\) at a time." You are going to be asked to construct two bijections that relate to these numbers and figure out what famous formula they prove. We are going to think about subsets of the \(n\)-element set \([n] = \{1,2,3,\ldots, n\}\text{.}\) As an example, the set of two-element subsets of \([4]\) is

This example tells us that \(\binom{4}{2} = 6\text{.}\)

Subsection 1.2.5 Pascal's Triangle

The Pascal Equation that you derived in Problem 29 gives us the triangle in Figure 1.2.4. This figure has the number of \(k\)-element subsets of an \(n\)-element set as the \(k\)th number over in the \(n\)th row (we call the top row the zeroth row and the beginning entry of a row the zeroth number over). You'll see that your formula doesn't say anything about \(\binom{n}{k}\) if \(k=0\) or \(k=n\text{,}\) but otherwise it says that each entry is the sum of the two that are above it and just to the left or right.

It is less common to see Pascal's triangle as a right triangle, but it actually makes your formula easier to interpret. In Pascal's Right Triangle, the element in row \(n\) and column \(k\) (with the convention that the first row is row zero and the first column is column zero) is \(\binom{n}{k}\text{.}\) In this case your formula says each entry in a row is the sum of the one above and the one above and to the left, except for the leftmost and rightmost entries of a row, for which that doesn't make sense. Since the leftmost entry is \(\binom{n}{0}\) and the rightmost entry is \(\binom{n}{n}\text{,}\) these entries are both one (to see why, ask yourself how many \(0\)-element subsets and how many \(n\)-element subsets an \(n\)-element set has), and your formula then tells how to fill in the rest of the table.

Seeing this right triangle leads us to ask whether there is some natural way to extend the right triangle to a rectangle. If we did have a rectangular table of binomial coefficients, counting the first row as row zero (i.e., \(n=0\)) and the first column as column zero (i.e., \(k=0\)), the entries we don't yet have are values of \(\binom{n}{k}\) for \(k>n\text{.}\) But how many \(k\)-element subsets does an \(n\)-element set have if \(k>n\text{?}\) The answer, of course, is zero, so all the other entries we would fill in would be zero, giving us the rectangular array in Figure 1.2.6. It is straightforward to check that Pascal's equation now works for all the entries in the rectangle that have an entry above them and an entry above and to the left.

In Problems 18, Problem 28, and Problem 33 you gave three proofs of the following theorem.

The proofs in Problem 28 and Problem 33 use essentially the same bijection, but they interpret sequences of zeros and ones differently, and so end up being different proofs. We will give yet another proof, using bijections similar to those we used in proving the Pascal Equation, at the beginning of Chapter 2.

Subsection 1.2.6 The quotient principle

We are now going to analyze the result of Problem 35 in more detail in order to tease out another counting principle that we can use in a wide variety of situations.

In Table 1.2.8 we list all three-element permutations from the \(5\)-element set \(\{a,b,c,d,e\}\text{.}\) Each row consists of all \(3\)-element permutations of some subset of \(\{a,b,c,d,e\}\text{.}\) Because a given \(k\)-element subset can be listed as a \(k\)-element permutation in \(k!\) ways, there are \(3!=6\) permutations in each row. Because each \(3\)-element permutation appears exactly once in the table, each row is a block of a partition of the set of \(3\)-element permutations of \(\{a,b,c,d,e\}\text{.}\) Each block has size six. Each block consists of all \(3\)-element permutations of some three-element subset of \(\{a,b,c,d,e\}\text{.}\) Since there are ten rows, we see that there are ten \(3\)-element subsets of \(\{a,b,c,d,e\}\text{.}\) An alternate way to see this is to observe that we partitioned the set of all \(60\) three-element permutations of \(\{a,b,c,d,e\}\) into some number \(q\) of blocks, each of size six. Thus by the product principle, \(q\cdot 6=60\text{,}\) so \(q=10\text{.}\)

The formula you found in the Problem 42 is so useful that we are going to single it out as another principle. The quotient principle says:

If we partition a set \(P\) into \(q\) blocks, each of size \(r\text{,}\) then \(q=p/r.\)

The quotient principle is really just a restatement of the product principle, but thinking about it as a principle in its own right often leads us to find solutions to problems. Notice that it does not always give us a formula for the number of blocks of a partition; it only works when all the blocks have the same size. In Chapter 6, we develop a way to solve problems with different block sizes in cases where there is a good deal of symmetry in the problem. (The roundness of the table was a symmetry in the problem of people at a table; the fact that we can order the sets in any order is the symmetry in the problem of counting \(k\)-element subsets.)

In Section A.2 of Appendix A we introduce the idea of an equivalence relation, see what equivalence relations have to do with partitions, and discuss the quotient principle from that point of view. While that appendix is not required for what we are doing here, if you want a more thorough discussion of the quotient principle, this would be a good time to work through that appendix.