文本说明讲稿dm2-ch3

2023/1/10DiscreteMathematicsShandongUniversityQiluSoftwareCollege2023/1/10鸬鹚lúcí2023/1/10计数问题？AB2023/1/10计数问题？十进制数串中有偶数个0的数串个数。。。。2023/1/10Chapter3Counting2023/1/10§3.1Thebasicsofcounting(1)3.1.1BasiccountingprinciplesDefinition：Supposethataprocedurecanbebrokendownintoasequenceoftwotasks.Iftherearen1waystodothefirsttaskandn2waystodothesecondtaskafterthefirsttaskhasbeendone,thentherearen1n2waystodotheprocedure.（1）Theproductrule2023/1/10§3.1Thebasicsofcounting(2)…n1:waystodoT1…n2:waystodoT2……………n1*n2:waystodotheprocedure2023/1/10§3.1Thebasicsofcounting(3)3.1.1BasiccountingprinciplesAnextendedversionoftheproductrule：SupposethataprocedureiscarriedoutbyperformingthetasksT1,T2,…,Tminsequence.IftaskTicanbedoneinniwaysaftertasksT1,T2,…,andTi-1havebeendone,thentherearen1n2…nmwaystocarryouttheprocedure.（1）Theproductrule2023/1/10§3.1Thebasicsofcounting(4)3.1.1BasiccountingprinciplesDefinition：Ifafirsttaskcanbedoneinn1waysandasecondtaskinn2ways,andifthesetaskscannotbedoneatthesametime,thentherearen1+n2waystodooneofthesetasks.（2）Thesumrule2023/1/10§3.1Thebasicsofcounting(5)3.1.1BasiccountingprinciplesAnextendedversionofthesumrule：SupposethatthetasksT1,T2,…,Tmcanbedoneinn1,n2,…,nmways,respectively,andnotwoofthistaskscanbedoneatthesametime.Thenthenumberofwaystodooneofthesetasksisn1+n2+…+nm.（2）Thesumrule2023/1/10§3.1Thebasicsofcounting(6)3.1.2Morecomplexcountingproblems2023/1/10CountingInternetAddressIPv4A类地址18162432B类地址C类地址D类地址E类地址主机地址范围1.0.0.0到124.253.253.255128.0.0.0到191.253.253.255192.0.0.0到223.253.253.255224.0.0.0到239.253.253.255240.0.0.0到244.253.253.2550网络地址（7位）主机地址（24位）10网络地址（14位）主机地址（16位）110网络地址（21位）主机地址（8位）1110多目的广播地址（28位）11110保留用于实验和将来使用2023/1/10§3.1Thebasicsofcounting(6)3.1.3Theinclusion-exclusionprincipleLetA1andA2besets;thereare|A1|waystoselectanelementfromA1and|A2|waystoselectanelementfromA2,thenumberofwaystoselectfromA1orA2isthesumofthenumberofwaystoselectanelementfromA1andthenumberofwaystoselectfromA2,minusthewaystoselectanelementthatisinbothA1andA2.2023/1/10§3.1Thebasicsofcounting(6)3.1.3Theinclusion-exclusionprinciple2023/1/10§3.2ThePigeonholeprinciple(1)Thepigeonholeprinciple(Dirichlet狄里克雷drawerprinciple)：Ifk+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.3.2.1Introduction2023/1/10§3.2ThePigeonholeprinciple(1)Corollary1：Afunctionffromasetwithk+1ormoretoasetwithkelementsisnotone-to-one.3.2.1Introduction2023/1/10§3.2ThePigeonholeprinciple(2)ThegeneralizedPigeonholeprinciple(Corollary2)：IfNobjectsareplacedintoKboxes,thenthereisatleastoneboxcontainingatleastN/Kobjects.Show：。。。Exam：3.2.2ThegeneralizedPigeonholeprinciple2023/1/10§3.2ThePigeonholeprinciple(2)3.2.2ThegeneralizedPigeonholeprinciple今有15种不同的工作技能，有10人来参加培训并掌握，设计一种最节约的培训方案使得任何情况下这15种工作技能都可以有人完成。2023/1/10§3.2ThePigeonholeprinciple(2)3.2.2ThegeneralizedPigeonholeprinciplep1p2p3w1w2w3p10w15K10,152023/1/10p1p2p3w1w2w3p10w4K10,5+G(V,E)w5……w6……w15V={P1,P2,…P10,W6,W7,…W15}E{{P1,W6},{P2,W7}…{P10…W15}}2023/1/10ThegeneralizedPigeonholeprinciple2023/1/10ThegeneralizedPigeonholeprinciple2023/1/10ThegeneralizedPigeonholeprinciple2023/1/10§3.2ThePigeonholeprinciple(3)Theorem：Everysequenceofn2+1distinctrealnumberscontainsasubsequenceoflengthn+1thatiseitherstrictlyincreasingorstrictlydecreasing.3.2.3Someelegantapplicationsofthepigeonholeprinciple2023/1/10§3.2ThePigeonholeprinciplea1,a2,…an2+1是n2+1个不同的实数对于数列中的每一个项ai都关联一个有序对(ik,dk)即任意ak∈{a1,a2,…an2+1}定义函数f:ak→(ik,dk)其中:ik从ak开始的最长递增子序列的长度dk从ak开始的最长递减子序列的长度(结论否定)假如没有长度为n+1的递增(减)序列那么ik和dk都是小于等于n的正整数2023/1/10§3.2ThePigeonholeprinciple由乘法法则知(ik,dk)有n2种可能的有序对又由鸽巢原理,n2+1种可能的有序对中必有两个相等即存在as和at(as≠ats<t)使is=it且ds=dt如有as<at且is=it则把as加到at开始的递增序列的前面,此时at开始的递增序列的长度为it+1(矛盾)(同样分析as>at)2023/1/10§3.2ThePigeonholeprinciple例:假如6人中任意2人都认识,或任意2人都不认识.证明在这6人组中或者3人彼此认识,或者3人互不认识.解:设A是6人中的其中一人.则其他5人与A认识的组成一组,与A不认识的组成一组根据鸽巢原理其中一组中至少有3人假如该3人组是与A认识的,如3人中有2人认识则该2人与A组成3人认识组;如3人中没有2人认识,即3人彼此互不认识.2023/1/10§3.2ThePigeonholeprinciple假如该3人组是与A不认识的,如3人中有2人不认识,则该2人与A组成3人不认识组;如3人中没有2人不认识,即3人彼此互相认识.2023/1/10§3.2ThePigeonholeprinciple(4)3.2.3Someelegantapplicationsofthepigeonholeprinciple定义：假设p,q为正整数，p,q≧2,则存在最小正整数R(p,q),使得n≧R(p,q)时,或者有p人是彼此相识,或者有q人彼此不相识,称R(p,q)为Ramsey数(拉姆齐数)。2023/1/10RamseyNumbersR(p,q)=R(q,p)2023/1/10k6完全图,对他的边用红，黑两种颜色任意涂色，则必存在同色边的三角形。拉姆齐数的应用图中边着色2023/1/10§3.3PermutationsandCombinations(1)3.3.1Permutations（1）r-permutationAnorderedarrangementofrelementsofasetiscalledanr-permutation.Thenumberofr-permutationsofasetwithnelementsisdenotedbyP(n,r).2023/1/10§3.3PermutationsandCombinations(2)3.3.1Permutations（1）r-permutationTheorem：Thenumberofr-permutationsofasetwithndistinctelementsisP(n,r)=n(n-1)(n-2)….(n-r+1).2023/1/10§3.3PermutationsandCombinations(3)3.3.1Permutations（2）Circle-permutation2023/1/10§3.3PermutationsandCombinations(4)3.3.1Permutations（2）Circle-permutation2023/1/10§3.3PermutationsandCombinations(5)3.3.1Permutations（3）r-permutationwithrepetitionTheorem：Thenumberofr-permutationsofasetofndistinctobjectswithrepetitionallowedisnr.2023/1/10§3.3PermutationsandCombinations(6)3.3.2Combinations（1）binationAnbinationofelementsofasetisanunorderedselectionofrelementsfromtheset.Thus,anbinationissimplyasubsetofthesetwithrelements.ThenumberofbinationofasetwithndistinctelementsisdenotedbyC(n,r).2023/1/10§3.3PermutationsandCombinations(7)3.3.2Combinations（1）binationNotethatC(n,r)isalsodenotedbyandiscalledabinomialcoefficient.2023/1/10§3.3PermutationsandCombinations(8)3.3.2Combinations（1）binationTheorem：Thenumberofbinationsofasetwithnelements,wherenisanonnegativeintegerandrisanintegerwith0rn,equals2023/1/10§3.3PermutationsandCombinations(9)3.3.2Combinations（1）binationCorollary：LetnandrbenonnegativeintegerswithrnThenC(n,r)=C(n,n-r).2023/1/10§3.3PermutationsandCombinations(10)3.3.2Combinations（2）CombinationswithrepetitionTheorem：ThereareC(n+r-1,r)binationsfromasetwithnelementswhenrepetitionofelementsisallowed.classAclassBclassCclassD15=3+6+3+3solutions2023/1/10§3.4Binomialcoefficients(1)3.4.1Thebinomialtheorem2023/1/10§3.4Binomialcoefficients(2)3.4.1ThebinomialtheoremThebinomialtheorem：Letxandybevariables,andletnbeanonnegativeinteger.Then2023/1/10§3.4Binomialcoefficients(3)3.4.1ThebinomialtheoremC(n,r)=C(n,n-r).2023/1/10§3.4Binomialcoefficients(4)3.4.1Thebinomialtheoremify=1then2023/1/10§3.4Binomialcoefficients(5)3.4.1ThebinomialtheoremCorollary1：Letnbeanonnegativeinteger.ThenCorollary2：Letnbeapositiveinteger.ThenCorollary3：Letnbeanonnegativeinteger.Thenx=1x=-1x=1y=22023/1/10§3.4Binomialcoefficients(6)3.4.2Pascal’sidentityandtrianglePascal’sidentity：Letnandkbepositiveintegerswithnk.ThenShow：basedonSETandSUBSET2023/1/10§3.4Binomialcoefficients(7)3.4.3SomeotheridentitiesofthebinomialcoefficientsVandermonde’sidentity：Letm,nandrbenonnegativeintegerswithrnotexceedingeithermorn,ThenShow：basedonSETandSUBSET2023/1/10§3.4Binomialcoefficients(8)3.4.3SomeotheridentitiesofthebinomialcoefficientsCorollary4：Ifnisanonnegativeinteger,then2023/1/10§3.4Binomialcoefficients(9)3.4.3SomeotheridentitiesofthebinomialcoefficientsTheorem：Letnandrbenonnegativeintegerswithrn.ThenShow：basedonBITSTRINGS2023/1/103.3.1PermutationswithrepetitionTheorem：Thenumberofr-permutationsofasetofndistinctobjectswithrepetitionallowedisnr.§3.5Generalizedpermutation(1)andcombinations2023/1/103.3.1combinationswithrepetition§3.5Generalizedpermutation(1)andcombinationsTheorem：ThereareC(n+r-1,r)binationsfromasetwithnelementswhenrepetitionofelementsisallowed.3.3.1combinationswithrepetition§3.5Generalizedpermutation(1)andcombinations1n个无区别的小球放入m个有区别的箱子里的方案数？相当于从m类物体中允许重复的选取n个物体的方案数：C(m+n-1,n)、C(m+n-1,m-1)2生活中的什么情况下可以使用该模型。选男女代表等3(x+y+z)4展开式有多少项？C(3+4-1,4),C(3+4-1,3-1)那(x+y+z)n展开式有多少项？C(3+n-1,3-1)4x1+x2+x3=11(n)其中x1≥0,x2≥0,x3≥0正整数解的个数？classAclassBclassCclassD3solutions三类水果每类先选取一个（第一步），剩余的4-3个中做允许重复的选择（第二步）1*C(4-3+3-1,4-3)或者1*C(4-3+3-1,3-1)m类物体允许重复的选取n个且每类必须至少选择一个C(n-m+m-1,n-m)=C(n-1,n-m)=C(n-1,m-1)2023/1/10§3.5Generalizedpermutation(1)andcombinations3.3.2PermutationswithindistinguishableobjectsTheorem：Thenumberofdifferentpermutationsofnobjects,wheretherearen1indistinguishableobjectsoftype