Chapter 1 Combinatorics (section 3.2...3.5) ********************************************** 1.1 Introduction *=*=*=*=*=*=*=*=* Goal: answer ``How many ?'' questions: - How many ways to climb a stair ? - How many rows in a truth table ? - How many trees ? Applications: - Analysis of algorithms - Statistics - Size of a database 1.2 Counting *=*=*=*=*=*=* 1.2.1 Preliminaries ==================== Définition 1 The size of a finite set is the number of elements in this set. The size of S is denoted by |S| (or, often in the literature, # S). Note 1 In the sequel, we only consider finite sets ! A``how many ?'' question is usually formalized as follow: 1. Define the set S of the objects to be counted 2. What is the size of S ? Techniques to answer this question: - breakup S as some combination of simpler sets - transform S into a set, the size of which is already known 1.2.2 The addition principle ============================= Exemple 1 A small company wants to know how many computers it owns, given that it owns 5 Mac's, and 3 UNIX stations. Let: - C be the sets of computers, - M be the set of Mac's (|M|=5), - U be the set of UNIX stations (|U|=3). Then, C=Munion U. What is the size of C ? | | | | | | |C|=|M|+|U|=5+3=8 | | | | | | Théorème 1 (Addition principle) Let A and B be disjoint sets (e.g. Aintersect B=Ø). Then: | | | | | | |Aunion B|=|A|+|B|. | | | | | | Exemple 2 Imagine 2 of the 5 Mac's are actually running Linux. What is the size of C ? Well, |C|=6<8. So, the disjoint hypothesis is important ! What to do when the sets are not disjoint ? Théorème 2 Let A and B be two sets. Then: | | | | | | | | |Aunion B|=|A|+|B|-|Aintersect B|. | | | | | | | | Proof. We just have to split A, B, and Aunion B into unions of disjoint subsets: A=(A-B)union(Aintersect B) B=(B-A)union(Aintersect B) Aunion B=(A-B)union(Aintersect B)union(B-A). (Practice: draw and prove those set identities!). Then, | | | | | | | | | | | | | | | | |A|+|B|-|Aintersect B| = (|A-B|+|Aintersect B|)+(|B-A|+|Aintersect B|)-|Aintersect B| | | | | | | | | | | | | | | | | | | | | | | = |A-B|+|Aintersect B|+|B-A| | | | | | | | | = |Aunion B| | | Exemple 3 In the example above, |C|=|M|+|U|-|Mintersect U|=5+3-2=6. Exercice 1 There are 24 students in a class, all of them are math majors or computer science major. 10 are math majors, and 20 are computer science majors. How many double-major are there in this class ? 1.2.3 The multiplication principle =================================== Exemple 4 You are a car dealer. For each car you sell, you propose several options (color, 2WD/4WD, airbag, ABS, radio, ...). Of course, you would like to always have all possible combinations of options in stock. On the other hand, you cannot afford to store too many cars in your parking lot. So you need to know how many possible combinations of options there are. - 2WD / 4WD - Black / Yellow / Green How many combinations are there ? First solution: draw a decision tree. The choices are independent! The number of sub-branches at each level is constant. Therefore, we have 2·3=6 choices. Let's formalize this. Let C be the set of all choices. Each choice can be represented by a couple. For example a yellow 2WD car with black seats can be represented as: (2,Y) So, C can be viewed as the cross product: {2,4}×{ B,Y,G}. Théorème 3 Let A and B be two sets. Then, | | | | | | |A× B|=|A|·|B|. | | | | | | Exemple 5 In the example above, |C|=|{2,4}×{ B,Y,G}|=|{2,4}|·|{ B,Y,G}|=2·3=6. Exercice 2 How many possible different phone numbers are there ? Strings ------- Strings are commonly used objects in computer science. ``how many'' questions often be translate into questions about sets of strings. Définition 2 Let S be a set, that we call alphabet. Elements of S are called letters. A string over S is a sequence (s_1,s_2,...,s_n) of elements of S. lambda:=() is the empty string. The set of all strings of length n is S^n=S×···× S. The set of all finite strings over S is denoted S^*. A language is a set of strings. Exemple 6 Let S:={0,1}. A string over S, like 001001 is called a binary string. Let S:={ a,b,...,z}. Then bonjour is a string over S of length 7. A phone number 3032733462 is a string over {0,1,2,3,4,5,6,7,8,9}. The set of all English words is a language. Exemple 7 Count the following: 1. binary strings of length 4? 2. strings of length n over an alphabet containing p letters ? 1.2.4 Decision trees ===================== Exemple 8 A kid is allowed to pick 3 candies (one after another), out of one jelly bean, one lollipop and 2 gummy bears (one blue, one yellow). In how many ways can he do this ? Draw a decision tree. The choices are not independent The multiplication principle does not apply. However, the number of choices at each step does not change! So the answer is: 5·4·3=60. Exercice 3 Count the following: 1. Strings of length 4 over {1,2,3,4,5} with no repetitions. 2. Strings of length n over {1,...,n} with no repetitions. Exercice 4 How many ways to toss a coin five times without two heads in a row ? Note: the decision tree is irregular. 1.2.5 Combining those principles together ========================================== Exemple 9 Count the following: Exercise 18-19 p. 195 - Strings of length n over {1,...,n} with repetitions. - Strings of length n over {0,1} with two consecutive 1. - How many four-digits numbers begin with 4 or 5? - How many ways to toss a coin seven times with two heads in a row ? 1.2.6 Principle of Inclusion and Exclusion =========================================== Exemple 10 All the guests at a dinner party drink coffee, chocolate or tea; 11drink coffee, 9 drink tea, 10 drink chocolate; 3 drink coffee and tea, 5 drink tea and chocolate; 6 drink coffee and chocolate Formalization: what is the size of |Aunion Bunion C|? Generalization ? Théorème 4 (Principle of Inclusion and exclusion) Let A_1,...,A_n be n sets. Then, |A A | |A | |A | | union···union | = | |+···+| | | 1 n| | 1| | n| |A A | |A A | -| intersect |-···-| intersect | | 1 2| | n-1 n| |A A A | |A A A | +| intersect intersect |+···| intersect intersect | | 1 2 3| | n-2 n-1 n| |A A | n+1| intersect···intersect | +(-1) | 1 n| -- | | \ |I|+1| A | = / (-1)| | |intersect | -- | iin I i| Iincluded in{1,···,n} Proof. Induction. 1.2.7 Pigeon Hole principle ============================ Exercice 5 It's early in the morning, and you don't want to wake up your significant whatever by turning on the light. You know you only have black and white socks in your drawer. Is it possible to exit the room with at least two socks with the same color ? Théorème 5 (Pigeon hole principle) If more than k items are placed in k bins, then at least one bin has more than one item inside. Exemple 11 How many people do you need to have in a room to ensure at least two of them have the same birthday ? 1.2.8 Permutations: sequences without repetitions ================================================== Exemple 12 How many ways to choose a committee with 1 president and 1 vice-president out of a group of n persons. This amount to find the number of strings of length 2 over a set of size n, without repetitions. This is n(n-1). Définition 3 We denote by P(n,k) the number of strings of length k over a set of size n without repetitions. Exemple 13 P(n,0)= , P(n,1)= , P(n,n)= , P(1,2)= . Théorème 6 P(n,k)=n(n-1)···(n-k+1)=n!/(n-k)!. 1.2.9 Combinations =================== Exemple 14 How many ways to choose 3 voluntaries out of a group of 5 persons? Définition 4 We denote by C(n,k) the number of subsets of size k of a set of size n. Exemple 15 C(n,0)= , C(n,1)= , C(n,n)= , C(1,2)= . Théorème 7 C(n,k)=n(n-1)···(n-k+1)/k(k-1)···1=n!/k!(n-k)!. Exemple 16 Ex. 51 p. 210: A committee of 8 students is to be selected from a class consisting of 19 freshmen and 34 sophomores. 1. In how many ways can 3 freshmen and 5 sophomores be selected? 2. In how many ways can a committee with exactly 1 freshman be selected? 3. In how many ways can a committee with at most 1 freshman be selected? 4. In how many ways can a committee with at least 1 freshman be selected? Exemple 17 What is the total number of subsets of S ? Exemple 18 What is the number of paths between Stratton Hall and Golden Tourism Information center ? 1.2.10 Combinations with repetitions ===================================== Exemple 19 In how many ways can you distribute 10 lollipops between 4 kids. Théorème 8 The number of combinations with repetitions of k elements of a set S of size n is C(n+k-1,n). Exemple 20 In how many ways can you distribute 10 lollipops between 4 kids, so that every kid get at least one lollipop ? 1.2.11 Summary =============== ------------------------------------------------------------------------ ---------------------------------------- | Addition principle (A and B disjoint) | |Aunion B|=|A|+|B| | ------------------------------------------------------------------------ ---------------------------------------- | Principle of Inclusion-Exclusion ||Aunion B|=|A|+|B|-|Aintersect B||A_1union···union A_n|=···| ------------------------------------------------------------------------ ---------------------------------------- | Multiplication principle | |A× B|=|A|·|B||A^k|=|A|^k | ------------------------------------------------------------------------ ---------------------------------------- | Sequences of k elements of S (|S|=n) | n^k | ------------------------------------------------------------------------ ---------------------------------------- | Permutations: | P(n,k)=n!/(n-k)! | ------------------------------------------------------------------------ ---------------------------------------- | Sequences of k elements of S, w/o repetitions | | ------------------------------------------------------------------------ ---------------------------------------- |Sequences of k elements of {0,1}, w/o successive 1| Fibonacci: F(k) | ------------------------------------------------------------------------ ---------------------------------------- | Combinations: subsets of size k of S | C(n,k)=n!/k!(n-k)! | ------------------------------------------------------------------------ ---------------------------------------- | All subsets of S | 2^n | ------------------------------------------------------------------------ ---------------------------------------- | Combinations with repetitions | C(n+k-1,k) | ------------------------------------------------------------------------ ---------------------------------------- 1.3 Properties of binomial coefficients; Combinatorial proofs *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= Exemple 21 How many subsets of size 14 of a set of size 15 ? Théorème 9 C(n,k)=C(n,n-k) Proof. 1. Algebraic proof 2. Combinatorial proof Définition 5 Combinatorial proof: Goal: prove that two quantities a and b are equal Technique: 1. construct a set A of size a; 2. construct a set B of size b; 3. construct a bijection between A and B Problem 1 Recursive computation of C(n,k) ? Théorème 10 C(n,k)=C(n-1,k)+C(n-1,k-1) Proof. 1. Algebraic proof 2. Combinatorial proof Exemple 22 Compute C(7,4), without calculator. Définition 6 Pascal triangle: ------------------------- |nk||0|1|2 |3 |4 |5 |6|7| ------------------------- ------------------------- |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| ------------------------- Théorème 11 C(n,0)+···+C(n,n)=2^n Proof. 1. Algebraic proof ? 2. Combinatorial proof 1.3.1 The binomial theorem =========================== Problem 2 Compute (x+y)^n . Théorème 12 There is a formula for expanding (x+y)^n: k=n -- n \ n-k k (x+y) = / C(n,k)x y -- k=0 n n-1 n-2 2 n = C(n,0)x +C(n,1)x y+C(n,2)x y +···+C(n,n)y 1.4 Conclusion *=*=*=*=*=*=*=* ----------------------------------------------------------------------- This document was translated from LaTeX by HeVeA (http://pauillac.inria.fr/~maranget/hevea/index.html).