Set, Combinatorics, Probability & Number TheoryPermutationsPermutations: Some special casesPermutation ExamplesCombinationsCombinations: Special CasesCombinations: ExamplesSlide 8Eliminating DuplicatesSummary of Counting TechniquesClass ExercisesSet, Combinatorics, Probability & Number TheoryMathematical Structures for Computer ScienceChapter 3Copyright © 2006 W.H. Freeman & Co. MSCS Slides Set, Combinatorics, Probability & Number TheorySection 3.4 Permutations and Combinations 2PermutationsAn ordered arrangement of objects is called a permutation.Hence, a permutation of n distinct elements is an ordering of these n elements.It is denoted by P(n,r) or nPr.Ordering of last four digits of a telephone number if digits are allowed to repeat10.10.10.10 = 10000Ordering of four digits if repetition is not allowed = 10.9.8.7 = 5040 = 10!/6! where n! = n*(n-1)*(n-2)*….*3*2*1 and by definition 0! = 1Hence, mathematically, for r  n, an r-permutation from n objects is defined byP(n,r) = n*(n-1)*(n-2)*…..*(n-r+1) =  P(n,r) = for 0  r  nHence, P(10,4) = 10! / (10-4)! = 10!/6! = 5040(n-r)!)*(n-r)! ..*(n-r)*)*(n-n*(n- 121 +…)!(!rnn−Section 3.4 Permutations and Combinations 3Permutations: Some special casesP(n,0) = n! / n! = 1This means that there is only one ordered arrangement of 0 objects, called the empty set.P(n,1) = n!/ (n-1)! = nThere are n ordered arrangements of one object (i.e. n ways of selecting one object from n objects).P(n,n) = n!/(n-n)! = n!/0! = n!This means that one can arrange n distinct objects in n! ways, that is nothing but the multiplication principle.Section 3.4 Permutations and Combinations 4Permutation Examples1. Ten athletes compete in an Olympic event. Gold, silver and bronze medals are awarded to the first three in the event, respectively. How many ways can the awards be presented?2. How many ways can six people be seated on six chairs?3. How many permutations of the letters ABCDEF contain the letters DEF together in any order?4. The professor’s dilemma: how to arrange four books on OS, seven on programming, and three on data structures on a shelf such that books on the same subject must be together?Hence, 3 objects from a pool of 10 = P(10,3) = 720P(6,6) = 6! = 720If DEF is considered as one letter, then we have 4 letters A B C DEF whichcan be permuted in 4! ways, DEF can be ordered by its letters in 3! ways.Hence, by the multiplication principle, total number of orderings possible = 4!*3! = 24*6 = 144.(4!*7!*3*)*3! = 24*5040*6*6 = 4,354,560Section 3.4 Permutations and Combinations 5CombinationsWhen order in permutations becomes immaterial, i.e. we are just interested in selecting r objects from n distinct objects, we talk of combinations denoted byC(n,r) or nCrFor each combination, there are r! ways of ordering those r chosen objectsHence, from multiplication principle, C(n,r)* r! = P(n,r)  Note: C(n,r) is much smaller than P(n,r) as seen from the graphs below:nrrrnnrrnPrnC ≤≤−== 0for !)!(!!),(),(Section 3.4 Permutations and Combinations 6Combinations: Special CasesC(n,0) = 1 Only one way to choose 0 objects from n objects-chose the empty setC(n,1) = n Obvious, since n ways to choose one object from n objectsC(n,n) = 1 Only one way to choose n objects from n objectsSection 3.4 Permutations and Combinations 7Combinations: ExamplesHow many ways can we select a committee of three from 10?How many ways can a committee of two women and three men be selected from a group of five different women and six different men?How many five-card poker hands can be dealt from a standard 52-card deck?How many poker hands contain cards all of the same suit?How many poker hands contain three cards of one denomination and two cards of another denomination?C(10,3) = 120For selecting two out of five women, we have C(5,2) ways = 10.For selecting three out of six men, we have C(6,3) ways = 20.Total number of ways for selecting the committee = 10*20 = 200C(52,5) = 2,598,9604*C(13,5) = 5148Order of events: Select first denomination, select three cards from this denomination, select the second denomination, select two cards from this denomination13*C(4,3)*12*C(4,2) = 3744.Section 3.4 Permutations and Combinations 8Combinations: ExamplesHow many routes are there from the lower-left corner of an n by n square grid to the upper-right corner if we are restricted to traveling only to the right (R) or upward (U)?Consider a 44 grid. Total steps required to get from A to B is 8. This can be a mixture of R’s and U’s as shown by the two paths in green and red above. So, 4 R’s and 4 U’s are required but the order is in which step is taken when is not important.In how many ways can three athletes be declared winners from a group of 10 athletes who compete in an Olympic event?So, basically, we are selecting four objects from eight that can be done in C(8,4) ways.For an nn grid, one can form C(2n,n) such routes to go from lower-left to the upper-right corner.C(10,3) = 120 (much less than to award three winners medals)Section 3.4 Permutations and Combinations 9Eliminating DuplicatesHow many ways can a committee of two be chosen from four men and three women and it must include at least one man.How many distinct permutations can be made from the characters in the word FLORIDA?How many distinct permutations can be made from the characters in the word MISSISSIPPI? !2!4!4!11Incorrect and impulsive answer = C(4,1)*C(6,1)Correct answer = C(7,2) – C(3,2) = C(4,1)*C(6,1) – C(4,2)C(4,2) is the number of committees with two men on it. It has to be subtracted since we are counting it twice in C(4,1)*C(6,1).C(7,2) = all committees possibleC(3,2) = all committees with no men on itSimple: 7!Since we have more than one S, interchanging the S’s at the same position will not result in a distinguishable change. Hence for four S’s, 4! possible permutations that look alike.Hence total number of permutations =Section 3.4 Permutations and Combinations 10Summary of Counting TechniquesSection 3.4 Permutations and Combinations 11Class ExercisesHow many permutations of the characters in the word COMPUTER are there? How many of these end in a vowel?How many distinct permutations of the characters in ERROR are there?In how many ways can you seat 11 men and eight women in a row if no two women are to sit together?A set of four coins is