排列组合公式及恒等式推导、证明

《排列组合公式及恒等式推导、证明》由会员分享，可在线阅读，更多相关《排列组合公式及恒等式推导、证明（10页珍藏版）》请在装配图网上搜索。

1、排列组合公式及恒等式推导、证明(word版)说明：因公式编辑需特定的公式编辑插件，不管是 word还是pps附带公式编辑经常是 出错用不了。下载此 word版的，记得下载 MathType公式编辑器哦，否则乱码一堆。如果 想偷懒可下截同名的截图版。另外，还有PPt课件(包含了排列组合的精典解题方法和精典试题)供学友们下载。一、排列数公式：mn!An = n(n - 1)(n - 2)L (n-m+1)= 一 (n - m)!A； = n(n -1)(n - 1)L 3仓iJ2 1推导：把n个不同的元素任选m个排次序或n个全排序，按计数 原理分步进行：第一步，排第一位： 有 n种选法；第二步，排

2、第二位： 有(n-1 )种选法；第三步，排第三位： 有(n-2)种选法； I I I I第m步，排第m位：有(n-m+1)种选法；I I I I最后一步，排最后一位：有 1 种选法。根据分步乘法原理，得出上述公式。二、组合数公式：Am n(n- 1)(n- 2)L (n- m+1) n!Cn = Z =Amm!m!(n-m)!Cnn =1推导：把n个不同的元素任选m个不排序，按计数原理分步进行：第一步，取第一个：有 n 种取法；第二步，取第二个：有(n-1 )种取法；第三步，取第三个：有(n-2)种取法；I I I I第m步，取第m个：有(n-m+1)种取法；I I I I最后一步，取最后一个

