1、Elements of Discrete StructuresChapter 6:Counting(Part 2)1The 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
2、and n are positive integers,and we divide 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,0
3、00 people there are at least 3 people 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
4、/k 1).We know n/k n/k+1(from the property: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:
5、1=30+1,11=33+2,111=337+0,1111=3370+1.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.Sho
6、w that there are at least 3 mutual friends 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
7、are friends of A.If the three 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 enemies9Workstation-Server Example We connect 15 workstations
8、 to 10 servers.One server 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 time10ServersWorkstationsWorkstation-Server Example Claim:The minimal number of cables required to connect between workstations and servers is 60 P
9、roof:By contradiction.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!11Permutations r-permutation:An ordere
10、d arrangement of r elements of a set 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 i
11、n(n 1)ways,.,r-th object in n r+1 ways.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
12、 6,4th among 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!13Combinations r-combination C(n,r):An unordered selection of r elements(or subset of size r)from a set of n elemen
13、ts.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-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 arrangem
14、ents.However,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
15、 thus need to divide P(n,r)by r!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 car
16、ds 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: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 m
17、any bit-strings of length 8 contain four 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
18、for math and C(11,4)possibilities for 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 tot
19、al number of bit-strings with exactly 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 ter
20、m xn-jyj is 20nnnnjjnnjnynnyxnnyxnxnyxjnyx111101.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
21、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)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
22、?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,-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 Binomia
23、l Theorem Let n be nonnegative integer.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 ele
24、ment 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 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).Hen
25、ce C(n+1,k)=C(n,k)+C(n,k 1)25 knknkn11Pascals 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
26、 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 can be form
27、ed 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 lettersCombination with Repetition The number of r-combinations of a set of n objects with repetition allowed is Example:How many 2-combinations with re
28、petition 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)!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 o
29、f bills 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)Combination with Repetition Consider the div
30、iders 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 together Stars=dollar bills,always 5,bars=dividers,always 66 dividersCombination with R
31、epetition 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
