Chapter 4 Combinatorial Analysis PDF

EMath 1105 Discrete Mathematics I for SE Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Combinatorial Analysis The Basics of Counting,...

EMath 1105 Discrete Mathematics I for SE Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Combinatorial Analysis The Basics of Counting, Permutations, and Combinations Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Product and Sum Rules Product Rule: Assuming a) We need to perform procedure 1 AND procedure 2. b) There are n1 ways to perform procedure 1 and c) n2 ways to perform procedure 2. There are n1 n2 ways to perform procedure 1 AND procedure 2. Sum Rule: Assuming a) We need to perform procedure 1 OR procedure 2. b) There are n1 ways to perform procedure 1 and c) n2 ways to perform procedure 2. There are n1+n2 ways to perform procedure 1 OR procedure 2. This “OR” is an “exclusive OR.” One choice or the other, but not both. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting Examples Q. How many ways can we label a chair if each label consists of both a letter and a number between 1 and 50, inclusive? There are 26 possibilities for the letter AND 50 for the number… A: 26x50=1300 Q. With 31 flavors of ice cream, 4 sizes of serving, and a choice of “cone” or “dish,” how many different orders of ice cream are there? A: 31x4x2=248 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting Examples Q: There is one position available for a faculty job at CPU. The applicant must come from either Harvard which has 20 candidates or UCLA which has 50 candidates. What is the total number of possible candidates for the position? A: The applicant must be from Harvard OR UCLA. So we have 20+50=70 possible applicants. Q: At a restaurant, there are 18 dinners with meat, 10 different dinners with fish, and 5 vegetarian dinners? How many dinners to choose from? A: Each dinner is meat OR fish OR vegetarian. So we have 18+10+5=33 choices. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting Examples Passwords consist of character strings of 6 to 8 characters. Each character is an upper case letter or a digit. Each password must contain at least one digit. How many passwords are possible? Total number of passwords possible = # passwords with 6 characters + # passwords with 7 characters + # passwords with 8 characters =P6+P7+P8 P6: # possibilities without constraint : 366 # exclusions is # passwords without any digits is 26 6 And so, P6 = 366-266 Similarly, P7 = 367-267 and P8 = 368-268 Giving a final answer of P = P6+P7+P8 = 36 6-266 + 367-267 + 368-268 P = 2.6845 x 10^12 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Example Rosen, section 4.1, question 38 Consider a wedding picture of 6 people ○ There are 10 people, including the bride and groom a) How many possibilities are there if the bride must be in the picture Product rule: place the bride AND then place the rest of the party First place the bride She can be in one of 6 positions Next, place the other five people via the product rule There are 9 people to choose for the second person, 8 for the third, etc. Total = 9*8*7*6*5 = 15120 Product rule yields 6 * 15120 = 90,720 possibilities Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Example Rosen, section 4.1, question 38 Consider a wedding picture of 6 people ○ There are 10 people, including the bride and groom b) How many possibilities are there if the bride and groom must both be in the picture Product rule: place the bride/groom AND then place the rest of the party First place the bride and groom She can be in one of 6 positions He can be in one 5 remaining positions Total of 30 possibilities Next, place the other four people via the product rule There are 8 people to choose for the third person, 7 for the fourth, etc. Total = 8*7*6*5 = 1680 Product rule yields 30 * 1680 = 50,400 possibilities Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Example Rosen, section 4.1, question 38 Consider a wedding picture of 6 people ○ There are 10 people, including the bride and groom c) How many possibilities are there if only one of the bride and groom are in the picture Sum rule: place only the bride Product rule: place the bride AND then place the rest of the party First place the bride ⚫ She can be in one of 6 positions Next, place the other five people via the product rule There are 8 people to choose for the second person, 7 for the third, etc. ○ We can’t choose the groom! Total = 8*7*6*5*4 = 6720 Product rule yields 6 * 6720 = 40,320 possibilities ⚫ OR place only the groom Same possibilities as for bride: 40,320 Sum rule yields 40,320 + 40,320 = 80,640 possibilities Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Example Rosen, section 4.1, question 38 Consider a wedding picture of 6 people ○ There are 10 people, including the bride and groom Alternative means to get the answer c) How many possibilities are there if only one of the bride and groom are in the picture Total ways to place the bride (with or without groom): 90,720 From part (a) Total ways for both the bride and groom: 50,400 From part (b) Total ways to place ONLY the bride: 90,720 – 50,400 = 40,320 Same number for the groom Total = 40,320 + 40,320 = 80,640 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Example How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers? Answer: 26×26×26×10×10×10×10 = 175,760,000 How about if repetition among letters and numbers were prohibited? Answer: 26×25×24×10×9×8×7 = 78,624,000 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Permutation The number of permutations of n things taken r at a time is given by 𝒏! 𝑷 𝒏, 𝒓 = 𝒏−𝒓 ! Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Circular Seatings How many ways are there to sit 6 people around a circular table, where seatings are considered to be the same if they can be obtained from each other by rotating the table? First, place the first person in the north-most chair ○ Only one possibility Then place the other 5 people ○ There are P(5,5) = 5! = 120 ways to do that By the product rule, we get 1*120 =120 Alternative means to answer this: There are P(6,6)=720 ways to seat the 6 people around the table For each seating, there are 6 “rotations” of the seating Thus, the final answer is 720/6 = 120 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Principle of Inclusion–Exclusion (PIE) Inclusion-Exclusion Principle: Assuming a) We need to perform procedure 1 OR procedure 2. b) There are n1 ways to perform procedure 1 and c) n2 ways to perform procedure 2 and d) m of the ways of doing procedures 1 and 2 are equivalent There are (n1 + n2 – m) ways to perform procedure 1 OR procedure 2. (Recall: |𝐴𝐵| = |𝐴| + |𝐵| − |𝐴𝐵| ) Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Inclusion-exclusion example Rosen, section 4.1, example 16 How may bit strings of length eight start with 1 or end with 00? Count bit strings that start with 1 ○ Rest of bits can be anything: 2 7 = 128 ○ This is |A1| Count bit strings that end with 00 ○ Rest of bits can be anything: 2 6 = 64 ○ This is |A2| Count bit strings that both start with 1 and end with 00 ○ Rest of the bits can be anything: 25 = 32 ○ This is This is |A1 ∩ A2| Use formula |A1 U A2| = |A1| + |A2| - |A1 ∩ A2| Total is 128 + 64 – 32 = 160 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Inclusion-exclusion example How many bit-strings of length 8 either begin with 1 or end with 00? A = 8-bit strings starting with 1 B = 8-bit strings starting with 00 What’s |AB| ? It’s |A| + |B| - |AB|: |A| = # of 8-bit strings starting with 1 is 27 |B| = # of 8-bit strings ending with 00 is 26 |AB| = # of 8-bit strings starting with 1 and ending with 00 is 25 Final Answer: |AB| = 2 7+ 26- 25 = |A| + |B| - |AB| = 160 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Combination The number of combination of n things taken r at a time is 𝒏! 𝑪 𝒏, 𝒓 = 𝒓! 𝒏 − 𝒓 ! Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Bit strings How many bit strings of length 10 contain: a) exactly four 1’s? Find the positions of the four 1’s Does the order of these positions matter? Nope! Positions 2, 3, 5, 7 is the same as positions 7, 5, 3, 2 Thus, the answer is C(10,4) = 210 b) at most four 1’s? There can be 0, 1, 2, 3, or 4 occurrences of 1 Thus, the answer is: C(10,0) + C(10,1) + C(10,2) + C(10,3) + C(10,4) = 1+10+45+120+210 = 386 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Bit strings How many bit strings of length 10 contain: c) at least four 1’s? There can be 4, 5, 6, 7, 8, 9, or 10 occurrences of 1 Thus, the answer is: C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10) = 210+252+210+120+45+10+1 = 848 Alternative answer: subtract from 210 the number of strings with 0, 1, 2, or 3 occurrences of 1 d) an equal number of 1’s and 0’s? Thus, there must be five 0’s and five 1’s Find the positions of the five 1’s Thus, the answer is C(10,5) = 252 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES 1. There are 18 mathematics majors and 325 computer science majors at a college. a) In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major? b) In how many ways can one representative be picked who is either a mathematics major or a computer science major? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES 2. A multiple-choice test contains 10 questions. There are four possible answers for each question. a) In how many ways can a student answer the questions on the test if the student answers every question? b) In how many ways can a student answer the questions on the test if the student can leave answers blank? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES 3. Two six-faced distinct dice are thrown. What is the number of outcomes if the sum of the digits shown is 3 or 6? 4. Three coins are tossed and the outcomes are placed in a row. a. How many outcomes are there? b. How many outcomes contain at least two consecutive heads? c. How many outcomes do not contain at least two consecutive heads? d. How many outcomes do not contain exactly two heads? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES 5. How many four letter words can be formed from the letters G, R, O, U, P, S if no letter is to be used more than once in any word? 6. A committee of six is to be made from four students and eight teachers. In how many ways can this be done: a. If the committee contains exactly three students? b. If the committee contains at least three students? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  ANSWERS TO EXERCISES 1. a) 18 x 325 = 5850 b)18 + 325 = 343 2. a) 4^10 = 1048576 b) 5^10 = 9765625 3. 7 outcomes 4. a. 2 x 2 x 2 = 8 b. 2 x 2 x 2 = 8 (head and tail) 1x2x2=4 (exactly 1 head) 1x1x1=1 (no head, only tails) Answer: 8 – 4 - 1= 3 c. based from letter b, Answer: 4+1 = 5 d. hht, thh, hth = 3 outcomes with exactly two head Answer: 8-3=5 outcomes Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  ANSWERS TO EXERCISES 5. How many four letter words can be formed from the letters G, R, O, U, P, S if no letter is to be used more than once in any word? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  ANSWERS TO EXERCISES 6. A committee of six is to be made from four students and eight teachers. In how many ways can this be done: a. If the committee contains exactly three students? b. If the committee contains at least three students? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  The Pigeonhole Principle Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  The Pigeonhole Principle If more than n pigeons are placed in n holes, at least one hole will contain more than one pigeon. With more than n pigeons in n holes the average number of pigeons per hole is greater than one. The statement “at least one hole will contain more than one pigeon” is equivalent to “the maximum number of pigeons in any whole is greater than one” Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Counting: Pigeonhole Principles Pigeonhole Principle: If we have 𝑛 > 𝑘 balls and we divide them among 𝑘 boxes, then at least one box contains 2 balls. Generalized Pigeonhole Principle: If we have 𝑛 > 𝑘 balls and we divide them among k boxes, then at least one box contains at least 𝑛/𝑘  balls. Example: k=5, n=11 11/5  = 3 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Tree Diagrams Example: ○ What are the possible results of A Tree Diagram systematically flipping a coin twice? lists all possible ways a sequence of events can occur. Advantage: Visual display of H Results: sequential events. H HH T HT Disadvantage: Only practical TH where the number of choices H TT T are small. T Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES PRINCIPLE OF COUNTING PERMUTATIONS COMBINATIONS Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob. 1: How many outcome sequences are possible when a die is rolled four times? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob. 2: John, Jim, Jay, and Jack have formed a band consisting of 4 instruments. If each of the boys can play all 4 instruments, how many different arrangements are possible? What if John and Jim can play all 4 instruments, but Jay and Jack can each play only piano and drums? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob. 3: For years, telephone area codes in the US and Canada consisted of a sequence of three digits. The first digit was an integer from 2 to 9; the second digit was either 0 or 1; the third digit was any integer from 1 to 9. How many area codes were possible? How many area codes starting with a 4 were possible? Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob.4: How many different letter arrangements can be made from the following words… (a) fluke (b) propose (c) Mississippi (d) arrange Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob. 5. In how many ways can 8 people be seated in a row if (a) there are no restrictions on the seating arrangement; 8! = 40,320 (b) person A and B must sit next to each other; 7!2! Or 2!*7*6! = 10,080 (c) there are 4 men and 4 women and no 2 men and 2 women can sit next to each other; 2*4!4! = 1,152 (d) there are 5 men and they must sit next to each other; 4!5!= 2,880 (e) there are 4 married couples and each couple must sit together? 4!2!2!2!2! = 384 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Prob. 6: Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place? 20! / (2! (18!) = 190 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  References: [email protected], [email protected] Discrete Mathematics, Kenneth Rosen Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Thank you! Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department