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

完好版摆列组合公式及恒等式推导、证明word版摆列组合公式及恒等式推导、证明（ 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 种选法；第二步，排第二位： 有（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 种取法。

上述各步的取法相乘是排序的方法数，由于选 m个，就有m!种排排法，选 n 个就有 n! 种排法故取 m个的取法应当除以 m!, 取 n 个的取法应当除以 n! 遂得出上述公式证明：利用摆列和组合之间的关系以及摆列的公式来推导证明将部分摆列问题 Anm 分解为两个步骤：第一步，就是从 n 个球中抽 m个出来，先不排序，此即定义的组合数问题 C nm ；第二步，则是把这 m个被抽出来的球全部排序，即全摆列 Amm 依照乘法原理， Anm = C nm Amm 即：m=Anmn(n- 1)(n - 2)L (n - m+1)n!Cnm==Amm!m!(n - m)!组合公式也适用于全组合的情况， 即求 C(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 个格子里面，问有多少种放法；这相当于 m 个相同的小球和（ n-1 ）块相同的隔板先进行全摆列：一共有（m+n-1 ）！种排法，再由于 m 个小球和（ n-1 ）块隔板是分别不加以区分的，所以除以重复的情况： m ！* （n-1 ）！于是答案就是： R m = ( m + n - 1)! =C mn n +m - 1四、不全相异的全摆列在不全相异的 n 个物体中，假 有 n1 个物体是相同的， n2 个五 是相同的，⋯⋯， nk 个物体是相同的。

n 个物体中不相同的物体种 数一共有 k 种那么， 些物体的全摆列数是 n!/(n 1!n 2! ⋯nk!) 可以想成： n 个物体直接全摆列，摆列完了今后，去重，第一种物体有 n1! 种，第二种物体有 n2! 种，以此 推例：有 3 个 球， 2 个白球，把 五个球排成一行， 有多少种排法？ 球和 球没有区 ，白球和白球没有区 答：一共有 10 种，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa 五、摆列恒等式的 明：① A nm = ( n - m + 1) A nm - 1n !n !m证明：右边 = ( n - m + 1)( n - m + 1)!=( n - m )!= A n左 =右 ② A nm=nmA nm- 1n -证明 ： 右 = nn?( n - 1)n != A nm- m( n - m - 1)!( n - m )!左 =右 m= nAm - 1③A nn - 1( n- 1)!n !m 明：右 = n=( n - m )!= A n( 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 - 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 ！= 右 六、 合恒等式的 明第一明弄清 合的两个性 公式：C nm = C nn - m互补性质： 取出有多少种，剩下就有多少种分类计数原C nm+1 =C nm +C nm - 1依照分类计数原理 :要么含有新加元素要么不含新加元素① C nm = m +1 C nm +1 = n - m +1C nm - 1n - mmm +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 = n - m +1gn !=n != C nmmm(m - 1)!(n - m +1)!m !( n - m)!m=nm② C n-C n - 1nm证明：右边 =nCnm-1 =ng(n - 1)!=n!=Cnmn - mn - m m!(n - m- 1)!m!(n - m)!③ Cm=nCm- 1nmn- 1证明：ng( n- 1)!=mn != Cnm右边 = m( m - 1)!(n-m )!!( n -m )!=左边rrrrr +1⑤C r+ C r +1+ C r + 2+ L + C n= C n +1证明：依照组合性质，左边各式可写成：r r +1C r =C r +1r r +1C r +1 =C r +2r r +1C r +2 = C r +3r r +1C r +3 = C r +4M- C rr ++11- C rr++21- C 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⑥ C n0 + C n1 + L + C nn = 2 n证明：用数学归纳法 证明。

1）当 n=1 时， C 10 +C11= 2 = 21 所以等式成立2）假设 n=k 时，（k ≥ 1 ， k ∈ N* ）时等式成立即：C k0 +C k1 +C k2 +L +C kkk= 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 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= 2。