3
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Are the p balls intrinsically distinct? When you ask "How many different combinations of ball can the player take?", what make one combination different from another? Does it depend on the boxes, e.g. all the balls in one box are "the same" but different from balls in other boxes? $\endgroup$ – hardmath Dec 7 '13 at 18:33
  • 1
    $\begingroup$ Let's say that all balls have a different color. If you open all the boxes, you'll have each color only once $\endgroup$ – Nisalon Dec 7 '13 at 19:05
  • $\begingroup$ Then the absence of knowledge about which balls are in which boxes amounts to an absence of "constraints" we can put on how many combinations of balls are possible. We'd just say $\binom{p}{k}$ combinations are possible, but this is because we don't know which pairs of balls are in the same box. If we did know, we could rule out combinations that contain two balls in the same box. Perhaps you do know which balls are in which boxes? $\endgroup$ – hardmath Dec 7 '13 at 20:39
  • 1
    $\begingroup$ Yes, I can say in each box how many balls I have $\endgroup$ – Nisalon Dec 7 '13 at 21:18
  • $\begingroup$ Okay, your "brute force method" produces the right answer! $\endgroup$ – hardmath Dec 7 '13 at 21:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.