排列数、组合数和式的计算方法

排列数、组合数和式的计算方法 排列数、组合数和式的计算方法 江苏 蔡道平 排列数、组合数和式的计算是本章的难点之一，在解时，要根据和式的结构灵活运用 各种方法才能解决问题，下面举例说明常用的求和方法。 1( 拆项法 nn,1231例1 计算: ？，，，，， 234nn，1AAAAA234nn，1 kkk，1,1k，1111，，,,,,,,解 因为 k，1，，，，，，，，，，k，1!k，1!k，1!k，1!k!k，1!Ak，1 k所以 , 在上式中将用1，2，3，„，依次代入，再将各式相加，得 n nn,1231？，，，，， 234nn，1AAAAA234nn，1 ，，1111111,,,,,,,1,，,，,，？，, ,,,,,,,,，，2!2!3!3!4!n!n，1!,,,,,,，， 11,= ，，n，1! 012mm例2 计算:,，,„，. CCC(,1)Cnnnn ,1kkk解 ?C,C，C(k,1,2,„m), ,1,1nnn 00 ? C,C,nn,1 101 ,C,,C,C, nnn,1,1 212 C,C，C,nnn,1,1 „„ m,1m,1m,1m,2m,1m,1 (,1)C,(,1)C，(,1)Cnn,1n,1 mmmm,1mm (,1)C,(,1)C，(,1)C. nn,1n,1 将上述m+1个等式相加得 mmmm012 „，(,1)C,(,1)C. C,C，C,nn,1nnn 说明 例1是分式的和，故运用了数列中求分式的和的方法:拆项法;例2中各项符号 ,1kkk正、负相间，故利用了组合数的性质:C,C，C，使其前后相消求得和. ,1,1nnn2( 并项法 mmmmm例3 计算: C，C，C，？C，C，1，2,2,1mmmnn mmmmm 解C，C，C，？C，C，1，2,2,1mmmnn ，1mmmmm = ，，C，C，C，？C，C，1，1，2,2,1mmmnn ，1mmmm =，，C，C，？，C，C，2，2,2,1mmnn ，1mmm，1 =„„== C，CC,1,1nnn 说明 本例结构特征是组合数中的“上标”均为,而“下标”是公差为1的等差数列, m ,1kkk这类问题可用组合数性质并项,另外组合数中的“上标”“下标”均为公 C,C，C,1,1nnn 12317差1的等差数列时,也可用上面的方法.如计算: ,即求: C，C，C，？，C45620 3333 ,转化为本例类型. C，C，C，？，C45620 3.转化通项法 11112n例4 计算: 1„ ，C，C，，Cnnn23n，1 11n!1(n，1)!kC,,,,解 ? nk，1k，1k!,(n,k)!n，1(k，1)!,[(n，1),(k，1)]! kk，1CC1k，1nn，1,, ?(*)， C,n，1k，1n，1，n1 11223nn，1CCCCCCCn，nn，nn，nn，1111,,,1,,,,,.在(*)式中令k=0，1，2，„，n时，有„ n，n，n，n，n，1213111 1111n12n，112将以上各式相加即得1„„ ，C)，C，C，，C,(C，C，nnnn，1n，1n，123n，1n，1 1n，1= ，，2,1n，1说明 本例中各项组合数的系数是不同的，通常是转化通项使其组合数的系数化为相同，然 后再用二项式系数的性质或组合数的性质求解. 4.倒序相加法 123n例5 计算: C，2C，3C，？，nCnnnn 123n,1n，，解 设S=C，2C，3C，？，n,1C，nC ? nnnnn kn,k由于，上式即为 C,Cnn nn,1321，，S=nC，n,1C，？，3C，2C，C nnnnn 01n,3n,2n,1 =，， ? nC，n,1C，？，3C，2C，Cnnnnn 01n,1n ?，?两式相加，2S=nC，nC，？，nC，nCnnnn 01n,1n = n，，C，C，？，C，Cnnnn nn,2 = 1nn,1所以S=. n,2,n,22 kn,k说明 因为,而系数的顺序与组合数中取出的元素数相同,故可利用等差数列前C,Cnnn kk,1项和公式的证明方法——倒序相加法来证明.另外由于,故本题也可用转化通项kC,nCnn,1法来解. 5(二项式定理赋值法 2n0122n，，例6 计算: C,3C，9C,？，,3C2n2n2n2n 2n02n12n,12n2n，，解 由a，b,Ca，Cab，？，Cb2n2n2n a,1,b,,3,在此式中令有 2n22n,12n02n122n,12n，，，，，，，，，，1,3,C,1，C,3，C,3，？，C,3，C,3 2n2n2n2n2n 2n0122n，， =C,3C，9C,？，,3C2n2n2n2n 2n0122nn，，故C,3C，9C,？，,3C,4 2n2n2n2n k说明 对于一个组合数数列,,和一个等比数列,它们对应项乘积的和往往可以利用 C,,ank a,b二项式定理,在等式两边赋予适当的值来解. 6.构造法 2222，，n2!012n,，，，，，，，，，，例7 求证:C，C，C，？，C,n,Nnnnn nn!! n0122n,1n,1nn，，证一1，x,C，Cx，Cx，？，Cx，Cx nnnnn n0n1n,12n,2n,1n，，x，1,Cx，Cx，Cx，？，Cx，C nnnnn将以上两式相乘，得 nn0122n,1n,1nn，xx，,C，Cx，Cx，，Cx，Cx，，，，，，11？nnnnn 0n1n,12n,2n,1n，，Cx，Cx，Cx，，Cx，C？nnnnn 2n0011nn,n，x,CC，CC，CCx，，，，，，1？nnnnnn 222201202nnnn，，，，，，，，,,，，C，C，C，，Cx，，CCx,？？nnnnnn 2n0122nn2n2n，，1，x,C，Cx，Cx，？，Cx，？，Cx又 2n2n2n2n2n nx这个展开式与(,)式展开式恒等。比较的系数就有 2222，，n2!012n,，，，，，，，，，， C，C，C，？，C,n,Nnnnnnn!! 证二 设有个男生和个女生共2个学生，现从中要选个学生去参加某项活动。 nnnn ，，2n!nC,共有不同的选法为种。 2nn!n! n，1另外我们可把选个学生分成类方法，即从个男生中选个，再从个女生中选 nnnr rn,r个，这样每类选法种数为.由分类计数原理,知共有不同 CC，，n,rr,0,1,2,3,？,nnn 的选法种数为 2222,,0n1n12n2n0012n，，，，，，，，CC，CC，CC，？，CC,C，C，C，？，C. nnnnnnnnnnnn 2222，，n2!012n,这两种选法种数是一样的,所以，，，，，，，，，，C，C，C，？，C,n,Nnnnn nn!!说明 证一与证二是两种不同的构造法.证一考虑等式右边是 2nnnn，1,是展开式中第项的二项式系数,左边和中每一项的幂底数恰是 C，，，，a，ba，b2n 展开式中的二项式系数,而幂指数都是2,故可构造两个二项展开式相乘再比较系数,从而 得证.证二的实质是通过构造集合来证明,即全集U含有2个元素,集合A,B各有个元素, nnA,B,U,A,B,,且,然后分两种情况来考虑取个元素. n