组合数学ch032学习教案

1、会计学1组合组合(zh)数学数学ch032第一页，共88页。,.,2211nnakakakM 多重集合(jh)表示为naaa,21其中(qzhng)： 互不相同 M中有ki个ai（1in）， 称ki为ai的重复度的重复度 ki是正整数，也可以是，表示M中有无限多个ai 第1页/共88页第二页，共88页。例子例子(l zi)ddddccbaaaM, 是一个是一个10个元素个元素(yun s)的多重集合，的多重集合， 其中有其中有3个个a，1个个b，2个个c，4个个d. dcbaM4 ,5 ,2 ,3 M表示表示(biosh)为为 第2页/共88页第三页，共88页。 定理(dngl)3.3.1 多

2、重集合 的r-排列数是nr 证明证明 在构造在构造M的一个的一个r-排列时，排列时，排列中的第一个元素有排列中的第一个元素有n种选择，种选择，第二个元素也有第二个元素也有n种选择，种选择，第第r个元素也有个元素也有n种选择。种选择。由于由于M中的每个元素都是无限中的每个元素都是无限(wxin)次地重复，所以次地重复，所以r-排列中的任意一项都有排列中的任意一项都有n种选种选择，而且不依赖于前面各项的选择，故择，而且不依赖于前面各项的选择，故M的的r-排列数为排列数为nr ,.,21naaaM3.3.1 多重集的排列多重集的排列(pili)第3页/共88页第四页，共88页。 若M中每个元素的重复

3、度大于等于r，则结论(jiln)仍然成立。 第4页/共88页第五页，共88页。例例3.3.1 用用26个英文字母可以构造出多个英文字母可以构造出多少个包含少个包含(bohn)2个元音字母（可以个元音字母（可以相同）且长度为相同）且长度为8的的“单词单词”28zbaM,解解 该问题是求该问题是求 的包含的包含2个元音字母的个元音字母的8-排列数。在长度为排列数。在长度为8的字符串中，的字符串中，2个元音字母出现的位置的选个元音字母出现的位置的选取方式取方式(fngsh)有有 种，而每个元音位置种，而每个元音位置可取可取5个元音字母中的一个，剩余个元音字母中的一个，剩余6个辅音字个辅音字母的位置可

4、取母的位置可取21个辅音字母中的任一个，因个辅音字母中的任一个，因而，满足题意的而，满足题意的“单词单词”有有 52216个个. 28第5页/共88页第六页，共88页。!.!k!.k ,., 2 . 3 . 321212211nnnnkkkkakakakM）（的全排列数为多重集定理 证明证明 首先把首先把M中所有的中所有的个元素看成个元素看成(kn chn)是互不相同的，则全是互不相同的，则全排列数为排列数为 。但。但ki个个ai的位置的位置相同，且其他元素排列也相同的排列实质上相同，且其他元素排列也相同的排列实质上是同一个排列。是同一个排列。故故M的全排列数为的全排列数为 nkkk21! 2

5、1nkkk!.!k!.k2121nnkkkk）（第6页/共88页第七页，共88页。解解 因为一共有因为一共有5个元音个元音(yunyn)字母，每字母，每个单词至少含有个单词至少含有3个元音个元音(yunyn)字母即包字母即包含含3个，个，4个或者个或者5个元音个元音(yunyn)字母。字母。则分三种情况，则分三种情况，有有3个元音个元音(yunyn)字母的单词有字母的单词有有有4个元音个元音(yunyn)字母的单词有字母的单词有有有5个元音个元音(yunyn)字母的单词有字母的单词有根据加法原理共根据加法原理共532153844215483521558354454215582154821538

