《lec09-鸽洞原理和排列组合》由会员分享，可在线阅读，更多相关《lec09-鸽洞原理和排列组合（21页珍藏版）》请在金锄头文库上搜索。
1、Lecture 9: Counting Principles,Discrete Mathematical Structures: Theory and Applications,Discrete Mathematical Structures: Theory and Applications,2,Learning Objectives,Learn the basic counting principlesmultiplication and addition Explore the pigeonhole principle Learn about permutations Learn abou
2、t combinations,Discrete Mathematical Structures: Theory and Applications,3,Learning Objectives,Learn about binomial coefficients and explore the algorithm to compute them Discover the algorithms to generate permutations and combinations Become familiar with discrete probability,Discrete Mathematical
3、 Structures: Theory and Applications,4,Basic Counting Principles,Discrete Mathematical Structures: Theory and Applications,5,Basic Counting Principles,Discrete Mathematical Structures: Theory and Applications,6,Basic Counting Principles,There are three boxes containing books. The first box contains
4、15 mathematics books by different authors, the second box contains 12 chemistry books by different authors, and the third box contains 10 computer science books by different authors. A student wants to take a book from one of the three boxes. In how many ways can the student do this?,Discrete Mathem
5、atical Structures: Theory and Applications,7,Basic Counting Principles,Suppose tasks T1, T2, and T3 are as follows: T1 : Choose a mathematics book. T2 : Choose a chemistry book. T3 : Choose a computer science book. Then tasks T1, T2, and T3 can be done in 15, 12, and 10 ways, respectively. All of th
6、ese tasks are independent of each other. Hence, the number of ways to do one of these tasks is 15 + 12 + 10 = 37.,Discrete Mathematical Structures: Theory and Applications,8,Basic Counting Principles,Discrete Mathematical Structures: Theory and Applications,9,Basic Counting Principles,Morgan is a le
7、ad actor in a new movie. She needs to shoot a scene in the morning in studio A and an afternoon scene in studio C. She looks at the map and finds that there is no direct route from studio A to studio C. Studio B is located between studios A and C. Morgans friends Brad and Jennifer are shooting a mov
8、ie in studio B. There are three roads, say A1, A2, and A3, from studio A to studio B and four roads, say B1, B2, B3, and B4, from studio B to studio C. In how many ways can Morgan go from studio A to studio C and have lunch with Brad and Jennifer at Studio B?,Discrete Mathematical Structures: Theory
9、 and Applications,10,Basic Counting Principles,There are 3 ways to go from studio A to studio B and 4 ways to go from studio B to studio C. The number of ways to go from studio A to studio C via studio B is 3 * 4 = 12.,Discrete Mathematical Structures: Theory and Applications,11,Basic Counting Princ
10、iples,Discrete Mathematical Structures: Theory and Applications,12,Basic Counting Principles,Consider two finite sets, X1 and X2. Then,This is called the inclusion-exclusion principle for two finite sets.,Consider three finite sets, A, B, and C. Then,This is called the inclusion-exclusion principle
11、for three finite sets.,Discrete Mathematical Structures: Theory and Applications,13,Basic Counting Principles,Discrete Mathematical Structures: Theory and Applications,14,Pigeonhole Principle,The pigeonhole principle is also known as the Dirichlet drawer principle, or the shoebox principle.,Discrete
12、 Mathematical Structures: Theory and Applications,15,Pigeonhole Principle,Discrete Mathematical Structures: Theory and Applications,16,Discrete Mathematical Structures: Theory and Applications,17,Pigeonhole Principle,Discrete Mathematical Structures: Theory and Applications,18,Permutations,Discrete Mathematical Structures: Theory and Applications,19,Permutations,Discrete Mathematical Structures: Theory and Applications,20,Combinations,Discrete Mathematical Structures: Theory and Applications,21,Combinations corollary,
