数列的排列组合问题30个变量,每个变量取值（1,2,3,4,5）中的一个,最后计算（1,2,3,4,5）分别的数量,比如记录为7-5-5-9-4表示7个1,5个2……,4个5,请问有多少种组合?怎么算,通过哪种途径可以得到所

数列的排列组合问题30个变量,每个变量取值（1,2,3,4,5）中的一个,最后计算（1,2,3,4,5）分别的数量,比如记录为7-5-5-9-4表示7个1,5个2……,4个5,请问有多少种组合?怎么算,通过哪种途径可以得到所
数列的排列组合问题
30个变量,每个变量取值（1,2,3,4,5）中的一个,最后计算（1,2,3,4,5）分别的数量,比如记录为7-5-5-9-4表示7个1,5个2……,4个5,请问有多少种组合?怎么算,通过哪种途径可以得到所有组合的列表?

数列的排列组合问题30个变量,每个变量取值（1,2,3,4,5）中的一个,最后计算（1,2,3,4,5）分别的数量,比如记录为7-5-5-9-4表示7个1,5个2……,4个5,请问有多少种组合?怎么算,通过哪种途径可以得到所
我是这样思考的：
如果1,2,3,4,5每一个都必须取到,把30个变量看成30个1,30个1排成一列,中间形成了29个间隔,在这29个间隔中随意插入4块隔板,便把30个1分成了5份,每一份便代表这个变量出现了多少次,因此共有29C4=23751种组合.
如果不要求每一个都要取时,另作考虑如下：
当1,2,3,4,5中有一个数不用取时,相当于29个间隔中插入3块隔板,此时要分步,即
（29C3）*（5C1）=18270
有两个不用取时,类似方法,即（29C2）*(5C2)=4060
有三个不用取时,（29C1）*(5C3)=290
有四个不用取时,为5C4=5C1=5
5个全取时,29C4=23751
所以总数是23751+18270+4060+290+5=46376.

假设1,2,3,4,5的数目为a,b,c,d,e，等价于求解不定方程
a+b+c+d+e=30
非负整数解的个数。
一般地，对于不定方程
x1+x2+...+xn=m，非负整数解的个数是C(m+n-1,m)，一个简单的证明方法如下：
每一个数组(x1,..., xn)一一对应着数组(y1,y2,...,yn):
y1=x1+1,
y2 = ...

全部展开

假设1,2,3,4,5的数目为a,b,c,d,e，等价于求解不定方程
a+b+c+d+e=30
非负整数解的个数。
一般地，对于不定方程
x1+x2+...+xn=m，非负整数解的个数是C(m+n-1,m)，一个简单的证明方法如下：
每一个数组(x1,..., xn)一一对应着数组(y1,y2,...,yn):
y1=x1+1,
y2 = x1+x2+2,
...
yn = x1+x2+...+xn+n = m+n
(y1,...,yn)只要满足1<=y1<...而数组(y1,...,yn)的个数相当于从1,2,...,m+n-1中取出n-1个数，从小到大排列就是y1,...,y(n-1)，加上yn=(m+n)，所以原方组解的个数是C(m+n-1,n-1)=C(m+n-1,m)
如果你想穷举，可以考虑如下的的方法：
a+b=n，解是(0,n),(1,n-1),....(n,0)
a+b+c=n，分c=0,1,2,...,n等情况讨论。当c=k时，a+b=n-k，上面已经列举出了所有情况。
由此得到4元、5元，。。。
如此层层递推，可保证不重不漏

收起