6、第7页/共88页第八页，共88页。解解 可分三种可分三种(sn zhn)情况计算：情况计算： M-a的的8-排列数排列数, 即为即为 排列数排列数 为：为： M-b的的8-排列数排列数,即为即为 排列数排列数 为：为： M-c的的8-排列数排列数,即为即为 排列数排列数 为：为： 多重集多重集M的的8-排列数为排列数为 420+280+560=1260 cbaM4 ,2 ,3cba4 ,2 ,2420! 4 ! 2 ! 2! 8cba4 ,1 ,3280! 4 ! 1 ! 3! 8cba3 ,2 ,3560!13! 2 ! 3! 8第8页/共88页第九页，共88页。解解 这个这个(zh ge)

7、问题实际上是求问题实际上是求 的的10-排列数，但要求每个排列数，但要求每个10排列中包含排列中包含a,b,c,d每个字母至少两个。每个字母至少两个。我们设我们设 ，则原问题可以分成如下两大类共，则原问题可以分成如下两大类共10种情况种情况：dcbaM4 ,4 ,4 ,4dcbaM2 ,2 ,2 ,2*第9页/共88页第十页，共88页。（一）（一） 的的10-排列排列(pili)数数; 的的10-排列排列(pili)数；数； 的的10-排列排列(pili)数：数：的的10-排列排列(pili)数，数，这这4种类情况的种类情况的10-排列排列(pili)数相等，均为数相等，均为2*aM2*bM2

8、*cM2*dM! 4 ! 2 ! 2 ! 2!10（二）（二） 的的10-排列排列(pili)数数; 的的10-排列排列(pili)数；数； 的的10-排列排列(pili)数：数：的的10-排列排列(pili)数；数； 10-排列排列(pili)数；数； 的的10-排列排列(pili)数数这这6种类情况的种类情况的10-排列排列(pili)数相等，均数相等，均为为,*baM ,*caM ,*daM ,*cbM !13!13! 2 ! 2!10,*dbM ,*dcM 满足条件的方法满足条件的方法(fngf)数为数为 226800! 3 ! 3 ! 2 ! 2!106! 4 ! 2 ! 2 ! 2

