03-1 第三章 基本计数方法及应用1.pptx

第1页：封面

第三章基本计数方法及应用一、集合的排列和组合(§3.1 ,§3.2.1 )二、圆排列（环排列）(§3.2.1 )三、排列和组合的生成(§3.2.2 )四、多重集的排列和组合(§3.3 )五、二项式系数(§3.4 )六、Stirling数(§3.5 )七、分拆问题(§3.6 )八、分配问题(§3.7 )

第2页：(1)加法原理如果有p1种不

(1)加法原理如果有p1种不同方法能够从一堆物体中选择出一个物体，有p2种不同方法能够从另一堆物体中选择出一个物体，那么从两堆物体中选择出一个物体的方法共有p1+p2种。

一、集合的排列和组合§3.1加法原理与乘法原理

第3页：如果有p1种不同方法能够从第

如果有p1种不同方法能够从第1堆物体中选择出一个物体，有p2种不同方法能够第2堆物体中选择出一个物体，…，有pn种不同方法能够第n堆物体中选择出一个物体，那么从这n堆物体中选择出一个物体的方法共有p1+p2+…+pn种推广形式

第4页：集合表达形式设集合

• 集合表达形式设集合，且对任意的1≤i<j≤n,有则有|S | = | S1|+ | S2|+…+ | Sm|其中|S|表示集合S的元素数。
• 注意各子集间交集均为空

第5页：解：根据加法原理有100+

解：根据加法原理有100+200=300种不同的挑选方法。

例3.1.1从100名教师和200名学生中挑选出1个代表参加会议，那么有多少种不同的挑选方法

第6页：(2)乘法原理如果执行第1项任务

(2)乘法原理如果执行第1项任务有p1个结果，而不论第1项任务结果如何，执行第2项任务有p2个结果，那么，两项任务连续执行有p1×p2个结果

第7页：如果执行第1项任务有p1个结果

如果执行第1项任务有p1个结果，而不论第1项任务结果如何，执行第2项任务有p2个结果，而不论第2项任务结果如何，执行第3项任务有p3个结果，…，而不论第n-1项任务结果如何，执行第n项任务有pn个结果，那么，所有任务连续执行有p1×p2×…×pn个结果推广形式

