有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}
前面的回答太繁琐了。有一种更简单的方法(隔板法)。
假设你要在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次,对应右边有一个球)。
设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
n个不同的数,取m个相当于m位n进制。例如8位2进制。就是2的零次方一直累加到2的(8-1)次方
n的m次方。没学过概率论么。。。。