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

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

2、法原理，得出上述公式。二、组合数公式：推导：把n个不同的元素任选m个不排序，按计数原理 分步进行：第 f,取第个：有n种取法；第二步，取第二个：有n-1种取法；第三步，取第三个：1 1有n-2 种取法；:第m步，取第m个：1 1有n-m+1种取法；:取后，步，取取后一个:有1种取法。上述各步的取法相乘是排序的方法数，由于选m个，就有m!种排排法，选n个就有n!种排法。故取m个的取法应当除以m!,取n个的取法应当除以n!。遂得出上述公式。证明：利用排列和组合之间的关系以及排列的公式来推导证明。将局部排列问题Ann分解为两个步骤：第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题第二

3、步，那么是把这m个被抽出来的球全部排序，即全排列A：o根据乘法原理，Am=c；Am即：组合公式也适用于全组合的情况，即求？C(n,?n)的问题。根据上述公式，C(n,?n)?=?n!/n!(n-n)!?=?n!?/?n!0!?=?1。这一结果是完全合理的，因为从n个球中抽取所有n个出来，当然只有1种方法。？三、重复组合数公式：重复组合定义：从n个不同的元素中每次取一个，放回后再取下一个，如此 连续m次所得的组合。重复组合数公式：Rnc+m-i(m可小于、大于、等于n,n 1)推导：可以把该过程看作是一个“放球模型：n个不同的元素看作是n个格子，其间一共有(n-1 )块相同的隔板，用m个相同的小

4、球代表取m次；那么原问题可以简化为将m个不加区别的小球放进n个格子里面，问有多少种放法；这相当于m个相同的小球和(n-1 )块相同的隔板先进行全排列：一共有(m+n-1) !种排法，再由于m(n-1)_ n证明：右边=n - m (n - m - 1)!n !(n - m )!. m=An个小球和(n-1 )块隔板是分别不加以区分的，所以除以重复的情况：m! *(n-1 ) !于是答案就是：Rnm=(m+n-1)!=cn-1m !(n - 1)!四、不全相异的全排列在不全相异的n个物体中，假设有ni个物体是相同的，n2个五题是相同,nk个物体是相同的。n个物体中不相同的物体种类数一共有k种。那

5、么，这些物体的全排列数是n!/(n1!n2! -nk!)。可以想成：n个物体直接全排列，排列完了以后，去重，第一种物体有nJ种，第二种物体有 田!种，以此类推。例：有3个红球，2个白球，把这五个球排成一行，问有多少种排法红球和红球没有区别，白球和白球没有区另U。答：一共有10种,aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa五、排列恒等式的证明:mm - 1 An= (n - m + 1) An左边=右边mn _2)An= -An - m的,证明：右边=(n - m +1)&n !_m + 1)!( nn !-m

6、)!Anm左边=右边证明：右边(n - 1 )!n !Am=n(n - m )! = (n - m )! = An左边=右边n n+1 nnAn= An+i- An证明：右边n+1 nn=An+1- An= (n +1)!- n! = (n+1)gi!- n! =ngi! = nAn右边=左边5证明：右边=+mn!=(n-m+1)n!-mgi!=(n+1)!=A3(n- m)!(n- m+1)!(n- m+1)!(n- m+1)!61!+2?2! 3?3! L +n?n! (n+1)!- 1证明：左边=(2-1)1 ! + (3-1 ) 2! + (4-1 ) 3!+(n+1-1)n!=2!-

7、1!+3!-2!+4!-3!(n+1)!-n!=(n+1)!-1右边六、组合恒等式的证明首先明弄清组合的两个性质公式:m +1m+1n - m +1m-1卜版居:土出有多小种，C有多少种出+1+1叽m+1)n!nnmd -=mm=沼m-m-1=Cn+CnMmm mn!m 要么含有新加元(n -m(m+1并珈粗I !板辨新而元素要么不含新加元素=勇n-m+1m-1n - m +1n!n!mCn=g-=-=Cnmm (m - 1)!(n - m +1)! m !(n - m)!/m mCnCn - ,1证明：右边=nCm=g ； if- =Cn- m n- m m!(n- m-1)! m!(n-

8、m)!Cmn证明:n(n - 1)!n：m一g=- =Cn右边= m (m - 1)!( n - m )! m !( n - m )!=左边rCr+ C证明：根据组合性质，左边各式可写成:左右两边相加即得: C + C1+ L + Cnn证明:用数学归纳法证明。1当n=1时，Ci0+Ci1=2 = 21所以等式成立。2假设n=k时，k 1 , k N*时等式成立即：C+Ck+C：+L +Ck=2kn!r+Cr+|+Cr=Cr+1r +1+ Cr + 2+ L +CnCn +1当n=k+1时,0 1 2 k k+1Ck+1+Ck+1+Ck+1+L +Ck+1+Ck+1=C0+ (C0+C1) +

9、 (C1+C2)+1 +(Ck-1+Ck)+Ck+1=Ck+1+(Ck+Ck) + (Ck+Ck)+L +(Ck+Ck)+Ck +1012k012k= (Ck+Ck+Ck+L +Ck)+(Ck+Ck+Ck+L +Ck)k= 2g2=2k+1等式也成立由1、2得，等式对n N*都成立。也可用二项式定理证明略=2n-1也可利用上述结论证明略本课件尽量避开用二项式定理，但这比拟简单，暂且用一下：设a=C：+C：+C：+Lb=C：+C；+C：+L由1+1n可得：a+b=Z=2x2n-1由1-1n可得a-b=0a=b=2-1不懂的去学学二项式定理 C；+2C：+3C；+L +nC；=ng2n-1nnnn证明：由mCm=nCnV可得：还记得这个恒等式吗，不记得就回过头去看的证明左边注：同时利用了的结论富己135|024|昂KMX(略)Cn Cn CnPr 0 r-V10 r=广rCmCnCmCnLCmCnCn+mr帝inm,用二项式定捶证明太麻烦了。能偷懒就不要太勤快了。n观察左边的每一项，发现均是