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

Question

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!

Answer 1

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.

Answer 2

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} $$