42排列与组合模型公式
4.2排列与组合模型公式
4.2.1排列与组合模型
这节我们将某些排列与组合问题总结一个模型,掌握这个模型的各种变化将有利于研究初等数学中各种类型的排列和组合问题。
这个模型就是把r个小球投入n个小盒的问题。r个小球可分两种情况:
(1)小球是可以互相区分的。就是说,这些球是彼此不同的,可以把这r个球看成是不同颜色的。
(2)小球是不可以互相区分的。这时可把r个球都看成一样的,或者是都具有同一颜色的小球。
n个小盒我们把它看成是可以互相区分的。即n个小盒可按序编号。每一个小盒盛球的方式有两种:
(1)每一小盒最多只盛一球,
(2)每一小盒盛球数目不限。
下面讨论几种典型情况:
(1)将r个可以区分的小球投入n个小盒内,每盒容量不限,这时共有多少种投法,
r 显然第一个小球有n种选择,第二个小球还有n种选择…,所以一共有n种投球方法。
(2)将r个可区分的小球投入n个盒内,每一个盒的容量不超过一个球。如果则r,n,
rn(n,1)??(n,r,1)r(r,1)?(r,n,1)有种,即投球方法。如果则有种方r,n,Pn
法[这时第一个盒有r种选择,第二个盒有r-1种选择,……]。
如果r=n,则有n!种投球方法。
(n,r)(3)将r个不可区分的小球投入n个盒,每一个盒容量不超过1个球,这时共
r有种投球方法。 Cn
(4)将r个不可区分的小球投入n个小盒里,每盒容量不限,这时投入的方法数显然是方程
x,x,?,x,r12n
的非负整数解的个数。这里x表示第i个盒盛球的个数。上述方程解的个数就是n个元素取i
rr个元素(可重复取)的组合数。 C,,1nr
例1 求多项式
7 (a,b,c,d,e)
展开合并同类项后共有多少项,
a,b,c,d,e解 指数7相当于7个不同的球;相当于5个不同的盒子,每一个盛球方法
7相当于一项。因此合并同类项后共有项。 C5,7,1
4.2.2 排列组合公式
下面给出一些常用的排列组合公式及其证明。
rrr,1(1) C,C,Cnn,1n,1
利用组合公式
(n,1)!(n,1)!(n)!rrr,1 ,,,CC,C,nn,1n,1r!(n,r,1)!(r,1)!(n,r)!r!(n,r)!
即可证明上式。另一方面,如果从n个元素1,2,…,n中取r个数码,我们把取法分
r,1为两种:一是取的数码有1,那么所取方法数为;二是取的数码没有1,所取方法数为Cn,1rr。两部分相加即为。 CC,1nn
01nnn01nn(2) 由二项式展开,得 C,C,?,C,2(1,1),C,C,?,C,2nnnnnn
即可证明。
另一方面,如令是n个不同元素的集合,而S,{a,a,?a}12n
集的样本集合。这里S的每一个A,{b,b,?b|b只能为0或1,i,1,2,?,n}是{0,1}n,12ni
子集合与A的一个元素对应,例如子集与元素(110…000)对应,子集{a,a}{a,a,a}12134
与元素(101100…0)对应。S的所有子集的个数为
01n C,C,?,C nnn
n而A的元素个数显然为2个,由此也证明了
01nn C,C,?,C,2nnn
012nn(3)C,C,C??(,1)C,0 nnnn
n展开(1-1)即可证明上式。
nkrk(,1)CC,0(4),由于 ,knk,r
k!n!(n,r)!rkC?C,??, knr!(k,r)!k!(n,k)!(n,r)!
n!(n,r)!rn,k?,CC nn,rr!(n,r)!(n,k)!(k,r)!
所以
nnnkrkkrn,krkn,k(,1)CC,(,1)CC,C(,1)C,0 ,,,knkn,rnn,rk,rk,rk,r
nkn,1(5)kC,n?2,由 ,nk,r
nnkk (1,x),Cx ,n,0k
nn,1kk,1两边微分,得n(1,x),Cx.令x,1,得 ,nk,1
n,1nk n?2,kC ,n,1k
另一方面,也可利用
kk,1 k?C,nCnn,1
01n,1n,1及 C,C,?,C,2n,1n,1n,1证明上述等式
nnnn,1(6)。由于 C,C,?,C,Cnn,1n,mn,m,1
,,n1n1n C,C,C,,,,nk1nknk
nn,1n,1所以 C,C,Cn,kn,k,1n,k
n,1n 而 C,C,1 n,1n所以有
nn,1n,1C,C,Cn,1n,2n,1 nn,1n,1C,C,Cn,2n,3n,2
?
nn,1n,1 C,C,C n,mn,m,1n,m把上式相加,得
nnnnn,1C,C,C,?,C,C nn,1n,2n,mn,m,1
kik,ikCC(7)=.比较等式 C,mn,mni,0
mnm,n (1,x)(1,x)?,(1,x)k两边x的系数,即可得出上述等式。
k另一方面,若有m个男生和n个女生,从这m+n个人中选取k个人的方法,显然有C,mn
种。选取k个人的方式:依次可以取男生人数为0,女生人数为k;男生人数为1,女生人
ik,i数为k-1;…男生人数为k,女生人数为0。每一种情况有种取法。即取i位男生,CCmn
k-i位女生;他们的总和即为上述等式的左边。
练习4.2
1(将n个球(不可区分)放入N个缸内,n>N。共有多少种放法,
102(求合并同类项后共有多少项, (x,y,z)
本文档为【42排列与组合模型公式】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。