经典课件：基本的组合计数公式

离散数学第12章基本的组合计数公式17十一月2022离散数学第12章11十一月2022前言组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方…...前言组合数学是一个古老而又年轻的数学分支。前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每前言贾宪北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》斅音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。前言贾宪北宋数学家（约11世纪）著有前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言1666年莱布尼兹所著《组合学论文》一书问世，这前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言组合数学的蓬勃发展则是在计算机问世和普遍应用之前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。前言组合数学经常使用的方法并不高深复杂。最主要的方计数问题计数问题是组合数学研究的主要问题之一。西班牙数学家AbrahambenMeiribnEzra(1092～1167)和法国数学家、哲学家、天文学家LevibenGerson(1288～1344)是排列与组合领域的两位早期研究者。另外，法国数学家BlaisePascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在《数据结构》、《算法分析与设计》等后续课程中有非常重要的应用。计数问题计数问题是组合数学研究的主要问题之一。西班牙

内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法法则1排列与组合2内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法

本章学习要求重点掌握一般掌握了解11加法法则和原理法则2排列组合的计算31离散概率2离散概念的计算公式及性质2二项式定理与组合恒等式计算

本章学习要求重点掌握一般掌握了解11加法法则和原理法则31组合问题的处理技巧一一对应数学归纳法上下界逼近组合问题的处理技巧一一对应一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最少用多少次切割可以将333的立方体切成27个单位边长的立方体？中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用6次切割。例2100个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法1：50+25+12+6+3+2+1=99方法2：比赛次数与淘汰人数之间存在一一对应，总计淘汰99人，因此至少需要99场比赛.一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最12.1加法法则与乘法法则开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.75表112.1加法法则与乘法法则开胃食品主食饮料种类价格(元)种类乘法法则如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：乘法法则如果一些工作需要t步完成，第一步有n1种不例1Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。例1Melissa病毒1990年，一种名叫Melissa例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有加法法则假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。加法法则假定X1,X2,…,Xt均为集合，第例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？例3由Alice、Ben、Connie、Dolph、Egbe例3解（1）根据乘法法则，可能的选法种数为6×5×4=120；（2）[法一]

根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法法则，可能的选法种数为2×5×4=40；[法二]若Alice被选为主席，共有5×4=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法法则，共有20＋20=40种选法；例3解（1）根据乘法法则，可能的选法种数为6×5×4=1例3解(续)(3)[法一]

将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法法则，共有3×5×4=60种选法；[法二]

根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法法则，共有20＋20＋20=60种选法；例3解(续)(3)[法一]将确定职位分为3步：确定Egb例3解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步：

给Dolph指定职位，有3个职位可选；

给Francisco指定职位，有2个职位可选；

确定最后一个职位的人选，有4个人选。根据乘法法则，共有3×2×4=24种选法。例3解(续)（4）将给Dolph、Francisco和另一12.2排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。12.2排列与组合Zeke、Yung、Xeno和Wi排列问题定义12.1

（1）

从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当r>n时，P(n,r)=0。

排列问题定义12.1例1从含3个不同元素的集合S中有序选取2个元素的排列总数。解从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。例1从含3个不同元素的集合S中有序选取2个元素的排列总数。定理12.1对满足r≤n的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)定理12.1对满足r≤n的正整数n和r有第r位第r-1位第3注意：n个不同元素的排列共有n！种，其中

注意：n个不同元素的排列共有n！种，其中例2A,B,C,D,E,F组成的排列中，（1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解(1)将DEF看成一个对象，根据定理，满足条件的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步：第一步确定D,E和F三个字母的全排列，有3！种排列，第二步将已排序的D,E和F看成一个整体，与A,B和C共4个元素构造出A,B,C,D,E,F的全排列，有4！种排列。又根据乘法原理，满足条件的排列总数有3！×4！=144。例2A,B,C,D,E,F组成的排列中，例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解6个人围坐在圆桌上，有120种不同的坐法。AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形r-排列。例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐推论1含n个不同元素的集合的环形r-排列数Pc(n,r)是推论1含n个不同元素的集合的环形r-排列数Pc(n,r)是例4求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解(1)根据定理，10个男孩的全排列为10!，5个女孩插入到10个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法法则，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!×P(11,5)=（10!×11!)/6!。例4求满足下列条件的排列数。例4解（续）（2）根据定理，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：9!×P(10,5)=（9!×10!)/5!。例4解（续）（2）根据定理，10个男孩站成一个圆圈的环排组合问题定义12.1（2）从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为C(n,r)。当n≥r=0时，规定C(n,r)=1。显然，当r>n时，C(n,r)=0。组合问题定义12.1定理12.1（2）对满足0<r≤n的正整数n和r有，即

