Inclusion-exclusion problem, k different balls into n different cells

I was given the following problem: in how many ways can one put $k$ different balls into $n$ different cells, such that $m$ cells remain empty? $m,n,k \ge1$ , $k \ge n-m$

I tried to solve it using Inclusion–exclusion principle. First, choose $m$ cells for the empty ones. Then, find in how many ways one can put $k$ different balls into $(n-m)$ different cells, such that no cell remains empty, then multiply the results. I got this answer: $$\sum_{t=0}^{n-m} \frac{n!}{t! \cdot m!} \cdot(n-m-t)^{k-1} \cdot (-1)^t$$

Is my answer correct? Is it a good way to solve the problem?

Thanks.

• Your approach seems correct. Make sure your calculation is correct. – Anant Joshi Jan 15 '17 at 20:01

With this problem the salient feature is that the first guess which is

$$\sum_{q=m}^n {n\choose q} (-1)^{m-q} (n-q)^k$$

does not produce the correct answer. The underlying poset has nodes for each subset $P$ of the set $Q$ of $n$ cells where the node represents cells from $P$ plus possibly additional cells being empty, ordered by the superset relation with the node of all cells $Q$ being empty (which does not contain any configurations) being at the bottom. (With $P_1$ a superset of $P_2$ the configurations of the former constitute a subset of the latter.) Now a configuration that has exactly $p$ empty cells where $m\le p\le n$ receives total weight (sum of the weights of all nodes where it is included)

$$\sum_{q=m}^p {p\choose q} (-1)^{m-q}.$$

While this yields a weight of one for $p=m$ it is not equal to zero for $p\gt m$ and hence cannot be used to count configurations with exactly $m$ empty cells. A better approach is to choose the $m$ empty cells first and use a poset where the nodes $P$ represent the extra empty cells in addition to the $m$ already selected, which no longer participate in the inclusion-exclusion. This yields

$${n\choose m} \sum_{q=0}^{n-m} {n-m\choose q} (-1)^q (n-m-q)^k.$$

Here we are interested in the count of zero empty extra cells. The single node with $q=n-m$ is at the bottom. With tbis approach the weight of a configuration on the remaining $n-m$ cells with exactly $p$ extra empty cells where $0\le p\le n-m$ is given by

$$\sum_{q=0}^{p} {p\choose q} (-1)^q.$$

This evaluates to one when $p=0$ and is zero otherwise, which is precisely the weights that we require for this problem. Observe that we have a Stirling number here which can be seen by writing

$$\frac{n!}{m!} \frac{1}{(n-m)!} \sum_{q=0}^{n-m} {n-m\choose q} (-1)^{n-m-q} q^k$$

which yields

$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{m!} {k\brace n-m}.}$$

If we had not been asked to use inclusion-exclusion the answer would have been ${n\choose m} \times {k\brace n-m} (n-m)!$ by inspection.