5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – David K Feb 19 at 13:38
4
$\begingroup$

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.

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

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

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