页数：88页文件大小：890.4 KB来源： 组合数学ppt课件
本课件承接集合计数，讨论含重复元素的多重集的排列与组合，给出多重集排列数、r组合数的计数公式与隔板法解释；随后系统展开二项式定理、牛顿二项式定理与多项式定理，列举常用组合恒等式，并把非降路径问题转化为组合计数模型求解。
§3.3多重集的排列与组合§3.3.1多重集的排列§3.3.2多重集的组合
多重集中可以有重复的元素。
多重集合表示为其中：互不相同M中有ki个ai（1≤i≤n），称ki为ai的重复度ki是正整数，也可以是∞，表示M中有无限多个ai
定理3.3.1多重集合的r-排列数是nr证明在构造M的一个r-排列时，排列中的第一个元素有n种选择，第二个元素也有n种选择，……，第r个元素也有n种选择。
由于M中的每个元素都是无限次地重复，所以r-排列中的任意一项都有n种选择，而且不依赖于前面各项的选择，故M的r-排列数为nr§3.3.1多重集的排列
这个问题对应的分配问题模型是：将r个有区别的球放入n个不同的盒子中，且每个盒子的球数不加以限制，而且同盒的球不分次序，则不同的放法为nr种若M中每个元素的重复度大于等于r，则结论仍然成立。
例3.3.1用26个英文字母可以构造出多少个包含2个元音字母（可以相同）且长度为8的“单词”解该问题是求的包含2个元音字母的8-排列数。
在长度为8的字符串中，2个元音字母出现的位置的选取方式有种，而每个元音位置可取5个元音字母中的一个，剩余6个辅音字母的位置可取21个辅音字母中的任一个，因而，满足题意的“单词”有·52·216个.
证明首先把M中所有的个元素看成是互不相同的，则全排列数为。
但ki个ai的位置相同，且其他元素排列也相同的排列实质上是同一个排列。
故M的全排列数为
例3.3.2使用英文字母表中26个字母构成8个字母的单词且允许字母重复，如果要求每个单词至少含有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个字母的序列，如果每个字母至少出现两次，有多少种方法形成这样的序列解这个问题实际上是求的10-排列数，但要求每个10排列中包含a,b,c,d每个字母至少两个。
我们设，则原问题可以分成如下两大类共10种情况：
多重集的排列问题小结：
证明1(1)M的任何一个r-组合都具有以下形式其中是非负整数，则有反之，若给出方程的非负整数解就是M的一个r-组合。
所以多重集M的r-组合数就等于方程的非负整数解的个数。
证明如下：为表达方便，将中n种不同元素用数字1,2,…,n替换，这样每个r-组合具有形式不妨设令，即则显然与一一对应，而是(n+r-1)元集合的r-组合，其数量为，从而原结论成立.
定理3.3.4设多重集r≥n，则M中每个元素至少取一个的r-组合数为证明设是满足条件的任一r-组合，则有令则显然其中的整数解个数等于方程的非负整数解的个数。
由定理3.3.3，满足定理条件的组合数为
例3.3.5求集合S={1,2,…,n}的r-组合数，其中要求r-组合中任意两个元素在S中都不是相邻的。
如当n=5，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个数按从小到大的顺序排成一个序列，其中我们只把标识出来，其余数字用“……”表示。
在序列中每个ji后面用以竖线“|”标记，则设第1个竖线前面的数字个数为x1，第1个竖线与第2个竖线间的数字个数为x2，…，第r个竖线前面的数字个数为xr+1。
根据题意，因为中任意两个数都彼此不相邻，所以满足：x1≥1，x2≥2，…，xr≥2，xr+1≥0，因为一共有n个数字，所以x1+x2+x3+…+xr+xr+1=n。
这样原问题要求的r-组合数就等价于方程x1+x2+…+xr+xr+1=n满足条件x1≥1，x2≥2，…，xr≥2，xr+1≥0的整数解个数。
进行代换，令y1=x1-1，y2=x2-2，…，yr=xr-2，yr+1=xr+1，则y1≥0，y2≥0，…，yr≥0，yr+1≥0，且y1+y2+…+yr+yr+1=n-1-2(r-1)。
根据定理3.3.3的证明：这个方程的非负整数解个数是：因此满足条件不相邻条件的r-组合数为。
例3.3.6从4个a，4个b，4个c，4个d中无序选取10个字母，如果每个字母至少包含两个，则有多少种取法解这个问题实际上是求多重集的10-组合数，且10-组合中每个字母至少包含两个。
显然，这个问题等价于方程x1+x2+x3+x4=10，其满足条件x1≥2，x2≥2，x3≥2，x4≥2的整数解个数。
进行代换，令y1=x1-2，y2=x2-2，y3=x3-2，y4=x4-2，则y1≥0，y2≥0，y3≥0，y4≥0，且y1+y2+y3+y4=2。
根据定理3.3.3，其非负整数解数为，因此共有10种取法。
多重集的组合问题小结：思考：设s={3.a,4.b,5.c,6.d}，求从中分别取得3个、4个和5个元素的组合数。
例将6个蓝色球，5个红色球，3个白色球排成一排，要求白色球不挨着，问有多少种排列方式？
§3.4二项式定理§3.4.1和式§3.4.2二项式定理§3.4.3二项式定理的推广§3.4.4组合恒等式§3.4.5非降路径问题
和式具有如下的性质（1），其中c为与k无关的常量；
（2）（3）
例3.4.1求和解令因为0≤k≤n，所以0≤n-k≤n，根据性质3，根据性质2，将S的两个表达式相加，有：根据性质1因此
例3.4.2对于任意正整数n，给出关于n的计算公式。
方法1我们观察图3.3.1中两个方阵，它们是完全相同的，我们采用不同的方式求和。
n…54321n…5432n…543n…54n…5……nn…54321n…5432n…543n…54n…5……n
对于图(a)，一列一列看，第1列1个1，第2列2个2，…，第n列n个n，如果按列求和，第1列为12，第2列为22，…，第n列n2，则所有数字的和恰好是对于图(b)，按行求和，第1行为，第2行为，…，第n行为，则所有数字的和恰好是因为图(a)和图(b)中的数字完全相同，所以
对于图(a)（续）：首先设
方法2首先设推出因此
§3.4二项式定理§3.4.1和式§3.4.2二项式定理§3.4.3二项式定理的推广§3.4.4组合恒等式§3.4.5非降路径问题
§3.4.2二项式定理定理3.4.1 (二项式定理)设n是正整数,则对任意的x,y有：
二项式系数
二项式系数的基本性质（1）对称关系（2）递推关系（3）单峰性n为偶数时，有n为奇数时，有
性质2又叫Pascal公式,可得杨辉三角
性质（3）的证明证明：设1≤k≤n，考虑与之比：若n为偶数，则为整数，于是（i）若k≤，则所以（ii）若，则所以
定理3.4.1 (二项式定理)设n是正整数,则对任意的x,y有：
证明用组合分析的方法证明。
等式左边是n个（x+y）因子相乘，即这些因子展开到没有括号为止。
在展开时，每个因子中均可贡献一个x或一个y。
由乘法原理，共有2n项，这些项都可写成的形式。
可以在n个x+y因子中选出k个，从这k个因子中取x，而在另外的n-k个因子中取y，如此得到项，所以的系数等于n个因子的k-组合数，即。
因此
二项式定理的几种特殊形式（1）（2）（3）
推论3.4.1设n是正整数，对一切x有推论3.4.2对任何正整数n有推论3.4.3对任何正整数n有
推论3.4.3证明在二项式定理中令x=-1,y=1,得将上式整理一下即得原等式成立。
§3.4.3二项式定理的推广(1)牛顿二项式定理(2)多项式定理
(1)牛顿二项式定理定义对于任何实数a和整数k，有
定理3.4.2 (牛顿二项式定理)设a是一个实数，则对一切x和y，满足有其中
1,当a=n(正整数)时，如果k＞n，则这时牛顿二项式定理就变成下面的形式这就是二项式定理，所以二项式定理是牛顿二项式定理的特例
2,当a=-n(负整数)时，有3,当a=-1时，有4,当a=1/2时，有
定理3.4.3 (多项式定理)设n是正整数，则其中称为多项式系数，并且是对所有满足n1+n2+…nt=n的非负整数解n1,n2,…,nt求和。
(2)多项式定理
证明(1)先将(x1+…+xt)n写成n个(x1+…+xt)因子的乘积：将其展开，直到没有括号为止。
因为每个因子中都可取x1, x2, …,xt中的任一个，所以展开式共有tn项，且每项都可以写成的形式.要得到这一项，我们应该在n个因子中的n1个里面取x1，有种取法；
在剩下的n-n1个因子中的n2个里面取x2，有种取法；
……；
最后，在个因子里面取xt，有种取法.由乘法原理知，前的系数为
在多项式定理中如果取t＝2，就得到普通的二项式定理.多项式系数组合意义如下：是多项式(x1+…+xt)n中项的系数。
是多重集S={n1.a1,n2.a2,…,nt.at}的排列数如果我们把n个不同的球放到t个不同的盒子里,并且使得第一个盒子里有n1个球，第二个盒子里有n2个球,…,第t个盒子里有nt个球，那么放球的方案数是
例3.4.3展开的系数为
例求(2x1-3x2+5x3)6中项的系数解:
推论3.4.4(x1+…+xt)n的展开式在合并同类项以后不同的数目是证明(x1+…+xt)n的展开式中任何一项对应于方程n1+n2+…nt=n的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数
推论3.4.5其中求和是对方程n1+n2+…nt=n的一切非负整数解来求。
证明:在多项式定理中令x1=x2=…=xt=1即可.
§3.4.4组合恒等式证明对等式两边微分得然后令x=1得等式成立
证明对等式两边积分得
然后令x=-1得成立即
证明采用组合分析的方法．等式右端是n+1元集合S={a1,a2,…,an+1}的k+1元子集的个数，这些子集可以分成如下n+1类：第(0)类：k+1元子集中含a1，这相当于S-{a1}的k元子集再加上a1构成S的k+1元子集，共个
第(1)类：不含a1但含a2的k+1元子集，共有个……；
第(n)类：不含a1,a2,…, an但含an+1的k+1元子集，共有个.由加法原理知所以等式成立
而第i类子集的个数为由加法原理，有即原等式成立。
证明此恒等式是恒等式（4）的推广，被称为Vandermonde恒等式.由二项式定理有
比较等式两边xr的系数，左边是右边是
证明方法1：由二项式定理有对上式两边对x微分得等式两边乘以x得
等式两边对x微分得：令x=1则：即：
方法2：
本页源文件未提取到正文文字，仅有图片。该页位于「等式两边对x微分（续）」与「非降路径问题」之间，建议对照原课件图片补充本页要点说明。
(0,0)(5,6)yx
本页为数字或符号粘连序列（幻方、拉丁方等方阵图或公式提取结果），源文本无法安全切分，需对照原课件图片人工核对还原。
解先考虑对角线下方的路径．这种路径都是从(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)点的除端点外不接触直线y＝x的非降路径数．
对其中任意一条接触对角线的路径，我们可以把它从最后离开对角线的点(图中的A点)到(1,0)点之间的部分关于对角线作一个反射，就得到一条从(0,2)点出发经过A点到达(n,n-1)点的非降路径．反之，任何一条从(0,1)点出发（必穿过）直线y=x而到达(n,n-1)点的非降路径，也可以通过这样的对称变换得到一条从(1,0)点出发接触到对角线而到达(n,n-1)点的非降路径．
从而在直线y=x下方不接触直线y=x的路径数是由对称性可知，所求的路径数是从(0,1)点到达(n,n-1)点的非降路径数是
(0,0)yx(0,1)(1,0)(n,n)A
本页为数字或符号粘连序列（幻方、拉丁方等方阵图或公式提取结果），源文本无法安全切分，需对照原课件图片人工核对还原。
解首先考虑直线y=x下不穿过直线y=x的路径，这种路径都是(1,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)点的除端点外不穿过直线的非降路径数
例3.4.8一场演唱会门票为50元一张，排队买票的歌迷中有m个人手持50元纸币，n个人手持100元纸币。
若售票处没有准备零钱，求有多少种排队方法能使购票顺利进行，而不出现找不出钱的状态。
假定每个人只能购票1张，而且m>n.
解根据题意，要满足总是能找出零钱，就意味着对于队列中每个歌迷而言，她前面的人（包括她在内）中持50元的人不少于持100元的人。
显然是求从（0，0）到（m,n）不穿过直线y=x且在y=x下方的非降路径数，根据例3.4.7，为(1,0 )点到(m,n)点非降路径数—(-1,2 )点到(m,n)点非降路径数，即：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}