排列组合公式及恒等式推导、证明(word 版)说明:因公式编辑需特定的公式编辑插件,不管是word 还是pps 附带公式编辑经常是出错用不了。
下载此word 版的,记得下载MathType 公式编辑器哦,否则乱码一堆。
如果想偷懒可下截同名的截图版。
另外,还有PPt 课件(包含了排列组合的精典解题方法和精典试题)供学友们下载。
一、排列数公式:!(1)(2)(1)()!mn n A n n n n m n m(1)(1)321n n A n n n推导:把n 个不同的元素任选m 个排次序或n 个全排序,按计数原理分步进行:第一步,排第一位: 有 n 种选法; 第二步,排第二位: 有(n-1) 种选法; 第三步,排第三位: 有(n-2) 种选法; ┋第m 步,排第m 位: 有(n-m+1)种选法; ┋最后一步,排最后一位:有 1 种选法。
根据分步乘法原理,得出上述公式。
二、组合数公式:(1)(2)(1)!!!()!m m n nm mA n n n n m n CA m m n m1nn C推导:把n 个不同的元素任选m 个不排序,按计数原理分步进行: 第一步,取第一个: 有 n 种取法; 第二步,取第二个: 有(n-1) 种取法; 第三步,取第三个: 有(n-2) 种取法; ┋第m 步,取第m 个: 有(n-m+1)种取法; ┋最后一步,取最后一个:有 1 种取法。
上述各步的取法相乘是排序的方法数,由于选m 个,就有m!种排排法,选n 个就有n!种排法。
故取m 个的取法应当除以m!,取n 个的取法应当除以n!。
遂得出上述公式。
证明:利用排列和组合之间的关系以及排列的公式来推导证明。
将部分排列问题m n A 分解为两个步骤:第一步,就是从n 个球中抽m 个出来,先不排序,此即定义的组合数问题m n C ;第二步,则是把这m 个被抽出来的球全部排序,即全排列m m A 。
根据乘法原理,m m m n n m A C A 即:(1)(2)(1)!!!()!m m n nm mA n n n n m n CA m m n m组合公式也适用于全组合的情况,即求 C(n, n)的问题。
根据上述公式,C(n, n) = n!/n!(n-n)! = n! / n!0! = 1。
这一结果是完全合理的,因为从n 个球中抽取所有n 个出来,当然只有1种方法。
三、重复组合数公式:重复组合定义:从n 个不同的元素中每次取一个,放回后再取下一个,如此连续m 次所得的组合。
重复组合数公式:1m m n n m R C (m 可小于、大于、等于n,n ≥1) 推导:可以把该过程看作是一个“放球模型”:n 个不同的元素看作是n 个格子,其间一共有(n-1)块相同的隔板,用m 个相同的小球代表取m 次;则原问题可以简化为将m 个不加区别的小球放进n 个格子里面,问有多少种放法;这相当 于m 个相同的小球和(n-1)块相同的隔板先进行全排列:一共有(m+n-1)!种排法,再由于m 个小球和(n-1)块隔板是分别不加以区分的,所以除以重复的情况:m !*(n-1)! 1(1)!!(1)!m n m m n C m n四、不全相异的全排列1(1)mnn mA右边=!!(1)(1)!()!m nn n nmA nm n m 左边=右边1mmnn n A A nm证明:右边=(1)!(1)!()!m nnn n A nmn m n m左边=右边11mm n n A nA证明:右边=(1)!!()!()!mnn n nA nm n m②③左边=右边11n n nn n n nA A A证明:右边=11(1)!!(1)!!!n n nnn n A A n n n n n n n nA右边=左边11m mmn nnA A mA证明:右边=1!!(1)!!(1)!()!(1)!(1)!(1)!m n n n n m n m n n mA n m n m n m n m1!22!33!!(1)!1n n n证明:左边=(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! =右边 六、组合恒等式的证明首先明弄清组合的两个性质公式:④⑤⑥互补性质:取出有多少种,剩下就有多少种 mnmn n C C 11m m mn n n C C C根据分类计数原理:要么含有新加元素要么不含新加元素1111m mnnm n m C C n mm证明:111(1)!!()(1)!(1)!!()!11!!(1)!(1)!!()!mmnn mmnn m m n n C C n mn m m n m m n m n m n m n n C C mm m n m m n m证明:右边=1(1)!!!(1)!!()!m mn n n nn n CC n mn m m n m m n m证明: 右边=(1)!!(1)!()!!()!m nn n n C m m n m m n m=左边证明:根据组合性质,左边各式可写成:1n n Cnm11m n n C m⑤1121rr r r r rr r nn C CCCC111112111232113431111111r r r r r rr r r r rr rr r r r r r r r r r rrn n n rr rn n n C C C C C C C C C C C C C C C C C左右两边相加即得:1121r r r r r r r r n n C C C C C证明:用数学归纳法证明。
1)当n=1时,0111122C C 所以等式成立。
2)假设n=k 时,(k≥1,k∈N*)时等式成立。
即:0122kkk k k k C C C C当n=k+1时,0121111110011211110120121()()()()()222kk k kk k k kk k k k k k k k k k k k k k k k k k k k k kC C C C C C C C C C C C C C C C C C C C C∴等式也成立由1)、2)得,等式对n∈N*都成立。
⑥ 012n nnnnC CC也可用二项式定理证明(略)证明:用归纳法同上(略) 也可利用上述结论证明(略) 本课件尽量避开用二项式定理,但这比较简单,暂且用一下: 设13524n n nnnna C C Cb C C C由(1+1)n 可得:a+b=2n =2×2n-1 由(1-1)n 可得a-b=0 ∴a=b=2n-1 (不懂的去学学二项式定理)证明: 由11m mm n n C nC 可得:(还记得这个恒等式吗,不记得就回过头去看③的证明)左边012311111101231111111=n n n n n n()n 2n n n n n n n n n n n n n C C C C C C C C C C注:同时利用了⑥的结论。
⑦ 13502412n nnnnnnC C C C C C ⑧ 1231232n n nnnnCCCnCn ⑨ 0110r r r r m nm nm nn mC CC CC CC用二项式定理证明太麻烦了。
能偷懒就不要太勤快了。
观察左边的每一项,发现均是分别从m 个不同素和n 个不同元素中取r 个元素的一个组合,其各项之和就是所有取法,即所有组合数。
其所有组合数当然等于右边。
还是用偷懒法:根据第⑨的结论并结合组合的互补性质,若r=m=n 即得些结论。
r ≤min{m,n}⑩ 021222()()()n n nnnnC C C C。