重复组合问题

来源:百度知道 编辑:UC知道 时间:2024/06/16 02:53:47
从n个不同元素中每次取出一个,放回后再取下一个,如此连续取r次所得的结果?

∵从n个不同元素中每次取出一个
∴结果是n-1
∵放回后再取下一个
∴第二次的结果是n-1
........
∴如此连续取第r次所得的结果仍是n-1
故 如此连续取r次所得的结果是(n-1)^r.

可以把问题转化成将r个同质的小球放入不同的n个小盒子里,一共有多少种方法?
用 | 作为盒子的分割线 那么n-1条分割线将分割成n个盒子,例如5个分割线分成六个盒子:
  O|O|O|O|O|O
然后把小球放到盒子里,例如:
   **||*|||*

星星表示小球,上边就表示为将两个小球放入第一个盒子,第二、四五个盒子为空,第三和第六个盒子里有一个小球,理解成原组合问题即将6个不同元素每次取出一个,放回后再取下一个,如此连续取4次所得的结果,对应关系为
第一个盒子两个小球表示将第一个元素取出了两次
第二个盒子没有小球表示第二个元素未被取到

第三个盒子1个小球表示第三个元素被取出1次

第四个…………

  转换后的问题相当于是求r个小球与n-1条分割线的组合问题,组合种类有Cr| r+n-1种。