Notes Combinatorics Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 4 1 4 6 6 5 6 6 of Rosen cse235 cse unl edu Combinatorics I Notes Introduction 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 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 Notes Product Rule Notes 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 ways of doing the overall procedure Sum Rule I Notes If two events are mutually exclusive that is they cannot be done at the same time then we must apply the sum rule Theorem Sum Rule 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 n1 n2 Sum Rule II 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 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 Notes Principle of Inclusion Exclusion PIE I Notes Introduction 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 In this situation we cannot apply the sum rule Why Principle of Inclusion Exclusion PIE II Notes Introduction 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 More generally we have the following Lemma Let A B be subsets of a finite set U Then 1 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 Notes Principle of Inclusion Exclusion PIE I Notes Theorem Theorem Let A1 A2 An be finite sets then X A1 A2 An Ai i X Ai Aj i j X Ai Aj Ak i j k 1 n 1 A1 A2 An Principle of Inclusion Exclusion PIE II Notes Theorem 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 III Theorem To illustrate when n 3 we have A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 Notes Principle of Inclusion Exclusion PIE IV Notes Theorem To illustrate when n 4 we have 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 Notes Example I 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 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 How big are each of these function A B C sets We can easily use the floor b300 3c 100 b300 5c 60 b300 7c 42 For 1 above we are asked to find A B C Notes Principle of Inclusion Exclusion PIE III Notes Example I By the principle of inclusion exclusion we have that A B C A B C h i A B A C B C A B C It remains to find the final 4 cardinalities All three divisors 3 5 7 are relatively prime Thus any integer that is divisible by both 3 and 5 must simply be divisible by 15 Principle of Inclusion Exclusion PIE IV Notes Example I Using the same reasoning for all pairs and the triple we have A B A C B C A B C b300 15c 20 b300 21c 14 b300 35c 8 b300 105c 2 Therefore A B C 100 60 42 20 14 8 2 162 Principle of Inclusion Exclusion PIE V Example I For 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 18 Notes Principle of Inclusion Exclusion PIE VI Notes Example I For 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 26 So the answer is B 26 60 26 34 Principle of Inclusion Exclusion PIE I Notes Example II The principle of inclusion exclusion can be used to count the number of onto functions Theorem Let A B be non empty sets of cardinality m n with m n Then there are n n n nm n 1 m n 2 m 1 n 1 1m 1 2 n 1 P i n m i e n 1 i 0 1 i n i onto functions f A B See textbook page 460 Principle of Inclusion Exclusion PIE II Example II Example How many ways of giving out 6 pieces of candy to 3 children if each child must receive at least one piece This can be modeled by letting A represent the set of candies and B be the set of children Then a function f A B can be interpreted as giving candy ai to child cj Since each child must receive at least one candy we are considering only onto functions Notes Principle of Inclusion Exclusion PIE III Notes Example II To count how …
View Full Document
Unlocking...