组合数学课件：第三章 基本计数方法及应用2

1、3.3 多重集的排列与组合3.3.1 多重集的排列3.3.2 多重集的组合 多重集中可以有重复的元素。 多重集合表示为其中： 互不相同 M中有ki个ai（1in）， 称ki为ai的重复度 ki是正整数，也可以是，表示M中有无限多个ai 3.3.1 多重集的排列例子 是一个10个元素的多重集合， 其中有3个a，1个b，2个c，4个d. M表示为 定理3.3.1 多重集合 的r-排列数是nr 证明 在构造M的一个r-排列时，第一个元素 有n种选择，第二个元素 有n种选择，第r个元素 有n种选择。 (由于M中的每个元素都是无限次地重复，所以r-排列中的任意一项都有n种选择，而且不依赖于前面各项的选择

2、) 故M的r-排列数为nr 那么它的3排列？ 2排列？4*4这个问题对应的分配问题模型是：将r个有区别的球放入n个不同的盒子中，且每个盒子的球数不加以限制( 实际上，容量大于等于r就行），而且同盒的球不分次序，则不同的放法为nr 种 若M中每个元素的重复度大于等于r，则结论仍然成立。 2 3 4.第 r个球n n n n n例3.3.1 用26个英文字母可以构造出多少个包含2个元音字母（可以相同）且长度为8的“单词”解 该问题是求 的包含2个元音字母的8-排列数。在长度为8的字符串中，2个元音字母出现的位置的选取方式有 种，而每个元音位置可取5个元音字母中的一个，剩余6个辅音字母的位置可取21

3、个辅音字母中的任一个，因而，满足题意的“单词”有 52216个. 证明 首先把M中所有的个元素看成是互不相同的，则全排列数为 。但ki个ai的位置相同，且其他元素排列也相同的排列实质上是同一个排列。故M的全排列数为 证明（二） M的一个排列就是它的(k1+k2+kn)个元素的一个全排列。因为M中有k1个a1，在排列时要占据k1个位置，这些位置的选法是C(k1+k2+kn, k1)种。接下去，我们在剩下的k2+kn个位置中选择k2个放a2，选法是C(k2+kn,k2)种。通过类似的分析可以得到，我们有C(k3+kn,k3)种方法放a3,，有C(ki+kn,ki)种方法放ai. 根据乘法原则，M的

4、排列数例3.3.2 我们再看例3.2.3，如其余条件不变，只是允许字母随意重复，那么能构成多少个这样的单词？解 因为一共有5个元音字母，每个单词至少含有3个元音字母即包含3个，4个或者5个元音字母。则分三种情况，有3个元音字母的单词有有4个元音字母的单词有有5个元音字母的单词有根据加法原理共例3.3.3 求多重集 的8-排列数解 可分三种情况计算： M-a的8-排列数, 即为 排列数 为： M-b的8-排列数,即为 排列数 为： M-c的8-排列数,即为 排列数 为： 多重集M的8-排列数为 420+280+560=1260 例3.3.4 从4个a，4个b，4个c，4个d中选择字母形成一个10

5、个字母的序列，如果每个字母至少出现两次，有多少种方法形成这样的序列 解 这个问题实际上是求 的10-排列数，但要求每个10排列中包含a,b,c,d每个字母至少两个。我们设 ，则原问题可以分成如下两大类共10种情况：（一） 的10-排列数; 的10-排列数； 的10-排列数：的10-排列数，这4种类情况的10-排列数相等，均为（二） 的10-排列数; 的10-排列数； 的10-排列数：的10-排列数； 10-排列数； 的10-排列数这6种类情况的10-排列数相等，均为满足条件的方法数为 3.3.2 多重集的组合 多重集合的r-组合是指从M中无序地选出r个元素例子 如果多重集M有n个元素(包括重复

6、的元素)，则M的n-组合只有一个，就是M本身。 如果M有n种不同元素，则M的1-组合恰有n个。 证明1 (1) M的任何一个r-组合都具有以下形式其中 是非负整数，则有反之，若给出方程的非负整数解 就是M的一个r-组合。所以多重集M的r-组合数就等于方程的非负整数解的个数。（2）方程 的一个非负整数解可以表示为(n-1)0, r1的一个全排列， 1 1 1 1 0 1 1 10 01 1 1 01111， x1个 x2个 xn个反之(n-1)0, r1的一个全排列，在这个排列中n-1个0把个1分成个组。 从左边数，第一个0左边的1的个数为x1，第一个0和第二个0之间的1的个数为x2 ，依此类推

7、，最后一个0右边的1的个数为xn ，则 是一组非负整数解。 因此 的非负整数解与集合的全排列之间是一一对应。 由(1)(2)知，M的r-组合数等于的全排列数，多重集M的r组合数为 方法2 分析定理的结论， 是(n+r-1)元普通集合的r-组合数，构造： 的r-组合(n+r-1)元的普通集合S的r组合一一对应. 证明如下：为表达方便，将中n种不同元素用数字1,2,n替换，这样每个r-组合具有形式 不妨设令 ，即则显然 与 一一对应，而 是(n+r-1)元集合的r-组合，其数量为 ，从而原结论成立. 定理3.3.4 设多重集rn，则M中每个元素至少取一个的r-组合数为证明 设 是满足条件的任一r-

8、组合，则有令 则显然 其中的整数解个数等于方程 的非负整数解的个数。由定理3.3.3，满足定理条件的组合数为例3.3.5 求集合S=1,2,n的r-组合数，其中要求r-组合中任意两个元素在S中都不是相邻的。 如当n=8，r=3时，S=1,2,3,4,5,6,7,8，1,3,8是满足条件的3-组合，而1,2,6是不满足条件的3-组合，因为1,2在S中是相邻的。解 考虑S的任意一个r-组合 ，不妨设 我们把1,2,n这n个数按从小到大的顺序排成一个序列，其中我们把标识出来，其余数字用“”表示。 在序列中每个ji后面用以竖线“|”标记，则设第1个竖线前面的数字个数为x1，第1个竖线与第2个竖线间的数

9、字个数为x2，第r个竖线后面的数字个数为xr+1。根据题意，因为 中任意两个数都彼此不相邻，所以满足：x11，x22，xr2，xr+10，因为一共有n个数字，所以x1+x2+x3+xr+xr+1=n。 等价于方程x1+x2+xr+xr+1=n满足条件x11，x22，xr2，xr+10的整数解个数。进行代换，令y1=x1-1，y2=x2-2，yr=xr-2，yr+1=xr+1，则y10，y20，yr0，yr+10，且y1+y2+yr+yr+1=n-1-2(r-1)。根据定理3.3.3的证明：这个方程的非负整数解个数是：因此满足条件不相邻条件的r-组合数为。 一般情况：间隔至少为k（k=2)例3.

