Find the number of ways in which 7 distinct objects can be put in three identical boxes so that no box remains empty.

Printable View

- May 27th 2009, 09:49 AMfardeen_genNumber of ways in which 7 distinct objects can be put..?
Find the number of ways in which 7 distinct objects can be put in three identical boxes so that no box remains empty.

- May 27th 2009, 04:45 PMDeadstar
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. - May 27th 2009, 05:14 PMSampras
- May 27th 2009, 05:26 PMDeadstar
Ah grim. Fixed!

- May 27th 2009, 05:31 PMDeadstar
Actually my first post was totally full of fail thanks for noticing that boxes thing...

- May 27th 2009, 08:35 PMfardeen_gen
The answer is 322. Are we missing something?

- May 28th 2009, 04:16 AMDeadstar
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$? - May 28th 2009, 08:27 AMpankaj
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 - May 28th 2009, 08:32 AMSampras
- May 28th 2009, 08:33 AMamitface
301 is correct.

The number is also $\displaystyle S(7,3)$, where S is the Stirling Number of the 2nd Kind. - May 28th 2009, 10:25 AMpankaj
(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.