组合数学ch032学习.pptx

《组合数学ch032学习.pptx》由会员分享，可在线阅读，更多相关《组合数学ch032学习.pptx（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、题对应的分配问题模型是：将r个有区别的球放入n个不同的盒子中，且每个盒子的球数不加以限制，而且同盒的球不分次序，则不同的放法为nr种 若M中每个元素的重复度大于等于r，则结论仍然成立。第4页/共88页例3.3.1 用26个英文字母可以构造出多少个包含2个元音字母（可以相同）且长度为8的“单词”解 该问题是求 的包含2个元音字母的8-排列数。在长度为8的字符串中，2个元音字母出现的位置的选取方式有 种，而每个元音位置可取5个元音字母中的一个，剩余6个辅音字母的位置可取21个辅音字母中的任一个，因而，满足题意的“单词”有 52216个.第5页/共88页 证明 首先把M中所有的个元素看成是互不相同的

3、，则全排列数为 。但ki个ai的位置相同，且其他元素排列也相同的排列实质上是同一个排列。故M的全排列数为 第6页/共88页例3.3.2使用英文字母表中26个字母构成8个字母的单词且允许字母重复，如果要求每个单词至少含有3个元音字母，那么能构成多少个这样单词解 因为一共有5个元音字母，每个单词至少含有3个元音字母即包含3个，4个或者5个元音字母。则分三种情况，有3个元音字母的单词有有4个元音字母的单词有有5个元音字母的单词有根据加法原理共第7页/共88页例3.3.3 求多重集 的8-排列数解 可分三种情况计算：M-a的8-排列数,即为 排列数 为：M-b的8-排列数,即为 排列数 为：M-c的8

4、-排列数,即为 排列数 为：多重集M的8-排列数为 420+280+560=1260 第8页/共88页例3.3.4 从4个a，4个b，4个c，4个d中选择字母形成一个10个字母的序列，如果每个字母至少出现两次，有多少种方法形成这样的序列 解 这个问题实际上是求 的10-排列数，但要求每个10排列中包含a,b,c,d每个字母至少两个。我们设，则原问题可以分成如下两大类共10种情况：第9页/共88页（一）的10-排列数;的10-排列数；的10-排列数：的10-排列数，这4种类情况的10-排列数相等，均为（二）的10-排列数;的10-排列数；的10-排列数：的10-排列数；10-排列数；的10-排列

5、数这6种类情况的10-排列数相等，均为满足条件的方法数为 第10页/共88页 多重集的排列问题小结：第11页/共88页3.3.2 多重集的组合 多重集合的r-组合是指从M中无序地选出r个元素例子 如果多重集M有n个元素(包括重复的元素)，则M的n-组合只有一个，就是M本身。如果M有n种不同元素，则M的1-组合恰有n个。第12页/共88页 证明1 (1)M的任何一个r-组合都具有以下形式其中 是非负整数，则有反之，若给出方程的非负整数解 就是M的一个r-组合。所以多重集M的r-组合数就等于方程的非负整数解的个数。第13页/共88页（2）方程 的一个非负整数解可以表示为(n-1)0,r1的一个全排

6、列，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，依此类推，最后一个0右边的1的个数为xn，则 是一组非负整数解。第14页/共88页 因此 的非负整数解与集合的全排列之间是一一对应。由(1)(2)知，M的r-组合数等于的全排列数，根据定理3.3.2，多重集M的r组合数为 方法2 分析定理的结论，是(n+r-1)元普通集合的r-组合数，因此我们想办法构造多重集合 的r-组合与某一(n+r-1)元的普通集合S的

7、r组合之间的一一对应，从而证明定理的结论.第15页/共88页证明如下：为表达方便，将中n种不同元素用数字1,2,n替换，这样每个r-组合具有形式 不妨设令 ，即则显然 与 一一对应，而 是(n+r-1)元集合的r-组合，其数量为 ，从而原结论成立.第16页/共88页定理3.3.4 设多重集rn，则M中每个元素至少取一个的r-组合数为证明 设 是满足条件的任一r-组合，则有令 则显然 其中的整数解个数等于方程 的非负整数解的个数。由定理3.3.3，满足定理条件的组合数为第17页/共88页例3.3.5 求集合S=1,2,n的r-组合数，其中要求r-组合中任意两个元素在S中都不是相邻的。如当n=5，