3、：有 1种取法。上述各步的取法相乘是排序的方法数，由于选 m个，就有m!种排 排法，选n个就有n!种排法。故取m个的取法应当除以m!,取n个的取法应当除以n!。遂得出上述公式。证明：利用排列和组合之间的关系以及排列的公式来推导证明。将部分排列问题Anm分解为两个步骤：第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题Cnm;第二步，则是把这m个被抽出来的球全部排序，即全排列 Am。根据乘法原理，An1二cnmAm即： Am n(n-1)n-2)L (n-m+1) n!(. =n mAmm!m!(n- m)!组合公式也适用于全组合的情况，即求 C(n, n)的问题。根据上述公式，C

4、(n, n) = n!/n!(n-n)!= n! / n!0!= 1。这一结果是完全合理的，因为从n个球中抽取所有n个出来，当 然只有1种方法。三、重复组合数公式：重复组合定义:从n个不同的元素中每次取一个，放回后再取下 一个，如此连续m次所得的组合。重复组合数公式：Rrm =Cn+m-i (m可小于、大于、等于n,n 1)推导：可以把该过程看作是一个“放球模型”：n个不同的元素看作是n个格子，其间一共有(n-1 )块相同的 隔板，用m个相同的小球代表取 m次；则原问题可以简化为将 m 个不加区别的小球放进n个格子里面，问有多少种放法；这相当于m个相同的小球和(n-1 )块相同的隔板先进行全排

5、列：一共有 (m+n-1 ) !种排法，再由于m个小球和(n-1 )块隔板是分别不 加以区分的，所以除以重复的情况：m! * (n-1 ) !于是答案就是：Rnm=(m+n-1)! =Cnm+m-1m !(n - 1)!四、不全相异的全排列在不全相异的n个物体中，假设有ni个物体是相同的，n2个五 题是相同的，nk个物体是相同的。n个物体中不相同的物体种 类数一共有k种。那么，这些物体的全排列数是 n!/(n i!n 2!心!)。可以想成：n个物体直接全排列，排列完了以后，去重，第一 种物体有ni!种，第二种物体有 作!种，以此类推。例：有3个红球，2个白球，把这五个球排成一行，问有多少 种排

6、法？红球和红球没有区别，白球和白球没有区别。答：一共有10种,aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bba aa。五、排列恒等式的证明:Anmm - 1=(n - m + 1) An证明:右边=(n - m+ 1)(nm + 1)!(n - m )!左边=右边n !(n - m )!n ? (n - 1)证明：右边=n - m (n - m - 1)!左边=右边n !(n - m )!Anm = nA nm11证明：右边二n (n - 1)!(n - m )!左边=右边nAn =An +1n +1An证明：右边=An+1 -

7、 An =(n+1)!- n! =(n+1)gn!- n! = ngi! = nA：Anm+1右边=左边+ mA证明：右边=+m n! =(n-m+1)n!-m5!= (n+1)!=1(n - m)!(n- m+1)!(n- m+1)! (n - m+1)! 1!+2?2! 3?3! L +n?n! (n +1)!- 1证明：左边=(2-1)1! + (3-1) 2! + (4-1) 3!+- - (n+1-1) n!=2!-1!+3!-2!+4!-3! (n+1)!-n!=(n+1)!-1!=右边六、组合恒等式的证明首先明弄清组合的两个性质公式：C：=C；m互补性质：取出有多少种，剩下就有多

8、少种分类计数原cnm+1 =cnm +cnm-1根据分类计数原理：要么含有新加元素要么不含新加元素m +1 c m+1 _ n - m +1m-1C n =C nn - mmm +1m+1Cn n - m(m +1)n!n!m=Cn(n - m)(m+1)!(n - m - 1)! m!(n- m)!证明：n - m +1C m-1 = n - m +1g n!= n! =C m mm (m - 1)!(n- m +1)! m!(n- m)!n!n mm证明：右边=高&-1(n-1)!n!-g ，n- m m!(n- m-1)! m!(n- m)!Cmnn g 右边二m(n - 1)!证明:(

9、m - 1)!( n - m )! m !( n - m )!=左边GC r + C r + C r +L + C r - C r +1 C r +Cr+1+Cr+2+L + C n = C n +1证明：根据组合性质，左边各式可写成:C： =C*rr +1rr +2rr +3r+1r +2r +1r+3-C-C=C rr+4 - Cr +1r +1r +1r +2r +1r +3C11_ C r +1 r+1=C n - Cn-1Cr r +1 r +1 n =C n +1 - Cn左右两边相加即得:C r +C r +C r +L+Cr =Cr+1Cr +Cr+1 +Cr+2 +L +Cn

10、 Cn+1 c2+cI+l +c nn证明:用数学归纳法证明。1）当n=1时，C10+C11=2 = 21所以等式成立。2）假设n=k时，（kA1, k6 N*）时等式成立k即：C：+C； +C：+L +Ck =2当n=k+1时,C 0+c1 +c 2 +l+Ck+C k+1C k +1+Ck+1 +C k+1 +L+Ck +1+C k+1c0-0-11 c2k-1-kck+1= Ck+1+(Ck+Ck)+(Ck+Ck)+L +(Ck +Ck)+Ck+1-fC 0 +C 1 +C 2 +L +Ck) + /C0+C1 +C 2 +L +C k) =(C k +Ck +Ck +L +Ck ) +

11、 (Ck +Ck +Ck +L +C k )=2g2k=2k+1等式也成立由1）、2）得，等式对n N*都成立。也可用二项式定理证明（略） C1+C3+C5L =C0+C2+C4L =2n-1 nnnnnn1-证明：用归纳法同上（略） 也可利用上述结论证明（略） 本课件尽量避开用二项式定理，但这比较简单，暂且用一下:135.a =Cn +Cn +C n +Lb =C：+C；+C：+L由（1+1） n可得：a+b=2n=2x 2n-1由（1-1 ） n可得 a-b=0.a=b=2-1（不懂的去学学二项式定理） C； +2C：+3C；+L +nC；=ng2n-1证明：- m m-1由mCn=nCn

12、-1可得：（还记得这个恒等式吗，不记得就回过头去看的证明）左边=rC0-1 +nC1-1+nCn-1+nCr3-1+L nC；=ne0-1+Cn-1+C：-1+C3-1+L C：；） =ng2n-1注：同时利用了的结论今r 0r-1010 r r CmCnCm Cn LCmCn =Cn+mr/inm,用工项式定理证明太麻烦了。能偷懒就不要太勤快了。观察左边的每一项，发现均是分别从m个不同素和n个不同元素 中取r个元素的一个组合，其各项之和就是所有取法，即所有组合 数。其所有组合数当然等于右边。0c：）2+（cn）2+L +（c；）2=c2n还是用偷懒法：根据第的结论并结合组合的互补性质， 若r=m=n即 得些结论。