




如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
第七章计数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

ys****39
实名认证
内容提供者


最近下载