排列组合公式及恒等式推导、证明（word 版）
说明：因公式编辑需特定的公式编辑插件，不管是word 还是pps 附带公式编辑经常是出错用不了。下载此word 版的，记得下载MathType 公式编辑器哦，否则乱码一堆。如果想偷懒可下截同名的截图版。另外，还有PPt 课件（包含了排列组合的精典解题方法和精典试题）供学友们下载。
一、排列数公式：
A n m =n (n -1)(n -2) (n -m +1) =
n ! (n -m )!
A n n =n (n -1)(n -1) 3创21
推导：把n 个不同的元素任选m 个排次序或n 个全排序，按计数原理分步进行：
第一步，排第一位： 有 n 种选法； 第二步，排第二位： 有（n-1） 种选法； 第三步，排第三位： 有（n-2） 种选法； ┋
第m 步，排第m 位： 有（n-m+1）种选法； ┋
最后一步，排最后一位：有 1 种选法。 根据分步乘法原理，得出上述公式。
二、组合数公式：
A n m n (n -1)(n -2) (n -m +1) n !
C =m ==
A m m ! m !(n -m )!
m n
C n n =1
推导：把n 个不同的元素任选m 个不排序，按计数原理分步进行： 第一步，取第一个： 有 n 种取法； 第二步，取第二个： 有（n-1） 种取法； 第三步，取第三个： 有（n-2） 种取法； ┋
第m 步，取第m 个： 有（n-m+1）种取法； ┋
最后一步，取最后一个：有 1 种取法。
上述各步的取法相乘是排序的方法数，由于选m 个，就有m! 种排排法，选n 个就有n! 种排法。故取m 个的取法应当除以m!, 取n 个的取法应当除以n! 。遂得出上述公式。
证明：利用排列和组合之间的关系以及排列的公式来推导证明。 将部分排列问题A n m 分解为两个步骤：
第一步，就是从n 个球中抽m 个出来，先不排序，此即定义的组合数问题C n m ；
m 第二步，则是把这m 个被抽出来的球全部排序，即全排列A m 。
m 根据乘法原理，A n m =C n m A m 即：
A n m n (n -1)(n -2) (n -m +1) n ! C =m ==
A m m ! m !(n -m )!
m n
组合公式也适用于全组合的情况，即求 C(n, n) 的问题。根据上述公式，
C(n, n) = n!/n!(n-n)! = n! / n!0! = 1。 这一结果是完全合理的，因为从n 个球中抽取所有n 个出来，当然只有1种方法。
三、重复组合数公式：
重复组合定义:从n 个不同的元素中每次取一个，放回后再取下一个，如此连续m 次所得的组合。
重复组合数公式：R n m =C n m +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）！
左边=右边
② A n
m
=
n m
A n -1 n -m
n (n -1) ?
证明：右边=n -m (n -m -1)!
n ! m
=A n
(n -m )!
左边=右边
m m -1
A =nA ③ n n -1
证明：右边=n
(n -1)! n ! m
==A n
(n -m )! (n -m )!
左边=右边
④
+1n
nA n n =A n n +-A 1n
n +1n n 证明：右边=A n +1-A n =(n +1)! -n ! =(n +1) n ! -n ! =n n ! =nA n
⑤
右边=左边
m m m -1A n =A +mA +1n n
A
m m
=n +1证明：右边n
=A +(n -m )!
m -n !
+m
n ! (n -m +1) n ! -m n ! (n +1)!
===A n m +1
(n -m +1)! (n -m +1)! (n -m +1)!
⑥
1! +2? 2! 3? 3! +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 n m =C n n -m
C n m +1=C n m +C n m -1
互补性质：取出有多少种，剩下就有多少种
根据分类计数原理:要么含有新加元素要么不含新加元素
m +1m +1(m +1) n ! n !
C n ===C n m
n -m (n -m )(m +1)!(n -m -1)! m !(n -m )!
证明：
n -m +1m -1n -m +1n ! n !
C n ===C n m
m m (m -1)!(n -m +1)! m !(n -m )!
n n (n -1) ! n ! m
C n -1===C n m
n -m n -m m ! (n -m -1) ! m n ! -(m ) !
证明：右边=
证明： 右边=
n (n -1) ! n ! m
==C n m (m -1) ! n (-m ) ! m -! n (m ) !
=左边
+C ⑤C
r r r r +1
+C
r
r +2
+ +C =C
r n r +1n +1
证明：根据组合性质，左边各式可写成：
+1
C r r =C r r +1
+1r +1C r r +1=C r r +-C 2r +1+1r +1C r r +2=C r r +-C 3r +2+1r +1C r r +3=C r r +-C 4r +3
1C n r -1=C n r +1-C n r -+1+1r +1
C n r =C n r +-C 1n
左右两边相加即得：
r r r r r +1C +C +C + +C =C r +1r +2n n +1 r
C ⑥ 证明：
n
+C
1n
+ +C
n n
=2
n
用数学归纳法证明。
1）当n=1时，C 10+C 11=2=21所以等式成立。 2）假设n=k时，（k≥1，k∈N*）时等式成立。 即：C k 0+C k 1+C k 2+ +C k k =2
k
当n=k+1时，
12k k +1
C k 0+1+C k +1+C k +1+ +C k +1+C k +1
11+1=C k 0+1+(C k 0+C k ) +(C k +C k 2) + +(C k k -1+C k k ) +C k k +1
=(C k 0+C k 1+C k 2+ +C k k ) +(C k 0+C k 1+C k 2+ +C k k )
=2 2k =2k +1
∴等式也成立
由1) 、2) 得，等式对n∈N*都成立。 也可用二项式定理证明（略）
⑦C +C +C =C +C +C =2
1
n 3n 5n 0n 2n 4n
n -1
证明：用归纳法同上（略） 也可利用上述结论证明（略）
本课件尽量避开用二项式定理，但这比较简单，暂且用一下： 设
135
a =C n +C n +C n +
n
2n
4n
b =C +C +C +
由（1+1）n 可得：a+b=2n =2×2n-1 由（1-1）n 可得a-b=0 ∴a=b=2n-1 (不懂的去学学二项式定理)
2⑧ C +2C +3C + +nC =n
1
n 2n 3n n n
n -1
证明：
m
由m C n =nC n m --11可得:（还记得这个恒等式吗，不记得就回过头去看③的证明）
左边
=nC n 0-1+n C n 1-1+n C n 2-1+n C n 3-1+ n C n n --11
=n(C n 0-1+C n 1-1+C n 2-1+C n 3-1+ C n n --11) =n 2n -1
注：同时利用了⑥的结论。
⑨ C C +C C ++ +C C =C
r ≤min{m,
r m 0n r -11m n 0
m r n r n +m
用二项式定理证明太麻烦了。能偷懒就不要太勤快了。 n} 观察左边的每一项，发现均是分别从m 个不同素和n 个不同元素中取r 个元素的一个组合，其各项之和就是所有取法，即所有组合数。其所有组合数当然等于右边。
(C ⑩ ) +(C ) + +(C ) =C
02
n 12n n 2n n 2n
还是用偷懒法：根据第⑨的结论并结合组合的互补性质，若r=m=n即得些结论。
排列组合公式及恒等式推导、证明（word 版）
说明：因公式编辑需特定的公式编辑插件，不管是word 还是pps 附带公式编辑经常是出错用不了。下载此word 版的，记得下载MathType 公式编辑器哦，否则乱码一堆。如果想偷懒可下截同名的截图版。另外，还有PPt 课件（包含了排列组合的精典解题方法和精典试题）供学友们下载。
一、排列数公式：
A n m =n (n -1)(n -2) (n -m +1) =
n ! (n -m )!
A n n =n (n -1)(n -1) 3创21
推导：把n 个不同的元素任选m 个排次序或n 个全排序，按计数原理分步进行：
第一步，排第一位： 有 n 种选法； 第二步，排第二位： 有（n-1） 种选法； 第三步，排第三位： 有（n-2） 种选法； ┋
第m 步，排第m 位： 有（n-m+1）种选法； ┋
最后一步，排最后一位：有 1 种选法。 根据分步乘法原理，得出上述公式。
二、组合数公式：
A n m n (n -1)(n -2) (n -m +1) n !
C =m ==
A m m ! m !(n -m )!
m n
C n n =1
推导：把n 个不同的元素任选m 个不排序，按计数原理分步进行： 第一步，取第一个： 有 n 种取法； 第二步，取第二个： 有（n-1） 种取法； 第三步，取第三个： 有（n-2） 种取法； ┋
第m 步，取第m 个： 有（n-m+1）种取法； ┋
最后一步，取最后一个：有 1 种取法。
上述各步的取法相乘是排序的方法数，由于选m 个，就有m! 种排排法，选n 个就有n! 种排法。故取m 个的取法应当除以m!, 取n 个的取法应当除以n! 。遂得出上述公式。
证明：利用排列和组合之间的关系以及排列的公式来推导证明。 将部分排列问题A n m 分解为两个步骤：
第一步，就是从n 个球中抽m 个出来，先不排序，此即定义的组合数问题C n m ；
m 第二步，则是把这m 个被抽出来的球全部排序，即全排列A m 。
m 根据乘法原理，A n m =C n m A m 即：
A n m n (n -1)(n -2) (n -m +1) n ! C =m ==
A m m ! m !(n -m )!
m n
组合公式也适用于全组合的情况，即求 C(n, n) 的问题。根据上述公式，
C(n, n) = n!/n!(n-n)! = n! / n!0! = 1。 这一结果是完全合理的，因为从n 个球中抽取所有n 个出来，当然只有1种方法。
三、重复组合数公式：
重复组合定义:从n 个不同的元素中每次取一个，放回后再取下一个，如此连续m 次所得的组合。
重复组合数公式：R n m =C n m +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）！
左边=右边
② A n
m
=
n m
A n -1 n -m
n (n -1) ?
证明：右边=n -m (n -m -1)!
n ! m
=A n
(n -m )!
左边=右边
m m -1
A =nA ③ n n -1
证明：右边=n
(n -1)! n ! m
==A n
(n -m )! (n -m )!
左边=右边
④
+1n
nA n n =A n n +-A 1n
n +1n n 证明：右边=A n +1-A n =(n +1)! -n ! =(n +1) n ! -n ! =n n ! =nA n
⑤
右边=左边
m m m -1A n =A +mA +1n n
A
m m
=n +1证明：右边n
=A +(n -m )!
m -n !
+m
n ! (n -m +1) n ! -m n ! (n +1)!
===A n m +1
(n -m +1)! (n -m +1)! (n -m +1)!
⑥
1! +2? 2! 3? 3! +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 n m =C n n -m
C n m +1=C n m +C n m -1
互补性质：取出有多少种，剩下就有多少种
根据分类计数原理:要么含有新加元素要么不含新加元素
m +1m +1(m +1) n ! n !
C n ===C n m
n -m (n -m )(m +1)!(n -m -1)! m !(n -m )!
证明：
n -m +1m -1n -m +1n ! n !
C n ===C n m
m m (m -1)!(n -m +1)! m !(n -m )!
n n (n -1) ! n ! m
C n -1===C n m
n -m n -m m ! (n -m -1) ! m n ! -(m ) !
证明：右边=
证明： 右边=
n (n -1) ! n ! m
==C n m (m -1) ! n (-m ) ! m -! n (m ) !
=左边
+C ⑤C
r r r r +1
+C
r
r +2
+ +C =C
r n r +1n +1
证明：根据组合性质，左边各式可写成：
+1
C r r =C r r +1
+1r +1C r r +1=C r r +-C 2r +1+1r +1C r r +2=C r r +-C 3r +2+1r +1C r r +3=C r r +-C 4r +3
1C n r -1=C n r +1-C n r -+1+1r +1
C n r =C n r +-C 1n
左右两边相加即得：
r r r r r +1C +C +C + +C =C r +1r +2n n +1 r
C ⑥ 证明：
n
+C
1n
+ +C
n n
=2
n
用数学归纳法证明。
1）当n=1时，C 10+C 11=2=21所以等式成立。 2）假设n=k时，（k≥1，k∈N*）时等式成立。 即：C k 0+C k 1+C k 2+ +C k k =2
k
当n=k+1时，
12k k +1
C k 0+1+C k +1+C k +1+ +C k +1+C k +1
11+1=C k 0+1+(C k 0+C k ) +(C k +C k 2) + +(C k k -1+C k k ) +C k k +1
=(C k 0+C k 1+C k 2+ +C k k ) +(C k 0+C k 1+C k 2+ +C k k )
=2 2k =2k +1
∴等式也成立
由1) 、2) 得，等式对n∈N*都成立。 也可用二项式定理证明（略）
⑦C +C +C =C +C +C =2
1
n 3n 5n 0n 2n 4n
n -1
证明：用归纳法同上（略） 也可利用上述结论证明（略）
本课件尽量避开用二项式定理，但这比较简单，暂且用一下： 设
135
a =C n +C n +C n +
n
2n
4n
b =C +C +C +
由（1+1）n 可得：a+b=2n =2×2n-1 由（1-1）n 可得a-b=0 ∴a=b=2n-1 (不懂的去学学二项式定理)
2⑧ C +2C +3C + +nC =n
1
n 2n 3n n n
n -1
证明：
m
由m C n =nC n m --11可得:（还记得这个恒等式吗，不记得就回过头去看③的证明）
左边
=nC n 0-1+n C n 1-1+n C n 2-1+n C n 3-1+ n C n n --11
=n(C n 0-1+C n 1-1+C n 2-1+C n 3-1+ C n n --11) =n 2n -1
注：同时利用了⑥的结论。
⑨ C C +C C ++ +C C =C
r ≤min{m,
r m 0n r -11m n 0
m r n r n +m
用二项式定理证明太麻烦了。能偷懒就不要太勤快了。 n} 观察左边的每一项，发现均是分别从m 个不同素和n 个不同元素中取r 个元素的一个组合，其各项之和就是所有取法，即所有组合数。其所有组合数当然等于右边。
(C ⑩ ) +(C ) + +(C ) =C
02
n 12n n 2n n 2n
还是用偷懒法：根据第⑨的结论并结合组合的互补性质，若r=m=n即得些结论。