Find the number of ways in which 7 distinct objects can be put in three identical boxes so that no box remains empty.
This is similar to a problem i had in an old course where you had to find integers x,y,z s.t. x + y + z = some +ve integer.
So i think this one can be reworded as the 3 boxes being x,y and z. And n being 7 distinct objects.
Since you want +ve integers what to do is set x' = x-1 etc and then you get x' + y' + z' = 4.
This is done by using the binomial expression $\displaystyle \left(\begin{array}{cc}n + k-1\\k-1\end{array}\right)$ where k is the number of 'boxes'
So we get $\displaystyle \left(\begin{array}{cc}4+3-1\\3-1\end{array}\right) = \left(\begin{array}{cc}6\\2\end{array}\right)$ = 15.
Yeah i think my way was if there was 7 identical objects... 15 is waaaay to low.
But how did you get 322? I just did a 'brute force' method and came up about 99 but didnt really check it.
Since each box must contain 1 object it can be simplified down to how many ways can 4 objects be distributed between 3 boxes... This questions bugging me now...
EDIT: Is the answer just $\displaystyle 3^4 = 81$?
Well,this is how it goes.
Since the boxes are identical the problem reduces to the fact $\displaystyle 7$ distinct objects have to be divided(not distributed) into $\displaystyle 3$ groups as arrangement among the boxes are immaterial since the boxes are identical
The groupings can be done as follows$\displaystyle 1,3,3),(1,2,4),(2,2,3),(1,1,5)$
This can be done in following ways:
=$\displaystyle \frac{7!}{1!3!3!}\frac{1}{2!}+\frac{7!}{1!2!4!}+\f rac{7!}{2!2!3!}\frac{1}{2!}+\frac{7!}{1!1!5!}\frac {1}{2!}$
$\displaystyle =70+105+105+21$
$\displaystyle
=301
$
Either the answer is 301 or I have missed a grouping which is not likely
301 is correct.
The number is also $\displaystyle S(7,3)$, where S is the Stirling Number of the 2nd Kind.
(1,2,4) is same as (1,4,2) since boxes are identical.There is no such thing as the first box or the second or the third .
If 2 groups contain same number of objects then it is required that we divide by 2!.
For example if {a,b,c,d,e,f,g} are the 7 obects.One grouping containing (2,2,3) objects can be described as follows.
{a,b},{c,d}{e,f,g} and another can be {c,d},{a,b}{e,f,g}.
Now arent these groupings same.