ChCounting离散数学英文实用.pptx

《ChCounting离散数学英文实用.pptx》由会员分享，可在线阅读，更多相关《ChCounting离散数学英文实用.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、The Pigeonhole Principle1Pigeonhole Principle:Let k and n be positive integers(n k),and we divide n balls among k boxes,then at least one box contains 2 balls13 Pigeons,12 Boxes第1页/共33页Generalized Pigeonhole PrincipleTheorem:If we have n k balls,k and n are positive integers,and we divide them among

2、 k boxes,then at least one box contains n/k ballsAssume 10 boxes(k=10).Number of balls n=11 20,at least a box has 2 ballsNumber of balls n=21 30,at least a box has 3 ballsNumber of balls n=31 40,at least a box has 4 ballsExample:In a group of 1,000 people there are at least 3 people who have their b

3、irthday on the same day.Why?This is because 1000/365=32第2页/共33页Generalized Pigeonhole PrincipleProof of the Generalized Pigeonhole Theorem:By contradiction:Assume none of the k boxes contains n/k balls.Then,each box contains at most n/k 1 balls.So,n k(n/k 1).We know n/k n/k+1(from the property:x x+1

4、).So,n k(n/k 1)k(n/k+1 1)=n.Or,n b).Definition of congruence.Let m=a b.m is a multiple of n and has only 1s&0s5第5页/共33页Pigeonhole Principle ExampleConsider the case n=3.Construct m from n+1=4 integers as follows:1,11,111,1111Divide each of them by n(3)to get:1=30+1,11=33+2,111=337+0,1111=3370+1.In t

5、his case:1 mod 3=1,1111 mod 3=1.If we subtract these two integers we get a new integer that is divisible by n:m=1111 1=1110(=3 370),which is a multiple of 36第6页/共33页Pigeonhole Principle ExampleAt a party of 6 people,every two people are either enemies or friends.Show that there are at least 3 mutual

6、 friends or 3 mutual enemies at the party7friendsfriendsfriendsenemiesenemiesenemiesOR第7页/共33页Pigeonhole Principle ExampleProof:Consider person A:A certainly has either 3 friends or 3 enemies at the party(Pigeonhole Principle:5 people in 2 categories).Assume three of them are friends of A.If the thr

7、ee are mutual enemies then we have 3 mutual enemies and we are done.If not,then at least 2 are friends,but they are also As friends,which makes a group of three mutual friends.Similar proof for the case of three enemies8第8页/共33页Workstation-Server ExampleWe connect 15 workstations to 10 servers.One s

8、erver can only let one workstation use it to communicate at a time.We require that any 10 workstations can use the 10 servers at any time9ServersWorkstations第9页/共33页Workstation-Server ExampleClaim:The minimal number of cables required to connect between workstations and servers is 60Proof:By contrad

9、iction.Assume it is 59.Then one server S must connect to at most 5 workstations(59/10=5).This means that the remaining 10 workstations are not connected to S.So these 10 workstations can only communicate to at most 9 servers.It is a contradiction!10第10页/共33页Permutationsr-permutation:An ordered arran

10、gement of r elements of a set of n distinct elements,r nExample:S=1,2,3,4:2134 is a permutation of S321 is a 3-permutation of S 32 is a 2-permutation of SPermutation Theorem:The number of r-permutations of n objects is:P(n,r)=n(n 1)(n 2).(n r+1)=First object can be chosen in n ways,second in(n 1)way

11、s,.,r-th object in n r+1 ways.Use product rule to get the above resultWhen r=n,P(n,n)=n(n 1)(n 2).1=n!11第11页/共33页Permutation ExamplesA mailman needs to bring 8 packages to 8 cities.He starts at city 1.How many ways are there to visit the remaining 7 cities?Pick second city among 7,3rd among 6,4th am

12、ong 5,.Answer:7!How many permutations of the letters“a,b,c,d,e,f,g,h”contain“abc”as a block.Rename“abc”to B.Now we have:how many permutations of B,d,e,f,g,h are there?Answer:6!12第12页/共33页Combinationsr-combination C(n,r):An unordered selection of r elements(or subset of size r)from a set of n element

13、s.Example:S=1,2,3,4.Then 3,2,1=1,2,3 is a 3-combination.1,3,4 is another and 1,4 is a 2-combinationCombination Theorem:The total number of r-combinations of a set of size n,0 r n,is given by 13第13页/共33页CombinationsProof of combination theorem:P(n,r)counts the total number of ordered arrangements.How

14、ever,the difference of C(n,r)is that it is only interested in unordered arrangements here.For every subset of r elements one can exactly construct r!ordered arrangements in the permutation,everyone of which is included in P(n,r).These r!arrangements should be considered the same in C(n,r).We thus ne

15、ed to divide P(n,r)by r!14第14页/共33页CombinationsNote that C(n,r)=C(n,n r).Its symmetricThis is because Also,15第15页/共33页Combination ExampleHow many poker hands of five cards can be dealt from a standard deck of 52 cards?Also,how many ways are there to select 47 cards from a deck of 52 cards?Solution:S

