- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
.排列.组合
第三章 计数Counting
3.1排列Permutations(置换)
3.1.1乘积集合 Product Sets,
卡氏积Cartesian Product
设A,B是两个集合,元素a(A, b(B,称(a,b)为一个序对,或序偶 ordered pair。
(a,b)=(c,d)当且仅当a=c(b=d
定义 乘积集合
A(B ={(a,b)| a(A,b(B }
定理1 乘法原理Multiplication Priciple
|A(B|=|A|(|B|
假设依次实行T1,T2两种任务,如果做T1有n1种不同的办法, 做T2有n2种不同的办法, 则共有n1(n2种方法完成任务T1T2。
定理2 乘法原理推广
|A1(A2 (…(Ak|=|A1|(|A2|(…(|Ak|
假设依次实行任务T1, T2, ……,Tk,如果做T1有n1种不同的办法, 做T2有n2种不同的办法,… 做Tk有nk种不同的办法, 则共有n1(n2(…(nk种方法完成任务T1T2…Tk。
a) 用1,2,3,4,5可以组成多少个不同的三位数?
用0,1,2,3,4,5可以组成多少个不同的三位数?
解 a) 第一位有5种取法,第二位,第三位也都有5种取法,共组成53=125个不同的三位数。
b) 第一位有5种取法,第二位,第三位有6种取法,共组成5(62=180个不同的三位数。
例2.n个元素的集合A共有多少个子集?
解 由第一章知可以用n个1的数组表示A, A的子集可以用长度为n的0,1序列表示。每一位可以取0或1,两种取法,共有2(2(2(…(2=2n种不同的01串,对应2n个不同的子集。
定理3. 从n个元素的集合A中可重复地取出r个元素排成一列,共有nr种不同的取法。
定理4. 从n个元素的集合A中不重复地取出r个元素排成一列,共有n(n-1)…(n-r+1)种不同的取法。简称n个元素中取r个元素的排列Permuations有种,
排列= n(n-1)…(n-r+1)==
全排列 从n个元素的集合A中不重复地取出n个元素排成一列,共有n!种不同的取法。简称n个元素的全排列Permuations有种,=n!。
重集 有重复元素的集合collection
{a,a,a,b,c},{a,b,b,c,c,c},{a,a,a,b,b,c,c,c,c}
分别记作
{3a,b,c}, {a,2b,3c}, { 3a,2b,4c}
重集的全排列
{3a,b,c}的全排列, 看成5个元素的全排列共5!个。其中3个a与不同次序无关,每个排列重复出现3!次。去除重复共有不同的排列=20个。
{a,2b,3c}的全排列, 看成6个元素的全排列共6!个。其中2个b与3个c不同次序无关,每个排列重复出现2!(3!次。去除重复共有不同的排列=60个。
{ 3a,2b,4c}的全排列,共有=1260个
定理5. n个元素的重集{k1a1,k2a2,…,klal}的不同的全排列共有个。
例 英文单词BANANA中所有字符组成的不同的全排列有多少个?
=60个
组合Combinations
定理1. n个物体中一次取出r个的组合,共有。
例1.52张扑克牌中一次取5张,有多少不同的取法
==2,598,960
3.2.1无穷重集的组合
n个元素的集合{a1,a2,…,an}中可重复地取k个元素的组合数
从n个元素的无穷重集{(a1, (a2,…,( an}中一次取k个元素的组合数
a1a1| a2 a2 a2 | a3 |……| an an an an
0 0 1 0 0 0 1 …… 1 0 0 0 0
相当于k个0,n-1个1的不同排列共有==
==
定理2. n个元素的集合{a1,a2,…,an}中可重复地取k个元素的组合数为=。
例2.一个电台有奖竞猜奖品为十佳CD中可重复地任选三张,问有多少种不同的选法?
====220
排列:与先后次序有关。
组合:与次序无关。
见教科书例5例6。
n个元素的集合{a1,a2,…,an}中可重复地取k个元素,每个元素至少取一个的组合数,
相当于n个元素的集合{a1,a2,…,an}中可重复地取k-n个元素的组合数:
= =
===
推论3. n个元素的集合{a1,a2,…,an}中可重复地取k个元素,每个元素至少取一个的组合数为。
例3. 四种月饼装盒,每盒8块,每种月饼至少一块,一共可装多少种不同的月饼盒?
解 相当于每盒4块月饼
文档评论(0)