Blog

MATH 239/249 Introduction to Combinatorics Hello World, and Thanks! The following parts of these notes are still UNDER CONSTRUCTION. (Estimated completion date: Fall 2021.) Most of these are additional topics not covered during the semester. The old notes are also available on the course website. Proof of Theorem 4.18 (inhomogeneous linear recurrence relations) Section 8.4 (planar duality) Part III: Chapters 12, 13, and 14 will appear in three installments over the course of the next year. c 2020 David G. Wagner Department of Combinatorics and Optimization Faculty of Mathematics University of Waterloo Contents I Introduction to Enumeration 11 1 Basic Principles of Enumeration. 15 1.1 The Essential Ideas. . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.1 Choices – “AND” versus “OR”. . . . . . . . . . . . . . . 15 1.1.2 Lists, permutations, and subsets. . . . . . . . . . . . . . 17 1.1.3 Think of what the numbers mean. . . . . . . . . . . . . 20 1.1.4 Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.1.5 Bijective proofs. . . . . . . . . . . . . . . . . . . . . . . . 23 1.1.6 Inclusion/Exclusion. . . . . . . . . . . . . . . . . . . . . 26 1.1.7 Combinatorial probabilities. . . . . . . . . . . . . . . . . 29 1.2 Examples and Applications. . . . . . . . . . . . . . . . . . . . . 30 1.2.1 The Vandermonde convolution formula. . . . . . . . . 30 1.2.2 Common birthdays. . . . . . . . . . . . . . . . . . . . . 31 1.2.3 An example with multisets. . . . . . . . . . . . . . . . . 33 1.2.4 Poker hands. . . . . . . . . . . . . . . . . . . . . . . . . 36 1.2.5 Derangements. . . . . . . . . . . . . . . . . . . . . . . . 38 1.3 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2 The Idea of Generating Series. 47 2.1 The Binomial Theorem and Binomial Series. . . . . . . . . . . . 48 3 2.2 The Theory in General. . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.1 Generating series. . . . . . . . . . . . . . . . . . . . . . . 52 2.2.2 The Sum, Product, and String Lemmas. . . . . . . . . . 54 2.3 Compositions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.4 Subsets with Restrictions. . . . . . . . . . . . . . . . . . . . . . 62 2.5 Proof of Inclusion/Exclusion. . . . . . . . . . . . . . . . . . . . 65 2.6 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3 Binary Strings. 73 3.1 Regular Expressions and Rational Languages. . . . . . . . . . 74 3.2 Unambiguous Expressions. . . . . . . . . . . . . . . . . . . . . 77 3.2.1 Translation into generating series. . . . . . . . . . . . . 78 3.2.2 Block decompositions. . . . . . . . . . . . . . . . . . . . 79 3.2.3 Prefix decompositions. . . . . . . . . . . . . . . . . . . . 82 3.3 Recursive Decompositions. . . . . . . . . . . . . . . . . . . . . 83 3.3.1 Excluded substrings. . . . . . . . . . . . . . . . . . . . . 84 3.4 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4 Recurrence Relations. 93 4.1 Fibonacci Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.2 Homogeneous Linear Recurrence Relations. . . . . . . . . . . . 96 4.3 Partial Fractions. . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.3.1 The Main Theorem. . . . . . . . . . . . . . . . . . . . . . 105 4.3.2 Inhomogeneous Linear Recurrence Relations. . . . . . 107 4.4 Quadratic Recurrence Relations. . . . . . . . . . . . . . . . . . 110 4.4.1 The general binomial series. . . . . . . . . . . . . . . . . 111 4.4.2 Catalan numbers. . . . . . . . . . . . . . . . . . . . . . . 112 4.5 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 II Introduction to Graph Theory 119 5 Graphs and Isomorphism. 123 5.1 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.2 The Handshake Lemma. . . . . . . . . . . . . . . . . . . . . . . 124 5.3 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.4 Isomorphism. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.5 Some more Basic Concepts. . . . . . . . . . . . . . . . . . . . . 136 5.6 Multigraphs and Directed Graphs. . . . . . . . . . . . . . . . . 140 5.7 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6 Walks, Paths, and Connectedness. 147 6.1 Walks, Trails, Paths, and Cycles. . . . . . . . . . . . . . . . . . . 147 6.2 Connectedness. . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.3 Euler Tours. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.4 Bridges / Cut-edges. . . . . . . . . . . . . . . . . . . . . . . . . 158 6.5 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7 Trees. 165 7.1 Trees and Minimally Connected Graphs. . . . . . . . . . . . . . 165 7.2 Spanning Trees and Connectedness. . . . . . . . . . . . . . . . 168 7.3 Search Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 7.4 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 8 Planar Graphs. 179 8.1 Plane Embeddings of Graphs. . . . . . . . . . . . . . . . . . . . 179 8.1.1 Stereographic projection. . . . . . . . . . . . . . . . . . 182 8.2 Kuratowski’s Theorem. . . . . . . . . . . . . . . . . . . . . . . . 183 8.3 Numerology of Planar Graphs. . . . . . . . . . . . . . . . . . . 185 8.3.1 The “Faceshaking” Lemma. . . . . . . . . . . . . . . . . 185 8.3.2 Euler’s Formula. . . . . . . . . . . . . . . . . . . . . . . 187 8.3.3 The Platonic solids. . . . . . . . . . . . . . . . . . . . . . 190 8.4 Planar Duality. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 8.5 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 9 Graph Colouring. 201 9.1 Chromatic Number. . . . . . . . . . . . . . . . . . . . . . . . . . 201 9.2 Colouring Planar Graphs. . . . . . . . . . . . . . . . . . . . . . 205 9.2.1 The Four Colour Theorem. . . . . . . . . . . . . . . . . 205 9.2.2 The Five Colour Theorem. . . . . . . . . . . . . . . . . . 205 9.3 Chromatic Number versus Girth. . . . . . . . . . . . . . . . . . 208 9.4 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10 Bipartite Matching. 211 10.1 Matchings and Covers. . . . . . . . . . . . . . . . . . . . . . . . 212 10.2 Ko¨nig’s Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . 214 10.2.1 Anatomy of a bipartite matching. . . . . . . . . . . . . . 215 10.2.2 A bipartite matching algorithm. . . . . . . . . . . . . . 217 10.3 Hall’s Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 10.4 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 III Further Topics 225 11 Computing Averages. 229 11.1 Bivariate Generating Series. . . . . . . . . . . . . . . . . . . . . 229 11.1.1 The Sum, Product, and String Lemmas. . . . . . . . . . 231 11.2 Computing Averages. . . . . . . . . . . . . . . . . . . . . . . . . 233 11.3 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 12 Finite State Machines. 243 12.1 Excluded Substrings. . . . . . . . . . . . . . . . . . . . . . . . . 243 12.2 Domino Tilings. . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 12.3 Tesselations of the Plane. . . . . . . . . . . . . . . . . . . . . . . 243 12.4 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 13 Optimal Trees. 247 13.1 Minimum Cost Spanning Trees. . . . . . . . . . . . . . . . . . . 247 13.2 Breadth-First Search Trees. . . . . . . . . . . . . . . . . . . . . . 247 13.3 Depth-First Search Trees. . . . . . . . . . . . . . . . . . . . . . . 247 13.4 The A* Path-finding Algorithm. . . . . . . . . . . . . . . . . . . 248 13.5 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 14 Graphs and Linear Algebra. 249 14.1 Turning on the Lights. . . . . . . . . . . . . . . . . . . . . . . . 249 14.2 Cycle Space and Cut Space. . . . . . . . . . . . . . . . . . . . . 254 14.3 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Preliminaries. MATH 239 is an introduction to two of the main areas in combinatorics – enumeration and graph theory. MATH 249 is an advanced version of MATH 239 intended for very strong students. These courses are designed for stu- dents in the second year of an undergraduate program in mathematics or computer science. The prerequisites required from first-year mathematics are as follows. From MATH 135. Abstract algebra I: sets and propositional logic, proofs, mathematical induction, modular arithmetic, complex numbers, the Fundamental Theorem of Algebra. From MATH 136. Linear algebra I: systems of linear equations, Gaus- sian elimination, matrix algebra, vector spaces. From MATH 137. Calculus I: algebra with power series, open/closed sets, continuous functions, differentiation (but not integration). We use the following standard notation for various number systems. natural numbers N = {0, 1, 2, 3, …} including zero 0 integers Z = {…, 2, 1, 0, 1, 2, …} rational numbers Q real numbers R complex numbers C integers (modulo n) Zn = {[0], [1], [2], …, [n 1]} finite field of prime size Fp = Zp The cardinality (size) of a set S is denoted by |S|. For convenience, we use LHS and RHS as shorthand for “left-hand side” and “right-hand side”, respectively. 9 Part I Introduction to Enumeration 11 Overview. Suppose I pay $5 for a lottery ticket – what is the chance that I win a share of the top prize It depends on the details, of course. There are a certain number of ways to win, and a certain number of ways to lose. Enumeration is the art and science of figuring out this kind of thing. This is the subject of the first part of these course notes. There are two broad principles of the subject. The combinatorial ap- proach is to construct explicit one-to-one correspondences between sets to show that they have the same size. The algebraic approach is to translate the information about the problem from combinatorics into algebra, and then to use algebraic techniques to determine the sizes of the sets. We will see many examples of both approaches. In Chapter 1 we begin by introducing the basic building blocks of the the- ory: subsets, lists and permutations, multisets, binomial coefficients, and so on. In Section 1.2 the use of these objects is illustrated by analyzing various applications and examples. In Chapter 2 we introduce the idea of generating series. This begins with the Binomial Theorem and Binomial Series, which are of fundamental im- portance for later results. The general theory of generating series is devel- oped in Section 2.2, and its use is illustrated by analyzing “compositions” in Section 2.3. In Chapter 3 we consider the enumeration of various sets of binary strings, namely those which can be described by regular expressions – the “rational languages”. This provides an interesting and varied class of examples to which the results of Chapters 2 and 4 apply. In Chapter 4 we consider sequences which satisfy a homogeneous linear recurrence relation with initial conditions, the sequences arising in Chapters 13 2 and 3 being examples. This technique allows us to calculate the numbers which answer the various counting problems we have been considering. By using Partial Fractions we can derive an even better solution to such problems, although the calculations involved are also more complicated. (We include a proof of Partial Fractions for completeness.) In Section 4.4 we briefly discuss recurrence relations which are quadratic rather than linear. Two additional topics are discussed in Chapters 11 and 12. Chapter 1 Basic Principles of Enumeration. 1.1 The Essential Ideas. 1.1.1 Choices – “AND” versus “OR”. In the next few pages we will often be constructing an object of some kind by repeatedly making a sequence of choices. In order to count the total number of objects we could construct we must know how many choices are available at each step, but we must know more: we also need to know how to combine these numbers correctly. A generally good guideline is to look for the words “AND” and “OR” in the description of the sequence of choices available. Here are a few simple examples. Example 1.1. On a table before you are 7 apples, 8 oranges, and 5 ba- nanas. Choose an apple and a banana. There are 7 choices for an apple AND 5 choices for a banana: 7×5 = 35 choices in all. Choose an apple or an orange. There are 7 choices for an apple OR 8 choices for an orange: 7+8 = 15 choices in all. Choose an apple and either an orange or a banana. There are 7× (8 + 5) = 91 possible choices. 15 16 Basic Principles. Section 1.1 Choose either an apple and an orange, or a banana. There are (7× 8) + 5 = 61 possible choices. Generally, “AND” corresponds to multiplication and “OR” corresponds to addition. The last two of the above examples show that it is important to determine exactly how the words “AND” and “OR” combine in the de- scription of the problem. From a mathematical point of view, “AND” corresponds to the Cartesian product of sets. If you choose one element of the set A AND you choose one element of the set B, then this is equivalent to choosing one element of the Cartesian product of A and B: A×B = {(a, b) : a ∈ A and b ∈ B}, which is the set of all ordered pairs of elements (a, b) with a ∈ A and b ∈ B. In general, the cardinalities of these sets are related by the formula |A×B| = |A| · |B|. Similarly, from a mathematical point of view, “OR” corresponds to the union of sets. If you choose one element of the set A OR you choose one element of the set B, then this is equivalent to choosing one element of the union of A and B: A ∪B = {c : c ∈ A or c ∈ B}, which is the set of all elements c which are either in A or in B. It is not always true that |A∪B| = |A|+ |B|, because any elements in both A and B would be counted twice by |A| + |B|. The intersection of A and B is the set A ∩B = {c : c ∈ A and c ∈ B}, which is the set of all elements c which are both in A and in B. What is generally true is that |A ∪B| = |A|+ |B| |A ∩B|. (This is the first instance of the Principle of Inclusion/Exclusion, which will be discussed in general in Subsection 1.1.6.) In particular, if A ∩ B = then |A ∪ B| = |A| + |B|. Thus, in order to interpret “OR” as addition, it Section 1.1 Basic Principles. 17 is important to check that the sets of choices A and B have no elements in common. Such a union of sets A and B for which A ∩ B = is called a disjoint union of sets. When solving enumeration problems it is usually very useful to describe a choice sequence for constructing the set of objects of interest, paying close attention to the words “AND” and “OR”. 1.1.2 Lists, permutations, and subsets. A list of a set S is a list of the elements of S exactly once each, in some order. For example, the lists of the set {1, a,X, g} are: 1aXg a1Xg X1ag g1aX 1agX a1gX X1ga g1Xa 1Xag aX1g Xa1g ga1X 1Xga aXg1 Xag1 gaX1 1gaX ag1X Xg1a gX1a 1gXa agX1 Xga1 gXa1 A permutation is a list of the set {1, 2, …, n} for some n ∈ N. A per- mutation σ : a1a2…an can be interpreted as a function σ : {1, 2, …, n} → {1, 2, …, n} by putting σ(i) = ai for all 1 ≤ i ≤ n. To construct a list of S we can choose any element v of S to be the first element in the list and follow this with any list of the set S r {v}. That is how the table above is arranged – each of the four columns corresponds to one choice of an element of {1, a,X, g} to be the first element of the list. Within each column, all the lists of the remaining elements appear after the first element. Let pn denote the number of lists of an n-element set S. The first sentence of the previous paragraph is translated into the equation pn = n · pn 1, provided that n is positive. (In this equation there are n choices for the first element v of the list, AND pn 1 choices for the list of S r {v} which follows it.) It is important to note here that each list of S will be produced exactly once by this construction. 18 Basic Principles. Section 1.1 Since it is easy to see that p1 = 1 (and p2 = 2), a simple proof by induction on n shows the following: Theorem 1.2. For every n ≥ 1, the number of lists of an n-element set S is n(n 1)(n 2) · · · 3 · 2 · 1. In particular, taking S = {1, 2, …, n}, this is the number of permutations of size n. The term n factorial is used for the number n(n 1) · · · 3 · 2 · 1, and it is denoted by n! for convenience. We also define 0! to be the number of lists of the 0-element (empty) set . Since we want the equation pn = n · pn 1 to hold when n = 1, and since p1 = 1! = 1, we conclude that 0! = p0 = 1 as well. A subset of a set S is a collection of some (perhaps none or all) of the elements of S, at most once each and in no particular order. To specify a particular subset A of S, one has to decide for each element v of S whether v is in A or v is not in A. Thus we have two choices – v ∈ A OR v 6∈ A – for each element v of S. If S = {v1, v2, …, vn} has n elements then the total number of choices is 2n since we have 2 choices for v1 AND 2 choices for v2 AND . . . AND 2 choices for vn. Theorem 1.3. For every n ≥ 0, the number of subsets of an n-element set is 2n. A partial list of a set S is a list of a subset of S. That is, it is a list of some (perhaps none or all) of the elements of S, at most once each and listed in some particular order. We are going to count partial lists of length k of an n-element set. First think about the particular case n = 6 and k = 3, and the set S = {a, b, c, d, e, f}. A partial list of S of length 3 is a list xyz of elements of S, which must all be different. There are: 6 choices for x (since x is in S), AND 5 choices for y (since y ∈ S but y 6= x), AND 4 choices for z (since z ∈ S but z 6= x and z 6= y). Altogether there are 6 · 5 · 4 = 120 partial lists of {a, b, c, d, e, f} of length 3. Section 1.1 Basic Principles. 19 This kind of reasoning works just as well in the general case. If S is an n-element set and we want to construct a partial list v1v2…vk of elements of S of length k, then there are: n choices for v1, AND n 1 choices for v2, AND …. n (k 2) choices for vk 1, AND n (k 1) choices for vk. This proves the following result. Theorem 1.4. For n, k ≥ 0, the number of partial lists of length k of an n-element set is n(n 1) · · · (n k + 2)(n k + 1). Notice that if k > n then the number 0 will appear as one of the factors in the product n(n 1) · · · (n k + 2)(n k + 1). This makes sense, because if k > n then there are no partial lists of length k of an n-element set. On the other hand, if 0 ≤ k ≤ n then we could also write this product as n(n 1) · · · (n k + 2)(n k + 1) = n! (n k)! . We next count subsets of an n-element set S which have a particular size k. So for n, k ≥ 0 let (n k ) denote the number of k-element subsets of an n- element set S. Notice that if k < 0 or k > n then ( n k ) = 0 because in these cases it is impossible for S to have a k-element subset. Thus we need only consider k in the range 0 ≤ k ≤ n. To count k-element subsets of S we consider another way of constructing a partial list of length k of S. Specifically, we can choose a k-element subset A of S AND a list of A. The result will be a list of a subset of S of length k. Since every partial list of length k of S is constructed exactly once in this way, this translates into the equation( n k ) · k! = n! (n k)! . 20 Basic Principles. Section 1.1 In summary, we have proved the following result. Theorem 1.5. For 0 ≤ k ≤ n, the number of k-element subsets of an n- element set is ( n k ) = n! k!(n k)! . The numbers ( n k ) are read as “n choose k” and are called binomial coefficients . 1.1.3 Think of what the numbers mean. Usually, when faced with a formula to prove, one’s first thought is to prove it by algebraic calculations, or perhaps with an induction argument, or maybe with a combination of the two. But often that is not the easiest way, nor is it the most informative. A much better strategy is one which gives some in- sight into the meaning of all of the parts of the formula. If we can interpret all the numbers as counting things, addition as “OR”, and multiplication as “AND”, then we can hope to find an explanation of the formula by con- structing some objects in the correct way. Example 1.6. Consider the equation, for any n ≥ 0:( n 0 ) + ( n 1 ) + ( n 2 ) + · · ·+ ( n n ) = 2n. This could be proved by induction on n, but many more details would have to be given and the proof would not address the true “meaning” of the formula. Instead, let’s interpret everything combinatorially: the number of subsets of the n-element set {1, 2, …, n} is 2n; for each 0 ≤ k ≤ n, the number of k-element subsets of {1, 2, …, n} is ( n k ) ; addition corresponds to “OR” (that is, disjoint union of sets). So, this formula is saying that choosing a subset of {1, 2, …, n} (in one of 2n ways) is equivalent to choosing a k-element subset of {1, 2, …, n} (in one of ( n k ) ways) for exactly one value of k in the range 0 ≤ k ≤ n. Said that way the formula becomes self–evident, and there is nothing more to prove. Section 1.1 Basic Principles. 21 Example 1.7. Consider the equation( n k ) = ( n 1 k 1 ) + ( n 1 k ) where we are using the fact that ( m j ) = 0 if j < 0 or j > m. This equation can be proven algebraically from the formula of Theo- rem 1.5, and that is a good exercise which I encourage you to try. But a more informative proof interprets these numbers combinatorially as follows: (n k ) is the number of k-element subsets of {1, 2, …, n}; (n 1 k 1 ) is the number of (k 1)-element subsets of {1, 2, …, n 1}; (n 1 k ) is the number of k-element subsets of {1, 2, …, n 1}; addition corresponds to disjoint union of sets. So, this equation is saying that choosing a k-element subsetA of {1, 2, …, n} is equivalent to either choosing a (k 1)-element subset of {1, 2, …, n 1} or a k-element subset of {1, 2, …, n 1}. This is perhaps not as clear as the previous example, but the two cases depend upon whether the cho- sen k-element subset A of {1, 2, …, n} is such that n ∈ A OR n 6∈ A. If n ∈ A then Ar {n} is a (k 1)-element subset of {1, 2, …, n 1}, while if n 6∈ A then A is a k-element subset of {1, 2, …, n 1}. This construction explains the correspondence, proving the formula. This principle – interpreting equations combinatorially and proving the formulas by describing explicit correspondences between sets of objects – is one of the most important and powerful ideas in enumeration. We will apply this way of thinking throughout the first part of these notes. Incidentally, the equation in Example 1.7 is a very useful recurrence rela- tion for computing binomial coefficients quickly. Together with the facts ( n k ) = n! k!(n k)! = n! (n k)!(n (n k))! = ( n n k ) and ( n 0 ) = ( n n ) = 1 it can be used to compute any number of binomial coeffi- 22 Basic Principles. Section 1.1 cients without difficulty. The resulting table is known as Pascal’s Triangle : nk 0 1 2 3 4 5 6 7 8 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 1.1.4 Multisets. Imagine a bag which contains a large number of marbles of three colours – red, green, and blue, say. The marbles are all indistinguishable from one another except for their colours. There are N marbles of each colour, where N is very, very large (more precisely we should be considering the limit as N → ∞). If I reach into the bag and pull out a handful of 11 marbles, I will have r red marbles, g green marbles, and b blue marbles, for some nonnegative integers (r, g, b) such that r + g + b = 11. How many possibile outcomes are there The word “multiset” is meant to suggest a set in which the objects can oc- cur more than once. For example, the outcome (4, 5, 2) in the above situation corresponds to the “set” {R,R,R,R,G,G,G,G,G,B,B} in which R is a red marble, G is a green marble, and B is a blue marble. This is an 11-element multiset with elements of three types. The number of these multisets is the solution to the above problem. Definition 1.8. Let n ≥ 0 and t ≥ 1 be integers. A multiset of size nwith elements of t types is a sequence of nonnegative integers (m1, …,mt) such that m1 +m2 + · · ·+mt = n. The interpretation is thatmi is the number of elements of the multiset which are of the i-th type, for each 1 ≤ i ≤ t. Section 1.1 Basic Principles. 23 Theorem 1.9. For any n ≥ 0 and t ≥ 1, the number of n-element multisets with elements of t types is ( n+ t 1 t 1 ) . Proof. Think of what that number means! By Theorem 1.5, ( n+t 1 t 1 ) is the number of (t 1)-element subsets of an (n + t 1)-element set. So, let’s write down a row of (n+ t 1) circles from left to right: O O O O O O O O O O O O O and cross out some t 1 of these circles to choose a (t 1)-element subset: O O O O X O O O O O X O O Now the t 1 crosses chop the remaining sequence of n circles into t seg- ments of consecutive circles. (Some of these segments might be empty, which is to say of length zero.) Let mi be the length of the i-th segment of consecutive O-s in this construction. Then m1 + m2 + · · · + mt = n, so that (m1,m2, …,mt) is an n-element multiset with t types. Conversely, if (m1,m2, …,mt) is an n-element multiset with t types then write down a se- quence of m1 O-s, then an X, then m2 O-s, then an X, and so on, finishing with an X and then mt O-s. The positions of the X-s will indicate a (t 1)- element subset of the positions {1, 2, …, n+ t 1}. The construction of the above paragraph shows how to translate between (t 1)-element subsets of {1, 2, …, n + t 1} and n-element multisets with t types of element. This one–to–one correspondence completes the proof of the theorem. To answer the original question of this section, the number of 11-element multisets with elements of 3 types is ( 11+3 1 3 1 ) = ( 13 2 ) = 78. 1.1.5 Bijective proofs. The arguments above, counting lists, permutations, subsets, multisets, and so on, can be phrased more formally using the idea of bijections between 24 Basic Principles. Section 1.1 finite sets. In simple cases as we have seen so far this is not always neces- sary, but it is good style. In more complicated situations, as we will see in Chapters 2 to 4, it is a very useful way to organize one’s thoughts. Definition 1.10. Let f : A→ B be a function from a set A to a set B. The function f is surjective if for every b ∈ B there exists an a ∈ A such that f(a) = b. The function f is injective if for every a, a′ ∈ A, if f(a) = f(a′), then a = a′. The function f is bijective if it is both surjective and injective. The notation A B indicates that there is a bijection between the sets A and B. Functions with these properties are called surjections, injections, or bijec- tions, respectively. An older terminology – now out of fashion – is that surjections are “onto” functions, injections are “one-to-one” functions, and bijections are “one-to-one and onto”. By Exercise 1.4(a), the relation is an equivalence relation. The point of Definition 1.10 is the following. Consider a bijection f : A→ B. Then every b ∈ B is the image of at least one a ∈ A, since f is surjective. On the other hand, every b ∈ B is the image of at most one a ∈ A, since f is injective. Therefore, every b ∈ B is the image of exactly one a ∈ A. In other words, the relation f(a) = b pairs off all the elements of A with all the elements of B. It follows that A and B have the same number of elements. That is, if A B then |A| = |B|. The converse implication holds, and for infinite sets the relation A B is taken as the definition of two sets “having the same size”. Proposition 1.11. Let f : A → B and g : B → A be functions between two sets A and B. Assume the following. For all a ∈ A, g(f(a)) = a. For all b ∈ B, f(g(b)) = b. Then both f and g are bijections. Moreover, for a ∈ A and b ∈ B, we have f(a) = b if and only if g(b) = a. Proof. Exercise 1.4(b). Section 1.1 Basic Principles. 25 A pair of functions as in Proposition 1.11 are called mutually inverse bijections . The notation g = f 1 and f = g 1 is used to denote this relation. Notice that for a bijection f , we have (f 1) 1 = f . Here are two examples of this way of thinking. Example 1.12 (Subsets and indicator vectors.). Let P(n) be the set of all subsets of {1, 2, …, n}, and let {0, 1}n be the set of all indicator vectors α = (a1, a2, …, an) in which each coordinate is either 0 or 1. There is a bijection between these two sets. For a subset S {1, 2, …, n}, define the vector α(S) = (a1(S), a2(S), …, an(S)) by saying that for each 1 ≤ i ≤ n, ai(S) = { 1 if i ∈ S, 0 if i 6∈ S. Conversely, for an indicator vector α = (a1, …, an) define a subset S(α) by saying that S(α) = {i ∈ {1, 2, …, n} : ai = 1}. For example, when n = 8 the subset {2, 3, 5, 7} corresponds to the indica- tor vector (0, 1, 1, 0, 1, 0, 1, 0). The constructions S 7→ α(S) and α 7→ S(α) are mutually inverse bijections between the sets P(n) and {0, 1}n as in Proposition 1.11. It follows that |P(n)| = |{0, 1}n| = 2n. This is a formal- ization of the proof of Theorem 1.3. Example 1.13 (Subsets and multisets.). The proof of Theorem 1.9 can be phrased in terms of bijections, as follows. LetM(n, t) be the set of all multisets of size n ∈ Nwith elements of t ≥ 1 types. Let B(a, k) be the set of all k-element subsets of {1, 2, …, a}. We establish a bijection betweenM(n, t) andB(n+t 1, t 1) in what follows. Theorem 1.5 implies that |B(n + t 1, t 1)| = (n+t 1 t 1 ) , completing the proof of Theorem 1.9. Here is a precise description of this bijection. Let S be any (t 1)-element subset of {1, 2, …, n+ t 1}. We can sort the elements of S in increasing order: S = {s1, s2, …, st 1} in which s1 < s2 < · · · < st 1. For notational convenience, let s0 = 0 and let st = n + t. Now define a sequence μ = (m1,m2, ...,mt) by letting mi = si si 1 1 for all 1 ≤ i ≤ t. 26 Basic Principles. Section 1.1 For example, with n = 10 and t = 4, consider the 3-element subset S = {2, 7, 11} of {1, 2, ..., 13}. Then s0 < s1 < · · · < st is 0 < 2 < 7 < 11 < 14, the sequence of differences is (2, 5, 4, 3), and subtracting 1 from each of these yields μ = (1, 4, 3, 2). Notice that μ is a multiset of size 10 with 4 types of elements. In general, since si 1 < si for all 1 ≤ i ≤ t, it follows that mi = si si 1 1 is a nonnegative integer. Also, since st = n + t, it follows that m1 + m2 + · · · + mt = st t = n. That is, μ is a multiset of size n with elements of t types. This describes a function S 7→ μ from the set B(n + t 1, t 1) to the set M(n, t). We claim that this function is a bijection between these two sets. To show that our construction S 7→ μ is a bijection, we will describe its inverse function. Begin with a multiset μ = (m1,m2, ...,mt) of size nwith t types of elements. For each 1 ≤ i ≤ t 1, let si = m1 +m2 + · · ·+mi + i. Notice that 1 ≤ s1 < s2 < · · · < st 1 ≤ n+ t 1. Therefore, S = {s1, s2, ..., st 1} is a member of the set B(n+ t 1, t 1). To finish this example, one must check that these constructions, S 7→ μ and μ 7→ S, are mutually inverse bijections as in Proposition 1.11. The details are left as Exercise 1.6. 1.1.6 Inclusion/Exclusion. In a vase is a bouquet of flowers. Each flower is (at least one of) fresh, fragrant, or colourful: (a) 11 flowers are fresh; (b) 7 flowers are fragrant; (c) 8 flowers are colourful; (d) 6 flowers are fresh and fragrant; (e) 5 flowers are fresh and colourful; (f) 2 flowers are fragrant and colourful; (g) 2 flowers are fresh, fragrant, and colourful. How many flowers are in the bouquet The Principle of Inclusion/Exclusion is a systematic method for answer- ing such questions, which involve overlapping conditions which can be sat- Section 1.1 Basic Principles. 27 fresh fragrant colourful Figure 1.1: A Venn diagram for three sets. isfied (or not) in various combinations. Example 1.14. For a small problem as above we can reason backwards as follows: (g): there are 2 flowers with all three properties (fresh, fragrant, and colourful); (h): from (g) and (f) there are 0 flowers which are fragrant and colourful but not fresh; (i): from (g) and (e) there are 3 flowers which are fresh and colourful but not fragrant; (j): from (g) and (d) there are 4 flowers which are fresh and fragrant but not colourful; (k): from (c)(g)(h)(i) there are 3 flowers which are colourful but neither fresh not fragrant; (`): from (b)(g)(h)(j) there is 1 flower which is fragrant but neither fresh nor colourful; (m): from (a)(g)(i)(j) there are 2 flowers which are fresh bu