8、r=3时，S=1,2,3,4,5,6，1,3,5是满足条件的3-组合，而1,2,6是不满足条件的3-组合，因为1,2在S中是相邻的。解 考虑S的任意一个r-组合 ，不妨设 我们把1,2,n这n个数按从小到大的顺序排成一个序列，其中我们只把标识出来，其余数字用“”表示。第18页/共88页在序列中每个ji后面用以竖线“|”标记，则设第1个竖线前面的数字个数为x1，第1个竖线与第2个竖线间的数字个数为x2，第r个竖线前面的数字个数为xr+1。根据题意，因为 中任意两个数都彼此不相邻，所以满足：x11，x22，xr2，xr+10，因为一共有n个数字，所以x1+x2+x3+xr+xr+1=n。第19页/

9、共88页这样原问题要求的r-组合数就等价于方程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-组合数为。第20页/共88页例3.3.6 从4个a，4个b，4个c，4个d中无序选取10个字母，如果每个字母至少包含两个，则有多少种取法解 这个问题实际上是求多重集的10-组合数，且10-组合中每个字母至少包含

10、两个。显然，这个问题等价于方程x1+x2+x3+x4=10，其满足条件x12，x22，x32，x42的整数解个数。进行代换，令y1=x1-2，y2=x2-2，y3=x3-2，y4=x4-2，则y10，y20，y30，y40，且y1+y2+y3+y4=2。根据定理3.3.3，其非负整数解数为 ，因此共有10种取法。第21页/共88页 多重集的组合问题小结：思考：设s=3.a,4.b,5.c,6.d，求从中分别取得3个、4个和5个元素的组合数。第22页/共88页例 将6个蓝色球，5个红色球，3个白色球排成一排，要求白色球不挨着，问有多少种排列方式？第23页/共88页3.4 二项式定理 3.4.1

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

12、，将S的两个表达式相加，有：根据性质1因此第27页/共88页例3.4.2 对于任意正整数n，给出 关于n的计算公式。方法1 我们观察图3.3.1中两个方阵，它们是完全相同的，我们采用不同的方式求和。12345 n2345 n345 n45 n5 n n12345 n2345 n345 n45 n5 n n第28页/共88页对于图(a)，一列一列看，第1列1个1，第2列2个2，第n列n个n，如果按列求和，第1列为12，第2列为22，第n列n2，则所有数字的和恰好是对于图(b)，按行求和，第1行为 ，第2行为 ，第n行为 ，则所有数字的和恰好是因为图(a)和图(b)中的数字完全相同，所以第29页/

13、共88页首先设 第30页/共88页方法2 首先设 推出 因此 第31页/共88页3.4 二项式定理 3.4.1 和式3.4.2 二项式定理3.4.3 二项式定理的推广3.4.4 组合恒等式3.4.5 非降路径问题第32页/共88页3.4.2 二项式定理定理3.4.1 (二项式定理)设n是正整数,则对任意的x,y有：第33页/共88页 二项式系数第34页/共88页二项式系数的基本性质（1）对称关系 （2）递推关系 （3）单峰性n为偶数时，有n为奇数时，有 第35页/共88页性质（2）的证明 利用的组合意义来证。n元集合 的k元子集可以分成两类：第一类k元子集含a1;第二类k元子集不含a1第一类k

14、元子集中的任一个去掉a1后，就是S-a1的k-1元子集；反过来，任给一个的k-1元子集，添上a1后就是S的k元子集，故二者这间有一一对应关系.因而，第一类k元子集共有 个.第二类k元子集就是S-a1的k元子集，共有 个.所以第36页/共88页 性质2又叫Pascal公式,可得杨辉三角第37页/共88页性质（3）的证明 证明：设1kn，考虑 与 之比：若n为偶数，则 为整数，于是（i）若k ，则 所以（ii）若 ，则 所以第38页/共88页定理3.4.1 (二项式定理)设n是正整数,则对任意的x,y有：第39页/共88页证明 用组合分析的方法证明。等式左边是n个（x+y）因子相乘，即这些因子展开

15、到没有括号为止。在展开时，每个因子中均可贡献一个x或一个y。由乘法原理，共有2n项，这些项都可写成 的形式。可以在n个x+y因子中选出k个，从这k个因子中取x，而在另外的n-k个因子中取y，如此得到项，所以的系数等于n个因子的k-组合数，即 。因此第40页/共88页二项式定理的几种特殊形式（1）（2）（3）第41页/共88页推论3.4.1 设n是正整数，对一切x有推论3.4.2 对任何正整数n有推论3.4.3 对任何正整数n有第42页/共88页推论3.4.3证明 在二项式定理中令x=-1,y=1,得 将上式整理一下即得原等式成立。第43页/共88页3.4.3 二项式定理的推广(1)牛顿二项式定

