(完整版)排列组合公式及恒等式推导、证明(word版)

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

2、种选法;第三步，排第三位：有（n-2）种选法;第m步，排第m位：有（n-m+1）种选法;IIII最后一步，排最后一位：有1 种选法。根据分步乘法原理，得出上述公式。、组合数公式:C =二 n(n-1)0- 2)L (n - m+1)= n!nA；m!m!( n-m)!Cnn =1推导：把n个不同的元素任选m个不排序，按计数原理分步进行：第步，取第个：有n种取法；第二步，取第二个：有（n-1）种取法；第三步，取第三个：11有(n-2)种取法；11第m步，取第m个：11有(n-m+1)种取法;11最后一步，取最后一个：有1种取法。上述各步的取法相乘是排序的方法数，由于选 m个，就有m!种排 排法，

3、选n个就有n!种排法。故取m个的取法应当除以m!,取n 个的取法应当除以n!。遂得出上述公式。证明：利用排列和组合之间的关系以及排列的公式来推导证明。将部分排列问题Anm分解为两个步骤：第一步，就是从n个球中抽m个出来，先不排序，此即定义的组 合数问题Cnm ；第二步，则是把这m个被抽出来的球全部排序，即全排列 A：。n(n _1)n_2)L( n-m+1)n!Ama：根据乘法原理，Ancnm 即:m!(n- m)!m!组合公式也适用于全组合的情况，即求 C(n, n)的问题。根据上述公式，C( n,n)二 n!/n!( n-n)! 二 n! / n !0! 二 1。这一结果是完全合理的，因为

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

5、以除以重复的情况：m ! * (n-1 )!于是答案就是：Rnn=(m+n-1)! =Cn：m-1m !(n - 1)!四、不全相异的全排列在不全相异的n个物体中，假设有ni个物体是相同的，n2个五 题是相同的，nk个物体是相同的。n个物体中不相同的物体种 类数一共有k种。那么，这些物体的全排列数是 n!/(n 1X2!n!)。可以想成：n个物体直接全排列，排列完了以后，去重，第一 种物体有ni!种，第二种物体有n2!种，以此类推。例：有3个红球，2个白球，把这五个球排成一行，问有多少 种排法？红球和红球没有区别，白球和白球没有区别。答：一共有10种，aaabb,aabab,aabba,aba

6、ab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的证明：Anm=(n - m + 1) A证明：右边=(n+ 1)(nn ! m + 1)!n !(n - m )!左边=右边nmA n -1n -n !(n - m )!n ? (n - 1) 证明：右边=n - m (n - m - 1)!左边=右边AnmnA证明：右边二 n (n - 1)!= 口一(n - m )!(n - m )!左边=右边nAn = A：；An证明：右边二A：；-A： =(n+1)!- n!=(n+10!- n!二ngi! = nA：右边=左边Anm+1Anm+ mA证明：右

7、边二+m M =(n-m+1)n!-叽(n+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!=右边 六、组合恒等式的证明首先明弄清组合的两个性质公式:m n-mC n =C n互补性质：取出有多少种，剩下就有多少种分类计数原mmm-1Cn+1 =C n 十C n根据分类计数原理：要么含有新加元素要么不含新加元素m +1n - m

8、m +1 nn - m +1m-1C n mm +1m+1n(m +1)n!_ n!(n - m)(m+1)!( n-m-1)! m!(n- m)!=C证明:n - m+1n!n!g=m (m -1)!(n- m+1)!m!(n- m)!C m二n=n n - mn - m +1c m-1mn- mn (n -1)!9n!n- m m!(n- m-1)! m!(n- m)!CmC m =n_nQm - 1C n - 1m证明：右边二证明:右边二(n - 1)!(m - 1)!( n -m )!n !m !( n - m )!=左边rrrC r +C r+1 +C r+2 + L+ C；证明：根

9、据组合性质，左边各式可写成:r +1n +1Crr =Cr +1r +1rr +1=Cr+1r +2-Cr +1r +1rr +2=Cr +1r+3-Cr +1r +2rr +3= C；：4-Cr +1r +3rn-1=Cr+1n-Cr +1n-1r r+1C n =C n+1-Cr +1 n左右两边相加即得:Crr +Crr+1Cl+L +C； =Cr+1n+1 c n + c n + l证明: 用数学归纳法证明1) 当 n=1时，C10+C11 = 2 = 21所以等式成立。2) 假设n=k时，(k 1 , k N* )时等式成立k即：C：+Ck +C：+L +C： =2当n=k+1 时，

10、0k +1+C：+1+C+1+L+Ck+1+Ck+1k+100112k-1 kk +1= Ck+1+(Ck+Ck)+(Ck+Ck)+L +(Ck +Ck )+Ck+1= (C；+C： +C：+L +C) + (Ck+Ck +Ck+L +Ckk) = 2g2k= 2k+1二等式也成立由1)、2)得，等式对n N*都成立。也可用二项式定理证明（略） c；+c3+c：L =C0+C：+C：L =2n-1证明：用归纳法同上（略）也可利用上述结论证明（略） 本课件尽量避开用二项式定理，但这比较简单，暂且用一下:135.a =Cn +Cn +Cn +L b =c n +c n +C：+L由（1+1） n可得：a+b=2n=2x 2n-1由（1-1 ） n可得 a-b=0 a=b=2n-1（不懂的去学学二项式定理） Cn+2C：+3C；+L +nC； =ng2n-1证明：亠m 亠m-1由mCn二nCn-1可得：（还记得这个恒等式吗，不记得就回过头去看的证明）左边=rC0-1 +10 +nCn-1 +nC；-1 +L nC；=n C-1V-1+C-1+C-1+L cn-11)n-1=ng2注：同时利用了的结论 cmco+cm-icn+L +cmc： =cn+m