Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I don't understand why the second answer is different from the first. Aren't they the exact same thing?

How many ways can we distribute 10 distinct balls into 5 distinct boxes? $5^{10}$ is correct

How many ways can we distribute 10 identical balls into 5 distinct boxes? $\begin{pmatrix}14\\4\end{pmatrix}= 1001$

Why is the second question's solution not $5^{10}$?

share|improve this question

3 Answers 3

up vote 6 down vote accepted

Physical balls can never be perfectly identical, so the word "identical" should be taken as shorthand for "We don't care which ball ends up in which box—only how many balls end up in each box."

Let's consider a small example: 3 balls, $A,$ $B,$ and $C,$ and $2$ boxes, $1,$ and $2.$ If we care which ball goes in which box, the $2^3=8$ configurations, $C_j,$ are $$ \begin{aligned} C_1&1:\{A,B,C\},&& 2:\{\}&&\leftrightarrow\quad111\\ C_2&1:\{A,B\},&& 2:\{C\}&&\leftrightarrow\quad112\\ C_3&1:\{A,C\},&& 2:\{B\}&&\leftrightarrow\quad121\\ C_4&1:\{A\},&& 2:\{B,C\}&&\leftrightarrow\quad122\\ C_5&1:\{B,C\},&& 2:\{A\}&&\leftrightarrow\quad211\\ C_6&1:\{B\},&& 2:\{A,C\}&&\leftrightarrow\quad212\\ C_7&1:\{C\},&& 2:\{A,B\}&&\leftrightarrow\quad221\\ C_8&1:\{\},&& 2:\{A,B,C\}&&\leftrightarrow\quad222.\\ \end{aligned} $$ The last column shows why $2^3$ is the correct count: each of $A,$ $B,$ and $C$ must be assigned either to box $1$ or to box $2.$ Each assignment corresponds to a string of $1$s and $2$s.

If we don't care which ball goes in which box, then the $\binom{3+2-1}{3}=4$ configurations, $D_j,$ are $$ \begin{aligned} D_1&1:\text{3 balls},&& 2:\text{0 balls}&&\leftrightarrow\quad***\mid&&\leftrightarrow\quad C_1\\ D_2&1:\text{2 balls},&& 2:\text{1 ball}&&\leftrightarrow\quad**\mid*&&\leftrightarrow\quad C_2,C_3,C_5\\ D_3&1:\text{1 ball},&& 2:\text{2 balls}&&\leftrightarrow\quad*\mid**&&\leftrightarrow\quad C_4,C_6,C_7\\ D_4&1:\text{0 balls},&& 2:\text{3 balls}&&\leftrightarrow\quad\mid***&&\leftrightarrow\quad C_8.\\ \end{aligned} $$ The last column shows that some of the previous configurations are now considered "the same." The second-to-last column shows a "stars-and-bars" or "balls in bins" representation of each configuration. Note that, for example, $D_2$ corresponds to the three configurations $C_2,$ $C_3,$ $C_5$ because there are $\frac{3!}{2!\,1!}=3$ assignments of boxes to balls $A,$ $B,$ $C$ that contain two $1$s and one $2.$ In general, the number of $C_j$ that a given $D_i$ corresponds to is given by a multinomial coefficient. You can use the multinomial theorem to see exactly how the correspondence works.

share|improve this answer

You can think about it with colors:

For the first question you have 10 balls, each one of different color, so each solution will be different. But for the second all of them are of the same color, so some solutions will be the same.

share|improve this answer
    
fast u were­­­­ –  Awesome Mar 23 at 16:17

Suppose you have a bag of 100 candies. If they are all the same, then the candies you eat are measured only by quantity: 1 candy, 2 candies, etc.

If the candies are all different, then you can eat candy #1 and candy #2, or candy #1 and candy #7. In both cases you ate 2 candies, but the number of possibilities explodes once you give each candy its own name.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.