Combinatorics I Combinatorics Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 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 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 5 1 5 6 7 5 7 6 of Rosen cse235 cse unl edu Combinatorics II Product Rule Introduction If two events are not mutually exclusive that is we do them separately then we apply the product rule 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 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 Sum Rule II 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 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 Principle of Inclusion Exclusion PIE I Principle of Inclusion Exclusion PIE II Introduction Introduction We cannot use the sum rule because we would be over counting the number of possible outcomes 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 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 Principle of Inclusion Exclusion PIE I Introduction Theorem More generally we have the following Theorem Lemma Let A B be subsets of a finite set U Then 1 A B A B A B Let A1 A2 An be finite sets then X Ai A1 A2 An i 2 A B min A B 3 A B A A B A B X Ai Aj i j 4 A U A X Ai Aj Ak i j k 5 A B A B A B A B 2 A B A B B A 6 A B A B 1 n 1 A1 A2 An Principle of Inclusion Exclusion PIE II Principle of Inclusion Exclusion PIE III Theorem Theorem To illustrate when n 3 we have Each summation is over all i pairs i j with i j triples i j k with i j k etc A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 Principle of Inclusion Exclusion PIE IV Principle of Inclusion Exclusion PIE I Theorem Example I To illustrate when n 4 we have Example 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 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 A1 A2 A3 A4 Principle of Inclusion Exclusion PIE II Principle of Inclusion Exclusion PIE III Example I Example I By the principle of inclusion exclusion we have that How big are each of these function A B C sets We can easily use the floor A B C A B C h i A B A C B C b300 3c 100 b300 5c 60 b300 7c 42 For 1 above we are asked to find A 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 Principle of Inclusion Exclusion PIE V Example I 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 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 Principle of Inclusion Exclusion PIE VI Principle of Inclusion Exclusion PIE I Example I Example II For 3 above we are asked to find The principle of inclusion exclusion can be used to count the number of onto surjective functions B A C B B A C Theorem 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 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 Pn 1 i e i 0 1 i ni n i m onto functions f A B See textbook page 509 Principle of Inclusion Exclusion PIE II Principle of Inclusion Exclusion PIE III Example 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 To count how many there are we apply the theorem and get for m 6 n 3 This can be modeled by letting A represent the set of candies and B be the set of children 36 3 3 3 1 6 3 2 6 540 1 2 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 …
View Full Document
Unlocking...