Combinatorics Section 5 1 5 6 7 5 7 6 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Motivation Combinatorics is the study of collections of objects Specifically counting objects arrangement derangement etc 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 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 CSCE 235 Fall 2008 Combinatorics 2 Outline Introduction Counting Product rule sum rule Principal of Inclusion Exclusion PIE Application of PIE Number of onto functions Pigeonhole principle Generalized probabilistic forms Permutations Combinations Binomial Coefficients Generalizations Combinations with repetitions permutations with indistinguishable objects Algorithms Generating combinations 1 permutations 2 More Examples CSCE 235 Fall 2008 Combinatorics 3 Product Rule 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 task then there are n1 n2 ways of doing the overall procedure CSCE 235 Fall 2008 Combinatorics 4 Sum Rule 1 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 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 CSCE 235 Fall 2008 Combinatorics 5 Sum Rule 2 There is a natural generalization to any sequence of m tasks namely the number of ways m mutually events can occur 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 Principal of Inclusion Exclusion PIE CSCE 235 Fall 2008 Combinatorics 6 Principle of Inclusion Exclusion PIE 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 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 A1 A2 CSCE 235 Fall 2008 Combinatorics 7 PIE 2 More generally we have the following Lemma Let A B be subsets of a finite set U Then 1 2 3 4 5 A B A B A B A B min A B A B A A B A B A U A A B A B A B A B 2 A B A B B A 6 A B A B CSCE 235 Fall 2008 Combinatorics 8 PIE Theorem Theorem Let A1 A2 An be finite sets then A1 A2 An i Ai i j Ai Aj i j k Ai Aj Ak 1 n 1 A1 A2 An Each summation is over all i pairs i j with i j triples with i j k etc CSCE 235 Fall 2008 Combinatorics 9 PIE Theorem Example 1 To illustrate when n 3 we have A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 CSCE 235 Fall 2008 Combinatorics 10 PIE Theorem Example 2 To illustrate when n 4 we have A1 A2 A3 A4 A1 A2 A3 A4 A1 A2 A1 A3 A1 A4 A2 A3 A2 A4 A3 A4 A1 A2 A3 A1 A2 A4 A1 A3 A4 A2 A3 A4 A1 A2 A3 A4 CSCE 235 Fall 2008 Combinatorics 11 Application of PIE Example A 1 How many integers between 1 and 300 inclusive are Divisible by at least one of 3 5 7 Divisible by 3 and by 5 but not by 7 Divisible by 5 but by neither 3 or 7 Let A n Z 1 n 300 3 n B n Z 1 n 300 5 n C n Z 1 n 300 7 n How big are these sets We use the floor function A 300 3 100 B 300 5 60 C 300 7 42 CSCE 235 Fall 2008 Combinatorics 12 Application of PIE Example A 2 How many integers between 1 and 300 inclusive are divisible by at least one of 3 5 7 Answer A B C By the principle of inclusion exclusion A B C A B C A B A C B C A B C How big are these sets We use the floor function A 300 3 100 A B 300 15 20 B 300 5 60 A C 300 21 100 C 300 7 42 B C 300 35 8 A B C 300 105 2 Therefore A B C 100 60 42 20 14 8 2 162 CSCE 235 Fall 2008 Combinatorics 13 Application of PIE Example A 3 How many integers between 1 and 300 inclusive are divisible by 3 and by 5 but not by 7 Answer A B C By the definition of set minus A B C A B A B C 20 2 18 Knowing that A 300 3 100 B 300 5 60 C 300 7 42 CSCE 235 Fall 2008 A B 300 15 20 A C 300 21 100 B C 300 35 8 A B C 300 105 2 Combinatorics 14 Application of PIE Example A 4 How many integers between 1 and 300 inclusive are divisible by 5 but by neither 3 or 7 Answer B A C B B A C Distributing B over the intersection 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 Knowing that A 300 3 100 B 300 5 60 C 300 7 42 CSCE 235 Fall 2008 A B 300 15 20 A C 300 21 100 B C 300 35 8 A B C 300 105 2 Combinatorics 15 Application of PIE Surjections Section 7 6 The principle of inclusion exclusion can be used to count the number of onto surjective functions Theorem Let A B be non empty sets of cardinality m n with m n Then there are n choose i See textbook Section 7 6 page 509 CSCE 235 Fall 2008 Combinatorics 16 Surjections Example How many ways of giving out 6 pieces of candy to 3 children if each child must receive at least one piece This problem can be modeled as follows Let A be …
View Full Document
Unlocking...