12基本的组合计数公式

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

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

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

组合问题的处理技巧一一对应数学归纳法上下界逼近一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最少用多少次切割可以将333的立方体切成27个单位边长的立方体？中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用6次切割。例2100个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法1：50+25+12+6+3+2+1=99方法2：比赛次数与淘汰人数之间存在一一对应，总计淘汰99人，因此至少需要99场比赛.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表1乘法法那么如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：例1Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被翻开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档翻开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。例2在一幅数字图像中，假设每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。加法法那么假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，那么可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。〔1〕共有多少种选法？〔2〕假设主席必须从Alice和Ben种选出，共有多少种选法？〔3〕假设Egbert必须有职位，共有多少种选法？〔4〕假设Dolph和Francisco都有职位，共有多少种选法？例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解(续)(3)[法一]将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法法那么，共有3×5×4=60种选法；[法二]根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；假设Egbert为秘书，有20种方法确定余下的职位；假设Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法法那么，共有20＋20＋20=60种选法；例3解(续)〔4〕将给Dolph、Francisco和另一个人指定职位分为3步：给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法法那么，共有3×2×4=24种选法。12.2排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取假设干个元素的问题，称为排列问题。排列问题定义12.1〔1〕从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，那么称这个排列为S的一个全排列，简称为S的排列。显然，当r>n时，P(n,r)=0。例1从含3个不同元素的集合S中有序选取2个元素的排列总数。解从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，那么6个排列为AB,AC,BA,BC,CB,CA。定理12.1对满足r≤n的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)注意：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。例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解6个人围坐在圆桌上，有120种不同的坐法。AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形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解〔续〕〔2〕根据定理，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：9!×P(10,5)=〔9!×10!)/5!。组合问题定义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〔2〕对满足0<r≤n的正整数n和r有，即

证明先从n个不同元素中选出r个元素，有C(n,r)种选法，再把每一种选法选出的r个元素做全排列，有r！种排法。定理12.1〔2〕〔续〕根据乘法法那么，n个元素的r排列数为：即

例5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A,2—10,J,Q,K。试求满足以下条件的组合数。〔1〕手中持有5张牌称为一手牌，一手牌共有多少种可能的组合？〔2〕一手牌中的5张都是同一花色，共有多少种可能的组合？〔3〕一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？例5解〔1〕一手牌可能的组合数等于从52张牌中选出5张的可能组合数，有C(52,5)种可能的组合；〔2〕选同一花色的5张牌分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)×C(13,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种选法。集合的排列定义12.1从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作P(n,r)定理12.1证明使用乘法法那么推论1S的环排列数=集合的组合定义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)证明方法方法1：公式代入并化简方法2：组合证明实例：证明

C(n,r)=C(n,n

r)证设S={1,2,…,n}是n元集合，对于S的任意r-组合A={a1,a2,…,ar}，都存在一个S的n

r组合S

A与之对应.显然不同的r组合对应了不同的n

r组合，反之也对，因此S的r组合数恰好与S的(n

r)组合数相等.C(n,r)=C(n

1,r

1)+C(n

1,r)称为Pascal公式，也对应了杨辉三角形，

两种证明方法都适用.杨辉三角根本计数公式的应用解分类选取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)3N=C(100,3)+1003=1485100例1

从1—300中任取3个数使得其和能被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？根本计数公式的应用(续)例3

设A为n元集，问(1)A上的自反关系有多少个？(2)A上的反自反关系有多少个？(3)A上的对称关系有多少个？(4)A上的反对称关系有多少个？(5)A上既不对称也不是反对称的关系有多少个？多重集的排列定理12.2

多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

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

=n

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

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

n1

n2

…

nk

1,nk)种方法

(2)若r

ni

时，每个位置都有

k种选法，得

kr.多重集的组合定理12.3

多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

+∞当r

ni,S的r组合数为N=C(k+r

1,r),证明一个r组合为{x1

a1,x2

a2,…,xk

ak}，其中

x1+x2+…+xk

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

x1个x2个

x3个xk个r个1，k

1个0的全排列数为实例例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!实例(续)例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人，有多少分法？实例(续)解使用一一对应的思想求解这个问题.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个不相邻的数，有多少种方法？12.3二项式定理与组合恒等式12.3.1二项式定理12.3.2组合恒等式12.3.3非降路径问题二项式定理定理12.4设n是正整数，对一切x和y

证明方法:数学归纳法、组合分析法.证当乘积被展开时其中的项都是下述形式：xiyn

i,i=0,1,2,…,n.而构成形如xiyn

i的项，必须从n个和(x+y)中选i个提供x，其它的n

i个提供y.因此，xiyn

i的系数是，定理得证.

二项式定理的应用例1

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

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

一种方法就是分类处理，n元集合的k子集个数是根据加法法那么，子集总数是另一种方法是分步处理，为构成S的子集A，每个元素有2种选择，根据乘法法那么，子集总数是2n.恒等式求和——变系数和证明方法：二项式定理、级数求导其他组合恒等式代入证明公式6(二项式定理+求导)证明公式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个元素取自空集由加法法那么公式得证恒等式——乘积转换式证明方法：组合分析.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.然后使用加法法那么.组合恒等式解题方法小结证明方法：恒等式带入二项式定理幂级数的求导、积分归纳法组合分析

求和方法：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)到(n,n)不接触对角线的非降路径数NN1：从(0,0)到(n,n)下不接触对角线非降路径数N2：从(1,0)到(n,n

1)下不接触对角线非降路径数N0:从(1,0)到(n,n

1)

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

1)

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

N3]一一对应N3:从(1,0)到(n,n

1)接触对角线的非降路径数N4:从(0,1)到(n,n

1)无限制条件的非降路径数关系:N3=N4

应用——证明恒等式例2

证明证：计数(0,0)到(m+n

r,r)的非降路径数按照k分类，再分步.(0,0)到(m

k,k)路径数，(m

k,k)到(m+n

r,r)的路径数应用——单调函数计数例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)

函数计数小结A={1,2,…,m},B={1,2,…,n}f:A

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应用——栈输出的计数(续)N:堆栈输出个数N

:(0,0)到(n,n)不穿过对角线的非降路径数N0:(0,0)到(n,n)的非降路径总数N1:(0,0)到(n,n)的穿过对角线的非降路径数N2:(

1,1)到(n,n)的非降路径数.关系：N=N=N0

N1,N1=N28.4.1多项式定理8.4.2多项式系数12.4多项式定理多项式定理.定理12.5

设n为正整数，xi为实数，i=1,2,…,t.求和是对满足方程n1+n2+…+nt=n的一切非负整数解求在n个因式中选n1个因式贡献x1,从剩下n

n1个因式选n2个因式贡献x2,…,从剩下的n

n1

n2

…

nt

1个因式中选nt个因式贡献xt.证明展开式中的项是如下构成的:推论推论1

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

C(n+t

1,n)推论2

例1

求(2x1

3x2+5x3)6中x13x2x32的系数.解由多项式定理得多项式系数组合意义多项式系数多重集S={n1

a1,n2

a2,…,nt

at}的全排列数

n个不同的球放到

t个不同的盒子使得第一个盒子含n1个球，第二个盒子含n2个球，…，第t个盒子含nt

个球的方案数多项式系数(续)恒等式推论2定理12.5组合证明补充计数问题的应用例17个科学工作者从事一项机密的技术研究，他们的工作