How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contain at least 1 object?

Can anyone tell me how should I approach this question? I'm kinda stuck :(

I'm quite bad at questions involving placing indistinguishable objects into distinguishable boxes/ distinguishable objects into indistinguishable boxes and etc. Any tips on how to approach this kind of questions?

  • $\begingroup$ HINT: This is a classic balls and boxes problem: We will let the boxes be labeled $x_1, x_2, x_3, x_4$. We wish the same of all thing in the boxes to be $6$. Thus, we need to find how many was to satisfy the equation $x_1+x_2+ x_3+x_4=6$ with integer solutions such that $x_i \geq 1$. $\endgroup$ – 9301293 Apr 22 '15 at 18:33
  • $\begingroup$ Here is a good reference for problems like this: math.wisc.edu/~ddrake/pdf/twelvefold-way.pdf $\endgroup$ – user84413 Apr 23 '15 at 1:15

If we let s be the number of ways to do this, then the number of ways to distribute 6 distinguishable objects into 4 distinguishable boxes so that no box is empty is given by $4!(s)=24s$,

$\;\;\;$since there are $4!$ ways to label the boxes.

We can also count the number of ways to distribute the objects into 4 distinguishable boxes so that no box is empty using Inclusion-Exclusion:

If $T$ is the set of all distributions, and $A_i$ is the set of distributions with box i empty, for $1\le i\le 4$,

then $\lvert A_1^c\cap\cdots\cap A_4^c\lvert=\lvert T\lvert-\dbinom{4}{1}\lvert A_1\lvert+\dbinom{4}{2}\lvert A_1\cap A_2\lvert-\dbinom{4}{3}\lvert A_1\cap A_2\cap A_3\lvert$

$\hspace{1.3 in}=\displaystyle 4^6-4\cdot3^6+6\cdot2^6-4\cdot1^6=1560$,

so $24s=1560$ and therefore $s=65$.

This answer is $S(6,4)$, a Stirling number of the second kind.


Since each box contains an object, there are 2 cases to consider:

1) If there is a 3/1/1/1 distribution, then there are $\dbinom{6}{3}=20$ possibilities (since the boxes are identical).

2) If there is a 2/2/1/1 distribution, then there are $\displaystyle\frac{\binom{6}{2}\binom{4}{2}}{2!}=\binom{6}{4}\cdot3=45$ possibilities.

Therefore there are $20+45=65$ possible ways to do this.


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.