An efficient method for computing the number of submultisets of size n, of a given multiset
I don't really understand the description of the SubMultiset problem.
I think I do understand the description of the integer partition problem.
This can be solved by generating functions.
The number of solutions to
$x_1 + x_2 + \dots + x_k = n$ with $0 \le x_i \le m_i$ is the coefficient of $x^n$ in
$$ (1+x+\dots+x^{m_1})(1+x+\dots+x^{m_2})\dots(1+x+\dots+x^{m_k}) $$
$$ = \frac{\prod_{i}^{k}(1-x^{m_i+1})}{(1-x)^{k}}$$
$$ = (\sum_{j=0}^{\infty}{k+j-1 \choose j} x^j) \prod_{i}^{k}(1-x^{m_i+1})$$