《排列组合公式及恒等式推导、证明》由会员分享，可在线阅读，更多相关《排列组合公式及恒等式推导、证明（9页珍藏版）》请在金锄头文库上搜索。
1、排列组合公式及恒等式推导、证明（word 版）说明：因公式编辑需特定的公式编辑插件，不管是word 还是 pps 附带公式编辑经常是出错用不了。下载此word 版的，记得下载MathType 公式编辑器哦，否则乱码一堆。如果想偷懒可下截同名的截图版。另外，还有PPt 课件（包含了排列组合的精典解题方法和精典试题）供学友们下载。一、排列数公式：Anm = n(n - 1)(n - 2)L(n - m +1) =n!(n - m)!n= n(n -1)(n -1)32 1AnL创推导：把 n 个不同的元素任选m个排次序或 n 个全排序，按计数原理分步进行 ：第一步，排第一位：有n种选法；第二步，排
2、第二位：有（n-1 ） 种选法；第三步，排第三位：有（n-2 ） 种选法；第 m步，排第 m位： 有（n-m+1）种选法；最后一步，排最后一位：有1种选法。根据分步乘法原理，得出上述公式。二、组合数公式：m= n(n - 1)(n - 2)L (n - m +1) =Cnm = Anmn!Amm!m!(n - m)!C nn =1推导：把 n 个不同的元素任选m个不排序，按计数原理 分步进行 ：第一步，取第一个：有n种取法；第二步，取第二个：有（n-1 ） 种取法；第三步，取第三个：有（n-2 ） 种取法；第 m步，取第 m个：有（n-m+1）种取法；最后一步，取最后一个：有1种取法。上述各步
3、的取法相乘是排序的方法数，由于选m个，就有m!种排排法，选 n 个就有 n! 种排法。故取 m个的取法应当除以 m!, 取 n 个的取法应当除以 n! 。遂得出上述公式。证明：利用排列和组合之间的关系以及排列的公式来推导证明。将部分排列问题Anm 分解为两个步骤：第一步，就是从n 个球中抽 m个出来，先不排序，此即定义的组合数问题 C nm ；第二步，则是把这m个被抽出来的球全部排序，即全排列Amm 。根据乘法原理， Anm = C nm Amm即：m= n(n - 1)(n - 2)L (n - m+1)Cnm = Anm=n!Amm!m!(n - m)!组合公式也适用于全组合的情况，即求C
4、(n,n) 的问题。根据上述公式，C(n,n)=n!/n!(n-n)!=n!/n!0!=1。这一结果是完全合理的，然只有 1 种方法。因为从n 个球中抽取所有n 个出来，当三、重复组合数公式：重复组合 定义 : 从 n 个不同的元素中每次取一个，放回后再取下一个，如此连续 m次所得的组合。重复组合数公式：R nm = C nm+ m- 1（m可小于、大于、等于n,n 1）推导： 可以把该过程看作是一个“放球模型”：n 个不同的元素看作是 n 个格子，其间一共有（ n-1 ）块相同的隔板，用 m个相同的小球代表取 m次；则原问题可以简化为将 m个不加区别 的小 球放进 n 个格子里面， 问有 多
5、少 种放法 ；这相当于 m 个相同的小球和（ n-1 ）块相同的隔板先进行全排列：一共有（m+n-1）！种排法，再由于 m个小球和（ n-1 ）块隔板是分别不加以区分的，所以除以重复的情况： m！* （n-1 ）！于是答案就是：R m = ( m + n - 1)! =C mnn +m - 1四、不全相异的全排列在不全相异的 n 个物体中，假设有 n1 个物体是相同的， n2 个五题是相同的， nk 个物体是相同的。 n 个物体中不相同的物体种类数一共有 k 种。那么，这些物体的全排列数是 n!/(n 1!n 2! nk!) 。可以想成： n 个物体直接全排列，排列完了以后，去重，第一种物体有
6、 n1! 种，第二种物体有 n2! 种，以此类推。例：有 3 个红球， 2 个白球，把这五个球排成一行，问有多少种排法？红球和红球没有区别，白球和白球没有区别。答：一共有 10 种，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的证明： A nm = ( n - m + 1) A nm - 1证明：右边 = ( n - m + 1)n !=n != A nm( n - m + 1)!( n - m )!左边 =右边A nm=nA nm- 1n-m证明n?( n - 1)n != A nm：右边 = n -m
7、( n - m - 1)!( n - m )!左边 =右边m= nAm - 1A nn - 1证明：右边 = n( n - 1 )!=n != A nm( n - m )!( n - m )!左边 =右边 nAnn = Ann+11 - Ann证明：右边 =Ann+11 - Ann = (n +1)!- n! = (n +1)gn!- n! = ngn! = nAnn右边 =左边 A nm+1 = A nm + mA nm - 1证明：右边 =n!+mn!= (n- m +1)n!- mgn! =(n +1)! = Anm+1(n - m)!(n - m +1)!(n - m +1)!(n -
8、 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 +1m +1(m +1)n !n !mn - mC n =m !( n - m)!= C n(n - m)( m +1)!(n - m - 1)!证明：n - m +1C nm - 1
9、= n - m +1gn !=n != C nmmm(m - 1)!(n - m +1)!m !( n - m)!证明：右边 =n Cnm-1 =n g(n -1)!=n!=Cnmn - mn - m m!(n - m-1)!m!(n- m)!证明：n g( n- 1)!=n != Cnm右边 = m( m - 1)!(n - m )!m !( n -m )!=左边证明：根据组合性质，左边各式可写成：rr +1C r =C r +1rr +1C r +1 =C r +2rr +1C r +2 = C r +3rr +1C r +3 = C r +4M- C rr +11- C rr+21- C
10、 rr+31C nr - 1 = C nr +1 - C nr -+11C nr =C nr +11 - C nr +1左右两边相加即得：Crr +Crr+1 +Crr+2 +L +Cnr =Cnr+11证明：用数学归纳法 证明。1 ）当 n=1 时， C 10 +C 11 = 2 = 21 所以等式成立。2 ）假设 n=k 时，（ k1，kN*）时等式成立。k即： C k0 +C k1 +C k2 +L +C kk = 2当 n=k+1 时，012kk +1C k +1+C k +1+C k +1+L +C k +1+C k +100112k - 1kk +1= C k +1+ (C k+C
11、 k) + (C k+C k) +L + (C k+C k) +C k +1= (C k0 +C k1 +C k2 +L +C kk ) + (C k0 +C k1 +C k2 +L +C kk )= 2g2k= 2k +1等式也成立由 1) 、2) 得，等式对 nN*都成立。也可用二项式定理证明（略）证明：用归纳法同上（略）也可利用上述结论证明（略）本课件尽量避开用二项式定理，但这比较简单，暂且用一下：135设 a =C n +C n +C n +L024b =C n +C n +C n +L由（ 1+1）n 可得： a+b=2n=22n-1由（ 1-1 ）n 可得 a-b=0a=b=2n-1(不懂的去学学二项式定理)证明：m m - 1由 mC n = nC n - 1 可得 : （还记得这个恒等式吗，不记得就回过头去看的证