16、理(2)多项式定理第44页/共88页(1)牛顿二项式定理v 定义 对于任何实数a和整数k，有第45页/共88页定理3.4.2 (牛顿二项式定理)设a是一个实数，则对一切x和y，满足有其中第46页/共88页 1,当a=n(正整数)时，如果kn，则这时牛顿二项式定理就变成下面的形式这就是二项式定理，所以二项式定理是牛顿二项式定理的特例第47页/共88页 2,当a=-n(负整数)时，有3,当a=-1时，有4,当a=1/2时，有第48页/共88页v 定理3.4.3 (多项式定理)设n是正整数，则其中称为多项式系数，并且是对所有满足n1+n2+nt=n 的非负整数解 n1,n2,nt求和。(2)多项式定

17、理第49页/共88页 证明 (1)先将(x1+xt)n写成n个(x1+xt)因子的乘积：将其展开，直到没有括号为止。因为每个因子中都可取x1,x2,xt中的任一个，所以展开式共有tn项，且每项都可以写成 的形式.要得到这一项，我们应该在n个因子中的n1个里面取x1，有 种取法；在剩下的n-n1个因子中的n2个里面取x2，有 种取法；第50页/共88页最后，在个因子里面取xt，有种取法.由乘法原理知，前的系数为第51页/共88页v 在多项式定理中如果取t2，就得到普通的二项式定理.v 多项式系数组合意义如下：是多项式(x1+xt)n中项的系数。第52页/共88页v 是多重集S=n1.a1,n2.

18、a2,nt.at的排列数v 如果我们把n个不同的球放到t个不同的盒子里,并且使得第一个盒子里有n1个球，第二个盒子里有n2个球,第t个盒子里有nt个球，那么放球的方案数是第53页/共88页例3.4.3 展开的系数为 第54页/共88页 例 求(2x1-3x2+5x3)6中 项的系数解:第55页/共88页 推论3.4.4 (x1+xt)n的展开式在合并同类项以后不同的数目是 证明(x1+xt)n的展开式中任何一项对应于方程 n1+n2+nt=n的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数第56页/共88页 推论3.4.5其中求和是对方程n1+n2+nt=n 的一切非

19、负整数解来求。证明:在多项式定理中令x1=x2=xt=1即可.第57页/共88页3.4.4 组合恒等式证明 对等式两边微分得然后令x=1得等式成立第58页/共88页证明 对等式两边积分得第59页/共88页然后令x=-1得成立即第60页/共88页 证明 采用组合分析的方法等式右端 是n+1元集合S=a1,a2,an+1的k+1元子集的个数，这些子集可以分成如下n+1类：第(0)类：k+1元子集中含 a1，这相当于S-a1 的k元子集再加上 a1构成S的k+1元子集，共 个第61页/共88页第(1)类：不含a1但含a2的k+1元子集，共有 个；第(n)类：不含a1,a2,an但含an+1的k+1元

20、子集，共有 个.由加法原理知所以等式成立第62页/共88页证明 采用组合分析的方法。是2n元集合S的n-组合数，把集合S分成两个集合S1和S2，使 ，则S的n元子集可以分成如下n+1类：从S1中选取i（0in）个元素，从S2中选取n-i个元素，将S1的i个元素与S2的n-i个元素并到一起构成S的第i类n元子集。第63页/共88页而第i类子集的个数为 由加法原理，有 即原等式成立。第64页/共88页证明此恒等式是恒等式（4）的推广，被称为Vandermonde恒等式.由二项式定理有第65页/共88页比较等式两边xr的系数，左边是右边是第66页/共88页证明 方法1：由二项式定理有对上式两边对x微

21、分得等式两边乘以x得第67页/共88页等式两边对x微分得：令x=1则：即：第68页/共88页方法2：第69页/共88页第70页/共88页3.4.5 非降路径问题一条非降路径，规定水平向右走一个单元格用x表示垂直向上走一个单元格用y表示第71页/共88页(0,0)(5,6)yx第72页/共88页一条从（0，0）点到（m,n）点的非降路径就是多重集mx，ny的一个排列。反之，给定多重集mx，ny的一个排列就唯一地确定了一条从（0，0）点到（m,n）点的非降路径。第73页/共88页 所以从（0，0）点到（m,n）点的非降路径数等于mx，ny的排列数，即二项式系数 或 下面用非降路径的思想证明组合恒等

