离散数学(计数).ppt

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

1、2021/7/21DiscreteMathematicsShandongUniversityQiluSoftwareCollege2021/7/21Chapter3Counting2021/7/21§3.1Thebasicsofcounting(1)3.1.1BasiccountingprinciplesDefinition：Supposethataprocedurecanbebrokendownintoasequenceoftwotasks.Iftherearen1waystodothefirsttaskandn2waystodothesecondtaskaftert

2、hefirsttaskhasbeendone,thentherearen1n2waystodotheprocedure.（1）Theproductrule2021/7/21§3.1Thebasicsofcounting(2)…n1:waystodoT1…n2:waystodoT2……………n1*n2:waystodotheprocedure2021/7/21§3.1Thebasicsofcounting(3)3.1.1BasiccountingprinciplesAnextendedversionoftheproductrule：Supposethataprocedu

3、reiscarriedoutbyperformingthetasksT1,T2,…,Tminsequence.IftaskTicanbedoneinniwaysaftertasksT1,T2,…,andTi-1havebeendone,thentherearen1n2…nmwaystocarryouttheprocedure.（1）Theproductrule2021/7/21§3.1Thebasicsofcounting(4)3.1.1BasiccountingprinciplesDefinition：Ifafirsttaskcanbedoneinn1waysa

4、ndasecondtaskinn2ways,andifthesetaskscannotbedoneatthesametime,thentherearen1+n2waystodooneofthesetasks.（2）Thesumrule2021/7/21§3.1Thebasicsofcounting(5)3.1.1BasiccountingprinciplesAnextendedversionofthesumrule：SupposethatthetasksT1,T2,…,Tmcanbedoneinn1,n2,…,nmways,respectively,andnotwoof

5、thistaskscanbedoneatthesametime.Thenthenumberofwaystodooneofthesetasksisn1+n2+…+nm.（2）Thesumrule2021/7/21§3.1Thebasicsofcounting(6)3.1.2Morecomplexcountingproblems3.1.3Theinclusion-exclusionprinciple3.1.4Treediagrams2021/7/21CountingInternetAddressIPv4A类地址18162432B类地址C类地址D类地址E类地址主机地址范围1.

6、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保留用于实验和将来使用2021/7/21§3.2ThePigeonholeprinciple(1)Thepigeonholeprinciple(dirichletdrawerp

7、rinciple)：Ifk+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.3.2.1Introduction2021/7/21§3.2ThePigeonholeprinciple(1)Corollary1：Afunctionffromasetwithk+1ormoretoasetwithkelementsisnotone-to-one.3.2.1Introduction2021/7/21§3.2ThePig