离散数学计数省公共课一等奖全国赛课获奖课件.pptx

第七章计数7.1基本计数原理加法原理加法原理乘法原理乘法原理乘法原理例7.1.3计数因特网地址。在由计算机物理网络互连而组成因特网中，每台计算机网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位位串，它以网络标识netid开始，后跟随主机标识hostid，该标识把一个计算机认定为某个指定网络组员。乘法原理乘法原理乘法原理7.2鸽洞原理鸽洞原理鸽洞原理鸽洞原理鸽洞原理推广7.3容斥原理设S为全集，又因为则有例一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试有21人得5分．假如两次考试中都没得5分有17人，那么两次考试都得5分有多少人？解设A，B分别表示在第一次和第二次考试中得5分学生集合，那么有|S|=50,|A|=26,|B|=21,=17由=|S|–(|A|+|B|)+|A∩B|，得|A∩B|=–|S|+(|A|+|B|)=17–50+26+21=14有14人两次考试都得5分．7.4排列与组合因为在圆排列中主要是元素彼此间相对位置，所以一个圆排列经过旋转后得到仍是同一个圆排列，而线排列则不然了，只要有一个元素位置发生改变便得到不一样排列。考虑到对每一个固定n个元素取r个圆排列均恰有r种不一样方式展成r个不一样线排列，不一样圆排列展成线排列彼此也必不一样，全部圆排列展出恰好就是全部线排列，所以线排列数是圆排列数r倍，于是K(n，r)=P(n，r)/r尤其当r=n时，K(n，n)=P(n，n)/n=(n-1)!例7.4.26颗颜色不一样钻石，可穿成几个钻石圈?圆排列——就是在P（6，6）基础上，原来在这里面ABCDEFG和BCDEFGA是不一样，不过“圆排列”这里因为形成了一个圆圈，所以，ABCDEFG和BCDEFGA是相同，一样“CDEFGAB”等和他们也是相同，可见，一个相同圆排列在原有P（6，6）中是被重复计算了6次，于是圆排列结果是：P(6,6)/6=1*2*3*4*5=120又因为钻石圈是能够翻转，也就是在这里“ABCDEF”和“FEDCBA”是一样（想象一下手镯，你平放着，你再翻转一下，还是原来手镯，不过你一样是顺时针编号，得出号码是恰好调转），于是在圆排列基础上你要除以2，得到P(6,6)/6/2=60种。下面我们主要讲解重集排列与组合所谓重集是指其元素能够屡次出现集合，某元素ai出现次数ni(ni=1，2，…，∞)称为该元素重复数或重复度。如重集S中有k个元素a1，a2，…，ak，其重复数分别为n1，n2，…，nk，则S={n1·a1，n2·an，…，nk·ak}。重集排列定义：从重集S={n1·a1，n2·an，…，nk·ak}中有序选择r个元素称为S一个r排列，当r=n1+n2+…+nk时也称S全排列或S排列。定理7.4.5设重集S={∞·a1，∞·a2，…，∞·ak}，则Sr排列数是kr。推论设重集S={n1·a1，n2·a2，…，nk·ak}，且ni≥r，1≤i≤k，则Sr排列数是kr。下面我们来看重集全排列。先看下面这个例子。例：1个m，4个i，5个s，2个p全部使用，共能组成多少个单词？解：有12个空格：□□□□□□□□□□□□把1＋4＋5＋2＝12个字母全部放进这12个格子中即算完成这件事。先从12个格子中选1个放m，再从剩下12－1＝11个格子中选4个放i，再从剩下12－1－4＝7个格子中选5个格式放s，再从最终12－1－4－5＝2个格子中选2个放p，由乘法原理知，共有种方法。定理7.4.6设重集S={n1·a1，n2·an，…，nk·ak}，且n1+n2+…+nk=n,则S全排列数是重集组合定义：设重集S={n1·a1,n2·an,…,nk·ak}，S中r个元素子重集称为Sr组合。由定义知，若S有n个元素，即n1+n2+…+nk=n，则Sn组合只有一个，即S本身。若S含有k个不一样元素，则存在k个S1组合。比如：S={3·a,1·b,2·c}，则{a,a},{a,b},{a,c},{b,c},{c,c}都是S2组合。定理7.4.7设重集S={∞·a1，∞·a2，…，∞·ak}，则Sr组合数是C(k+r-1，r)。推论1设重集S={n1·a1，n2·a2，…，nk·ak}，且ni≥r，1≤i≤k，则Sr组合数是C(k+r-1，r)。推论2设重集S={∞·a1，∞·a2，…，∞·ak}，且r≥k，则S中每个元素最少选择一个r组合数是C(r-1，k-1)。例7.4.6面包店供给8种面点。假如一盒装12个面点，而且面包店有大量（每种最少12个）各种面点，问能供给多少不一样面点盒？解设8种面点分别记为a1，a2，…，a8，所求不一样面点盒个数是重集={∞·a1，∞·a2，…，∞·a8}或={12·a1，12·a2，…，12·a8}12组合数，即C(8+12-1,12)