0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your approach seems correct. Make sure your calculation is correct. $\endgroup$ – Anant Joshi Jan 15 '17 at 20:01
0
$\begingroup$

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.

$\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.