【“重复组合数”是怎么算出来的?】-查字典问答网
分类选择

来自刘文涛的问题

  【“重复组合数”是怎么算出来的?】

  “重复组合数”是怎么算出来的?

1回答
2020-02-04 11:36
我要回答
请先登录
刘宏芳

  从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的自然数解的个数.

2020-02-04 11:38:07

最新问答

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读

  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •