Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Discrete mathematics and its applications (7/e) – Chapter 6: Counting

Chapter 6 - Counting. This chapter presents the following content: The basics of counting, the pigeonhole principle, permutations and combinations, binomial coefficients and identities, generalized permutations and combinations, generating permutations and combinations (not yet included in overheads). | Counting Chapter 6 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary The Basics of Counting The Pigeonhole Principle Permutations and Combinations Binomial Coefficients and Identities Generalized Permutations and Combinations Generating Permutations and Combinations (not yet included in overheads) The Basics of Counting Section 6.1 Section Summary The Product Rule The Sum Rule The Subtraction Rule The Division Rule Examples, Examples, and Examples Tree Diagrams Basic Counting Principles: The Product Rule The Product Rule: A procedure can be broken down into a sequence of two tasks. There are n1 ways to do the first task and n2 ways to do the second task. Then there are n1∙n2 ways to do the procedure. Example: How many bit strings of length seven are there? Solution: Since each of the seven bits is either a 0 or a 1, the answer is 27 = 128. The Product Rule Example: How many different license plates can be made if each plate contains a sequence of three uppercase English letters followed by three digits? Solution: By the product rule, there are 26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 different possible license plates. Counting Functions Counting Functions: How many functions are there from a set with m elements to a set with n elements? Solution: Since a function represents a 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. Counting One-to-One Functions: How many one-to-one functions are there from a set with m elements to one with n elements? Solution: Suppose the elements in the domain are a1, a2, , am. There are n ways to choose the value of a1 and n−1 ways to choose a2, etc. The product rule tells us that there are n(n−1) (n−2)∙∙∙(n−m +1) such functions. Telephone Numbering Plan Example: The North . | Counting Chapter 6 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary The Basics of Counting The Pigeonhole Principle Permutations and Combinations Binomial Coefficients and Identities Generalized Permutations and Combinations Generating Permutations and Combinations (not yet included in overheads) The Basics of Counting Section 6.1 Section Summary The Product Rule The Sum Rule The Subtraction Rule The Division Rule Examples, Examples, and Examples Tree Diagrams Basic Counting Principles: The Product Rule The Product Rule: A procedure can be broken down into a sequence of two tasks. There are n1 ways to do the first task and n2 ways to do the second task. Then there are n1∙n2 ways to do the procedure. Example: How many bit strings of length seven are there? Solution: Since each of the seven bits is either a 0 or a 1, the answer is 27 = 128. .