CombinatoricsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 4.1-4.6 & 6.5-6.6 of [email protected] IIntroductionCombinatorics is the study of collections of objects . Specifically,counting objects, arrangement, derangement, etc. of objects alongwith their mathematical properties.Counting objects is important in order to analyze algorithms andcompute discrete probabilities.Originally, combinatorics was motivated by gambling: countingconfigurations is essential to elementary probability.NotesCombinatorics IIIntroductionA simple example: How many arrangements are there of a deck of52 cards?In addition, combinatorics can be used as a proof technique.A combinatorial proof is a proof method that uses countingarguments to prove a statement.NotesProduct RuleIf two events are not mutually exclusive (that is, we do themseparately), then we apply the product rule.Theorem (Product Rule)Suppose a procedure can be accomplished with two disjointsubtasks. If there are n1ways of doing the first task and n2waysof doing the second, then there aren1· n2ways of doing the overall procedure.NotesSum Rule IIf two events are mutually exclusive, that is, they cannot b e doneat the same time, then we must apply the sum rule.Theorem (Sum Rule)If an event e1can be done in n1ways and an event e2can be donein n2ways and e1and e2are mutually exclusive, then the numberof ways of both events occurring isn1+ n2NotesSum Rule IIThere is a natural generalization to any sequence of m tasks;namely the number of ways m mutually exc lusive e vents can occurisn1+ n2+ · · · nm−1+ nmWe can give another formulation in terms of sets. Le tA1, A2, . . . , Ambe pairwise disjoint sets. Then|A1∪ A2∪ · · · ∪ Am| = |A1| + |A2| + · · · + |Am|In fact, this is a special case of the general Principle ofInclusion-Exclusion.NotesPrinciple of Inclusion-E xclus ion (PIE) IIntroductionSay there are two ev ents, e1and e2for which there are n1and n2possible outcomes respectively.Now, say that only one event can occ ur, not both.In this situation, we cannot apply the sum rule? Why?NotesPrinciple of Inclusion-E xclus ion (PIE) IIIntroductionWe cannot use the sum rule because we would be over countingthe number of possible outcomes.Instead, we have to count the number of possible outcomes of e1and e2minus the number of possible outcomes in common toboth; i.e. the number of ways to do both “tasks”.If again we think of them as sets, we have|A1| + |A2| − |A1∩ A2|NotesPrinciple of Inclusion-E xclus ion (PIE) IIIIntroductionMore generally, we have the following.LemmaLet A, B be subsets of a finite set U. Then1. |A ∪ B| = |A| + |B| − |A ∩ B|2. |A ∩ B| ≤ min{|A|, |B|}3. |A \ B| = |A| − |A ∩ B| ≥ |A| − |B|4. |A| = |U | − |A|5. |A⊕B| = |A∪B|−|A∩B| = A+B−2|A∩B| = |A\B|+|B\A|6. |A × B| = |A| × |B|NotesPrinciple of Inclusion-E xclus ion (PIE) ITheoremTheoremLet A1, A2, . . . , Anbe finite sets, then|A1∪ A2∪ · · · ∪ An| =Xi|Ai|−Xi<j|Ai∩ Aj|+Xi<j<k|Ai∩ Aj∩ Ak|− · · ·+(−1)n+1|A1∩ A2∩ · · · ∩ An|NotesPrinciple of Inclusion-E xclus ion (PIE) IITheoremEach summation is over all i, pairs i, j with i < j, triples i, j, kwith i < j < k etc.NotesPrinciple of Inclusion-E xclus ion (PIE) IIITheoremTo illustrate, when n = 3, we have|A1∪ A2∪ A3| = |A1| + |A2| + |A3|−|A1∩ A2| + |A1∩ A3| + |A2∩ A3| +|A1∩ A2∩ A3|NotesPrinciple of Inclusion-E xclus ion (PIE) IVTheoremTo illustrate, when n = 4, we have|A1∪ A2∪ A3∪ A4| = |A1| + |A2| + |A3| + |A4|−h|A1∩ A2| + |A1∩ A3| + +|A1∩ A4||A2∩ A3| + |A2∩ A4| + |A3∩ A4|i+h|A1∩ A2∩ A3| + |A1∩ A2∩ A4| +|A1∩ A3∩ A4| + |A2∩ A3∩ A4|i−|A1∩ A2∩ A3∩ A4|NotesPrinciple of Inclusion-E xclus ion (PIE) IExample IExampleHow many integers between 1 and 300 (inclusive) are1. Divisible by at least one of 3, 5, 7?2. Divisible by 3 and by 5 but not by 7?3. Divisible by 5 but by neither 3 nor 7?LetA = {n | 1 ≤ n ≤ 300 ∧ 3 | n}B = {n | 1 ≤ n ≤ 300 ∧ 5 | n}C = {n | 1 ≤ n ≤ 300 ∧ 7 | n}NotesPrinciple of Inclusion-E xclus ion (PIE) IIExample IHow big are each of these sets? We can easily use the floorfunction;|A| = b300/3c = 100|B| = b300/5c = 60|C| = b300/7c = 42For (1) above, we are asked to find |A ∪ B ∪ C|.NotesPrinciple of Inclusion-E xclus ion (PIE) IIIExample IBy the principle of inclusion-exclusion, we have that|A ∪ B ∪ C| = |A| + |B| + |C|−h|A ∩ B| + |A ∩ C| + |B ∩ C|i+|A ∩ B ∩ C|It remains to find the final 4 cardinalities.All three divisors, 3, 5, 7 are relatively prime. Thus, any integerthat is divisible by both 3 and 5 must simply be divisible by 15.NotesPrinciple of Inclusion-E xclus ion (PIE) IVExample IUsing the same reasoning for all pairs (and the triple) we have|A ∩ B| = b300/15c = 20|A ∩ C| = b300/21c = 14|B ∩ C| = b300/35c = 8|A ∩ B ∩ C| = b300/105c = 2Therefore,|A ∪ B ∪ C| = 100 + 60 + 42 − 20 − 14 − 8 + 2 = 162NotesPrinciple of Inclusion-E xclus ion (PIE) VExample IFor (2) above, it is enough to find|(A ∩ B) \ C|By the definition of set-minus,|(A ∩ B) \ C| = |A ∩ B| − |A ∩ B ∩ C| = 20 − 2 = 18NotesPrinciple of Inclusion-E xclus ion (PIE) VIExample IFor (3) above, we are asked to find|B \ (A ∪ C)| = |B| − |B ∩ (A ∪ C)|By distributing B over the intersection, we get|B ∩ (A ∪ C)| = |(B ∩ A) ∪ (B ∩ C)|= |B ∩ A| + |B ∩ C| − |(B ∩ A) ∩ (B ∩ C)|= |B ∩ A| + |B ∩ C| − |B ∩ A ∩ C|= 20 + 8 − 2 = 26So the answer is |B| − 26 = 60 − 26 = 34.NotesPrinciple of Inclusion-E xclus ion (PIE) IExample IIThe principle of inclusion-exclusion can be used to count thenumber of onto functions.TheoremLet A, B be non-empty sets of cardinality m, n with m ≥ n. Thenthere arenm−n1(n − 1)m+n2(n − 2)m− · · · + (−1)n−1nn − 11mi.e.Pn−1i=0(−1)ini(n − i)monto functions f : A → B.See textbook page 460.NotesPrinciple of Inclusion-E xclus ion (PIE) IIExample IIExampleHow many ways of giving out 6 pieces of candy to 3 children ifeach child must receive at least one piece?This can be modeled by letting A represent the set of candies andB be the set of children.Then a function f : A → B can be interpreted as giving candy aito child cj.Since each child must receive at least one candy, we areconsidering only onto
View Full Document
Unlocking...