16、ince the order in which the cards are dealt does not matter,the number of five card hands is:The different ways to select 47 cards from 52 is 第16页/共33页Combination Examples1.How many bit-strings of length 8 contain four 1s2.We need to form a committee of 7 people,3 from math and 4 from computer scien

17、ce to develop a discrete math course.There are 9 math candidates and 11 CS candidates TTwo separate problems that need to be combined using the product rule.C(9,3)possibilities for math and C(11,4)possibilities for CS:Total=C(9,3)C(11,4)=27,72017第17页/共33页Combination ExampleHow many paths are there f

18、rom(0,0)to(m,n)with right and up moves as the only allowed moves?We need exactly n up moves and m right moves to get to(m,n).Let“up”be a“1”and right be a“0”.Thus we need to count the total number of bit-strings with exactly m 1s and n 0s.18One possible path(m,n)(0,0)This is equivalent to select n(or

19、 m)elements from a set of n+m elements:C(n+m,n)011100001010(7,5)第18页/共33页Binomial CoefficientsBinomial Theorem(n,j 0 and j n)(Note that )When(x+y)n is in its expanded form,the coefficient of term xn-jyj is 19第19页/共33页Binomial Coefficient ExamplesWhat is the coefficient of x12 y13 in the expansion of

20、(x+y)25?We need to pick 12 xs from 25 terms:C(25,12)=C(25,13)=25!/(12!13!)What is the coefficient of x12y13 in(2x 3y)25?First replace a=2x and b=-3y.The coefficient of a12b13 in(a+b)25 is C(25,13).thus it follows that:C(25,13)a12b13=C(25,13)212x12(-3)13 y13.So the coefficient of x12y13 is C(25,13)21

21、2(-3)13=-(25!/(12!13!)21231320第20页/共33页Binomial Coefficient ExampleWhat are coefficients for xk in the expansion of(x+1/x)100 in terms of k,where k is an integer?A typical term for j is (i)Let k=100 2j.Then j=(100 k)/2 As j runs from 0 to 100,k runs from 100 to-100 in decrements of 2(100,98,0,-2,-10

22、0)So,(i)is equivalent to 21第21页/共33页Binomial Coefficient CorollariesLet n be nonnegative integer.Then Let x=1 and y=1 in the Binomial TheoremLet n be nonnegative integer.ThenLet x=1 and y=2 in(i)and let x=1 and y=-1 in(ii)in the Binomial Theorem22(i)and(ii)第22页/共33页23Pascals Triangle/Identity第23页/共3

23、3页Pascals IdentityPascals Identity,where n,k 0 and k n:Proof:Denote T=a1,a2,ak+1,and S=T aj where aj is some arbitrary element in T.The number of subsets of k elements of T is C(n+1,k).This must be equal to the number of ways to pick k elements from T that do not contain aj(=picking k elements from

24、S,or C(n,k),plus the number of ways to pick k elements that always contain aj(=picking k 1 elements from S,or C(n,k 1).Hence C(n+1,k)=C(n,k)+C(n,k 1)24第24页/共33页Pascals IdentityPascals Identity,where n,k 0 and k n:An algebraic proof 25第25页/共33页Permutation with RepetitionThe number of r-permutations o

25、f a set of n objects with repetition allowed is nrExample:How many 3-permutations can be formed from S=1,2,3,4 with repetition?First object can be chosen in 4 ways.The second object can be chosen also in 4 ways because the elements can be used repeatedly.So,444=43Example:How many strings of length r

26、 can be formed from the English alphabet?This is 262626 26(r of them multiplied together)=26r,because each position can repeatedly select any of the 26 English letters第26页/共33页Combination with RepetitionThe number of r-combinations of a set of n objects with repetition allowed isExample:How many 2-c

27、ombinations with repetition from 1,2,3,4?They are 1,1,1,2,1,3,1,4,2,2,2,3,2,4,3,3,3,4,4,4.There are C(4+21,2)=C(5,2)=10第27页/共33页Combination with RepetitionExample:How many ways are there to select five bills from a cash box containing$1,$2,$5,$10,$20,$50 and$100(seven different)bills?The number of b

28、ills for each dollar value is greater than or equal to 5(enough for the case that all five bills are from one value)Order is not important.This is to select five(r=5)elements from seven(n=7)that are repeatable:Prove:The total number of ways is C(7+51,5)第28页/共33页Combination with RepetitionConsider th

29、e dividers as movable bars.Examples:1.when you select two 5-dollar bills,you put two stars between the two bars for the 5-dollar box2.When you dont pick any 10-dollar bills then the two bars for the 10-dollar box stay togetherStars=dollar bills,always 5,bars=dividers,always 66 dividers第29页/共33页Combi

30、nation with Repetition Example30The number of ways to select five bills is corresponding to the number of ways to arrange the bars and stars in 11 positions,or to select the five stars out of 11 positions:So this is C(71+5,5)=C(n+r1,r)=C(11,5)=462第30页/共33页31Summary第31页/共33页Exercises#106.3,P413:5d,5e,6c,6e,8,13,19,206.4,P421:7,8,932第32页/共33页33感谢您的欣赏！第33页/共33页