Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?

864 Views Asked by At

I have n objects and k boxes, each box has its own size. The arrangement of objects in a box doesn't matter. How many combinations are there, respectively the formula?

Say we have 7 objects and 3 boxes with sizes of 2, 3 and 4. The solution is 6, the same result appears (it has to appear) when we place the gaps [(2+3+4)-7=2]

The multinomial coefficient only considers (I think so) the case when a box has to contain a specific number of objects, so the result is wrong: $$ \frac{7!}{2!\cdot 3!\cdot 4!} = 17.5 \not= \frac{2!}{2!\cdot 3!\cdot 4!} = \frac{1}{144} $$ But what's the correct formula?

1

There are 1 best solutions below

2
On BEST ANSWER

This count can be obtained using inclusion-exclusion as

$$ \sum_{S\subseteq B}(-1)^{|S|}\binom{n+k-1-\sum_{b\in S}(c_b+1)}{k-1}\;, $$

where $B$ is the set of boxes and $c_b$ is the capacity of box $b$: If the restriction is violated for the boxes in $S$, we can put $c_b+1$ objects in each box $b\in S$ and then count the number of ways of distributing the remaining objects. Here, contrary to convention, the binomial coefficient is taken to be zero if the upper index is negative. See also Balls In Bins With Limited Capacity.

In your example, this is

$$ \binom92-\binom62-\binom52-\binom42+\binom22=6\;. $$