EMath 1105 Discrete Mathematics I for SE PDF

EMath 1105 DISCRETE MATHEMATICS FOR SE I Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Number Theory  THE INTEGERS AND DIVISION...

EMath 1105 DISCRETE MATHEMATICS FOR SE I Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Number Theory  THE INTEGERS AND DIVISION Of course, you already know what the integers are, and what division is… However: There are some specific notations, terminology, and theorems associated with these concepts which you may not know. These form the basics of number theory. Vital in many important algorithms today (hash functions, cryptography, digital signatures; in general, on-line security). Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  New notation: 3 | 12 To specify when an integer THE DIVIDES evenly divides another integer Read as “3 divides 12” OPERATOR The not-divides operator: 𝟓 ∤ 𝟏𝟐 To specify when an integer does not evenly divide another integer Read as “5 does not divide 12” Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Divides, Factor, Multiple Let a,bZ with a0. Definition.: a|b  “a divides b” “There is an integer c such that c times a equals b.” Example: 3  −12  True, but 3  7  False. Iff a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  RESULTS ON THE DIVIDES OPERATOR If a | b and a | c, then a | (b+c) Example: if 5 | 25 and 5 | 30, then 5 | (25+30) If a | b, then a | bc for all integers c Example: if 5 | 25, then 5 | 25*c for all ints c If a | b and b | c, then a | c Example: if 5 | 25 and 25 | 100, then 5 | 100 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Divides Relation Theorem: a,b,c  Z: 1. a|0 2. (a|b  a|c) → a | (b + c) 3. a|b → a|bc 4. (a|b  b|c) → a|c Corollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  q is called the quotient r is called the remainder d is called the divisor a is called the dividend What are the quotient and remainder when 101 is divided by 11? a d q r 101 = 11  9 + 2 We write: q = 9 = 101 div 11 r = 2 = 101 mod 11 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  More examples: 25 𝑚𝑜𝑑 7 = 4 25 𝑚𝑜𝑑 5 = 0 35 𝑚𝑜𝑑 11 = 2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  If a = 7 and d = 3, then q = 2 and r = 1 So: given positive a and (positive) d, in order to get r we repeatedly subtract d from a, as many times as needed so that what remains, r, is less than d. If a = −7 and d = 3, then q = −3 and r = 2 Given negative a and (positive) d, in order to get r we repeatedly add d to a, as many times as needed so that what remains, r, is positive (or zero) and less than d. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  PRACTICE! Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  REVIEW Find “a div m” and “a mod m” when a.) a = 228, m = 119 b.) a = 9009, m = 223 c.) a = - 10101, m = 333 d.) a = - 765432, m = 38271 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department MODULAR ARITHMETIC  MODULAR ARITHMETIC If a and b are integers and m is a positive integer, then “a is congruent to b modulo m” if m divides a-b Notation: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅 𝒎) Rephrased: 𝒎 | 𝒂 − 𝒃 Rephrased: 𝒂 𝒎𝒐𝒅 𝒎 = 𝒃 𝒎𝒐𝒅 𝒎 If they are not congruent: 𝒂 ≢ 𝒃 (𝒎𝒐𝒅 𝒎) Example: Is 17 congruent to 5 modulo 6? Rephrased: 17 ≡ 5 (mod 6) As 6 divides 17-5, they are congruent Example: Is 24 congruent to 14 modulo 6? Rephrased: 24 ≡ 14 (mod 6) As 6 does not divide 24-14, they are not congruent Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES: Identify if TRUE or FALSE (a) 7 ≡ 19 (mod 3) (b) 21 ≡ −8 (mod 6) (c) 53 ≡ 108 (mod 7) (d) −58 ≡ 14 (mod 8) Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department NUMBER SYSTEMS  Bases of Particular Interest Base b=10 (decimal): 10 digits: 0,1,2,3,4,5,6,7,8,9 Base b=2 (binary): 2 digits: 0,1. (“Bits”=“binary digits.”) Base b=8 (octal): 8 digits: 0,1,2,3,4,5,6,7 Base b=16 (hexadecimal): 16 digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Converting to Base b (An algorithm, informally stated.) To convert any integer n to any base b>1: To find the value of the rightmost (lowest-order) digit, simply compute n mod b. Now, replace n with the quotient n/b. Repeat above two steps to find subsequent digits, until n is gone (n = 0). Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Convert 25 in binary? N = 25 a0 = 25 mod 2 = 1 N = 25 / 2 = 12 ∴ 2510 = 110012 a1 = 12 mod 2 = 0 N = 12 / 2 = 6 a2 = 6 mod 2 = 0 N = 6/2 = 3 a 3 = 3 mod 2 = 1 N = 3/ 2 =1 a4 = 1 mod 2 = 1 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Convert 23670 in hexadecimal? ∴ 2367010 = 5𝐶7616 23670 mod 16 = 6; N=  23670/16  = 1479 mod 16 = 7 N=  1479/16  = 92 mod 16 = 12 N= 92/16  = 5 mod 16 = 5 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Binary Expansions Most computers represent integers and do arithmetic with binary (base 2) expansions of integers. In these expansions, the only digits used are 0 and 1. Example: What is the decimal expansion of the integer that has (101011111)2 as its binary expansion? Solution: (1 0101 1111)2 = 1∙28 + 0∙27 + 1∙26 + 0∙25 + 1∙24 + 1∙23 + 1∙22 + 1∙21 + 1∙20 =351. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Binary Expansions Example: What is the decimal expansion of the integer that has (11011)2 as its binary expansion? Solution: (11011)2 = 1 ∙24 + 1∙23 + 0∙22 + 1∙21 + 1∙20 =27. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Octal Expansions The octal expansion (base 8) uses the digits {0,1, 2, 3, 4, 5, 6, 7}. Example: What is the decimal expansion of the number with octal expansion (7016) 8 ? Solution: 7∙83 + 0∙82 + 1∙81 + 6∙80 = 3598 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Octal Expansions Example: What is the decimal expansion of the number with octal expansion (111)8 ? Solution: 1∙82 + 1∙81 + 1∙80 = 64 + 8 + 1 = 73 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Hexadecimal Expansions The hexadecimal expansion needs 16 digits, but our decimal system provides only 10. So letters are used for the additional symbols. The hexadecimal system uses the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. The letters A through F represent the decimal numbers 10 through 15. Example: What is the decimal expansion of the number with hexadecimal expansion (2AE0B)16 ? Solution: 2∙164 + 10∙163 + 14∙162 + 0∙161 + 11∙160 =175627 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Hexadecimal Expansions Example: What is the decimal expansion of the number with hexadecimal expansion (1E5)16 ? Solution: 1∙162 + 14∙161 + 5∙160 = 256 + 224 + 5 = 485 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Base Conversion To construct the base b expansion of an integer n:  Divide n by b to obtain a quotient and remainder.  The remainder, a0 , is the rightmost digit in the base b expansion of n. Next, divide q0 by b.  The remainder, a1, is the second digit from the right in the base b expansion of n.  Continue by successively dividing the quotients by b, obtaining the additional base b digits as the remainder. The process terminates when the quotient is 0. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Base Conversion Example: Find the octal expansion of (12345)10 Solution: Successively dividing by 8 gives: 12345/8 = 1543 r. 1 1543/8 = 192 r. 7 192/8 = 24 r. 0 24/8 = 3 r. 0 3/8 = 0 r. 3 The remainders are the digits from right to left yielding (30071)8. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Comparison of Hexadecimal, Octal, and Binary Representations Initial 0s are not shown Each octal digit corresponds to a block of 3 binary digits. Each hexadecimal digit corresponds to a block of 4 binary digits. So, conversion between binary, octal, and hexadecimal is easy. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Conversion Between Binary, Octal, and Hexadecimal Expansions Example: Find the octal and hexadecimal expansions of (11 1110 1011 1100) 2. Solution:  To convert to octal, we group the digits into blocks of three (011 111 010 111 100)2, adding initial 0s as needed. The blocks from left to right correspond to the digits 3, 7, 2, 7, and 4. Hence, the solution is (37274)8.  To convert to hexadecimal, we group the digits into blocks of four (0011 1110 1011 1100)2, adding initial 0s as needed. The blocks from left to right correspond to the digits 3, E, B, and C. Hence, the solution is (3EBC)16. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Exercises: 1. Convert the decimal expansion of each of these integers to a binary expansion. a) 231 b) 4532 c) 97644 2. Convert to binary expansion of each of these integers to a decimal expansion. a) (0001 1111)2 b) (0010 0000 0001)2 c) (0001 0101 0101)2 d) (0110 1001 0001 0000)2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Exercises: 3. Convert the octal expansion of each of these integers to a binary expansion. a) (572)8 c) (423)8 b) (1604)8 d) (2417)8 4. Convert the hexadecimal expansion of each of these integers to a binary expansion. a) (80𝐸)16 c) (𝐴𝐵𝐵𝐴)16 b) (135𝐴𝐵)16 d) (𝐷𝐸𝐹𝐴𝐶𝐸𝐷)16 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations ADDITION ALGORITHM Example: Add a = (1110)2 and b = (1011)2 1110 + 1011 ------------ 11001 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations MULTIPLICATION ALGORITHM Example: Find the product of a = (110)2 and b = (101)2. 110 x 101 ------------ 110 000 110 ------------ 11110 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations ALGORITHM FOR div AND mod Given integers a and d , d > 0 we can find q = a div d r = a mod d * Until such time what is left is less than d, that’s the remainder. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations MODULAR EXPONENTIATION It is important to be able to find 𝑏 𝑛 𝑚𝑜𝑑 𝑚 efficiently, where b, n, and m are large integers. Example: Use algorithm to find 3644 𝑚𝑜𝑑 645. Step 1: Initially, set x = 1 Step 2: power = 𝑏 𝑛 mod m (power = 32 mod 645) Step 3: Exponent n convert to binary. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations Exercises: 1. Use algorithm to find 7644 𝑚𝑜𝑑 645. 2. Find the sum and product of each of these pairs of numbers. Express the answers in binary. a) (0100 0111)2 and (0111 0111)2 b) (1110 1111)2 and (1011 1101)2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  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