ChCounting离散数学英文版课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《ChCounting离散数学英文版课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ChCounting 离散数学 英文 课件
- 资源描述:
-
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
展开阅读全文