离散数学第七章 计数.ppt

第七章计数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}，则S的r排列数是kr。

推论设重集S={n1·a1，n2·a2，…，nk·ak}，且ni≥r，1≤i≤k，则S的r排列数是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个元素的子重集称为S的r组合。
由定义知，若S有n个元素，即n1+n2+…+nk=n，则S的n组合只有一个，即S自身。若S含有k个不同元素，则存在k个S的1组合。
例如：S={3·a,1·b,2·c}，则{a,a},{a,b},{a,c},{b,c},{c,c}都是S的2组合。定理7.4.7设重集S={∞·a1，∞·a2，…，∞·ak}，则S的r组合数是C(k+r-1，r)。推论1设重集S={n1·a1，n2·a2，…，nk·ak}，且ni≥r，1≤i≤k，则S的r组合数是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，a