Variations of the problem of the number of ways to divide $N$ items into $K$ bins

71 Views Asked by At

I can use the stars and bars approach to solve the problem of dividing $N$ items into $K$ distinct bins with no restrict on the number of items each bin has to have. It's simply $$ \binom{N+K - 1}{K - 1} $$

Essentially $N+K-1$ is the number of items plus the number of "bars," where the latter is the number of bins minus 1. The binomial coefficient essentially says "For $N+K-1$ things, we want to choose $K-1$ things and have these be the bars, and the remaining things be the $N$ items." Alternatively, it could also mean "For $N+K-1$ things, we want to choose $N$ of these things and have these be the items, and the remaining things will be the $K-1$ bars."

What if there's a constraint on how many items each bin has? For example, what if we constrained each bin to have at least 1 item (assume $N \geq K$)? What would be the approach? I was thinking in that situation, we can just remove $K$ items from $N$, leaving us with $N-K$ items, then we just simply apply the stars and bars approach again but with $N-K$ items instead of $N$, so we get

$$ \binom{N - 1}{K - 1} $$

As long as we have sufficient number of items, we can generalize this to a minimum of $c$ items in each bin $$ \binom{N - (c - 1)K - 1}{K - 1} $$

But how do we handle the case where there's a different minimum amount for each of the bins? For example, what if we specify that only 1 of the bin has to be non-empty, i.e., only 1 of the bin has to have at least 1 item?

In this situation, I think you can remove 1 item, place this item in, say, bin 1, and then use the formula $$ \binom{N - 1 + K - 1}{K - 1} $$ to place the remaining $N - 1$ items. However, this only accounts for bin 1 being non-empty, but there are $K$ possible choices for the non-empty bin, so the answer is

$$ K \binom{N - 1 + K - 1}{K - 1} $$

So for this case, it wasn't that difficult. But I would like to generalize this to be able to handle some minimum requirement for all bins. i.e.,, bin i must have at least $a_i$ items, where $$ \sum_{i=1}^K a_i \leq K \\ a_i \geq 0 $$

Is there a way to generalize this?