证明先从n个不同元素中选出r个元素，有C(n,r)种选法，再把每一种选法选出的r个元素做全排列，有r！种排法。定理12.1（2）对满足0<r≤n的正整数n和r有，即定理12.1（2）（续）根据乘法法则，n个元素的r排列数为：即

定理12.1（2）（续）根据乘法法则，n个元素的r排列数为：例5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A,2—10,J,Q,K。试求满足下列条件的组合数。（1）手中持有5张牌称为一手牌，一手牌共有多少种可能的组合？（2）一手牌中的5张都是同一花色，共有多少种可能的组合？（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？例5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；例5解（1）一手牌可能的组合数等于从52张牌中选出5张的可能组合数，有C(52,5)种可能的组合；（2）选同一花色的5张牌分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)×C(13,5)种；例5解（1）一手牌可能的组合数等于从52张牌中选出5张的可例5解（续）（3）该组合问题需四步完成：

一选第一个点数，有C(13,1)种；

二选第二个点数，有C(12,1)种：

三选第一点数的3张牌，有C(4,3)种；

四选第二点数的2张牌，有C(4,2)种。根据乘法法则，共有C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744种选法。例5解（续）（3）该组合问题需四步完成：集合的排列定义12.1

从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r

排列的数目记作

P(n,r)定理12.1

证明使用乘法法则推论1

S的环排列数=集合的排列定义12.1从n元集S中有序、不重复集合的组合定义12.1

从n元集S中无序、不重复选取的r个元素称为S

的一个r

组合，S的所有r组合的数目记作C(n,r)定理12.1推论2

设n,r为正整数，则(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)集合的组合定义12.1从n元集S中无序、不重复选证明方法方法1：公式代入并化简方法2：组合证明实例：证明

C(n,r)=C(n,nr)证设S={1,2,…,n}是n元集合，对于S的任意r-组合A={a1,a2,…,ar}，都存在一个S的nr组合SA与之对应.显然不同的r组合对应了不同的nr组合，反之也对，因此S的r组合数恰好与S的(nr)组合数相等.C(n,r)=C(n1,r1)+C(n1,r)称为Pascal公式，也对应了杨辉三角形，

两种证明方法都适用.证明方法方法1：公式代入并化简杨辉三角杨辉三角基本计数公式的应用解分类选取

A={1,4,…,298}

B={2,5,…,299}

C={3,6,…,300}分别取自A,B,C:各C(100,3)A,B,C各取1个（分步处理）：C(100,1)3

N=C(100,3)+1003=1485100例1

从1—300中任取3个数使得其和能被3整除有多少种方法？基本计数公式的应用解分类选取例1从1—300中任取3个基本计数公式的应用(续)解:1000!=1000999998…21将上面的每个因子分解，若分解式中共有i个5,j个2，那么min(i,j)就是0的个数.1,…,1000中有500个是2的倍数，j>500;200个是5的倍数，40个是25的倍数（多加40个5），8个是125的倍数（再多加8个5），1个是625的倍数（再多加1个5）i=200+40+8+1=249.min(i,j)=249.例2

求1000！的末尾有多少个0？基本计数公式的应用(续)解:1000!=1000基本计数公式的应用(续)例3

设A为n元集，问(1)A上的自反关系有多少个？(2)A上的反自反关系有多少个？(3)A上的对称关系有多少个？(4)A上的反对称关系有多少个？(5)A上既不对称也不是反对称的关系有多少个？基本计数公式的应用(续)例3设A为n元集，问多重集的排列定理12.2

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk

=n

证明：分步选取.先放a1,有C(n,n1)种方法；再放a2,有C(n

n1,n2)种方法,...,放ak,有C(nn1n2

…

nk1,nk)种方法

(2)若rni

时，每个位置都有

k种选法，得

