DOC PREVIEW
UNL CSCE 235 - Combinatorics

This preview shows page 1-2-3-4-5-6-7-49-50-51-52-53-54-55-99-100-101-102-103-104-105 out of 105 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 105 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionCountingPIEExamplesDerangementsPigeonhole PrincipleGeneralizedExamplesPermutationsCombinationsBinomial CoefficientsGeneralizationsAlgorithmsCombinationsPermutationsMore ExamplesCombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatoricsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 5.1-5.6 & 7.5-7.6 of [email protected] / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatorics IIntroductionCombinatorics 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 algorithmsand compute discrete probabilities.Originally, combinatorics was motivated by gambling: countingconfigurations is essential to elementary probability.2 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesCombinatorics IIIntroductionA sim ple example: How many arrangements are there of a deckof 52 cards?In addition, combinatorics can be used as a proof technique.A combinatorial proof is a proof method that uses countingarguments to prove a statement.3 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesProduct RuleIf two events are not mutually exclusive (that is, we do themseparately), then we apply the product rule.Theorem (Product Rule)Suppose a procedure can be accomplished with two disjointsubtasks. If there are n1ways of doing the first task and n2ways of doing the second, then there aren1· n2ways of doing the overall procedure.4 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesSum Rule IIf two events are mutually exclusive, that is, they cannot bedone at the same time, then we must apply the sum rule.Theorem (Sum Rule)If an event e1can be done in n1ways and an event e2can bedone in n2ways and e1and e2are mutually exclusive, then thenumber of ways of both events occurring isn1+ n25 / 94CombinatoricsCSE235IntroductionCountingPIEPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesSum Rul e IIThere is a natural generalization to any sequence of m tasks;namely the number of ways m mutually exclusive events canoccur isn1+ n2+ · · · nm−1+ nmWe can give another formulation in terms of sets. LetA1, A2, . . . , Ambe pairwise disjoint sets. Then|A1∪ A2∪ · · · ∪ Am| = |A1| + |A2| + · · · + |Am|In fact, this is a special case of the general Principle ofInclusion-Exclusion.6 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIntroductionSay there are two events, e1and e2for which there are n1andn2possible outcomes respectively.Now, say that only one event can occur, not both.In this situation, we cannot apply the sum rule? Why?7 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIIntroductionWe cannot use the sum rule because we would be overcounting the number of possible outcomes.Instead, we have to count the number of possible outcomes ofe1and e2minus the number of possible outcomes in commonto 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|8 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIIIntroductionMore generally, we have the following.LemmaLet A, B be subsets of a finite se t U . Then1|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|9 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) ITheoremTheoremLet A1, A2, . . . , Anbe finite sets, then|A1∪ A2∪ · · · ∪ An| =Xi|Ai|−Xi<j|Ai∩ Aj|+Xi<j<k|Ai∩ Aj∩ Ak|− · · ·+(−1)n+1|A1∩ A2∩ · · · ∩ An|Each summation is over all i, pairs i, j with i < j, triples i, j, kwith i < j < k etc.10 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IITheoremTo illustrate, when n = 3, we have|A1∪ A2∪ A3| = |A1| + |A2| + |A3|−|A1∩ A2| + |A1∩ A3| + |A2∩ A3| +|A1∩ A2∩ A3|11 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IIITheoremTo illustrate, when n = 4, we have|A1∪ A2∪ A3∪ A4| = |A1| + |A2| + |A3| + |A4|−h|A1∩ A2| + |A1∩ A3| + +|A1∩ A4||A2∩ A3| + |A2∩ A4| + |A3∩ A4|i+h|A1∩ A2∩ A3| + |A1∩ A2∩ A4| +|A1∩ A3∩ A4| + |A2∩ A3∩ A4|i−|A1∩ A2∩ A3∩ A4|12 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion (PIE) IExample IExampleHow many integers between 1 and 300 (inclusive) are1Divisible by at least one of 3, 5, 7?2Divisible by 3 and by 5 but not by 7?3Divisible by 5 but by neither 3 nor 7?LetA = {n | 1 ≤ n ≤ 300 ∧ 3 | n}B = {n | 1 ≤ n ≤ 300 ∧ 5 | n}C = {n | 1 ≤ n ≤ 300 ∧ 7 | n}13 / 94CombinatoricsCSE235IntroductionCountingPIEExamplesDerangementsPigeonholePrinciplePermutationsCombinationsBinomialCoefficientsGeneralizationsAlgorithmsMoreExamplesPrinciple of Inclusion-Exclusion


View Full Document

UNL CSCE 235 - Combinatorics

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Combinatorics
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Combinatorics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Combinatorics 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?