22、式由此可见非降路径实质上是二项式系数的一种几何解释。第74页/共88页例3.4.4 证明：证明：是从(0,0)点到(m,n)点的非降路径数。这些路径可以分成两类：第75页/共88页 一类由（0,0）点经由（m-1,n）点到达（m,n）点，共有 条；另一类经由（m,n-1）点到达（m,n）点，共有 条，根据加法原理，等式成立。第76页/共88页例3.4.5 证明证明:等式右端表示从(0,0)点到(m+n-r,r)点的非降路径数。任何一条这样的非降路径一定经过图中斜线上的点，按所经过点的不同将路径分类。第77页/共88页 从(0,0)点到(m-k,k)点的非降路径是 条从(m-k,k)点到(m+n

23、-r,r)非降路径是 条由乘法原理，可知从(0,0)点经过(m-k,k)点的非降路径是 条再对k=0,1,r求和就得到所有的从(0,0)点到(m+n-r,r)点的非降路径数所以等式成立第78页/共88页解 先考虑对角线下方的路径这种路径都是从(0,0)点出发经过(1,0)点及(n,n-1)点到达(n,n)点的我们可以把它看作是从(1,0)点出发到达(n,n-1)点的不接触对角线的非降路径。从(1,0)点到(n,n-1)点的所有的非降路径数是 例3.4.6 求从(0,0)点到(n,n)点的除端点外不接触直线yx的非降路径数第79页/共88页对其中任意一条接触对角线的路径，我们可以把它从最后离开对

24、角线的点(图中的A点)到(1,0)点之间的部分关于对角线作一个反射，就得到一条从(0,2)点出发经过A点到达(n,n-1)点的非降路径反之，任何一条从(0,1)点出发（必穿过）直线y=x而到达(n,n-1)点的非降路径，也可以通过这样的对称变换得到一条从(1,0)点出发接触到对角线而到达(n,n-1)点的非降路径第80页/共88页从而在直线y=x下方不接触直线y=x的路径数是由对称性可知，所求的路径数是从(0,1)点到达(n,n-1)点的非降路径数是第81页/共88页(0,0)yx(0,1)(1,0)(n,n)A第82页/共88页解 首先考虑直线y=x下不穿过直线y=x的路径，这种路径都是(1

25、,0)经过(n,n-1)点到达(n,n)点的，其路径数为 根据非降路径的定义，任意一条从(1,0)点并经过(n,n-1)点到达(n,n)点的穿过直线y=x的非降路径都对应接触直线y=x+1的非降路径。例3.4.7 求从(0,0)点到(n,n)点的除端点外不穿过直线 的非降路径数第83页/共88页 设从(1,0)点到(n,n-1)点接触直线y=x+1的非降路径最后一次离开直线y=x+1的点为B，将(1,0)点和B点之间的部分关于直线y=x+1作对称图形，则得到从 (-1,2)点到达(n,n-1)点的穿过直线y=x+1的非降路径。反之，任何一条从(-1,2)点出发穿过直线y=x+1而到达(n,n-

26、1)点的非降路径，也可以通过这样的对称变换得到一条从(1,0)点出发接触直线y=x+1而到达(n,n-1)点的非降路径第84页/共88页 路径数为 由对称性可知，所求的路径数是B第85页/共88页例3.4.8 一场演唱会门票为50元一张，排队买票的歌迷中有m个人手持50元纸币，n个人手持100元纸币。若售票处没有准备零钱，求有多少种排队方法能使购票顺利进行，而不出现找不出钱的状态。假定每个人只能购票1张，而且mn.第86页/共88页解 根据题意，要满足总是能找出零钱，就意味着对于队列中每个歌迷而言，她前面的人（包括她在内）中持50元的人不少于持100元的人。显然是求从（0，0）到（m,n）不穿过直线y=x且在y=x下方的非降路径数，根据例3.4.7，为(1,0)点到(m,n)点非降路径数(-1,2)点到(m,n)点非降路径数，即：第87页/共88页感谢您的观看！第88页/共88页