1、Ch-Counting离散数学英文版PPTThe Pigeonhole Principle2 Pigeonhole 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 BoxesGeneralized Pigeonhole Principle Theorem:If we have n k balls,k and n are positive integers,and we di
2、vide them among k boxes,then at least one box contains n/k balls Assume 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 balls Example:In a group of 1,000 people there are at least 3 people
3、 who have their birthday on the same day.Why?This is because 1000/365=33Generalized Pigeonhole Principle Proof 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 prop
4、erty:x x+1).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&0s6Pigeonhole Principle Example Consider the case n=3.Construct m from n+1=4 integers as follows:1,11,111,1111 Divide each of them by n(3)to get:1=30+1,11=33+2,111=337+0,1111=3370+1.
5、In this 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 37Pigeonhole Principle Example At a party of 6 people,every two people are either enemies or friends.Show that there are at least 3 mutual fr
6、iends or 3 mutual enemies at the party8friendsfriendsfriendsenemiesenemiesenemiesORPigeonhole Principle Example Proof: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 three are mut
7、ual 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 enemies9Workstation-Server Example We connect 15 workstations to 10 servers.One server can only le
8、t one workstation use it to communicate at a time.We require that any 10 workstations can use the 10 servers at any time10ServersWorkstationsWorkstation-Server Example Claim:The minimal number of cables required to connect between workstations and servers is 60 Proof:By contradiction.Assume it is 59
9、.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!11Permutations r-permutation:An ordered arrangement of r elements of a set
10、of n distinct elements,r n Example:S=1,2,3,4:2134 is a permutation of S321 is a 3-permutation of S 32 is a 2-permutation of S Permutation 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)ways,.,r-th object in n r+1 way
11、s.Use product rule to get the above result When r=n,P(n,n)=n(n 1)(n 2).1=n!12)!(!rnnPermutation Examples A 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 among 5,.Answer:7!How many per
12、mutations 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!13Combinations r-combination C(n,r):An unordered selection of r elements(or subset of size r)from a set of n elements.Example:S=1,2,3,4.Then 3,2,1=1,2,3
13、 is a 3-combination.1,3,4 is another and 1,4 is a 2-combination Combination Theorem:The total number of r-combinations of a set of size n,0 r n,is given by 14)!(!),(rnrnrnCCombinations Proof of combination theorem:P(n,r)counts the total number of ordered arrangements.However,the difference of C(n,r)
14、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 need to divide P(n,r)by r!15)!(
15、!),(),(rnrnrrnPrnCCombinations Note that C(n,r)=C(n,n r).Its symmetricThis is because Also,16),(!)!(!)!()!(!),(rnCrrnnrnnrnnrnnC(i)if,!)1).(2)(1()!(!),(rnrrrnnnnrnrnrnC(ii)if,)!()1).(2)(1()!(!),(rnrrnrnnnrnrnrnCCombination Example How many poker hands of five cards can be dealt from a standard deck
16、of 52 cards?Also,how many ways are there to select 47 cards from a deck of 52 cards?Solution:Since 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 Combination Examples1.How many bit-strings of length 8 contain f
17、our 1s2.We need to form a committee of 7 people,3 from math and 4 from computer science to develop a discrete math course.There are 9 math candidates and 11 CS candidates T Two separate problems that need to be combined using the product rule.C(9,3)possibilities for math and C(11,4)possibilities for
18、 CS:Total=C(9,3)C(11,4)=27,72018Combination ExampleHow many paths are there from(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
19、 m 1s and n 0s.19One possible path(m,n)(0,0)This is equivalent to select n(or m)elements from a set of n+m elements:C(n+m,n)011100001010(7,5)Binomial Coefficients Binomial 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 20nnnnjjnnjnynnyxnnyxnxny
20、xjnyx111101.10)(),(jnCjnjnBinomial Coefficient Examples What is the coefficient of x12 y13 in the expansion of(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(
21、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)212(-3)13=-(25!/(12!13!)21231321Binomial Coefficient Example What 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
22、 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,-100)So,(i)is equivalent to 22jjjxjxxj2100100100)1(100kxk2/)100(100Binomial Coefficient Corollaries Let n be nonnegative integer.Then Let x=1 and y=1 in the Binomial Theorem Let n be nonnegative intege
23、r.ThenLet x=1 and y=2 in(i)and let x=1 and y=-1 in(ii)in the Binomial Theorem230(1)0njjnj (i)and(ii)nnjjn20nnjjjn32024Pascals Triangle/IdentityPascals 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
24、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 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)25 knknkn1
25、1Pascals Identity Pascals Identity,where n,k 0 and k n:An algebraic proof 26 knknkn11 knkknnnnkkknknnnkkknnnknknnnkknnnkknknnnknkn1!)2).(1()1(!)1)(2).(1(!)2).(1()1)(2).(1()!1()2).(1(!)1)(2).(1(1Permutation with RepetitionThe number of r-permutations of a set of n objects with repetition allowed is n
26、rExample: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 can be formed from the English alphabet?This is
27、262626 26(r of them multiplied together)=26r,because each position can repeatedly select any of the 26 English lettersCombination with Repetition The number of r-combinations of a set of n objects with repetition allowed is Example:How many 2-combinations with repetition from 1,2,3,4?They are 1,1,1,
28、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)!1(!)!1()1,1(),1(nrrnnrnCrrnCCombination with Repetition Example: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 bills for each dollar value is grea
29、ter 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)Combination with Repetition Consider the dividers as movable bars.Examples:1.when
30、 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 together Stars=dollar bills,always 5,bars=dividers,always 66 dividersCombination with Repetition Example31 The 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)=46232SummaryExercises#10 6.3,P413:5d,5e,6c,6e,8,13,19,20 6.4,P421:7,8,933
