Thread: Number 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.

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.

Originally Posted by Deadstar

This is similar to a problem i had in an old course where you had to find integers w,x,y,z s.t. w + x + y + z = some +ve integer.

So i think this one can be reworded as the 4 boxes being w,x,y and z. And n being 7 distinct objects.

Since you want +ve integers what to do is set w' = w-1 etc and then you get w + x + y + z = 5.

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}5+4-1\\4-1\end{array}\right) = \left(\begin{array}{cc}8\\3\end{array}\right)$ = 56.

its $\displaystyle 3 $ boxes.

Ah grim. Fixed!

Actually my first post was totally full of fail thanks for noticing that boxes thing...

The answer is 322. Are we missing something?

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

Originally Posted by pankaj

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

What about $\displaystyle (1,4,2) $? Or $\displaystyle (1,5,1) $? Also why did you divide by $\displaystyle 2! $?

301 is correct.

The number is also $\displaystyle S(7,3)$, where S is the Stirling Number of the 2nd Kind.

Originally Posted by Sampras

What about $\displaystyle (1,4,2) $? Or $\displaystyle (1,5,1) $? Also why did you divide by $\displaystyle 2! $?

(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.