I am interested in understanding a variation problem of distributing balls into boxes. It seems to be not any of the individual case mentioned in twelvefold way classification.
The problem is described as follows:
In total there are $K$ balls, there are $I$ distinguishable groups by color, and in each color group the balls are indistinguishable with number to be $n_i$ where $i = 1, 2, \ldots, I$. Meanwhile, we have $N$ distinguishable boxes where $N$ is always bigger than any $n_i$. Therefore, how many ways are there to distribute these $K$ balls into $N$ boxes, when no box can contain more than one ball from same indistinguishable color group and no empty boxes?
Any suggestion will be appreciated.
Best Answer
This is a straightforward application of the principle of inclusion-exclusion. First, count up all the ways to put all the balls into boxes, ignoring the condition that no box can be empty. This is simply $$ \prod_{i=1}^I \binom{N}{n_i} $$ Next, you have to subtract out the "bad" cases where some box is empty. For each of the $N$ boxes, there are $\prod_{i=1}^I \binom{N-1}{n_i}$ ways to place the balls where that box is empty, and you subtract this for each box, so we are left with $$ \prod_{i=1}^I \binom{N}{n_i}-N\cdot \prod_{i=1}^I \binom{N-1}{n_i} $$ However, distributions with two empty boxes were subtracted out twice by the above formula, so they must be added back in. The result is $$ \prod_{i=1}^I \binom{N}{n_i}-N\cdot \prod_{i=1}^I \binom{N-1}{n_i}+\binom{N}2\prod_{i=1}^I \binom{N-2}{n_i} $$ The summation continues developing in this way. The end result is $$ \boxed{\sum_{j=0}^N (-1)^j\binom{N}j\prod_{i=1}^I \binom{N-j}{n_i}.} $$