排列组合公式及恒等式推导证明.docx
《排列组合公式及恒等式推导证明.docx》由会员分享，可在线阅读，更多相关《排列组合公式及恒等式推导证明.docx（10页珍藏版）》请在冰点文库上搜索。
排列组合公式及恒等式推导证明
排列组合公式及恒等式推导、
明（word版）
排列组合公式及恒等式推导、证明（word版）
说明：
因公式编辑需特定的公式编辑插件,
不管是word还是pps附带公式编辑经常是出错用不了。
下载此word版的，记得下载MathTyp（公式编辑器哦，否则乱码一堆。
如果想偷懒可下截同名的截图版。
另外，还有PPt课件（包含了排列组合的精典解题方法和精典试题）供学友们下载。
、排列数公式:
Anm二n（n-1）（n-2）L（n-m+1）=
-n!
（n-m）!
A；=n（n-1）（n-1）L3仓吃1
推导：
把n个不同的元素任选m个排次序或n个全排序，按计数
原理分步进行：
第步，排第位：
有n种选法;
第二步，排第二位：
有（n-1）种选法;
第三步，排第三位：
有（n-2）种选法;
第m步，排第m位：
有（n-m+1）种选法;
根据分步乘法原理，得出上述公式。
二、组合数公式：
y=Aj=n（n-1）0-2）L（n-m+1）=n!
nAj?
m!
m!
（n-m）!
C；=1
推导：
把n个不同的元素任选m个不排序，按计数原理分步进行:
第一步，取第一个：
有n种取法；
第二步，取第二个：
有（n-1）种取法；
第三步，取第三个：
有（n-2）种取法；
I
I
I
I
第m步，取第m个：
有（n-m+1）种取法；
I
I
I
I
最后一步，取最后一个：
有1种取法。
上述各步的取法相乘是排序的方法数，由于选m个，就有m!
种排排法，选n个就有n!
种排法。
故取m个的取法应当除以m!
取n个的取法应当除以n!
。
遂得出上述公式。
证明：
利用排列和组合之间的关系以及排列的公式来推导证明。
将部分排列问题Anm分解为两个步骤：
第一步，就是从n个球中抽m个出来，先不排序，此即定义的组合数问题cnm；
第二步，则是把这m个被抽出来的球全部排序，即全排列A：
。
根据乘法原理，Am=cnmAm即：
Cm=Am=n（n-1）n-2）L（n-m+1）_n!
nAm!
m!
（n-m）!
组合公式也适用于全组合的情况，即求C（n,n）的问题。
根据
上述公式，
C（n,n）_n!
/n!
（n-n）!
_n!
/n!
0!
_1。
这一结果是完全合理的，因为从n个球中抽取所有n个出来，当
然只有1种方法。
三、重复组合数公式：
重复组合定义：
从n个不同的元素中每次取一个，放回后再取下
一个，如此连续m次所得的组合。
重复组合数公式：
Rm_c：
+m-i（m可小于、大于、等于n,n>1）
推导：
可以把该过程看作是一个“放球模型”：
n个不同的元素看作是n个格子，其间一共有（n-1）块相同_—_丄
的隔板，用m个相同的小球代表取m次；则原问题可以简化为将
m个不加区别的小球放进n个格子里面，问有多少种放法；这相当
于m个相同的小球和（n-1）块相同的隔板先进行全排列：
一共有
I
（m+n-1）!
种排法，再由于m个小球和（n-1）块隔板是分别不
加以区分的，所以除以重复的情况：
m!
*（n-1）!
于是答案就是：
Rnm=（m+n-1）!
=席-1m!
（n-1）!
四、不全相异的全排列
在不全相异的n个物体中，假设有ni个物体是相同的，n2个五题是相同的，……，nk个物体是相同的。
n个物体中不相同的物体种类数一共有k种。
那么，这些物体的全排列数是n!
/（ni!
n2!
…nk!
）。
可以想成：
n个物体直接全排列，排列完了以后，去重，第一种物体有ni!
种，第二种物体有m!
种，以此类推。
例：
有3个红球，2个白球，把这五个球排成一行，问有多少种排法？
红球和红球没有区别，白球和白球没有区别。
答：
一共有10种，
aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。
五、排列恒等式的证明：
①A；
m-1
=（n-m+1）An
证明:
右边=（n-m
n!
+1）=
（n-m+1）!
（n
n!
=A-m）!
左边=右边
Anm
n!
（n-m）!
n?
（n-1）证明：
右边=n-m（n-m-1）!
左边=右边
左边=右边
证明：
右边=A：
；-An=（n+1）!
-n!
=（n+1）gi!
-n!
二ngi!
=nA：
右边=左边
—n!
_（n-m+1）n!
-mgn!
_（n+1）!
_加
+m===A+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!
右边
六、组合恒等式的证明
首先明弄清组合的两个性质公式:
mn-m
Cn=Cn
互补性质：
取出有多少种，剩下就有多少种
分类计数原
mmm-1
Cn+1=Cn+Cn
根据分类计数原理：
要么含有新加元素要么不含新加元素
①Cm=m+1Cm+1
-m
n-m+1m-iCn
（m+1）n!
m+1m+1
Cnn-m
证明：
n-m+1小m-1n-m+1
Cn=g
=C（n-m）（m+1）!
（n-m-1）!
m!
（n-m）!
n!
M=Cnm
m!
（n-m）!
②Cm=
n
nCm
Cn-1
n-m
证
明：
右
边
mm（m-1）!
（n-m+1）!
=1亠』^=」^=Ct
n-mn-mm!
（n-m-1）!
m!
（n-m）!
③Cm:
n
_nQm-1
~Cn-1
m
证明:
.m
n
右边二
n（n-1）!
—g
m（m-1）!
（n-m）!
m!
（n-m）!
=左边
rrr
⑤Cr+Cr+1+Cr+2+L
+Cnr
r+1
Cn+1
证明：
根据组合性质，左边各式可写成:
Crr=C
C；+1=C
C：
+2
C；+3
M
C；1
r+1
r+1
r+1r+1r+2-Cr+1
r+1r+1
=Cr+3-Cr+2
r+1r+1
=Cr+4-Cr+3
C；=C
r+1r+1
=Cn-Cn-1
r+1r+1
n+1-Cn
-C
左右两边相加即得：
Crr+Crr+1+Crr+2+L+Cnr=cn：
；
⑥cn+cn+l+cn
证明:
用数学归纳法证明。
1）当n=1时，Ci0+C；=2=21所以等式成立。
2）假设n=k时，（k>1,k€N*）时等式成立即：
C：
+Ck+C：
+L+C：
=2k
当n二k+1时，
c：
+1+ck+1+c：
+1+L+Ckk+1+c：
：
11
=C°+1+（C；0+C1）+（Ck+C：
）+L+（Ckk-1+C：
）+C阳=（C：
+Ck+C：
+L+C；）+（C：
+Ck+Ci+L+Ckk）
=20
=2k+1
二等式也成立
由1）、2）得，等式对n€N*都成立。
也可用二项式定理证明（略）
7Cn+C；+C；L=C：
+C；+C：
L=2n-1
证明：
用归纳法同上（略）
也可利用上述结论证明（略）
本课件尽量避开用二项式定理，但这比较简单，暂且用一下：
设a=C：
+C；+C；+Lb=C°+Cn+Cn+L
由（1+1）n可得：
a+b=21=2x2n-1
由（1-1）n可得a-b=0
a=b=2-1（不懂的去学学二项式定理）
8C；+2C：
+3C；+L+nC；=ng2n-1
证明：
由mCnm=nCn呼可得：
（还记得这个恒等式吗，不记得就回过头去看③的证明
左边
n-1
n-1
=rC0-1+nCn-1+nC；2-1+nC3-1+LnC=nCn-1+Cn-1+Cn-1+Cn-1+-Cn-1）=ng2n-1
注：
同时利用了⑥的结论。
9cmc：
+cm-icn++L+cma=cn+m
rEmin{m,
n}
用二项式定理证明太麻烦了。
能偷懒就不要太勤快了。
观察左边的每一项，发现均是分别从m个不同素和n个不同元素
中取r个元素的一个组合，其各项之和就是所有取法，即所有组合
j■
数。
其所有组合数当然等于右边。
10c：
）2+（Cn）2+L+（C：
）2=C；n
还是用偷懒法：
根据第⑨的结论并结合组合的互补性质，若
r=m=n
即得些结论。
升级会员 