您所在位置: 网站首页 / 离散数学第七章 计数.ppt / 文档详情
离散数学第七章 计数.ppt 立即下载
2024-08-16
约3.2千字
约42页
0
218KB
举报 版权申诉
预览加载中,请您耐心等待几秒...

离散数学第七章 计数.ppt

离散数学第七章计数.ppt

预览

免费试读已结束,剩余 37 页请下载文档后查看

10 金币

下载文档

如果您无法下载资料,请参考说明:

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
查看更多
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

离散数学第七章 计数

文档大小:218KB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
全场最划算
12个月
199.0
¥360.0
限时特惠
3个月
69.9
¥90.0
新人专享
1个月
19.9
¥30.0
24个月
398.0
¥720.0
6个月会员
139.9
¥180.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用