Set/Subset number of combinations I'm struggling on a counting problem, and I would like some help :) I'm rephrasing the problem to make it easy to understand ;) 
So, let's say I have a set of $n$ boxes. The $i$th box contains $m_{i}$ of $p$ different balls ( there are $p = \sum_{i = 1}^{n}$ balls in total ). 
A player comes into the room. He chooses $k$ different boxes ($1\le k \le n$), and then he takes exactly one ball from each box he chose. 
How many different combinations of balls can the player take ?
Currently, to compute that, I "brute force" it, generating the combinations of choosing $k$ boxes and then I sum the products of the number of balls of each of the $k$ chosen boxes. Of course this takes a lot of computation time :/
Do you have any idea about how to solve more efficiently this problem ?
 A: Let's define some notation for the quantity asked about, and then discuss complexity.
Suppose that a sequence $m_1, m_2, \ldots, m_n, \ldots$ of integers $m_i \ge 1$ is given.  We denote the sum of all products over $k$-subsets of the sequence truncated at $m_n$ by:
$$ Q_k^{(n)} = Q_k(m_1,\ldots,m_n) = \sum_{1\le i_1 \lt i_2 \lt \ldots \lt i_k \le n}
   m_{i_1} m_{i_2} \ldots m_{i_k} $$
A naive (aka "brute force") evaluation of this requires $\binom{n}{k} (k-1)$ multiplies and $\binom{n}{k} - 1$ additions.  For fixed $k$, $k \ll n$, this amounts to $O(n^k)$ complexity.
However it is obvious that many terms in the summation have factors in common.  One recursive approach gives us $O(nk)$ complexity, a significant improvement over "brute force".
If all the terms of $Q_k^{(n)}$ that contain $m_n$ are grouped together, we have:
$$ Q_k^{(n)} = m_n Q_{k-1}^{(n-1)} + Q_{k}^{(n-1)} $$
Thinking of these as an array with rows of constant $k \ge 1$ and increasing $n$, we can evaluate row-by-row out to column $n$ using the above recurrence, using constant cost operations for each new entry (one multiply and one addition).  It remains only to say a few words about the initial and boundary values of the array.
The initial row is simply an accumulated sum, $Q_1^{(n)} = \sum_{i=1}^n m_i$, which can clearly be found with $O(n)$ operations.  Indeed if we make a convention that $Q_0^{(n)} \equiv 1$ when $n \ge 0$ and zero otherwise, then forming these running sums agrees with applying the recurrence relation.
Consistent with this we know $Q_k^{(n)} \equiv 0$ when $k \gt n$ because it represents an empty sum.  Together with $Q_0^{(0)} = 1$ (as a single empty product), we can derive:
$$ Q_n^{(n)} = \prod_{i=1}^n m_i $$
by applications of the recurrence relation to the first nonzero entries of each row.
Note that the space complexity of the recursive algorithm can be just $O(n)$ by overwriting a single row of $Q_k^{(n)}$ as we go.
