CombinatoricsMotivationOutlineProduct RuleSum Rule (1)Sum Rule (2)Principle of Inclusion-Exclusion (PIE)PIE (2)PIE: TheoremPIE Theorem: Example 1PIE Theorem: Example 2Application of PIE: Example A (1)Application of PIE: Example A (2)Application of PIE: Example A (3)Application of PIE: Example A (4)Application of PIE: #Surjections (Section 7.6)#Surjections: ExampleSlide 18Pigeonhole Principle (1)Pigeonhole Principle (2)Generalized Pigeonhole Principle (1)Generalized Pigeonhole Principle (2)Generalized Pigeonhole Principle: ExamplePigeonhole Principle: Example A (1)Pigeonhole Principle: Example A (2)Pigeonhole Principle: Example BSlide 27PermutationsApplication of PIE and Permutations: Derangements (I) (Section 7.6)Application of PIE and Permutations: Derangements (II)Permutations: Example APermutations: Example BPermutations: Example C (1)Permutations: Example C (2)Slide 35Combinations (1)Combinations (2)Combinations (3)Combinations: Example ACombinations: Example BCombinations: Example CSlide 42Binomial Coefficients (1)Binomial Coefficients (2)Binomial Coefficients: ExampleBinomial Coefficients (3)Binomial Coefficients (4)Binomial Coefficients: Pascal’s Identity & TrianglePascal’s TriangleSlide 50Generalized Combinations & Permutations (1)Generalized Combinations & Permutations: ExampleGeneralized Combinations & Permutations (2)ExampleSlide 55AlgorithmsAlgorithms: ExampleGenerating Combinations (1)Generating Combinations (2)Generating Combinations: ExampleGenerating PermutationsNext Permutation (lexicographic order)Generating Permutations (2)Johnson-Trotter AlgorithmAlgorithm: Johnson TrotterSlide 66Example AExample: Counting Functions (1)Example: Counting Functions (2)Another Example: Counting FunctionsExample: SetsSummaryCombinatoricsSection 5.1—5.6 7.5—7.6 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] 235, Fall 20082Motivation•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 statementCombinatoricsCSCE 235, Fall 20083Outline•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 ExamplesCombinatoricsCSCE 235, Fall 20084Product Rule•If two events are not mutually exclusive (that is we do them separately), then we apply the product rule•Theorem: Product RuleSuppose 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 procedureCombinatoricsCSCE 235, Fall 20085Sum 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 exclusivethen the number of ways of both events occurring is n1+ n2CombinatoricsCSCE 235, Fall 20086Sum Rule (2)•There is a natural generalization to any sequence of m tasks; namely the number of ways m mutually events can occurn1 + 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 ofInclusion-Exclusion (PIE))CombinatoricsCSCE 235, Fall 20087Principle 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|CombinatoricsCSCE 235, Fall 20088PIE (2)•More generally, we have the following•Lemma: Let A, B, be subsets of a finite set U. Then1. |AB| = |A| + |B| - |AB|2. |A B| min {|A|, |B|}3. |A\B| = |A| - |AB| |A|-|B|4. |A| = |U| - |A|5. |AB| =|AB|-|AB|= |A|+|B|-2|AB|= |A\B|+ |B\A| 6. |A B| = |A||B|CombinatoricsCSCE 235, Fall 20089PIE: 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 |A1A2...An|Each summation is over •all i, •pairs i,j with i<j, •triples with i<j<k, etc.CombinatoricsCSCE 235, Fall 200810PIE Theorem: Example 1•To illustrate, when n=3, we have|A1 A2 A3|= |A1|+ |A2| +|A3| - [|A1A2|+|A1A3|+|A2A3|] +|A1 A2 A3|CombinatoricsCSCE 235, Fall 200811PIE Theorem: Example 2•To illustrate, when n=4, we have|A1A2A3A4|= |A1|+|A2|+|A3|+|A4| - [|A1A2|+|A1A3|+|A1A4| +|A2A3|+|A2A4|+|A3A4|] + [|A1A2A3|+|A1A2A4| +|A1A3A4|+|A2A3A4|] - |A1 A2 A3 A4|CombinatoricsCSCE 235, Fall 200812Application 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 = {nZ | (1 n 300) (3|n)} B = {nZ | (1 n 300) (5|n)} C = {nZ | (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 =
View Full Document
Unlocking...