离散数学课件(英文版)----counting

《离散数学课件(英文版)----counting》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CountingCountingCountableSetPermutationsandcombinationsPigeonholePrincipleRecurrenceRelationsCountableSetAsetAiscountableifandonlyifwecanarrangeallofitselementsinalinearlistinadefiniteorder.“Definite”meansthatwecanspecifythefirst,second,thirdelement,and

2、soon.Ifthelistendedandwiththenthelementasitslastelement,itisfinite.Ifthelistgoesonforever,itisinfinite.ProofofCountabilityThesetofallintegersiscountable.Wecanarrangeallintegerinalinearlistasfollows:0,-1,1,-2,2,-3,3,...thatis:positivekisthe(2k+1)thelemen

3、t,andnegativekisthe2kthelementinthelist.Isthesetofrationalnumberscountable?SetofOrderedPairsThesetofallobjectswiththeformiscountable,wherei,jarenonnegativeintegers.<0,0><1,0><2,0><3,0><4,0><0,1><1,1><2,1><3,1><0,2><1,2><2,2><0,3><1,3><0,4>.........

4、...<0,0>,<0,1>,<1,0>,<0,2>,<1,1>,<2,0>,<0,3>,......So,thesetofrationalnumbersiscountable.RealNumberSetIsNotCountableTheproofbycontradictionproceedsasfollows:(1)Assumethattheinterval(0,1)iscountablyinfinite.(2)Wemaythenenumeratethenumbersinthisintervalas

5、asequence,{r1,r2,r3,...}(3)Assume,forexample,thatthedecimalexpansionsofthebeginningofthesequenceareasfollows.r1=0.0105110...r2=0.4132043...r3=0.8245026...r4=0.2330126...r5=0.4107246...r6=0.9937838...r7=0.0105130...RealNumberSetIsNotCountableThedigitswew

6、illconsiderareindicatedinredFromthesedigitswedefinethedigitsofxasfollows.ifthenthdigitofrnis0thenthenthdigitofxis1ifthenthdigitofrnisnot0thenthenthdigitofxis0Fortheexampleabovethiswillresultinthefollowingdecimalexpansion.x=0.1001001...Isxoneof{r1,r2,…}?

7、So:(0,1)isnotacountableset集合的等势关系等势关系的定义：如果存在从集合A到集合B的双射，则称集合A与B等势。集合A与B等势记为：AB,否则A≉BAB意味着：A，B中的元素可以“一一对应”。要证明AB，找出任意一个从A到B的双射即可。“等势”的集合就被认为是“一样大”可列集(无穷可数集)与自然数集等势的集合称为可列集直观上说：集合的元素可以按确定的顺序线性排列，所谓“确定的”顺序是指对序列中任一元素，可以说出：它“前”、“后”元素是什么。整数集(包括负数)与自然数集等势0

8、,-1,1,-2,2,-3,3,-4,......证明无限集等势的例子(0,1)与整个实数集等势双射：f:(0,1)R:f(x)=tg(x-)对任意不相等的实数a,b(a