9、!104第10页/共88页第十一页，共88页。 多重集的排列问题多重集的排列问题(wnt)小结：小结：第11页/共88页第十二页，共88页。 多重集合的r-组合(zh)是指从M中无序地选出r个元素例子例子(l zi)cc,c,b,c,a,b,b,b,a,a,a, 62,2,2,2 个：组合有的 McbaM 如果多重集M有n个元素(包括重复的元素)，则M的n-组合只有一个，就是M本身。 如果M有n种不同元素，则M的1-组合恰有n个。第12页/共88页第十三页，共88页。), 1( ,., 3 . 3 . 321rrnCraaaMn组合数是的，多重集定理,2211nnaxaxaxnxxx,21 证

10、明证明1 (1) M的任何一个的任何一个r-组合都具有以下形式组合都具有以下形式其中其中 是非是非(shfi)负整数，则有负整数，则有反之，若给出方程反之，若给出方程的非负整数解的非负整数解 就是就是M的一个的一个r-组合。组合。所以多重集所以多重集M的的r-组合数就等于方程组合数就等于方程的非负整数解的个数。的非负整数解的个数。rxxxn21rxxxn21nxxx,21rxxxk21nnaxaxax,1211第13页/共88页第十四页，共88页。（2）方程）方程 的一个非负整数解可以的一个非负整数解可以表示为表示为(n-1)0, r1的一个全排列，的一个全排列， 1 1 1 1 0 1 1

11、10 01 1 1 01111， x1个个 x2个个 xn个个反之反之(n-1)0, r1的一个全排列，在这个排列中的一个全排列，在这个排列中n-1个个0把个把个1分成个组。分成个组。 从左边从左边(zu bian)数，第一个数，第一个0左边左边(zu bian)的的1的个数为的个数为x1，第一个，第一个0和第二个和第二个0之间的之间的1的个数的个数为为x2 ，依此类推，最后一个，依此类推，最后一个0右边的右边的1的个数为的个数为xn ，则，则 是一组非负整数解。是一组非负整数解。 rxxxn21nxxx,21第14页/共88页第十五页，共88页。 因此因此 的非负整数解与集的非负整数解与集合

12、合(jh)的全排列之间是一一对应。的全排列之间是一一对应。rxxxn21 由由(1)(2)知，知，M的的r-组合数等于组合数等于(dngy)的全排列数，根据定理的全排列数，根据定理3.3.2，多重集，多重集M的的r组组合数为合数为 1, 0) 1(rnrrn1方法方法2 分析定理的结论，分析定理的结论， 是是(n+r-1)元普通元普通集合的集合的r-组合数，因此我们想办法组合数，因此我们想办法(bnf)构造构造多重集合多重集合 的的r-组合与某一组合与某一(n+r-1)元的普通集合元的普通集合S的的r组合之间的一一对应组合之间的一一对应，从而证明定理的结论，从而证明定理的结论. rrn1,.,

13、21naaaM第15页/共88页第十六页，共88页。. ,.,21naaaM,21rjjjnjjjr211) 1( ijkii) 1(,.,1,2211rjkjkjkrr11321rnkkkkr,21rjjj, ,21rkkk, ,21rkkkrrn1第16页/共88页第十七页，共88页。定理3.3.4 设多重集rn，则M中每个元素(yun s)至少取一个的r-组合数为,.,21naaaM11nr证明证明 设设 是满足条件的任一是满足条件的任一r-组合，则有组合，则有令令 则则显然显然 其中的整数解个数等于方程其中的整数解个数等于方程 的非负整数解的个数。由定理的非负整数解的个数。由定理(dn

14、gl)3.3.3，满足定理满足定理(dngl)条件的组合数为条件的组合数为nnaxaxax,2211,21rxxxn)., 2 , 1( 1nixi),1 ( 1nixyii,21nryyyn)., 2 , 1(0niyi,21rxxxnnryyyn21.11) 1()(1)(nrnrnnrnrnrn第17页/共88页第十八页，共88页。例例3.3.5 求集合求集合S=1,2,n的的r-组合数，组合数，其中要求其中要求r-组合中任意组合中任意(rny)两个元素在两个元素在S中都不是相邻的。中都不是相邻的。 如当如当n=5，r=3时，时，S=1,2,3,4,5,6，1,3,5是是满足条件的满足条

15、件的3-组合组合(zh)，而，而1,2,6是不满足是不满足条件的条件的3-组合组合(zh)，因为，因为1,2在在S中是相邻的中是相邻的。解解 考虑考虑S的任意一个的任意一个r-组合组合 ，不妨设不妨设 我们把我们把1,2,n这这n个数按从小到大的顺序排成一个序列，个数按从小到大的顺序排成一个序列，其中我们只把标识出来其中我们只把标识出来(ch li)，其余数字，其余数字用用“”表示。表示。 ,21rjjjnjjjr211第18页/共88页第十九页，共88页。在序列中每个在序列中每个ji后面用以竖线后面用以竖线“|”标记，则标记，则设第设第1个竖线前面的数字个数为个竖线前面的数字个数为x1，第，

16、第1个竖个竖线与第线与第2个竖线间的数字个数为个竖线间的数字个数为x2，第，第r个竖线前面的数字个数为个竖线前面的数字个数为xr+1。根据根据(gnj)题意，因为题意，因为 中任意两中任意两个数都彼此不相邻，所以满足：个数都彼此不相邻，所以满足：x11，x22，xr2，xr+10，因为一共有因为一共有n个数字，所以个数字，所以x1+x2+x3+xr+xr+1=n。 |321rjjjj,21rjjj第19页/共88页第二十页，共88页。rrnrnrnrnrnr1121) 1(211)1(21) 1(rrn1第20页/共88页第二十一页，共88页。例例3.3.6 从从4个个a，4个个b，4个个c，

17、4个个d中无序中无序选取选取10个字母，如果每个字母至少包含两个字母，如果每个字母至少包含两个，则有多少个，则有多少(dusho)种取法种取法解解 这个问题实际上是求多重集的这个问题实际上是求多重集的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+y

18、4=2。根据。根据(gnj)定理定理3.3.3，其非，其非负整数解数为负整数解数为 ，因此共有，因此共有10种取法。种取法。102124第21页/共88页第二十二页，共88页。 多重集的组合多重集的组合(zh)问问题小结：题小结：思考：设思考：设s=3.a,4.b,5.c,6.d，求从中分别取得求从中分别取得3个、个、4个和个和5个元素个元素(yun s)的的组合数。组合数。第22页/共88页第二十三页，共88页。第23页/共88页第二十四页，共88页。第24页/共88页第二十五页，共88页。3.4.1 和式和式nkk1 一般地，表示法的和式为 ，表示，读作“k从1到n对ak求和”。这种表示方

19、法可以(ky)推广，即把难以表达或者复杂的k的取值范围写到下方。nkka1naaa21第25页/共88页第二十六页，共88页。PkkPkkaccaPkkPkkPkkkbaba)(PkfkfPkkaa)()(第26页/共88页第二十七页，共88页。nkbka0)(nkbkaS0)(nknknnkbkbnaknbabkaS000)()(nknkbnabkbnabkaS00)2()()(2)2)(1(1)2(20bnanbnaSnk)2)(1(21bnanS第27页/共88页第二十八页，共88页。nkk1212345 n2345 n345 n45 n5 n n12345 n2345 n345 n45

20、 n5 n n第28页/共88页第二十九页，共88页。nkk12nkk1nkk22nnknninikk1niniknkkk112第29页/共88页第三十页，共88页。nSnnnniinniinnininkSkSninininininiknnkn21) 1(41) 1(212121) 1(21)(212) 1)( 211221221112) 1(41) 1(21232nnnnSn6) 12)(1() 1(61) 1(312nnnnnnnSn第30页/共88页第三十一页，共88页。nknkT13) 1() 1(233) 1(33) 133() 1() 1(1023031133nnnSTnkSTkk

21、kkknTnnnknnnknknkn)21)(1( 123) 1)(1() 1() 1(23) 1(3223nnnnnnnnnnSn6) 12)(1(nnnSn推出 因此(ync) 第31页/共88页第三十二页，共88页。第32页/共88页第三十三页，共88页。定理定理(dngl)3.4.1 (二项式定理二项式定理(dngl)设设n是正整数是正整数,则对任意的则对任意的x,y有：有：n0kknknnnnnnyxkn xnnyxnn yxnxynynyx.1210)(1221第33页/共88页第三十四页，共88页。 二项式系数二项式系数(xsh)n k0 k)!-(nk!n!nk , 0knck

22、n第34页/共88页第三十五页，共88页。 knnkn1 ,111knknknkn;1210nnnnnnnn.1212110nnnnnnnnnn第35页/共88页第三十六页，共88页。性质（性质（2）的证明）的证明 利用的组合意义来证。利用的组合意义来证。n元集合元集合 的的k元子集可以分成两元子集可以分成两类：类： 第一类第一类k元子集含元子集含a1; 第二类第二类k元子集不元子集不含含a1第一类第一类k元子集中的任一个去掉元子集中的任一个去掉a1后，就是后，就是S- a1的的k-1元子集；反过来，任给一个的元子集；反过来，任给一个的k-1元元子集，添上子集，添上a1后就是后就是S的的k元子

23、集，故二者这间元子集，故二者这间有一一对应关系有一一对应关系(gun x).因而，第一类因而，第一类k元子元子集共有集共有 个个.第二类第二类k元子集就是元子集就是S- a1的的k元子集，共有元子集，共有 个个.所以所以naaaS,21naaaS,2111knkn11 ,111knknknkn第36页/共88页第三十七页，共88页。 性质性质(xngzh)2又叫又叫Pascal公式公式,可得杨辉三角可得杨辉三角第37页/共88页第三十八页，共88页。所以所以kn1kn.1 )!1()!1(!)!( !1kknknknknknknkn2n2n,2121knnnkn;1knkn12nk,21121

24、knnnkn;1knkn第38页/共88页第三十九页，共88页。定理定理(dngl)3.4.1 (二项式定理二项式定理(dngl)设设n是正整数是正整数,则对任意的则对任意的x,y有：有：n0kknknnnnnnyxkn xnnyxnn yxnxynynyx.1210)(1221第39页/共88页第四十页，共88页。证明证明 用组合分析的方法证明。用组合分析的方法证明。等式等式(dngsh)左边是左边是n个（个（x+y）因子相乘，）因子相乘，即即这些因子展开到没有括号为止。在展开时，每这些因子展开到没有括号为止。在展开时，每个因子中均可贡献一个个因子中均可贡献一个x或一个或一个y。由乘法原。由

25、乘法原理，共有理，共有2n项，这些项都可写成项，这些项都可写成 的形式。可以在的形式。可以在n个个x+y因子中选出因子中选出k个，从这个，从这k个因子中取个因子中取x，而在另外的，而在另外的n-k个因子中取个因子中取y，如此得到项，所以的系数等于，如此得到项，所以的系数等于n个因子的个因子的k-组合数，即组合数，即 。因此。因此 )()()(个nnyxyxyxyx)0(nkyxknkknn0k.)(knknyxknyx第40页/共88页第四十一页，共88页。2222)(yxyxyx3223333)(yxyyxxyx4322344464)(yxyyxyxxyx第41页/共88页第四十二页，共88

26、页。推论推论(tuln)3.4.1 设设n是正整数是正整数，对一切，对一切x有有knknxknx0)1(推论推论(tuln)3.4.2 对任何正整对任何正整数数n有有nnnnn210推论推论(tuln)3.4.3 对任何正整数对任何正整数n有有531420nnnnnn第42页/共88页第四十三页，共88页。0)1(0knnkk第43页/共88页第四十四页，共88页。knknknyxknyx0)(3.4.3 二项式定理二项式定理(dngl)的推广的推广第44页/共88页第四十五页，共88页。0k !1)k-1).(a-a(a0k 10k 0kka第45页/共88页第四十六页，共88页。定理定理(

27、dngl)3.4.2 (牛顿二项式定理牛顿二项式定理(dngl) 设设a是一个实数，则对一切是一个实数，则对一切x和和y，满足，满足有有其中其中yx !)1).(1(,)(0kkaaakayxkayxkakka第46页/共88页第四十七页，共88页。knknknyxknyx0)( 1,当当a=n(正整数正整数)时，如果时，如果kn，则，则这时牛顿二项式定理就变成下面这时牛顿二项式定理就变成下面(xi mian)的形式的形式0kn这就是二项式定理，这就是二项式定理，所以所以(suy)二项式定理是牛顿二项式定理的特例二项式定理是牛顿二项式定理的特例第47页/共88页第四十八页，共88页。 2, 当

28、当a=-n(负整数负整数(zhngsh)时，有时，有.1) 1()1 (0rrrnxr rnx3, 当当a=-1时，有时，有.) 1()1 (01rrrxx4, 当当a=1/2时，有时，有.1-r 222) 1(1)1 (112121rrrrxrrx第48页/共88页第四十九页，共88页。v 定理定理(dngl)3.4.3 (多项式定理多项式定理(dngl) v设设n是正整数，则是正整数，则tntnntntxxxnnnnxxx.).(21212121其中其中称为多项式系数，并且是对所有满足称为多项式系数，并且是对所有满足(mnz)n1+n2+nt=n 的非负整数解的非负整数解 n1,n2,nt

29、求和。求和。,!2121ttnnnnnnnn第49页/共88页第五十页，共88页。 证明证明(zhngmng) (1) 先将先将(x1+xt)n写成写成n个个(x1+xt)因子的乘积：因子的乘积：. )()( )(212121个nttntxxxxxxxxx将其展开，直到没有括号为止。因为每个因将其展开，直到没有括号为止。因为每个因子中都可取子中都可取x1, x2, ,xt中的任一个，所以展中的任一个，所以展开式共有开式共有tn项，且每项都可以写成项，且每项都可以写成 的形式的形式.要得到这一项，我们应该要得到这一项，我们应该(ynggi)在在n个因子中的个因子中的n1个里面取个里面取x1，有，

30、有 种取法；在剩下的种取法；在剩下的n-n1个因子中的个因子中的n2个里面个里面取取x2，有，有 种取法；种取法；tntnnxxx21211nn21nnn第50页/共88页第五十一页，共88页。最后，在最后，在个因子里面取个因子里面取xt，有，有种取法种取法(qf).由乘法原理知，由乘法原理知， 前前的系数为的系数为)(121ttnnnnnttn nnnn)(121tntnnxxx2121.!)(21121211tttnnnnnnnnnnnnnn第51页/共88页第五十二页，共88页。v 在多项式定理在多项式定理(dngl)中如果取中如果取t2，就，就得到普通的二项式定理得到普通的二项式定理(

31、dngl).1121211212121)(nnnnnnxxnnxxnnnxxv 多项式系数多项式系数(xsh)组合意义如下：组合意义如下：tnnnn.21是多项式是多项式(x1+xt)n中中tntnnxxx.2121项的系数项的系数(xsh)。第52页/共88页第五十三页，共88页。tnnnn.21v 是多重集是多重集S=n1.a1,n2.a2,nt.atv的排列的排列(pili)数数tnnnn.21v 如果我们把如果我们把n个不同的球放到个不同的球放到t个不同的个不同的盒子里盒子里,并且使得第一个盒子里有并且使得第一个盒子里有n1个球，个球，第二个盒子里有第二个盒子里有n2个球个球,第第t个

32、盒子里有个盒子里有nt个球，那么个球，那么(n me)放球的方案数是放球的方案数是第53页/共88页第五十四页，共88页。34322174321,)(xxxxxxxx则.420! 3 ! 1 ! 1 ! 2! 7第54页/共88页第五十五页，共88页。 例例 求求(2x1-3x2+5x3)6中中 项的系数项的系数(xsh)解解:23231xxx3600025) 3(8! 2 ! 3! 65) 3(22 , 1 , 3623第55页/共88页第五十六页，共88页。 推论推论3.4.4 (x1+xt)n的展开式在合并同的展开式在合并同类项以后不同类项以后不同(b tn)的数目是的数目是ntn1 证

33、明证明 (x1+xt)n的展开式中任何一项对应于方程的展开式中任何一项对应于方程 n1+n2+nt=n的一组非负整数的一组非负整数(zhngsh)解，所以合并同类项后不同的项数等于这个方程的非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数(zhngsh)解的个数解的个数ntn1第56页/共88页第五十七页，共88页。nttnnnn.21 推论推论(tuln)3.4.5其中求和其中求和(qi h)是对方程是对方程n1+n2+nt=n 的一切非负整数解来求。的一切非负整数解来求。证明证明(zhngmng): 在多项式定理中令在多项式定理中令x1=x2=xt=1即可即可.第57页/共88

34、页第五十八页，共88页。12.2211 , 1nnnnnnn证明证明(zhngmng) 对等式对等式knknxknx0)1 (两边两边(lingbin)微分得微分得111)1 (knknxknkxn然后令然后令x=1得得nnnnnnn221121等式成立等式成立第58页/共88页第五十九页，共88页。证明证明(zhngmng) 对等式对等式两边两边(lingbin)积分得积分得1111) 1(2311211 )2(nnnnnnnknknxknx0)1 (xknkxndxxkndxx000)1 ()1 (110001dxxknxnnkxkxn11)01 ()1(110111nkknnxkknxn

35、第59页/共88页第六十页，共88页。然后然后(rnhu)令令x=-1得得成立成立(chngl)nkknxknkxn01111) 1)1(11nkkknkn01) 1(111111) 1(110nknknkk即即第60页/共88页第六十一页，共88页。11.10 )3(knknkk 证明 采用组合分析的方法等式右端 是n+1元集合(jh)S=a1,a2,an+1的k+1元子集的个数，这些子集可以分成如下n+1类：第(0)类：k+1元子集中含 a1，这相当于S-a1 的k元子集再加上 a1构成S的k+1元子集，共 个kn11kn第61页/共88页第六十二页，共88页。第第(1)类：不含类：不含a

36、1但含但含a2的的k+1元子集，元子集， 共有共有 个个；第第(n)类：不含类：不含a1,a2, an但含但含an+1的的k+1元元子集，共有子集，共有 个个.由加法由加法(jif)原理知原理知所以等式成立所以等式成立k0kn1kknknkn0.111第62页/共88页第六十三页，共88页。nnnnnn210 )4(222证明证明 采用采用(ciyng)组合分析的方法。组合分析的方法。 是是2n元集合元集合S的的n-组合数，把集合组合数，把集合S分成两个集合分成两个集合S1和和S2，使，使 ，则，则S的的n元子集可以分成元子集可以分成如下如下n+1类：类：从从S1中选取中选取i（0in）个元素

37、，）个元素，从从S2中选取中选取n-i个元素，个元素，将将S1的的i个元素与个元素与S2的的n-i个元素并到一起构成个元素并到一起构成S的第的第i类类n元子集。元子集。nn2nSS21第63页/共88页第六十四页，共88页。而第而第i类子集的个数为类子集的个数为 由加法由加法(jif)原理，有原理，有 即原等式成立。即原等式成立。 ),0(2niininninninnin022第64页/共88页第六十五页，共88页。rnmnrmrnmrnm0.110, 5证明证明(zhngmng)此恒等式是恒等式（此恒等式是恒等式（4）的）的推广，推广， 被称为被称为Vandermonde恒等式恒等式. 由二

38、项式定理有由二项式定理有kmkmxkmx0)1 (lnlnxlnx0)1 (第65页/共88页第六十六页，共88页。比较等式两边比较等式两边xr的系数的系数(xsh)，左边是，左边是右边是右边是lnlkmknmnmxlnxkmxxx00 )1 ()1 ()1 (rnm0.110nrmrnmrnm第66页/共88页第六十七页，共88页。为正整数nnnknknnk,2)1( )6(212证明证明 方法方法1：由二项式定理有由二项式定理有对上式两边对对上式两边对x微分微分(wi fn)得得等式两边乘以等式两边乘以x得得knknxknx11)1(111(1)nnkknnxkxk 11(1)nnkknn

39、xxkxk 第67页/共88页第六十八页，共88页。等式两边等式两边(lingbin)对对x微分得：微分得：令令x=1则：则：即：即： 12211(1)(1)(1)nnnkknnxnx nxkxk 12212(1)2nnnknnn nkk 221(1)2nnknn nkk 第68页/共88页第六十九页，共88页。方法方法(fngf)2：2211111111011111(1 1)111(1)11211(1)212(1)2nnnkkknknnkknnkknnnnkkknkkkknnkknnnkkknnnnkkkknnnk 1101nnkknk第69页/共88页第七十页，共88页。11012122(

40、1)21222(1).2102(1)22(1)2nnknnnnnnnknnnnnnnnn n第70页/共88页第七十一页，共88页。一条一条(y tio)非降路径，规定非降路径，规定水平向右走一个单元格用水平向右走一个单元格用x表示表示垂直向上走一个单元格用垂直向上走一个单元格用y表示表示第71页/共88页第七十二页，共88页。(0,0)(5,6)yx第72页/共88页第七十三页，共88页。一条从（一条从（0，0）点到（）点到（m, n）点的非降路）点的非降路径就是多重集径就是多重集mx，ny的一个排列的一个排列(pili)。 反之，给定多重集反之，给定多重集mx，ny的一个排列的一个排列(p

41、ili)就唯一地确定了一条从（就唯一地确定了一条从（0，0）点）点到（到（m, n）点的非降路径。）点的非降路径。第73页/共88页第七十四页，共88页。 所以从（所以从（0，0）点到（）点到（m, n）点的非降路径）点的非降路径数等于数等于(dngy)mx，ny的排列数，即二的排列数，即二项项式系数式系数 或或 mnmnnm下面用非降路径的思想下面用非降路径的思想(sxing)证明组合恒等式证明组合恒等式由此可见非降路径实质由此可见非降路径实质(shzh)上是二项上是二项式系数的一种几何解释。式系数的一种几何解释。第74页/共88页第七十五页，共88页。例例3.4.4 证明证明(zhngmn

42、g)：1- 1 1 mnmmnmmnm证明：证明： 是从是从(0,0)点到点到(m,n)点的非降点的非降路径路径(ljng)数。这些路径数。这些路径(ljng)可以分可以分成两类：成两类：mnm 第75页/共88页第七十六页，共88页。 一类由（一类由（0,0）点经由（）点经由（m-1, n）点到）点到达（达（m, n）点，共有）点，共有 条；条；另一类经由（另一类经由（m, n-1）点到达（）点到达（m, n）点，共有点，共有 条，条，根据加法根据加法(jif)原理，等式成立。原理，等式成立。1 1mnmmnm 1第76页/共88页第七十七页，共88页。例例3.4.5 证明证明(zhngmn

43、g)rnmnrmrnmrnm0.110证明证明: 等式右端表等式右端表示从示从(0,0)点到点到(m+n-r,r)点的非降点的非降路径数。任何一条路径数。任何一条这样这样(zhyng)的的非降路径一定经过非降路径一定经过图中斜线上的点，图中斜线上的点，按所经过点的不同按所经过点的不同将路径分类。将路径分类。第77页/共88页第七十八页，共88页。 从从(0,0)点到点到(m-k,k)点的非降路径点的非降路径(ljng)是是 条条从从(m-k,k)点到点到(m+n-r,r) 非降路径非降路径(ljng)是是 条条由乘法原理，可知从由乘法原理，可知从(0,0)点经过点经过(m-k,k)点点的非降路

44、径的非降路径(ljng)是是 条条再对再对k=0,1,r求和就得到所有的从求和就得到所有的从(0,0)点到点到(m+n-r,r)点的非降路径点的非降路径(ljng)数数所以等式成立所以等式成立kmkrnkm krn第78页/共88页第七十九页，共88页。解解 先考虑对角线下方的路径先考虑对角线下方的路径这种路径都是从这种路径都是从(0,0)点出发经过点出发经过(jnggu)(1,0)点及点及(n,n-1)点到达点到达(n,n)点的我们可以把它看作是从点的我们可以把它看作是从(1,0)点出点出发到达发到达(n,n-1)点的不接触对角线的非降点的不接触对角线的非降路径。从路径。从(1,0)点到点到

45、(n,n-1)点的所有的非点的所有的非降路径数是降路径数是 例例3.4.6 求从求从(0,0)点到点到(n,n)点的除端点点的除端点(dun din)外不接触直线外不接触直线yx的非降路的非降路径数径数122nn第79页/共88页第八十页，共88页。对其中任意一条接触对角线的路径，我们对其中任意一条接触对角线的路径，我们可以把它从最后离开对角线的点可以把它从最后离开对角线的点(图中的图中的A点点)到到(1,0)点之间的部分关于对角线作一个点之间的部分关于对角线作一个反射，就得到一条从反射，就得到一条从(0,2)点出发经过点出发经过A点点到达到达(n,n-1)点的非降路径点的非降路径反之，任何一条从反之，任何一条从(0,1)点出发（必穿过）点出发（必穿过）直线直线y=x而到达而到达 (n,n-1)点的非降路径，也点的非降路径，也可以通过这样的对称可以通过这样的对称(duchn)变换得到一变换得到一条从条从(1,0)点出发接触到对角线而到达点出发接触到对角线而到达(n,n-1)点的非降路径点的非降路径第80页/共88页第八十一页，共88页。从而在直线从而在直线(zhxin)y=x下方不接触直线下方不接