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

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

上述各步的取法相乘是排序的方法数，由于选m个，就有m!种排排法，选n个就有n!种排法故取m个的取法应当除以m!,取n个的取法应当除以n!遂得出上述公式证明：利用排列和组合之间的关系以及排列的公式来推导证明将部分排列问题Am分解为两个步骤：n第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题Cm ；n第二步，则是把这m个被抽出来的球全部排序，即全排列Amm根据乘法原理，Am二CmAm即:n n mAm n(n-1)©-2)・(n-m+1) n!Cm n-:n Am m! m!(n-m)!m组合公式也适用于全组合的情况，即求C(n, n)的问题根据上述公式，C(n, n) = n!/n!(n-n)! = n! / n!0! = 1这一结果是完全合理的，因为从 n 个球中抽取所有 n 个出来，当 然只有 1 种方法三、重复组合数公式：重复组合定义:从 n 个不同的元素中每次取一个，放回后再取下 一个，如此连续 m 次所得的组合重复组合数公式：Rm (m可小于、大于、等于n,n^l)n n m 1推导：可以把该过程看作是一个“放球模型”：n个不同的元素看作是n个格子，其间一共有(n-1 )块相同的 隔板，用m个相同的小球代表取m次；则原问题可以简化为将m个不 加区别的小球放进n个格子里面，问有多少种放法；这相当 于m个相同的小球和(n-1)块相同的隔板先进行全排列：一共有(m+n-1) !种排法，再由于m个小球和(n-1)块隔板是分别不加以 区分的，所以除以重复的情况：m! * (n-1)!于是答案就是：Rm = ( 9= Cm _n m !(n -1)! nm~1四、不全相异的全排列在不全相异的n个物体中，假设有n个物体是相同的，n个五1 2题是相同的，……，n个物体是相同的。

n个物体中不相同的物体种k类数一共有k种那么，这些物体的全排列数是n!/(n!n!・・・n!)1 2 k可以想成：n个物体直接全排列，排列完了以后，去重，第一 种物体有n !种，第二种物体有n !种，以此类推1 2例：有3个红球，2个白球，把这五个球排成一行，问有多少 种排法？红球和红球没有区别，白球和白球没有区别答：一共有10种，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa五、排列恒等式的证明：—(n _m 1)A m-1n证明:右边=(n —* +1)(n —m'+l)! =(n Im )! = A左边=右边(n —1)证明：右边—n _m " (n_m _ 1)! — (n_m )!—— Amn左边=右边③ A m = nA m -1n n — 1证明：右边二n (n —1)! A m(n _ m )! ( n _ m )! n左边=右边nAnn二 An+1 _ Ann+1 n证明：右边二 An 1 - An 二(n + 1)L n != (n+1) n!- n ! = nn ! = nAnn 1 n n右边=左边A m A m + mA m Tn +1 n n证明：右边二 n! + n! _(n-m + 1)n!-m・n!_ (n +1)!(n — m)! (n — m +1)! (n — m +1)! (n — m +1)! n1*22!十3.3!+…+ n n !_(J1)!」证明：左边=(2-1)1! + (3-1) 2! + (4-1) 3!+…(n+1—l)n!=2!-1!+3!-2!+4!-3!・・・(n+1)!-n!=(n+1)!-1!=右边六、组合恒等式的证明首先明弄清组合的两个性质公式：互补性质：类计数原理根据分类计数原理:证明：ml cm 1 =n-m n(m+ 1)n!(n-m )(m + 1)!(n _m _ 1)!n!m !(n -m)!n — m+ 1厂 _ n—m+1 n! n!C m 1 C mm n m (m — 1)!(n—m+1)! m !(n -m)! n证明：右边=nCm Cmn-m n1 n-m m!(n-m-1)! m!(n-m)! nn (n-1)!n!证明：n (n _ 1)! n ! — — C m右边二 m •(m _1)!( n _m )! 一 m !(n _m )! 一 n 二左边证明：根据组合性质，左边各式可写成：C r = c r 1 r r+1C r C r+1 _ c r+1r+1 r+2 r+1C r C r+1 _ c r+1r+2 r+3 r+2C r C r+1 _ C r+1r+3 r+4 r+3C r C r+1 _ C r+1〃一1 n n— 1Cr 二 Cr+1_ Cr+1n n+1 n左右两边相加即得：Cr+Cr +Cr C r -C r^ 1r r+1 r+2 n n+1⑥证明：用数学归纳法证明。

1) 当n =1时，co+ Ci = 2 = 2i所以等式成立1 12) 假设n二k时，(k21,kWN*)时等式成立即：Co+ C1 +C2+・・・+Ck 二2kk k k k当n=k+1时，C 0 C1 C 2 Ck C k：1k 1 k 1 k 1 k 1 k 1—C0 (C0 + C1) + (C1 + C2) — • + (Ck 1 + Ck) + C 叮1k 1 k k k k k k k 1=(C 0 + C 1 + C 2 +…+Ck) + (C 0 + C 1 + C 2 +…+Ck)k k k k k k k k二 2・2k二 2 k* 1・••等式也成立由1）、2）得，等式对neN*都成立也可用二项式定理证明（略）⑦证明：用归纳法同上（略）也可利用上述结论证明（略）本课件尽量避开用二项式定理，但这比较简单，暂且用一下:、设 a 二C 1 +C 3 +C 5 + •. •^设 n n nb 二C o +C 2 +C 4 +…n n n由（l + l）n 可得：a+b = 2n=2 X 2n-1由 （1-1） n 可得 a-b=O••• a=b=2n-i （不懂的去学学二项式定理）⑧证明：由mCm二nCm「1可得：（还记得这个恒等式吗，不记得就回过头去看③的证明）n n 1左边=rC o nC1 nC 2 nC3 nC n-1n~1 n~1 n~1 n~1 n~1二 n C o +C1 +C 2 _|_C 3 C n-1）n~1 n~1 n~1 n~1 n~1二 n・2n-1注：同时利用了⑥的结论。

rWmin{m用二项式定理证明太麻烦了能偷懒就不要太勤快了观察左边的每一项，发现均是分别从m个不同素和n个不同元素中取 r 个元素的一个组合，其各项之和就是所有取法，即所有组合 数其所有组合数当然等于右边⑩还是用偷懒法：根据第⑨的结论并结合组合的互补性质，若r=m=n即得些结论。