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 你咋这么聪明呢,赞!
2 年多之前 回复
herozhangbz
herozhangbz   2016.03.23 13:32

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

qq_37782765
qq_37782765 杠精么
4 个月之前 回复
herozhangbz
herozhangbz 回复孟梦514: 如果你的m很小则可以分几种情况,比如m=4,则需要考虑只有一个数字,只有两个数字,只有三个数字,有四个不同的数字。其中只有两个数字又有三个是同一个数字两两相同两种情况。如果m=3那你考虑的情况就少了,只有一个数字,只有两个数值,有三个不同的数字。分别考虑着三种情况就行了
2 年多之前 回复
mengfanxue514
mengfanxue514 集合是无序的 所以不能用n^m 如{0,0,1}和{0,1,0}是相同的集合
2 年多之前 回复
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
2 年多之前 回复
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种情况。
2 年多之前 回复
cxsmarkchan
cxsmarkchan 回复孟梦514: 另一个边界条件a(i,0)=1,表示从i个不同的数里面取0次,也就是什么都不取。这显然也只有唯一的情况,就是空集。
2 年多之前 回复
cxsmarkchan
cxsmarkchan 回复孟梦514: a(n,m)代表从n个不同的数里面可重复地取m个。先说边界条件a(1,j)=1,也就是有1个数,取j次,那无论怎么取,都是1种情况。例如1个数为0,取3次,那只有(0,0,0)这1种情况
2 年多之前 回复
mengfanxue514
mengfanxue514 不好意思 我刚学 没看明白 a(1,j)=1 是啥意思? 要不能帮我写个3 个数取3个数的例子吗 谢谢哦
2 年多之前 回复
weixin_32769751
weixin_32769751   2016.03.23 15:33

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
<<离散数学>>n个元素,m个组合,可重复
3个元素,11个组合 苹果,梨子,桃子,选11个的组合c(n+m-1,m-1)=c(n+m-1,n)#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<math.h> int main() { int k = 0; for (int i1 = 1; i1 < 4; i1++) { for (int i
计数与概率基础(容斥、有重复元素的全部排列、可重复选择的全排列、杨辉、二项式定理、欧拉函数)
1、容斥原理。 如果班里有15个人喜欢物理,
面试题精选(64):元素可重复组合算法
可重复组合问题是指,在计算(生成)组合时可以允许元素重复的一类组合问题。例如,对于有四个元素的集合{a, b, c, d},其可重复组合C(4, 3)有20个:aaa, aab, aac, aad, abb, abc, abd, acc, acd, add, bbb, bbc, bbd, bcc, bcd, bdd, ccc, ccd, cdd, ddd。用P(n, k)表示从n个元素中选出k个元
Lucky Numbers(排列问题)(数学)(n个数排列且可重复用,元素个数不定)(等比数列)
Lucky Numbers(排列问题)(数学)(n个数排列且可重复用,元素个数不定) Lucky Numbers Crawling in process... Crawling failed Time Limit:500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status
(排列组合的重复问题)
将6个同学平均分成3组,问有几种分法。错解;C(2,6)*C(2,4)*C(2,2)=90, 为什么这样错了呢,因为我们没考虑重复的情况,假如分组情况如下1,2;3,4;5,6;先挑出1,2和后调出1,2没区别,所以产生了重复。正解:C(2,6)*C(2,4)*C(2,2)/3!=15一般情况下分为几组,结果就除以几的阶乘。...
回溯法解决 排列组合问题 全排 选排 可重复 不可重复
/* 华科机试练手 * 回溯法解决 排列组合问题 * 1 : 全排列 * 2 :可重复全排列 * 3 : 不可重复的选择排序 * …… */ #include #include int solution[100]; /* 可重复全排 */ int Perm(int a[], int n, int level) { int i; static int sum = 0
全排列的java实现(含重复数字)
题目原型: Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and
全排列的简单递归方法(有重复元素和无重复元素的递归算法)
无论是有重复元素还是无重复元素
(数论)可重复选择的组合、杨辉三角
本文参考刘汝佳《算法竞赛入门经典》(第2版) 组合数 【题目】有n个不同的数,每个数可以选择多次,共选k个数,有多少种选法?例如有3个数:3,4,5,选2个数,所有选法是(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)共6种选法。 【分析】设第i个数选xi个,那么x1+x2+…+xn=k,转化成求解该n元一次方程的非负整数解的个数,又设yi=xi+1,那么y1+y2...
集合的全排列(可包含重复元素)
利用求下一个序列的方式求取序列的全排列