排列组合公式及恒等式推导、证明(word版)
根据分步乘法原理，得出上述公式。
二、组合数公式：
CnmCnnAnmmAm1
n(n1)(n2)(nm1)m!n!m!(nm)!
推导：把n个不同的元素任选m个不排序，按计数原理分步进行： 第一步，取第一个： 有 n 种取法； 第二步，取第二个： 有（n-1） 种取法； 第三步，取第三个： 有（n-2） 种取法； ┋
第m步，取第m个： 有（n-m+1）种取法； ┋
最后一步，取最后一个：有 1 种取法。
上述各步的取法相乘是排序的方法数，由于选m个，就有m!种排排法，选n个就有n!种排法。故取m个的取法应当除以m!,取n个的取法应当除以n!。遂得出上述公式。
证明：利用排列和组合之间的关系以及排列的公式来推导证明。 将部分排列问题Anm分解为两个步骤：
第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题Cnm；
m第二步，则是把这m个被抽出来的球全部排序，即全排列Am。
m根据乘法原理，AnmCnmAm 即：
CmnAnmmAmn(n1)(n2)(nm1)n!m!m!(nm)!
组合公式也适用于全组合的情况，即求 C(n, n)的问题。根据上述公式，
C(n, n) = n!/n!(n-n)! = n! / n!0! = 1。 这一结果是完全合理的，因为从n个球中抽取所有n个出来，当然只有1种方法。
三、重复组合数公式：
重复组合定义:从n个不同的元素中每次取一个，放回后再取下一个，如此连续m次所得的组合。
重复组合数公式：RnmCnmm1 （m可小于、大于、等于n,n≥1） 推导：可以把该过程看作是一个“放球模型”：
n个不同的元素看作是n个格子，其间一共有（n-1）块相同的隔板，用m个相同的小球代表取m次；则原问题可以简化为将m个不加区别的小球放进n个格子里面，问有多少种放法；这相当 于m个相同的小球和（n-1）块相同的隔板先进行全排列：一共有（m+n-1）！种排法，再由于m个小球和（n-1）块隔板是分别不加以区分的，所以除以重复的情况：m！*（n-1）！
于是答案就是：Rnm(mn1)!Cnmm1 m!(n1)!四、不全相异的全排列 在不全相异的n个物体中，假设有n1个物体是相同的，n2个五题是相同的，……，nk个物体是相同的。n个物体中不相同的物体种类数一共有k种。那么，这些物体的全排列数是n!/(n1!n2!…nk!)。 可以想成：n个物体直接全排列，排列完了以后，去重，第一种物体有n1!种，第二种物体有n2!种，以此类推。 例：有3个红球，2个白球，把这五个球排成一行，问有多少种排法？红球和红球没有区别，白球和白球没有区别。 答：一共有10种， aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。 五、排列恒等式的证明： ①Anm(nmmm1)An1 n!m1)!n!(nm)!mAn 证明：右边=(n1)(n 左边=右边
②
mAnnnmmAn1
n!(nm)!mAn 证明：右边=nnm(n1)(nm1)!
左边=右边
mA③ n
m1nAn1
1)!m)!n!(nm)!mAn
n 证明：右边=n((n
左边=右边
④
nAnnAn1n1An11nn证明：右边=An
⑤
Ann(n1)!n!(n1)n!n!nn!nAnn
右边=左边
mAn1mAnmmAn1
n!(nm1)n!mn!(n1)!Anm1(nm1)!(nm1)!(nm1)!
⑥ 1!22!33!
（n+1-1）n!
=2!-1!+3!-2!+4!-3!…(n+1)!-n! =(n+1)!-1！ =右边 六、组合恒等式的证明
首先明弄清组合的两个性质公式：
CnmCnnm证明：右边=n!(nm)!m
nn!(n1)!1
证明：左边=(2-1)1！+（3-1）2！+（4-1）3!+…
1互补性质：取出有多少种，剩下就有多少种
分类计数原Cnm1CnmCnm根据分类计数原理:要么含有新加元素要么不含新加元素
m① Cn m1mCnnm11nm1mCnm1m1mCnnm(m1)n!n!Cnm(nm)(m1)!(nm1)!m!(nm)!1 证明：
nm1mCnmnm1n!n!Cnmm(m1)!(nm1)!m!(nm)!
② Cmnnn明
mmCn1
证
nnmCmn1：右边
=
(n1)!n!Cnmnmm!(nm1)!m!(nm)! nm1Cn1mn③ Cm n 证明： 右边=
n(n1)!m(m1)!(nm)!n!m!(nm)!mCn
=左边
⑤C
rrCrr1Crr2CrnCr1n1
证明：根据组合性质，左边各式可写成：
CrrCrrCrr1112Crr1Crr2Crr11121Crr31Crr3Crr14Crr3CrrCnrCrn
1CnrCr1n11CnrCr1n11
左右两边相加即得：
CrrCrr1Crr20n1CnrCnr1C ⑥
证明：
C1n
Cnn2n 用数学归纳法证明。
1）当n=1时，C10C11221所以等式成立。 2）假设n=k时，（k≥1，k∈N*）时等式成立。 即：Ck0Ck1Ck2 当n=k+1时，
1Ck01Ck1Ckk2
kCk21Ckk1Ckk1111Ck01(Ck0Ck)(CkCk2)(Ckk1Ckk)Ckk11 (Ck0Ck1Ck222k2k11Ckk)(Ck0CkCk2Ckk)
∴等式也成立
由1)、2)得，等式对n∈N*都成立。 也可用二项式定理证明（略）
⑦ C1nC3nC5nC0nC2nC4n2n1
证明：用归纳法同上（略） 也可利用上述结论证明（略）
本课件尽量避开用二项式定理，但这比较简单，暂且用一下： 设
135aCnCnCn0n2n4nbCCC
由（1+1）n可得：a+b=2n=2×2n-1 由（1-1）n可得a-b=0 ∴a=b=2n-1 (不懂的去学学二项式定理)
⑧ C1n2CnCnm112n3C3nnCnnn2n1 证明： 由mCmn可得:（还记得这个恒等式吗，不记
得就回过头去看③的证明） 左边
=nCn01nCn11nCn21nCn31nCnn11Cnn11)
n(Cn01Cn11Cn21Cn31n2n1
注：同时利用了⑥的结论。
⑨ CCrm0nCCr1m1nCC0mrnCrnm
r≤min{m,n}
用二项式定理证明太麻烦了。能偷懒就不要太勤快了。 观察左边的每一项，发现均是分别从m个不同素和n个不同元素中取r 个元素的一个组合，其各项之和就是所有取法，即所有组合数。其所有组合数当然等于右边。
(C ⑩
02 n)(C)12n(C)n2nCn2n还是用偷懒法：根据第⑨的结论并结合组合的互补性质，若r=m=n即得些结论。
