1、Elements of Discrete Structures,Chapter 6: Counting (Part 1),1,Counting,Count the number of different ways in performing a task Examples How many subsets of size 2 from set 1, 2, 3, 4?They are 1, 2, 1, 3, 1, 4, 2, 3, 2, 4, 3, 4. There are 6 How many decimal numbers can be formed from any two differe

2、nt digits from the set 1, 2, 3, 4?12, 21, 13, 31, 14, 41, 23, 32, 24, 42, 34, 43There are 12 (order is important!),2,Two Basic Counting Principles,Product Rule: Assume we need to perform a task consisting of procedure 1 AND procedure 2 There are n1 ways to perform procedure 1 and for each of them th

3、ere are n2 ways to perform procedure 2 Then there are n1 n2 ways to perform the task Sum Rule: Assume we need to perform a task consisting of procedure 1 OR procedure 2 There are n1 ways to perform procedure 1 or n2 different ways to perform procedure 2 Then there are n1 + n2 ways to perform the tas

4、k,3,Product Rule Examples,We need to label chairs with a letter and a number between 1.100. What is the number of ways to label a chair? 26 possibilities to assign a letter, and for every letter there are 100 possibilities to assign a number. Total 26 100 = 2600 How many ways to allocate two new emp

5、loyees into 12 offices, one employee per office: 1st employee, 12 ways, 2nd employee, 11 ways. Total 12 11 = 131 ways,4,Product Rule Examples Continued,How many bit-strings of length 7? We need to assign the first bit AND the second bit AND the third etc, each with two possible digit 0 or 1. Total:

6、2222222 = 27 Automobile license plate has 3 letters and 3 digits: such as TBC123. How many different license plates are possible? 262626101010 = 17,576,000,5,Product Rule Examples Continued,How many functions are there from set A with m elements to set B with n elements?Since a function represents a

7、 choice of one of the n elements of the codomain for each of the m elements in the domain, the product rule tells us that there are n n n = nm such functions,6,|A| = m,|B| = n,For every m, there are n possibilities,Product Rule Examples Continued,How many possible one-to-one functions are there from

8、 set A with m elements to set B with n elements (m n)? First element from A has n choices in B. Second element has (n 1) choices etc. Answer: n(n1)(n2). (nm+1),7,Product Rule Examples Continued,What is the number of elements in the Cartesian product of the sets A and B? Or, cardinality |AB| = ? For

9、every element in A, ai, it pairs with each of the elements in B, (ai, b1), (ai, b2), , (ai, bn) in the Cartesian product. So, |AB| = |A|B|,8,Evaluating Your Instructor,Current Progress,9,Please help! When you evaluate your instructors, your name or identity will not be released to anybody! It is an

10、anonymous procedure,Product Rule Examples Continued,What is the value in k after executing the following?,k:= 0 for i1 := 1 to n1 for i2 := 1 to n2 for im := 1 to nm k := k + 1 next im next i2 next i1,10,m nested loops,Sum Rule Examples,What is the number of elements in the union set of the disjoint

11、 A1, A2, ., An? Or, |A1A2. An| = ? Answer: |A1| + |A2| +.+ |An| What is the value in k after executing the following?,k:= 0 for i1 := 1 to n1 k := k + 1 next i1 for i2 := 1 to n2 k := k + 1 next i2 for im := 1 to nm k := k + 1 next im,11,m sequential loops,More Example,Counting Internet Protocol (IP

12、) Addresses (IPv4 32 bits) “netid” identifies a network, and “hostid” identifies computers in the network. “netid” excludes all 1s only for Class A addresses. “hostid” excludes all 1s and all 0s Number of Class A addresses: (27 1) (224 2) Number of Class B addresses: (214) (216 2) Number of Class C

13、addresses: (221) (28 2),12,(21 bits),(14 bits),(7 bits),(24 bits),(16 bits),(8 bits),More Example,Passwords consist of 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? Solution: For a 6-ch

14、aracter word, there are 366 possibilities. The exclusion is words without any digits, which is 266. Number of 6-character passwords = 366 266 Number of 7-character passwords = 367 267 and Number of 8-character passwords = 368 268 The total is the sum of 3), 4) and 5),13,Inclusion Exclusion Principle

15、,Assume that m out of n1 ways to do procedure 1 are equivalent to m out of n2 ways to do procedure 2. Then the number of ways to perform procedure 1 OR procedure 2 are n1 + n2 m Example 1: The cardinality of the union set of A, B |A B| = |A| + |B| | A B| Example 2: There are 3 topics and 20 projects

16、 per topic, but 1 project is listed in all three topics. What is the total number of projects? 20 + 20 + 20 2 because one project was over-counted twice,14,Inclusion Exclusion Principle,Example 3: How many bit-strings of length 8 either begin with a 1 or end with 00? Total number of bit-strings star

17、ting with 1 is 27. Total number of bit-strings ending with 00 is 26 However, out of those 26 bit-strings there are 25 bit-strings which started with a one and were counted in the 27 of the first line Conclusion: 27+26 25,15,Tree Diagrams,16,Enumerate all possibilities in a “decision tree” Example: What is the total number of bit-strings of length 4 that