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

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

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

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

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

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

6、种排法？红球和红球没有区别，白球和白球没有区别。答：一共有10种，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,bab aa,bbaaa 。五、排列恒等式的证明：A；m - 1=(n - m + 1) A n证明:右边=(n - mn !+ 1) =(n - m + 1)! ( nn ! =A -m )!左边=右边A nmn !(n - m )!n ? (n - 1) 证明：右边=n - m (n - m - 1)!左边=右边左边=右边证明：右边=A：；- An = (n +1)!- n! =(n+1)gi!- n!二ngi! = nA：右边=

7、左边 n! _(n-m+1)n!-mgn!_ (n +1)! _加+m = = =A+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互补性质：取出有多少种，剩下就有多少种分类计数原m m m -1C n+1 =C n +C n根据分类计数原理：要么含有新

8、加元素要么不含新加元素 Cm = m +1 Cm+1-mn - m +1 m-i C n(m +1)n!m +1 m+1Cn n - m证明：n - m +1 小 m-1 n - m+1Cn = g=C (n - m)(m+1)!(n-m -1)! m!(n-m)!n!M =Cnmm!(n- m)!C m =nn C mC n - 1n-m证明 ： 右边m m (m - 1)!(n - m +1)!=1亠=Ctn-m n-m m!(n-m-1)! m!(n- m)!C m :n_ n Q m - 1 C n - 1m证明:.mn右边二n (n - 1)!gm (m - 1)!( n - m )

9、! m !( n - m )!=左边r r rC r +C r+1 +C r+2 + L+ Cnrr +1C n +1证明：根据组合性质，左边各式可写成:Crr =C C；+1 = CC：+2C；+3MC；1r +1r+1r+1 r +1 r +2 - C r +1r+1 r +1=C r+3 - Cr+2r+1 r +1=C r+4 - C r +3C； =Cr+1 r+1=C n - Cn-1r +1 r +1n +1 - C n-C左右两边相加即得：Crr +Crr+1 +Crr+2 +L +Cnr =cn：； c n + c n + l + c n证明:用数学归纳法证明。1 )当n=1

10、时，Ci0+C； = 2=21所以等式成立。2)假设n=k时，(k 1 , k N* )时等式成立 即：C：+Ck +C：+L +C： =2k当n二k+1 时，c：+1+ck+1+c：+1+L +Ckk+1+c：11= C+1+（C；0+C1）+（Ck +C：）+L +（Ckk-1+C：）+C阳 = （C：+Ck +C：+L +C；） + （C：+Ck +Ci+L +Ckk）=20= 2k+1二等式也成立由1）、2）得，等式对n N*都成立。也可用二项式定理证明（略）7Cn+C；+C；L =C：+C；+C：L =2n-1证明：用归纳法同上（略）也可利用上述结论证明（略）本课件尽量避开用二项式定

11、理，但这比较简单，暂且用一下：设a =C：+C；+C；+L b =C+Cn +Cn +L由（1 + 1） n可得：a+b=21=2x 2n-1由（1-1） n可得 a-b=0a=b=2-1 （不懂的去学学二项式定理）8C； +2C：+3C；+L +nC； =ng2n-1证明：由mCnm=nCn呼可得：（还记得这个恒等式吗，不记 得就回过头去看的证明左边n-1n-1=rC0-1 +nCn-1 +nC；2-1 +nC3-1 +L nC = nCn-1 +Cn-1 +Cn-1 +Cn-1 +- Cn-1) = ng2n-1注：同时利用了的结论。9cmc：+cm-icn+L +cma =cn+mr Emin m,n用二项式定理证明太麻烦了。能偷懒就不要太勤快了。观察左边的每一项，发现均是分别从m个不同素和n个不同元素中取r个元素的一个组合，其各项之和就是所有取法，即所有组合j 数。其所有组合数当然等于右边。10c：)2+(Cn)2+L +(C：)2=C；n还是用偷懒法：根据第的结论并结合组合的互补性质，若r=m=n即得些结论。