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

1、排列组合公式及恒等式推导、证明word版作者:日期:排列组合公式及恒等式推导、证明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个全排序，按计数原理分步进行：第步，排第位

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

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

4、!二 n! / n !0! 二 1。这一结果是完全合理的，因为从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 )!种排

5、法，再由于 m个小球和(n-1 )块隔板是分别不 加以区分的，所以除以重复的情况：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个白球，把这五个球排成一行，问有多少 种排法？红球和红球没有区别，白球和白球没有区

6、别。答：一共有10种，aaabb,aabab,aabba,abaab,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：+1- An =(n+1)!- n! = (n +10!

7、- n!二ngi!=nA：右边=左边Anm+1Anm+ mA证明：右边二+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!=右边六、组合恒等式的证明首先明弄清组合的两个性质公式：mn- mCn =Cn互补性质：取出有多少种，剩下就有多少种分类计数原-1C n +1 =C n +C n根据分类计数原

8、理：要么含有新加元素要么不含新加元素Cmnm +1m +1 nn - m +1m-1C n m(m +1)n!m +1m+1Cnn - m证明：n-口+1严1 二n-m+1= n! 二严mm (m -1)!(n- m+1)!m!(n- m)!=C (n - m)(m+1)!( n-m-1)! m!(n- m)!n!n!C m二n=nC nm 1n - mn- mn(n -1)!g n- m m!(n- m-1)!n!m!(n- m)!CmC m =n_nQm - 1C n - 1m证明：右边二证明:右边二(n - 1)!(m - 1)!( n -m )!n !m !( n - m )!=左边r

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

10、k即：C：+Ck +C：+L +C： =2当n=k+1 时，C 0 +c 1 +c 2 +l +C k +c k+1Ck +1 +C k+1 +Ck+1 +L +C k +1 +Ck+100112k-1 kk +1= Ck+1+(Ck+Ck)+(Ck+Ck)+L +(Ck +Ck )+Ck+1= (C；+C： +C：+L +C) + (Ck+Ck +C+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：