2 mengfanxue514 mengfanxue514 于 2016.03.23 12:45 提问

元素可重复的组合的问题

有n个不同数,在其中取m个数组成一个集合,可重复取,有多少种取法,这个怎么算呢?
如 0,1,2 三个数,取3个数的集合有
{0,0,0)
{0,0,1}
{0,0,2}
{0,1,1}
{0,1,2}
{0,2,2}
{1,1,1}
{1,1,2}
{1,2,2}
{2,2,2}

4个回答

cxsmarkchan
cxsmarkchan   2016.03.23 20:58
已采纳

前面的回答太繁琐了。有一种更简单的方法(隔板法)。
假设你要在n个数里面重复取m次,就可以设想下面一种场景:取n+m-1个位置,其中n-1个位置放上隔板,其他的m个位置放上小球。这样,m个小球就被隔板分成了n份(可能有一份中没有小球的情况)。
从左到右的n份中的小球数目,就对应着原问题的n个数各取了多少次,总共m个小球,表示m次。
这样,问题的答案就是n+m-1个数里面取n-1个数,这个组合数。可以记作C(n+m-1,n-1)
例如3个数取3次,就有C(3+3-1, 3-1)=10种取法。
你举出的{0,1,2}这种组合,对应着3个数各取1次,在隔板法里就对应着"球-板-球-板-球",而(0,0,2)这种组合,就是“球-球-板-板-球”(0取了2次,对应左边有2个球。1取了0次,对应中间两个板之间没有球。2取了1次,对应右边有一个球)。

mengfanxue514
mengfanxue514 你咋这么聪明呢,赞!
一年多之前 回复
herozhangbz
herozhangbz   2016.03.23 13:32

n的m次方。没学过概率论么。。。。

herozhangbz
herozhangbz 回复孟梦514: 如果你的m很小则可以分几种情况,比如m=4,则需要考虑只有一个数字,只有两个数字,只有三个数字,有四个不同的数字。其中只有两个数字又有三个是同一个数字两两相同两种情况。如果m=3那你考虑的情况就少了,只有一个数字,只有两个数值,有三个不同的数字。分别考虑着三种情况就行了
一年多之前 回复
mengfanxue514
mengfanxue514 集合是无序的 所以不能用n^m 如{0,0,1}和{0,1,0}是相同的集合
一年多之前 回复
cxsmarkchan
cxsmarkchan   2016.03.23 15:25

设n个数取m的的取法数量为a(n, m),n>=1, m>=0,则满足如下的递推关系:
a(n, m) = a(n - 1, m) + a(n - 1, m - 1) + a(n - 1, m - 2) + ... + a(n - 1, 0)
a(n, 0)=1;a(1, m) = 1
然后你开一个(n+1)*(m+1)的数组,从a(0,0)开始,按如下方法计算(下面是伪码,你需要自己转换成vba)

定义 a(n+1, m+1)
for j: 0->m
    a(1, j) = 1
end
for i: 1->n
    a(i, 0) = 1
end
for i: 2 -> n
    for j: 1->m
        按照递推公式计算a(i, j)
    end
end
cxsmarkchan
cxsmarkchan 回复孟梦514: 所以a(3,3)=a(2,3)+a(2,2)+a(2,1)+a(2,0),这4种情况又可以进一步往下推,a(2,3)=a(1,3)+a(1,2)+a(1,1)+a(1,0)=4, a(2,2)=a(1,2)+a(1,1)+a(1,0)=3, a(2,1)=a(1,1)+a(1,0)=2, a(2,0)=1。所以a(3,3)=10
一年多之前 回复
cxsmarkchan
cxsmarkchan 回复孟梦514: 其余的情况就要递推。例如a(3,3),假设3个数为0,1,2,取3次。我们分4种情况讨论。1)取0个0,即3次都在1或2中取,这和2个数取3次是一样的,即a(2,3)。2)取1个0,另外2次在1或2中取,这是a(2,2)种情况。3)取2个0,另外1次在1或2中取,这是a(2,1)种情况。4)3次都取0,这是a(2,0)=1种情况。
一年多之前 回复
cxsmarkchan
cxsmarkchan 回复孟梦514: 另一个边界条件a(i,0)=1,表示从i个不同的数里面取0次,也就是什么都不取。这显然也只有唯一的情况,就是空集。
一年多之前 回复
cxsmarkchan
cxsmarkchan 回复孟梦514: a(n,m)代表从n个不同的数里面可重复地取m个。先说边界条件a(1,j)=1,也就是有1个数,取j次,那无论怎么取,都是1种情况。例如1个数为0,取3次,那只有(0,0,0)这1种情况
一年多之前 回复
mengfanxue514
mengfanxue514 不好意思 我刚学 没看明白 a(1,j)=1 是啥意思? 要不能帮我写个3 个数取3个数的例子吗 谢谢哦
一年多之前 回复
weixin_32769751
weixin_32769751   2016.03.23 15:33

n个不同的数,取m个相当于m位n进制。例如8位2进制。就是2的零次方一直累加到2的(8-1)次方

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!