第8页：集合表达形式令S是n元组(a

• 集合表达形式令S是n元组(a1,a2…,an)的集合，其中a1来自大小为p1的集合A1，a2来自大小为p2的集合A2，…，an来自大小为pn的集合An，而且每个ai的选择是独立的，则S的大小为p1×p2×…×p，即：∣S∣=p1×p2×…×p
• n元组中各个元素的选择是相互独立的

第9页：例3.1.2 从100名教师

例3.1.2从100名教师和200名学生中挑选出教师和学生各1名参加会议，那么有多少种不同的挑选方法解：根据乘法原理有100×200=20000种不同的挑选方法

第10页：例3.1.3 确定数共有多少个正整数因子

例3.1.3确定数共有多少个正整数因子解：因为3，5，13都是质数，所以每个正因子的形式均为，其中0≤i≤4, 0≤j≤2, 0≤k≤7,根据乘法原理共有5×3×8=120个正因子。

第11页：例3.1.4 按要求第4位必须是奇数，可

例3.1.4在1000到9999之间有多少个各位数字不同的奇数解：按要求第4位必须是奇数，可取1、3、5、7和9，共有5种选择。

第1位不能取0，也不能取第4位已选定的数字，所以在第4位选定后第1位有8种选择。

第2位不能取第1位和第4位已选定的数字，共有8种选择。

类似地，第3位有7种选择。

从而，根据乘法原理，满足题意的数共5×8×8×7=2240个课堂思考：1,为什么先从第4位考虑？

2,如果是不同的偶数？

第12页：（3）把元素的有序安排称为排列

（3）把元素的有序安排称为排列（4）把元素的无序安排即与顺序无关的安排称为组合2排列和组合

第13页：把没有重复元素的排列和组合问

把没有重复元素的排列和组合问题称之为集合的排列与组合把有重复元素的排列和组合问题称为多重集合的排列与组合

第14页：不重复的线性r排列数和r组合

不重复的线性r排列数和r组合数

第15页：（1）r>

（1）r>n时，P(n,r)＝0,（2）r=1时，（3）（4）若0≤r≤n，则

第16页：(4)的组合意义是n元集合S的r

(4)的组合意义是n元集合S的r元子集的个数，是集合S的n-r元子集的个数.设A是S的r元子集，则S-A是S的n-r元子集，这种对应关系显然是一一的。

即S的r元子集的个数等于S的n-r元子集的个数

第17页：集合排列组合问题抽象为分配问

集合排列组合问题抽象为分配问题将r个有区别的小球放入n个不同的盒子，每盒不超过一个，则总的放法为P(n,r)。

同样，若小球不加以区别，则有种放法。

第18页：例3.2.1 每个人在场上的位置

例3.2.1在一场足球比赛中，从20名队员中选出11名队员首发，如果不考虑每个人在场上的位置，求有多少种选择方法解：共有种选择方法

第19页：例3.2.2 从100名教师

例3.2.2从100名教师和200名学生中挑选出教师和学生各2名参加会议，那么有多少种不同的挑选方法解：从100名教师中选出2名教师的方法数是，从200名学生中选出2名学生的方法数是，根据乘法原理共有98505000种不同的挑选方法

第20页：例3.1.4 每个单词至

例3.1.4使用英文字母表中26个字母构成8个字母的单词且不允许字母重复，如果要求每个单词至少含有3个元音字母，那么能构成多少个这样的单词解：因为一共有5个元音字母，每个单词至少含有3个元音字母即包含3个，4个或者5个元音字母。

第21页：则分三种情况

• 则分三种情况:
• 有3个元音字母的单词有
• 有4个元音字母的单词有
• 有5个元音字母的单词有
• 根据加法原理共能构成个单词

第22页：例3.2.4 每个盒子中的小球有次序之分

例3.2.4把10个有区分的小球放到5个不同的盒子中，如果要求每个盒子中的小球有次序之分，求有多少种不同的放法解：先是把10个小球进行排列，然后按顺序任意分成5段，从前往后每个部分对应一个盒子。

但问题是，这10个小球的排列数容易得到，但按顺序任意分成5段的方法数不好计算。

按着这个思路把问题转换一下，实际上就是10个小球和4个分隔符号的一个全排列，排列数为14！

，由于4个分隔符号是相同的，所以共有种不同的方法

第23页：组合分析的方法在证明组合等式时不

组合分析的方法在证明组合等式时不是进行代数推导，而是对等式所代表的组合意义进行分析，通过建立一一对应的方法说明等式两边恰好是对同一组合模型进行计数。

这种组合分析的方法是很有用的，请看下面的例子。

第24页：例3.2.5 首先设S为n元集合

例3.2.5对任意正整数n，有解：首先设S为n元集合。

一方面，S的r元子集的个数为，而r可取0,1,2,…,n,由加法原理，S的所有子集的个数为

第25页：另一方面

另一方面，S有n个元素，在构成S的一个子集的时候，S的每个元素都有在该子集中或不在该子集中两种可能，由乘法原理，共有2n种方式构造S的一个子集，即S的子集有2n个。

显然等式两边都表示集合S的子集数，当然相等

第26页：例3.2.6 证明证明等式左边表示

• 例3.2.6证明证明等式左边表示从2n个不同的球中选取两个球的方法数，我们把这2n个球平均分成2组，选取的方法分成两种情况：
• 取自同一组的选法数
• 取自不同组的选法数
• 由加法原理，所求的选法数是等式两边是对同一个组合模型的计数，显然等式成立。

第27页：二、集合的圆排列

• 二、集合的圆排列（不重复）定义：如果在圆周上排成首尾相连的一个环，只考虑元素间的相对顺序的排列称圆排列（或称为环排列）。
• 排列数将会减少。
• 因为对于两个圆排列，如果其中的一个通过旋转可以变成另一个，则认为它们是同样的圆排列．

第28页：S={1

S={1,2,3,4},n=4,r=3,3-线形排列

第29页：定理3.2.1 n元素集合的r-圆排列数

• 定理3.2.1n元素集合的r-圆排列数为
• 当n=r时，此圆排列数为(n-r)!

第30页：例3.2.710 限制条件，1

例3.2.710个人围坐圆桌旁聚餐，如果A和B不能相邻，则不同的坐法有多少种解不考虑限制条件，10个人的圆排列数为9！

，考虑A和B相邻的情况，有两种情形A在B的左侧和A在B的右侧，则A和B相邻的圆排列数为2×8！

，所以不同的坐法有9！

-2×8！

=7×8！

=282240种

第31页：例3.2.8 5个元素的

例3.2.8将5个不同颜色的珠子串成一条项链，能够串成多少不同的项链解首先我们考虑5个元素的圆排列问题，根据定理3.2.1有4！

=24个不同5-圆排列。

但这个问题很特殊，因为项链可以翻转但不影响珠子的相对位置，即每2个圆排列对应同一个项链，因此能够串成12个不同的项链。

第32页：三、集合排列和组合的生成

三、集合排列和组合的生成（1）排列的生成（a）邻位互换法以初始排列1234为例，在各数上方加一箭头，如当箭头所指一侧，相邻的数比较小时，称该数处于活动状态，例如，在中2,3,4都处于活动状态。

第33页：算法3.1邻位互换法生成

算法3.1邻位互换法生成1,2,…,n的所有排列输入：n输出：{1,2,…,n}的所有n!个全排列

第34页：步骤1：初始化

步骤1：初始化，设，输出P；

步骤2：考虑排列P，若排列中无一处于活动状态，则停止；

步骤3：求所有处于活动状态的数中的最大者，设为m。

m和它的箭头所指的一侧的相邻数互换位置，输出P；

步骤4：令比m大的所有数的箭头改变方向，转步骤2.

第35页：当n=4时

当n=4时，算法生成各个排列的顺序

第36页：（b）字典序法算法3.2字典序法

（b）字典序法算法3.2字典序法生成1,2,…,n的所有排列输入：n输出：{1,2,…,n}的所有n!个全排列

第37页：步骤1：初始化

步骤1：初始化，设，输出P；

步骤2：考虑排列P，若对所有的i，都有pi>pi+1，则算法终止；

步骤3：求满足关系式pj-1<pj的j的最大值，设为i，即i=max{j|pj-1<pj}；

步骤4：求满足关系式pi-1<pk的k的最大者，设为j，即j=max{k|pi-1<pk}.

第38页：步骤5：pi-1与pj互换得步骤

步骤5：pi-1与pj互换得步骤6：部分的顺序逆转，得，输出P并转步骤2.

第39页：排列序号排列序号

排列序号排列序号312413123413142141243232141513243324116134243412171423534211814326412319213474132202143842132123149423122234110431223241311432124243112

本页含连续数字序列（方阵图、排列序号表等），源文本无法安全切分，需对照原课件图片人工还原为真表格。

第40页：（2）组合的生成

（2）组合的生成（a）生成集合I={1,2,…,n}的所有组合算法3.3按字典序生成所有长度为n的二进制数串输入：n输出：所有长度为n的二进制数串

第41页：步骤1：初始化

步骤1：初始化，设，输出P;步骤2：如果对于所有的i，若pi=1，则算法终止；

步骤3：求满足pj=0的j的最大值i，即i=max{j|pj=0}；

步骤4：令pi=1，且pi+1=0，pi+2=0，…，pn=0，得到新的数串P，输出P并转步骤2.

第42页：（b）生成集合I={

（b）生成集合I={1,2,…,n}的所有r-组合算法3.4生成I={1,2,…,n}的所有r-组合输入：n,r输出：输出的字典序下所有I={1,2,…,n}的r-组合

第43页：步骤1：令

步骤1：令，输出C；

步骤2：考虑当前的r-组合C，求满足不等式cj<n-r+j的最大的下标i，即步骤3：ci=ci+1；

步骤4：从i+1位开始修改：cj=cj-1+1,其中j=i+1,i+2,…r，形成新的r-组合C，输出并转步骤2.

第44页：生成从{

生成从{1,2,3,4,5,6}的3-组合，按字典序依次为：（1）123（2）124（3）125（4）126（5）134（6）135（7）136（8）145（9）146（10）156（11）234（12）235（13）236（14）245（15）246（16）256（17）345（18）346（19）356（20）456