kr.多重集的排列定理12.2多重集S={n1a1,n2a多重集的组合定理12.3

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞当r

ni,S的r组合数为N=C(k+r1,r),证明一个r组合为{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi为非负整数.这个不定方程的非负整数解对应于下述排列1…101…101…10……01…1

x1个x2个

x3个xk个r个1，k1个0的全排列数为多重集的组合定理12.3多重集S={n1a1,n2实例例5

排列26个字母，使得a与b之间恰有7个字母，求方法数.解：设盒子的球数依次记为x1,x2,…,xn,则满足

x1+x2+…+xn

=r，x1,x2,…,xn为非负整数

N=C(n+r1,r)

例4

r

个相同的球放到n个不同的盒子里，每个盒子球数不限，求放球方法数.解：固定a和b,中间选7个字母，有2P(24,7)种方法，将它看作大字母与其余17个字母全排列有18！种，共

N=2P(24,7)18!实例例5排列26个字母，使得a与b之间恰有7个字实例(续)例6(1)10个男孩，5个女孩站成一排，若没有女孩相邻，有多少种方法？(2)如果站成一个圆圈，有多少种方法？解:(1)

P(10,10)P(11,5)(2)

P(10,10)P(10,5)/10解：相当于2n不同的球放到n个相同的盒子，每个盒子2个，放法为例7

把2n个人分成n

组，每组2人，有多少分法？实例(续)例6(1)10个男孩，5个女孩站成一排，若没有实例(续)解使用一一对应的思想求解这个问题.a1,a2,…,ak

：k个不相邻的数,属于集合{1,2,…,n}b1,b2,…,bk：k个允许相邻的数,属于集合{1,…,n(k1)}

对应规则是

bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8

从S={1,2,…,n}中选择k个不相邻的数，有多少种方法？实例(续)解使用一一对应的思想求解这个问题.例8从12.3二项式定理与组合恒等式12.3.1二项式定理12.3.2组合恒等式12.3.3非降路径问题12.3二项式定理与组合恒等式12.3.1二项式定理二项式定理定理12.4设n是正整数，对一切x和y

证明方法:数学归纳法、组合分析法.证当乘积被展开时其中的项都是下述形式：xiyni,i=0,1,2,…,n.而构成形如xiyni的项，必须从n个和(x+y)中选i个提供x，其它的ni个提供y.因此，xiyni的系数是，定理得证.

二项式定理定理12.4设n是正整数，对一切x和y二项式定理的应用例1

求在(2x－3y)25的展开式中x12y13的系数.解由二项式定理令i=13得到展开式中x12y13的系数，即

二项式定理的应用例1求在(2x－3y)25的展开式中x1组合恒等式——递推式证明方法：公式代入、组合分析应用：1式用于化简2式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并组合恒等式——递推式证明方法：公式代入、组合分析组合恒等式——变下项求和证明公式4.方法：二项式定理或者组合分析.设S={1,2,…,n}，下面计数S的所有子集.

一种方法就是分类处理，n元集合的k子集个数是根据加法法则，子集总数是另一种方法是分步处理，为构成S的子集A，每个元素有2种选择，根据乘法法则，子集总数是2n.组合恒等式——变下项求和证明公式4.方法：二项式定理或者恒等式求和——变系数和证明方法：二项式定理、级数求导其他组合恒等式代入恒等式求和——变系数和证明方法：证明公式6(二项式定理+求导)证明公式6(二项式定理+求导)证明公式7(已知恒等式代入)证明公式7(已知恒等式代入)恒等式——变上项求和证明组合分析.令S={a1,a2,…,an+1}为n+1元集合.等式右边是S的k+1子集数.考虑另一种分类计数的方法.将所有的k+1元子集分成如下n+1类：第1类：含a1,剩下k个元素取自{a2,…,an+1}

第2类：不含a1,含a2,剩下k个元素取自{a3,…,an+1}……不含a1,a2,…,an,含an+1,剩下k个元素取自空集由加法法则公式得证恒等式——变上项求和证明组合分析.令S={a1,a恒等式——乘积转换式证明方法：组合分析.n元集中选取

r个元素，然后在这r个元素中再选

k个元素.不同的r

元子集可能选出相同的k子集，例如{a,b,c,d,e}{a,b,c,d}{b,c,d}{b,c,d,e}{b,c,d}重复度为：应用：将变下限r变成常数k，求和时提到和号外面.恒等式——乘积转换式证明方法：组合分析.恒等式——积之和关系证明思路：考虑集合A={a1,a2,…,am}，B={b1,b2,…,bn}.等式右边计数了从这两个集合中选出r个元素的方法.将这些选法按照含有A中元素的个数k进行分类，k=0,1,…,r.然后使用加法法则.恒等式——积之和关系证明思路：考虑集合A={a1,a2,…,组合恒等式解题方法小结证明方法：已知恒等式带入二项式定理幂级数的求导、积分归纳法组合分析

求和方法：Pascal公式级数求和观察和的结果，然后使用归纳法证明利用已知的公式组合恒等式解题方法小结证明方法：非降路径问题基本计数模型限制条件下的非降路径数非降路径模型的应用证明恒等式单调函数计数栈的输出

非降路径问题基本计数模型基本计数模型(0,0)到(m,n)的非降路径数：C(m+n,m)(a,b)到(m,n)的非降路径数：等于(0,0)到(ma,nb)的非降路径数(a,b)经过(c,d)到(m,n)的非降路径数：乘法法则基本计数模型(0,0)到(m,n)的非降路径数：C(m限制条件的非降路径数从(0,0)到(n,n)不接触对角线的非降路径数NN1：从(0,0)到(n,n)下不接触对角线非降路径数N2：从(1,0)到(n,n1)下不接触对角线非降路径数N0:从(1,0)到(n,n1)

的非降路径数N3:从(1,0)到(n,n1)

接触对角线的非降路径数关系:N=2N1=2N2=2[N0

N3]限制条件的非降路径数从(0,0)到(n,n)不接触对角线的非一一对应N3:从(1,0)到(n,n1)接触对角线的非降路径数N4:从(0,1)到(n,n1)无限制条件的非降路径数关系:N3=N4

一一对应N3:从(1,0)到(n,n1)应用——证明恒等式例2

证明证：计数(0,0)到(m+nr,r)的非降路径数按照k分类，再分步.(0,0)到(mk,k)路径数，(mk,k)到(m+nr,r)的路径数应用——证明恒等式例2证明应用——单调函数计数例3A={1,2,…,m},B={1,2,…,n}，N1:B上单调递增函数个数是(1,1)到(n+1,n)的非降路径数N:B上单调函数个数

N=2N1N2:A到B单调递增函数个数是从(1,1)到(m+1,n)的非降路径数N:A到B的单调函数个数，N=2N2

严格单调递增函数、递减函数个数都是C(n,m)

应用——单调函数计数例3A={1,2,…,m},B={1函数计数小结A={1,2,…,m},B={1,2,…,n}f:AB函数计数小结A={1,2,…,m},B=应用——栈输出的计数例4将1,2,…,n按照顺序输入栈,有多少个不同的输出序列？解：将进栈、出栈分别记作x,y,出栈序列是n个x，n个y的排列，排列中任何前缀的x

个数不少于y的个数.等于从(0,0)到(n,n)的不穿过对角线的非降路径数.实例：n=5

x,x,x,y,y,x,y,y,x,y

进,进,进,出,出,进,出,出,进,出

3,2,4,1,5应用——栈输出的计数例4将1,2,…,n按照顺序输入栈,应用——栈输出的计数(续)N:堆栈输出个数N:(0,0)到(n,n)不穿过对角线的非降路径数N0:(0,0)到(n,n)的非降路径总数N1:(0,0)到(n,n)的穿过对角线的非降路径数N2:(1,1)到(n,n)的非降路径数.关系：N=N=N0N1,N1=N2应用——栈输出的计数(续)N:堆栈输出个数8.4.1多项式定理8.4.2多项式系数12.4多项式定理8.4.1多项式定理12.4多项式定理多项式定理.定理12.5

设n为正整数，xi为实数，i=1,2,…,t.求和是对满足方程n1+n2+…+nt=n的一切非负整数解求在n个因式中选n1个因式贡献x1,从剩下nn1个因式选n2个因式贡献x2,…,从剩下的nn1n2…nt1个因式中选nt个因式贡献xt.证明展开式中的项是如下构成的:多项式定理.定理12.5设n为正整数，xi为实数，i推论推论1

多项式展开式中不同的项数为方程的非负整数解的个数

C(n+t1,n)推论2

例1

求(2x13x2+5x3)6中x13x2x32的系数.解由多项式定理得推论推论1多项式展开式中不同的项数为方程例1求(2多项式系数组合意义多项式系数多重集S={n1

a1,n2a2,…,nt

at}的全排列数

n个不同的球放到

t个不同的盒子使得第一个盒子含n1个球，第二个盒子含n2个球，…，第t个盒子含nt个球的方案数多项式系数组合意义多项式系数(续)恒等式推论2定理12.5组合证明多项式系数(续)恒等式推论2定理12.5组合证明补充计数问题的应用例17个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的“钥匙”。为了安全起见，必须有4位在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学工作者的“钥匙”至少应有多少种特征？解为了使任意3个人在场时至少缺少一个特征而打不开门，该电子锁应具备C(7,3)=35种特征；每个科学工作者的“钥匙”至少要有C(6,3)=20种特征。补充计数问题的应用例17个科学工作者从事一项机密的技术例2某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在a克到（a+0.1）克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生产多少铁盘才能得到一对符合要求的铁盘。例2某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的例2解将铁盘按重量分类，所有a克到a+0.005克的分为第一类；a+0.005克到a+0.01克的分为一类；a+0.01克到a+0.015克的又为一类，….，最后，a+0.095克到a+0.1克为一类，共计20类，由鸽笼原理知，若该工厂生产21个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量差将不超过0.005克。例2解将铁盘按重量分类，例3Fibonacci数列假定一对新出生的兔子一个月又成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，一年可以繁殖成多少队兔子？解因为Fn=Fn-1+Fn-2，所以根据迭代法，有F12=F11+F10=2F10+F9=3F9+2F8

=5F8+3F7=8F7+5F6=…=89F2+55F1=89+55=143。例3Fibonacci数列假定一对新出生的兔子一个月又成熟例4计算下面算法中基本操作的次数算法

输入：s1,s2,…,sn和序列的长度。

输出：s1,s2,…,sn，按非递减顺序排列。例4计算下面算法中基本操作的次数算法例4（续）1.selection_sorts(s,n){2.//基本情况3.if(n==1)4.return5.//找到最大的元素6.max_index=1//初始时认为s1是最大的元素7.fori=2ton8.if(si>smax_index)//比较得到较大的元素，并更新最大元素9.max_index=i10.//将最大的元素移至序列尾11.swap((sn,smax_index)12.selection_sort(s,n-1)13.}例4（续）1.selection_sorts(s,n){例4解设计算n个数排序的比较执行次数为bn，则该算法中的比较语句的执行次数的递归关系为：bn=bn-1+n–1，其初始条件为：b1=0。例4解设计算n个数排序的比较执行次数为bn，则该算法中的比例4解（续）用迭代法求解该递归关系：bn=bn-1+n–1=bn-2+n–2+n-1=bn-3+n–3+n–2+n–1=…=b1+1+2+…+n–3+n–2+n–1=0+1+2+…+n–3+n–2+n–1=n(n-1)/2。例4解（续）用迭代法求解该递归关系：个人观点供参考，欢迎讨论个人观点供参考，欢迎讨论离散数学第12章基本的组合计数公式17十一月2022离散数学第12章11十一月2022前言组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方…...前言组合数学是一个古老而又年轻的数学分支。前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每前言贾宪北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》斅音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。前言贾宪北宋数学家（约11世纪）著有前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言1666年莱布尼兹所著《组合学论文》一书问世，这前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言组合数学的蓬勃发展则是在计算机问世和普遍应用之前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。前言组合数学经常使用的方法并不高深复杂。最主要的方计数问题计数问题是组合数学研究的主要问题之一。西班牙数学家AbrahambenMeiribnEzra(1092～1167)和法国数学家、哲学家、天文学家LevibenGerson(1288～1344)是排列与组合领域的两位早期研究者。另外，法国数学家BlaisePascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在《数据结构》、《算法分析与设计》等后续课程中有非常重要的应用。计数问题计数问题是组合数学研究的主要问题之一。西班牙

内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法法则1排列与组合2内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法

本章学习要求重点掌握一般掌握了解11加法法则和原理法则2排列组合的计算31离散概率2离散概念的计算公式及性质2二项式定理与组合恒等式计算

本章学习要求重点掌握一般掌握了解11加法法则和原理法则31组合问题的处理技巧一一对应数学归纳法上下界逼近组合问题的处理技巧一一对应一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最少用多少次切割可以将333的立方体切成27个单位边长的立方体？中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用6次切割。例2100个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法1：50+25+12+6+3+2+1=99方法2：比赛次数与淘汰人数之间存在一一对应，总计淘汰99人，因此至少需要99场比赛.一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最12.1加法法则与乘法法则开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.75表112.1加法法则与乘法法则开胃食品主食饮料种类价格(元)种类乘法法则如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：乘法法则如果一些工作需要t步完成，第一步有n1种不例1Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。例1Melissa病毒1990年，一种名叫Melissa例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有加法法则假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。加法法则假定X1,X2,…,Xt均为集合，第例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？例3由Alice、Ben、Connie、Dolph、Egbe例3解（1）根据乘法法则，可能的选法种数为6×5×4=120；（2）[法一]

根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法法则，可能的选法种数为2×5×4=40；[法二]若Alice被选为主席，共有5×4=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法法则，共有20＋20=40种选法；例3解（1）根据乘法法则，可能的选法种数为6×5×4=1例3解(续)(3)[法一]

将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法法则，共有3×5×4=60种选法；[法二]

根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法法则，共有20＋20＋20=60种选法；例3解(续)(3)[法一]将确定职位分为3步：确定Egb例3解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步：

给Dolph指定职位，有3个职位可选；

给Francisco指定职位，有2个职位可选；

确定最后一个职位的人选，有4个人选。根据乘法法则，共有3×2×4=24种选法。例3解(续)（4）将给Dolph、Francisco和另一12.2排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。12.2排列与组合Zeke、Yung、Xeno和Wi排列问题定义12.1

（1）

从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当r>n时，P(n,r)=0。

排列问题定义12.1例1从含3个不同元素的集合S中有序选取2个元素的排列总数。解从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。例1从含3个不同元素的集合S中有序选取2个元素的排列总数。定理12.1对满足r≤n的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)定理12.1对满足r≤n的正整数n和r有第r位第r-1位第3注意：n个不同元素的排列共有n！种，其中

注意：n个不同元素的排列共有n！种，其中例2A,B,C,D,E,F组成的排列中，（1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解(1)将DEF看成一个对象，根据定理，满足条件的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步：第一步确定D,E和F三个字母的全排列，有3！种排列，第二步将已排序的D,E和F看成一个整体，与A,B和C共4个元素构造出A,B,C,D,E,F的全排列，有4！种排列。又根据乘法原理，满足条件的排列总数有3！×4！=144。例2A,B,C,D,E,F组成的排列中，例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解6个人围坐在圆桌上，有120种不同的坐法。AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形r-排列。例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐推论1含n个不同元素的集合的环形r-排列数Pc(n,r)是推论1含n个不同元素的集合的环形r-排列数Pc(n,r)是例4求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解(1)根据定理，10个男孩的全排列为10!，5个女孩插入到10个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法法则，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!×P(11,5)=（10!×11!)/6!。例4求满足下列条件的排列数。例4解（续）（2）根据定理，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：9!×P(10,5)=（9!×10!)/5!。例4解（续）（2）根据定理，10个男孩站成一个圆圈的环排组合问题定义12.1（2）从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为C(n,r)。当n≥r=0时，规定C(n,r)=1。显然，当r>n时，C(n,r)=0。组合问题定义12.1定理12.1（2）对满足0<r≤n的正整数n和r有，即

证明先从n个不同元素中选出r个元素，有C(n,r)种选法，再把每一种选法选出的r个元素做全排列，有r！种排法。定理12.1（2）对满足0<r≤n的正整数n和r有，即定理12.1（2）（续）根据乘法法则，n个元素的r排列数为：即

定理12.1（2）（续）根据乘法法则，n个元素的r排列数为：例5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A,2—10,J,Q,K。试求满足下列条件的组合数。（1）手中持有5张牌称为一手牌，一手牌共有多少种可能的组合？（2）一手牌中的5张都是同一花色，共有多少种可能的组合？（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？例5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；例5解（1）一手牌可能的组合数等于从52张牌中选出5张的可能组合数，有C(52,5)种可能的组合；（2）选同一花色的5张牌分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)×C(13,5)种；例5解（1）一手牌可能的组合数等于从52张牌中选出5张的可例5解（续）（3）该组合问题需四步完成：

一选第一个点数，有C(13,1)种；

二选第二个点数，有C(12,1)种：

三选第一点数的3张牌，有C(4,3)种；

四选第二点数的2张牌，有C(4,2)种。根据乘法法则，共有C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744种选法。例5解（续）（3）该组合问题需四步完成：集合的排列定义12.1

从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r

排列的数目记作

P(n,r)定理12.1

证明使用乘法法则推论1

S的环排列数=集合的排列定义12.1从n元集S中有序、不重复集合的组合定义12.1

从n元集S中无序、不重复选取的r个元素称为S

的一个r

组合，S的所有r组合的数目记作C(n,r)定理12.1推论2

设n,r为正整数，则(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)集合的组合定义12.1从n元集S中无序、不重复选证明方法方法1：公式代入并化简方法2：组合证明实例：证明

C(n,r)=C(n,nr)证设S={1,2,…,n}是n元集合，对于S的任意r-组合A={a1,a2,…,ar}，都存在一个S的nr组合SA与之对应.显然不同的r组合对应了不同的nr组合，反之也对，因此S的r组合数恰好与S的(nr)组合数相等.C(n,r)=C(n1,r1)+C(n1,r)称为Pascal公式，也对应了杨辉三角形，

两种证明方法都适用.证明方法方法1：公式代入并化简杨辉三角杨辉三角基本计数公式的应用解分类选取

A={1,4,…,298}

B={2,5,…,299}

C={3,6,…,300}分别取自A,B,C:各C(100,3)A,B,C各取1个（分步处理）：C(100,1)3

N=C(100,3)+1003=1485100例1

从1—300中任取3个数使得其和能被3整除有多少种方法？基本计数公式的应用解分类选取例1从1—300中任取3个基本计数公式的应用(续)解:1000!=1000999998…21将上面的每个因子分解，若分解式中共有i个5,j个2，那么min(i,j)就是0的个数.1,…,1000中有500个是2的倍数，j>500;200个是5的倍数，40个是25的倍数（多加40个5），8个是125的倍数（再多加8个5），1个是625的倍数（再多加1个5）i=200+40+8+1=249.min(i,j)=249.例2

求1000！的末尾有多少个0？基本计数公式的应用(续)解:1000!=1000基本计数公式的应用(续)例3

设A为n元集，问(1)A上的自反关系有多少个？(2)A上的反自反关系有多少个？(3)A上的对称关系有多少个？(4)A上的反对称关系有多少个？(5)A上既不对称也不是反对称的关系有多少个？基本计数公式的应用(续)例3设A为n元集，问多重集的排列定理12.2

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk

=n

证明：分步选取.先放a1,有C(n,n1)种方法；再放a2,有C(n

n1,n2)种方法,...,放ak,有C(nn1n2

…

nk1,nk)种方法

(2)若rni

时，每个位置都有

k种选法，得

kr.多重集的排列定理12.2多重集S={n1a1,n2a多重集的组合定理12.3

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞当r

ni,S的r组合数为N=C(k+r1,r),证明一个r组合为{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi为非负整数.这个不定方程的非负整数解对应于下述排列1…101…101…10……01…1

x1个x2个

x3个xk个r个1，k1个0的全排列数为多重集的组合定理12.3多重集S={n1a1,n2实例例5

排列26个字母，使得a与b之间恰有7个字母，求方法数.解：设盒子的球数依次记为x1,x2,…,xn,则满足

x1+x2+…+xn

=r，x1,x2,…,xn为非负整数

N=C(n+r1,r)

例4

r

个相同的球放到n个不同的盒子里，每个盒子球数不限，求放球方法数.解：固定a和b,中间选7个字母，有2P(24,7)种方法，将它看作大字母与其余17个字母全排列有18！种，共

N=2P(24,7)18!实例例5排列26个字母，使得a与b之间恰有7个字实例(续)例6(1)10个男孩，5个女孩站成一排，若没有女孩相邻，有多少种方法？(2)如果站成一个圆圈，有多少种方法？解:(1)

P(10,10)P(11,5)(2)

P(10,10)P(10,5)/10解：相当于2n不同的球放到n个相同的盒子，每个盒子2个，放法为例7

把2n个人分成n

组，每组2人，有多少分法？实例(续)例6(1)10个男孩，5个女孩站成一排，若没有实例(续)解使用一一对应的思想求解这个问题.a1,a2,…,ak

：k个不相邻的数,属于集合{1,2,…,n}b1,b2,…,bk：k个允许相邻的数,属于集合{1,…,n(k1)}

对应规则是

bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8

从S={1,2,…,n}中选择k个不相邻的数，有多少种方法？实例(续)解使用一一对应的思想求解这个问题.例8从12.3二项式定理与组合恒等式12.3.1二项式定理12.3.2组合恒等式12.3.3非降路径问题12.3二项式定理与组合恒等式12.3.1二项式定理二项式定理定理12.4设n是正整数，对一切x和y

证明方法:数学归纳法、组合分析法.