请问一道排列组合的有关问题，高中没学好，都忘记了

请教一道排列组合的问题，高中没学好，都忘记了
有9个集合
A{100}
B{101,102,103}
C{104,105,106,107,108}
D{109,110}
E{111,112,113,114,115,116,117}
F{118,119,120,121,122}
G{123,124,125,126}
H{127,128,129,130}
I{131,132}
从任意6个集合中取一个数字，组成一个组合，没有顺序
比如：{101,104,109,111,118,123}
总能可以有多少个这样的组合，究竟是如何计算的呢？ 排列组合
[解决办法]
这个还是有点麻烦的，要72种组合分别算然后加
比如123456各取一个，一共有1×3×5×2×6×4种
遍历所有组合分别计算结果后累加
[解决办法]
sorry, 忘了，这只是算出选集合的可能，然后每种可能还要乘上所有包含集合的元素的个数的乘积。
[解决办法]
9次多项式(x+a1)(x+a2)(x+a3)...(x+a9)的3次项系数。其中ai=第i个集合的元素个数。
直接展开这个多项式算出系数就行。可以用dp但是dp算法也退化到这个多项式算系数上的。
[解决办法]

引用:

有人告诉我
C(9,6)*C(1,1)*C(3,1)*C(5,1)*C(2,1)*C(7,1)*C(5,1)*C(4,1)*C(4,1)*C(2,1)
这里再确认一下，是否正确

显然错的，为了简单假定所有数据都是2个，那么结果应该是C(9,6) *2^6,但是按你这个是C(9,6) *2^9明显不对
[解决办法]
DP:

令f(i,j)表示前i个集合中选取j个集合的组合数，A(i)表示第i个集合的元素个数，则

f(i,j) = 0 , j>i , 否则
       = f(i-1,j-1)x A(i) + f(i-1,j)
          

查看更多 下一篇