从n个元素中有重复地取r个,不计其顺序,则不同的取法有C(r,n+r-1)种
很多教材都仅仅给出了公式,但是没有给出这个公式的证明,这里就给出一种证明,由于本人的语言表述能力欠佳,因此在阐述时显得十分罗嗦,希望大家能提出意见.
事实上,若将n个元素看做n个盒子,r看作r个同质的球,则相当于:
把r个同样的球放入n个顺次排列的盒子,求不计放球顺序的放法种数
把0看作是盒子,1看做是球;
由于球必须放在盒子中,规定某个0位之前,到上一个0位为止的1的个数,表示该盒子中装的球数:
则有重复排列数要求,
在n个0中放入r个1
这样,就相当于(n-1)个0和r个1的排列数,即(n+r-1)!/n!*(r-1)!
比如:
1110100011111110 (1110 | 10 | 0 | 0 | 11111110) 是n=5,r=11 的一种具体情形
表示第一个盒子装3个球,因为第一个0前有3个1
第二个盒子装1个球,因为第二个0到第一个0间有1个1
第三个盒子装0个球,因为第三个0到第二个0间有0个1
第四个盒子装0个球,因为第四个0到第三个0间有0个1
第五个盒子装7个球,因为第屋个0到第五个0间有7个1
详细一点的解释是:
若规定这样的字段:
1.每个字段可能含有若干个1
2.0代表字段的结束
3.若一个字段只含0不含1,称之为空字段.
其中,设:
r 为1的个数
n 为0的个数,也就是字段的数量(因为0是结束字符,有多少的结束字符就有多少个字段)
则
字符串1100100 表示 110 | 0 | 10 | 0 ,其中r=3,n=4
字符串0101010 表示 0 | 10 | 10 | 10 ,同样有r=3,n=4
又如 0011010100 表示 0 | 0 | 110 | 10 | 10 | 0 ,其中r=4,n=6
若规定 110 | 0 | 10 | 0 表示:
第一个元素取2次,第二个元素取0次,第三个元素取1次,第四个元素取0次
则同样 0 | 10 | 10 | 10 表示:
第一个元素取0次,第二个元素取1次,第三个元素取1次,第四个元素取1次
又如?0 | 0 | 110 | 10 | 10 | 0 表示:
第一个元素取0次,第二个元素取0次,第三个元素取2次,第4个元素取1次,表示第五个元素取1次,第六个元素取1次
则要在n个元素中有重复地取出r个,即是求按上述规则组成的字段,能排列成多少中不同的字符串.由于字符串的结尾总是0,故相当于(n-1)个0和r个1的组合,即(n+r-1)!/n!*(r-1)!
实际上,这也相当于求方程 X1+X2+...+Xn=r 的自然数解的个数.
猜你喜欢
- 1Excuse me,is there a library near here?(改为同义句)
- 2watch的现在分词
- 3用英文翻译下列句子:1.上课不要迟到.2.我们可以在外面听音乐.3.他不得不在周三打扫教室.
- 4单位换算3mg/cm³=___kg/m³_百度知道
- 5我们经常去游泳在周末用英语怎么说
- 6小明第一次喝了一杯纯牛奶的1/6然后加满水又喝了一杯的1/3再到满水又喝了半杯,这
- 7柴门闻犬吠 风雪夜归人
- 8铁,镁,铝三种金属混合物共27g,将该混合物与足量的稀硫酸充分反应,共得硫酸盐质量123g,则反应共可收集到氢气多少g?
- 9思乡的古诗句
- 10已知在△ABC中AB=AC,BD是AC边上一条中线,△ABD的周长比△BCD的周长大2,则AC-BC=?