This preview shows page 1-2-3-4-5-6-7-49-50-51-52-53-54-55-99-100-101-102-103-104-105 out of 105 pages.
IntroductionCountingPIEExamplesDerangementsPigeonhole PrincipleGeneralizedExamplesPermutationsCombinationsBinomial CoefficientsGeneralizationsAlgorithmsCombinationsPermutationsMore ExamplesCombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatoricsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 5.1-5.6 & 7.5-7.6 of [email protected] / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatorics IIntroductionCombinatorics is the study of collections of objects.Specifically, counting objects, arrangement, derangement, etc.of objects along with their mathematical properties.Counting objects is important in order to analyze algorithmsand compute discrete probabilities.Originally, combinatorics was motivated by gambling: countingconfigurations is essential to elementary probability.2 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatorics IIIntroductionA sim ple example: How many arrangements are there of a deckof 52 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.3 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesProduct 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 n2ways of doing the second, then there aren1· n2ways of doing the overall procedure.4 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesSum Rule IIf two events are mutually exclusive, that is, they cannot bedone at 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 bedone in n2ways and e1and e2are mutually exclusive, then thenumber of ways of both events occurring isn1+ n25 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesSum Rul e IIThere is a natural generalization to any sequence of m tasks;namely the number of ways m mutually exclusive events canoccur isn1+ n2+ · · · nm−1+ nmWe can give another formulation in terms of sets. LetA1, 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.6 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIntroductionSay there are two events, e1and e2for which there are n1andn2possible outcomes respectively.Now, say that only one event can occur, not both.In this situation, we cannot apply the sum rule? Why?7 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIIntroductionWe cannot use the sum rule because we would be overcounting the number of possible outcomes.Instead, we have to count the number of possible outcomes ofe1and e2minus the number of possible outcomes in commonto both; i.e. the number of ways to do both “tasks”.If again we think of them as sets, we have|A1| + |A2| − |A1∩ A2|8 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIIIntroductionMore generally, we have the following.LemmaLet A, B be subsets of a finite se t 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|9 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (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|Each summation is over all i, pairs i, j with i < j, triples i, j, kwith i < j < k etc.10 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IITheoremTo illustrate, when n = 3, we have|A1∪ A2∪ A3| = |A1| + |A2| + |A3|−|A1∩ A2| + |A1∩ A3| + |A2∩ A3| +|A1∩ A2∩ A3|11 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIITheoremTo 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|12 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IExample IExampleHow many integers between 1 and 300 (inclusive) are1Divisible by at least one of 3, 5, 7?2Divisible by 3 and by 5 but not by 7?3Divisible 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}13 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion
View Full Document