《离散数学英文课件：DM_lecture5_1_4 Sum and Product Rules》由会员分享，可在线阅读，更多相关《离散数学英文课件：DM_lecture5_1_4 Sum and Product Rules（24页珍藏版）》请在金锄头文库上搜索。
1、Discrete Mathematics 1Hui GaoCombinatoricslThe study of the number of ways to put things together into various combinations.lE.g. In a contest entered by 100 people,lHow many different top-10 outcomes could occur?lE.g. If a password is 6-8 letters and/or digits, lHow many passwords can there be?Disc
2、rete Mathematics 2Hui Gao5.1 Sum and Product RuleslLet m be the number of ways to do task 1 and n the number of ways to do task 2,lWith each number independent of how the other task is done, lAnd also assume that no way to do task 1 simultaneously also accomplishes task 2.lThen, we have the followin
3、g rules:lThe sum rule: The task “do either task 1 or task 2, but not both” can be done in m+n ways.lThe product rule: The task “do both task 1 and task 2” can be done in mn ways.Discrete Mathematics 3Hui GaoSet Theoretic VersionlIf A is the set of ways to do task 1, and B the set of ways to do task
4、2, and if A and B are disjoint, then:lThe ways to do either task 1 or 2 are AB, and |AB|=|A|+|B|lThe ways to do both task 1 and 2 can be represented as AB, and |AB|=|A|B|Discrete Mathematics 4Hui GaoExample- Sum RulelThere are three boxes containing booksBox 1 has 15 math booksBox 2 has 12 chemistry
5、 bookBox 3 has 10 computer science books.lA student wants to take a book from one of the three boxes. In how many ways can the student do this?lT1: Choose Math booklT2: Choose Chem. booklT3: Choose CS book15 +12+10Discrete Mathematics 5Hui GaoExample Product RulelHow many different license plates ar
6、e available if each plate contains a sequence of three letters followed by three digits? _ _ _ _ _ _ 26ch. 10ch.l262626101010 = 17 576 000Discrete Mathematics 6Hui GaoIP Address Example Sum & Product RulelSome facts about the Internet Protocol, version 4:lValid computer addresses are in one of 3 typ
7、es:lA class A IP address contains a 7-bit “netid” 17, and a 24-bit “hostid”lA class B address has a 14-bit netid and a 16-bit hostid.lA class C addr. Has 21-bit netid and an 8-bit hostid.lHostids that are all 0s or all 1s are not allowed.lHow many valid computer addresses are there?ClassNetIDHostIDA
8、7 bits24 bitsDiscrete Mathematics 7Hui GaoIP address solutionl(# addrs) = (# class A) + (# class B) + (# class C)(by sum rule)l# class A = (# valid netids)(# valid hostids)(by product rule)l(# valid class A netids) = 27 1 = 127.l(# valid class A hostids) = 224 2 = 16,777,214.lContinuing in this fash
9、ion we find the answer is:3,737,091,842 (3.7 billion IP addresses)Discrete Mathematics 8Hui GaoInclusion-Exclusion Principle lSuppose that km of the ways of doing task 1 also simultaneously accomplish task 2.lAnd thus are also ways of doing task 2.lThen, the number of ways to accomplish “Do either t
10、ask 1 or task 2” is mnk.lSet theory: If A and B are not disjoint, then |AB|=|A|B|AB|.lIf they are disjoint, this simplifies to |A|+|B|.Discrete Mathematics 9Hui GaoInclusion/Exclusion ExamplelSome hypothetical rules for passwords:lPasswords must be 2 characters long.lEach character must be a letter
11、a-z, a digit 0-9, or one of the 10 punctuation characters !#$%&*().lEach password must contain at least 1 digit or punctuation character.Discrete Mathematics 10Hui GaoSetup of ProblemlA legal password has a digit or punctuation character in position 1 or position 2. lThese cases overlap, so the prin
12、ciple applies.l(# of passwords w. OK symbol in position #1) = (10+10)(10+10+26)l(# w. OK sym. in pos. #2): also 2046lExclude the commons:l(# w. OK sym both places): 2020lAnswer: 920+920400 = 1,440Discrete Mathematics 11Hui Gao5.2 Pigeonhole Principle lA.k.a. the “Dirichlet drawer principle”lIf k+1 o
13、bjects are assigned to k places, then at least 1 place must be assigned 2 objects. lIn terms of the assignment function: lIf f:AB and |A|B|+1, then some element of B has 2 preimages under f.li.e., f is not one-to-one.Discrete Mathematics 12Hui GaoExample of Pigeonhole PrinciplelThere are 101 possibl
14、e numeric grades (0%-100%) rounded to the nearest integer.lAlso, there are 101 students in this class.lTherefore, there must be at least one (rounded) grade that will be shared by at least 2 students at the end of the semester.li.e., the function from students to rounded grades is not a one-to-one f
15、unction.Discrete Mathematics 13Hui GaoGeneralized Pigeonhole PrinciplelIf N objects are assigned to k places, then at least one place must be assigned at least N/k objects.lE.g., there are N=280 students in this class. There are k=52 weeks in the year.lTherefore, there must be at least 1 week during
16、 which at least 280/52= 5.38=6 students in the class have a birthday.Discrete Mathematics 14Hui GaoProof of G.P.P.lBy contradiction. Suppose every place has | B |.lWe order the elements of A, a1, a2, . . . and assume the urn contains the set B.lThere are | B | ways to choose the image of a1, | B | -
17、 1 ways to choose the image of a2, .lSelection is without replacement. Otherwise we do not construct an injection.lThere are P( | B |, | A | ) injections.Discrete Mathematics 19Hui GaoPermutation Example - 2lAn actress is depicted disabling a bomb by cutting wires to the trigger device. There are 10
18、 wires to the device. If she cuts exactly the right 3 wires, in exactly the right order, she will disable the bomb, otherwise it will explode! If the wires all look the same, what are her chances of survival?P(10,3) = 10!/(10-3)! 1098 = 720, so there is a 1 in 720 chance that shell survive!Discrete
19、Mathematics 20Hui GaoCombinationslAn r -combination of elements of a set S is simply a subset TS with r = |T| members.l Without replacement but order doesnt matter.lThe number of r -combinations of a set with n=|S| elements is lNote that C(n,r) = C(n, nr)lBecause choosing the r members of T is the s
20、ame thing as choosing the nr non-members of T.Discrete Mathematics 21Hui GaoCombination ExamplelHow many distinct 7-card hands can be drawn from a standard 52-card deck?lThe order of cards in a hand doesnt matter.lAnswer C(52,7) = P(52,7)/P(7,7)= 52515049484746 / 765432152171074746 = 133,784,560Disc
21、rete Mathematics 22Hui GaoCombination Example - 2lSuppose you flip a fair coin n times. How many different ways can you getl no heads? C(n, 0)l exactly one head? C(n, 1)l exactly two heads? C(n, 2)l exactly r heads? C(n, r)l at least 2 heads? 2n - C(n, 0) - C(n, 1)Discrete Mathematics 23Hui Gao5.4 B
22、inomial CoefficientslC(n, r) can be used as a coefficient in an expression like (x + y)nC(3,0)C(3,1)C(3,2)C(3,3)Discrete Mathematics 24Hui GaoPascal TrianglelPascals Identity C(n+1, k) = C(n, k-1) + C(n, k)lThe total include all of the subsets from the set of size n which do not contain the new element C(n, k),lPlus the subsets of size k - 1 with the new element added C(n, k-1).PascalTriangle
