Combinatorics CSE235 Combinatorics Introduction Counting PIE Pigeonhole Principle Slides by Christopher M Bourke Instructor Berthe Y Choueiry Permutations Combinations Binomial Coefficients Generalizations Fall 2007 Algorithms More Examples Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 5 1 5 6 7 5 7 6 of Rosen 1 94 Combinatorics I Introduction Combinatorics CSE235 Introduction Counting PIE Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 2 94 Combinatorics 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 algorithms and compute discrete probabilities Originally combinatorics was motivated by gambling counting configurations is essential to elementary probability Combinatorics II Introduction Combinatorics CSE235 Introduction Counting PIE Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 3 94 A simple example How many arrangements are there of a deck of 52 cards In addition combinatorics can be used as a proof technique A combinatorial proof is a proof method that uses counting arguments to prove a statement Product Rule Combinatorics CSE235 Introduction Counting PIE Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations If two events are not mutually exclusive that is we do them separately then we apply the product rule Theorem Product Rule Suppose a procedure can be accomplished with two disjoint subtasks If there are n1 ways of doing the first task and n2 ways of doing the second then there are n1 n2 Algorithms More Examples 4 94 ways of doing the overall procedure Sum Rule I Combinatorics CSE235 Introduction Counting PIE If two events are mutually exclusive that is they cannot be done at the same time then we must apply the sum rule Pigeonhole Principle Theorem Sum Rule Permutations If an event e1 can be done in n1 ways and an event e2 can be done in n2 ways and e1 and e2 are mutually exclusive then the number of ways of both events occurring is Combinations Binomial Coefficients Generalizations Algorithms More Examples 5 94 n1 n2 Sum Rule II Combinatorics CSE235 Introduction Counting PIE There is a natural generalization to any sequence of m tasks namely the number of ways m mutually exclusive events can occur is n1 n2 nm 1 nm Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 6 94 We can give another formulation in terms of sets Let A1 A2 Am be pairwise disjoint sets Then A1 A2 Am A1 A2 Am In fact this is a special case of the general Principle of Inclusion Exclusion Principle of Inclusion Exclusion PIE I Introduction Combinatorics CSE235 Introduction Counting PIE Examples Derangements Pigeonhole Principle Say there are two events e1 and e2 for which there are n1 and n2 possible outcomes respectively Now say that only one event can occur not both Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 7 94 In this situation we cannot apply the sum rule Why Principle of Inclusion Exclusion PIE II Introduction Combinatorics CSE235 Introduction Counting PIE Examples Derangements Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 8 94 We cannot use the sum rule because we would be over counting the number of possible outcomes Instead we have to count the number of possible outcomes of e1 and e2 minus the number of possible outcomes in common to 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 Principle of Inclusion Exclusion PIE III Introduction Combinatorics CSE235 More generally we have the following Introduction Lemma Counting Let A B be subsets of a finite set U Then PIE 1 A B A B A B 2 A B min A B 3 A B A A B A B Combinations 4 A U A Binomial Coefficients 5 A B A B A B A B 2 A B A B B A 6 A B A B Examples Derangements Pigeonhole Principle Permutations Generalizations Algorithms More Examples 9 94 Principle of Inclusion Exclusion PIE I Theorem Combinatorics CSE235 Introduction Counting PIE Examples Derangements Pigeonhole Principle Permutations Theorem Let A1 A2 An be finite sets then X Ai A1 A2 An i X Ai Aj i j X Combinations Ai Aj Ak i j k Binomial Coefficients Generalizations 1 n 1 A1 A2 An Algorithms More Examples 10 94 Each summation is over all i pairs i j with i j triples i j k with i j k etc Principle of Inclusion Exclusion PIE II Theorem Combinatorics CSE235 Introduction Counting To illustrate when n 3 we have PIE Examples Derangements Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 11 94 A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 Principle of Inclusion Exclusion PIE III Theorem Combinatorics CSE235 To illustrate when n 4 we have Introduction Counting PIE Examples Derangements Pigeonhole Principle Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 12 94 A1 A2 A3 A4 A1 A2 A3 A4 h A1 A2 A1 A3 A1 A4 i A2 A3 A2 A4 A3 A4 h A1 A2 A3 A1 A2 A4 i A1 A3 A4 A2 A3 A4 A1 A2 A3 A4 Principle of Inclusion Exclusion PIE I Example I Combinatorics CSE235 Introduction Counting PIE Examples Derangements Pigeonhole Principle Example How many integers between 1 and 300 inclusive are 1 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 Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 13 94 Let A n 1 n 300 3 n B n 1 n 300 5 n C n 1 n 300 7 n Principle of Inclusion Exclusion PIE II Example I Combinatorics CSE235 Introduction Counting PIE Examples Derangements Pigeonhole Principle Permutations How big are each of these sets We can easily use the floor function A b300 3c 100 B b300 5c 60 C b300 7c 42 Combinations Binomial Coefficients Generalizations Algorithms More Examples 14 94 For 1 above we are asked to find A B C Principle of Inclusion Exclusion PIE III Example I Combinatorics CSE235 By the principle of inclusion exclusion we have that Introduction Counting PIE Examples Derangements Pigeonhole Principle A B C A B C h i A B A C B C A B C Permutations Combinations Binomial Coefficients Generalizations Algorithms More Examples 15 94 It remains to find the final 4
View Full Document
Unlocking...