Permutations CS311H: Discrete Mathematics Permutations

PermutationsCS311H: Discrete MathematicsIPermutations and CombinationsInstructor: Işıl DilligIA permutation of a set of distinct objects is an orderedarrangement of these objectsINo object can be selected more than onceIOrder of arrangement mattersExample: S {a, b, c}. What are the permutations of S ?IInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations1/26How Many Permutations?Consider set S {a1 , a2 , . . . an }IHow many permutations of S are there?IDecompose using product rule:IHow many ways to choose first element?IHow many ways to choose second element?I.IHow many ways to choose last element?2/26IConsider the set {7, 10, 23, 4}. How many permutations?IHow many permutations of letters A, B, C, D, E, F, G contain”ABC” as a substring?IIICS311H: Discrete MathematicsPermutations and Combinations3/26r -PermutationsInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations4/26Computing P (n, r )IGiven a set with n elements, what is P (n, r )?IDecompose using product rule:r-permutation is ordered arrangment of r elements in a set SIS can contain more than r elementsIBut we want arrangement containing r of the elements in SIThe number of r-permutations in a set with n elements iswritten P (n, r )IExample: What is P (n, n)?IInstructor: Işıl Dillig,Permutations and CombinationsWhat is number of permutations of set S ?Instructor: Işıl Dillig,ICS311H: Discrete MathematicsExamplesIIInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations5/26Instructor: Işıl Dillig,IHow many ways to pick first element?IHow many ways to pick second element?IHow many ways to pick i ’th element?IHow many ways to pick last element?Thus, P (n, r ) n · (n 1) . . . · (n r 1) CS311H: Discrete MathematicsPermutations and Combinationsn!(n r )!6/26

ExamplesICombinationsWhat is the number of 2-permutations of set {a, b, c, d , e}?IIIHow many ways to select first-prize winner, second-prizewinner, third-prize winner from 10 people in a contest?IIISalesman must visit 4 cities from list of 10 cities: Must beginin Chicago, but can choose the remaining cities and order.IHow many possible itinerary choices are there?An r-combination of set S is the unordered selection of relements from that setUnlike permutations, order does not matter in combinationsIExample: What are 2-combinations of the set {a, b, c}?IFor this set, 6 2-permutations, but only 3 2-combinationsIInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations7/26Number of r -combinationsIIC (n, r ) is often also written asI ITheorem:nr nr nr What is the relationship between P (n, r ) and C (n, r )?ILet’s decompose P (n, r ) using product rule:n!r ! · (n r )!IFirst choose r elementsIThen, order these r elementsIHow many ways to choose r elements from n?IHow many ways to order r elements?IThus, P (n, r ) C (n, r ) r !ITherefore,C (n, r ) Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations9/26ExamplesIIHow many hands of 5 cards can be dealt from a standarddeck of 52 cards?Instructor: Işıl Dillig,IP (n, r )n! r!(n r )! · r !CS311H: Discrete MathematicsPermutations and Combinations10/26How many bitstrings of length 8 contain at least 6 ones?IIThere are 9 faculty members in a math department, and 11 inCS department.IIf we must select 3 math and 4 CS faculty for a committee,how many ways are there to form this committee?IIIInstructor: Işıl Dillig,8/26More Complicated ExampleIIPermutations and CombinationsI, read ”n choose r”is also called the binomial coefficientC (n, r ) CS311H: Discrete MathematicsProof of TheoremThe number of r -combinations of a set with n elements iswritten C (n, r ) Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations11/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations12/26

One More ExampleIBinomial CoefficientsHow many bitstrings of length 8 contain at least 3 ones and 3zeros?IIRecall: C (n, r ) is also denoted asbinomial coefficientII nr and is called theIBinomial is polynomial with two terms, e.g., (a b), (a b)2I I ncalled binomial coefficient b/c it occurs asrcoefficients in the expansion of (a b)nIInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations13/26An ExampleConsider expansion of (a b)3I(a b)3 (a b)(a b)(a b)I (a 3 2a 2 b ab 2 ) (a 2 b 2ab 2 b 3 )I 1a 3 3a 2 b 3ab 2 1b 31Instructor: Işıl Dillig,3CS311H: Discrete Mathematics3(x y)n 14/26 n Xnx n j y jjj 0IWhat is the expansion of (x y)4 ?1Permutations and Combinations15/26Another ExampleInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations16/26Corollary of Binomial TheoremWhat is the coefficient of x 12 y 13 in the expansion of(2x 3y)25 ?IIBinomial theorem allows showing a bunch of useful results.ICorollary:nPk 0IIIIInstructor: Işıl Dillig,Permutations and CombinationsLet x , y be variables and n a non-negative integer. Then, (a 2 2ab b 2 )(a b)IICS311H: Discrete MathematicsThe Binomial TheoremIIInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations17/26Instructor: Işıl Dillig, nk 2nCS311H: Discrete MathematicsPermutations and Combinations18/26

Another CorollaryICorollary:nPPascal’s Triangle( 1)kk 0I nk 0IInstructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations19/26Proof of Pascal’s Identity n 1k nk 1 This identity is known as Pascal’s identityIProof: Ink 1nk Multiply first fraction by Instructor: Işıl Dillig, nk 1 kk nkIIn’th row consists ofInstructor: Işıl Dillig, nk for k 0, 1, . . . nCS311H: Discrete Mathematics Permutations and Combinationsand second bynk CS311H: Discrete Mathematicsn k 1n k 1 :21/26 nk 20/26k · n! (n k 1)n!(k )!(n k 1)!Factor the numerator: (n 1) · n!(n 1)!nn k 1k(k )!(n k 1)!k ! · (n k 1)!IBut this is exactlyk · n! (n k 1)n!(k )!(n k 1)!Permutations and Combinationsnk 1In!n! (k 1)!(n k 1)! (k )!(n k )!Interesting Facts about Pascal’s TriangleIPascal arranged binomial coefficients as a triangleProof of Pascal’s Identity, cont.I IInstructor: Işıl Dillig, n 1k CS311H: Discrete MathematicsPermutations and Combinations22/26Some Fun Facts about Pascal’s Triangle, cont.What is the sum of numbers in n’th row in Pascal’s triangle(starting at n 0)?IPascal’s triangle is perfectly symmetricIObserve: This is exactly the corollary we proved earlier! n Xn 2nkINumbers on left are mirror image of numbers on rightWhy is this the case?k 0Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations23/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations24/26

Permutations with RepetitionsGeneral Formula for Permutations with RepetitionIEarlier, when we defined permutations, we only allowed eachobject to be used once in the arrangementIP (n, r ) denotes number of r-permutations with repetitionfrom set with n elementsIBut sometimes makes sense to use an object multiple timesIWhat is P (n, r )?IExample: How many strings of length 4 can be formed usingletters in English alphabet?IHow many ways to assign 3 jobs to 6 employees if everyemployee can be given more than one job?IA permutation with repetition of a set of objects is an orderedarrangement of these objects, where each object may be usedmore than onceIHow many different 3-digit numbers can be formed from1, 2, 3, 4, 5?Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations25/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsPermutations and Combinations26/26

Instructor: Is l Dillig, CS311H: Discrete Mathematics Permutations and Combinations 25/26 General Formula for Permutations with Repetition I P (n ;r) denotes number of r-permutations with repetition from set with n elements I What is P (n ;r)? I How many ways to assign 3 jobs to 6 employees if every employee can be given more than one job?