10、3.6 从4个a，4个b，4个c，4个d中无序选取10个字母，如果每个字母至少包含两个，则有多少种取法解 这个问题实际上是求多重集的10-组合数，且10-组合中每个字母至少包含两个。 x1+x2+x3+x4=10，其满足条件x12，x22， x32，x42的整数解个数。 进行代换，令y1=x1-2， y2=x2-2， y3=x3-2， y4=x4-2， 则2 y10， 2 y20， 2 y30， 2 y40，且y1+y2+y3+y4=2。根据定理3.3.3，其非负整数解数为 ，因此共有10种取法。（全排列的那道题）3.4 二项式定理 3.4.1 和式3.4.2 二项式定理3.4.3 二项式定理

11、的推广3.4.4 组合恒等式3.4.5 非降路径问题在组合数学中求和是最基本的运算而表示法的引入给求和问题的表示和运算都带来了极大的便捷。例如，我们求1到n的正整数的和原来写成1+2+n，有了 表示法，就可以表示成3.4.1 和式 一般地，表示法的和式为 ，表示，读作“k从1到n对ak求和”。这种表示方法可以推广，即把难以表达或者复杂的k的取值范围写到下方。和式具有如下的性质 （1） ，其中c为与k无关的常量；（2） （3） 例3.4.1 求和 解 令因为0kn，所以0n-kn，根据性质3，根据性质2，将S的两个表达式相加，有：根据性质1因此例3.4.2 对于任意正整数n，给出 关于n的计算公

12、式。 方法1 我们观察图3.3.1中两个方阵，它们是完全相同的，我们采用不同的方式求和。12345n2345n345n45n5n n12345n2345n345n45n5n n对于图(a)，一列一列看，第1列1个1，第2列2个2，第n列n个n，如果按列求和，第1列为12，第2列为22，第n列n2，则所有数字的和恰好是对于图(b)，按行求和，第1行为 ，第2行为 ，第n行为 ，则所有数字的和恰好是因为图(a)和图(b)中的数字完全相同，所以首先设 方法2 首先设 推出 因此 3.4.2 二项式定理定理3.4.1 (二项式定理)设n是正整数,则对任意的x, y有：证明 用组合分析的方法证明。等式左

13、边是n个（x+y）因子相乘，即在展开时，每个因子中均可贡献一个x或一个y。由乘法共有2n项: 可以在n个x+y因子中选出k个，k xn-k y，因此二项式定理的几种特殊形式是我们已往熟悉的公式：（1）（2）（3） 基本性质（1）对称关系 （2）递推关系 （3）单峰性n为偶数时，有n为奇数时，有 性质（2）的证明 利用的组合意义来证。n元集合 的k元子集可以分成两类： 第一类k元子集含a1; 第二类k元子集不含a1(1)S- a1的k-1元子集: 一一对应关系. (2) S- a1的k元子集，共有性质（3）的证明 证明：设1kn，考虑 与 之比： 若n为偶数，则 为整数，于是（i）若k ，则 所

14、以（ii）若 ，则 所以推论3.4.1 设n是正整数，对一切x有推论3.4.2 对任何正整数n有推论3.4.3 对任何正整数n有推论3.4.3证明 证明1：在二项式定理中令x=-1, y=1,得(x+y) n=(-1+1) n=0 将上式整理一下即得原等式成立。推论3.4.3证明 方法2：n元集的偶子集数等于奇子集数任取S中的一个元素x对S的任何一个偶子集A，如果x属于A，则令B=A-x;如果x不属于A，则令B=Ax, B显然是S的奇子集 一一对应关系所以S的偶子集数与奇子集数相等定理3.4.2 (牛顿二项式定理) 设a是一个实数，则对一切x和y，满足有其中3.4.3 二项式定理的推广证明见高等数学的微积分是二项式定理的推广对于任何实数r和整数k，有牛顿二项式定理 例如 (