# How many ways can n identical balls be distributed into k distinct boxes, such that at least one box is empty?

This is a problem in my combinatorics book that uses the principle of inclusion-exclusion. I can follow almost all of what is said, except the book says that if we consider $$A_{i}$$ to be the set of solutions where box i is empty, then $$|A_{i}| = {n-(k-1)-1 \choose k-1}$$.

The book does not explain why this is true. And I want to know why, since I thought that $$|A_{i}| = {n+(k-1)-1 \choose k-1}$$.

So that you can get to the root of my misunderstanding, my reasoning was that a placement of n identical balls into k distinct boxes is the same as the number of nonnegative integer solutions to $$x_{1}+\cdots+x_{k} = n$$.

Any help would be much appreciated!

• I think you are right. Perhaps it is a typo. Since this is an exercise in inclusion-exclusion, it might be instructive to follow the rest of the steps, see if the error is corrected, and also see if the final answer agrees with ${n+k-1\choose k-1} - {n-1\choose k-1}$ as explained in the answer below. (You might have to plug in actual numbers to do the checking.) – David K Feb 19 at 13:38

To begin with, I'd solve the problem differently: By a stars-and-bars, there are $$n-1\choose k-1$$ ways to place $$n$$ balls into $$k$$ bins such that no bin is empty. Subtract this from the $$n+k-1\choose k-1$$ ways to place $$n$$ balls into $$k$$ bins without restriction.

• (+1) sorry, I didn't see your answer when I posted my answer. – robjohn Feb 19 at 8:27

First of all, let's clear that, in common speaking
"distributing $$n$$ identical (undistinguishable) balls into $$k$$ distinct (distinguishable) boxes" does not have the same acception as
"launching $$n$$ identical (undistinguishable) balls into $$k$$ distinct (distinguishable) boxes"

In the first case (distributing, pouring, ..) it is understood that you consider the number of different occupation hystograms, i.e. the number of k-tuples $$(x_1,x_2, \cdots , x_k)$$ such that $$\left\{ \matrix{ {\rm 0} \le {\rm integer}\;x_{\,j} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = n \hfill \cr} \right.$$ which are the "weak" Compositions of $$n$$ into $$k$$ parts,
and in your particular case, the complement of the case in which no box is empty $$\left\{ \matrix{ {\rm 1} \le {\rm integer}\;x_{\,j} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = n \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ {\rm 0} \le {\rm integer}\;y_{\,j} \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,k} = n - k \hfill \cr} \right.$$ which are the "standard" Compositions of $$n$$ into $$k$$ parts.

As explained in the referenced article they are respectively $$N_w = \binom{n+k-1}{n} \quad N_s =\binom{n-1}{n-k} \quad \left| {\;0 \le n,k} \right.$$ note that this way of writing the binomials extends the definition also to null values of the parameters. The repartition of $$N_w$$ over the configurations with exactly $$j$$ empty boxes is given by $$N_w = \binom{n+k-1}{n} = \sum\limits_{\left( {0\, \le } \right)j\left( { \le k} \right)} {\binom{k}{j} \binom{n-1}{n - \left( {k - j} \right) } }$$

The number of configurations in which precisely the box $$i$$ is empty will then clearly be $$N_w(n,k-1)$$ if the others may be empty or not, and $$N_s(n,k-1)$$ if the others are non-empty.
So you are right, and the global answer to your problem will $$N = N_w - N_s = \binom{n+k-1}{n} - \binom{n-1}{n-k}$$