# 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?

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?

• 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$. – 9301293 Apr 22 '15 at 18:33
• Here is a good reference for problems like this: math.wisc.edu/~ddrake/pdf/twelvefold-way.pdf – 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.