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 am wondering can some explain these concepts with examples

1.Counting the number of ways of distributing indistinguishable balls into distinct boxes,

2.Counting the number of ways of distributing distinct balls into distinct boxes,

share|improve this question

2 Answers 2

up vote 5 down vote accepted

These concepts come up in counting, but not so much in probability. We consider them in the order opposite to your list.

Distinguishable balls in distinguishable boxes: (This I think is the easier of the two to explain.)

We have $n$ distinct toys, to be given to $k$ kids. We put no restrictions on how many toys a kid may get. Some kids may get nothing.

The toys are the "balls," and the kids are the boxes. A kid does not care in what order she gets whatever toys she gets. A chemistry set, followed by a real semi-automatic pistol, is for her exactly the same as the same objects obtained in the opposite order.

For definiteness, suppose there are $8$ toys and $5$ kids. To count the number of ways to distribute the toys, line up the toys in some order. The order is totally irrelevant, and will play no role in the calculation.

Santa takes the first toy, and decides who to give it to. He has $5$ choices. For every decision about the first toy, Santa has $5$ choices as to who gets the second toy. And so on. The total number of choices available as Santa goes through all the toys is $5^8$. Exactly the same argument shows that there are $k^n$ ways to distribute $n$ toys among $5$ kids.

Indistinguishable balls in distinguishable boxes: So Santa is distributing $n$ identical candies among $k$ kids. I will describe a method often called Stars and Bars. There is a thorough discussion in Wikipedia.

Again, take a concrete case, $19$ candies and $5$ kids. It is to me easier to solve first a slightly different problem: How many ways are there to distribute $19$ candies among $5$ kids, with every kid getting at least one candy?

Line up the candies in a line, with a little gap between them. There are $18$ intercandy gaps. Choose $4$ of these gaps to put a divider into. Kid $1$ will get all the candies from the left end to the first divider. Kid $2$ will get all the candies between the first divider and the second divider, and so on.

It is not hard to see that there are just as many ways to distribute the candies as there are of placing the dividers. It follows that there are $\dbinom{18}{4}$ ways to distribute the candies with every kid getting at least one.

To solve the problem of distributing candies, where some kid(s) may get none, we use a cruel method to do the distribution. We distribute $19+5$ candies, at least $1$ to each kid. There are $\dbinom{23}{4}$ ways to do this. Then we take away a candy from each kid. Now the total number of candies the kids have is $19$. Every distribution of $19$ candies, with some kid(s) maybe getting none, can be done in this cruel way. So there are $\dbinom{23}{4}$ ways to distribute the candies, if there are no restrictions.

There are many related problems, where we put additional restrictions on the distribution. The idea generalizes immediately to $n$ kids and $k$ candies. You can write down and remember the appropriate formulas. I prefer to figure it out each time.

share|improve this answer
    
Chemistry sets and real semi-automatic pistols? Way too exciting! :-) –  Brian M. Scott Dec 2 '12 at 3:29
    
Thanks Really good explanation , I have two quick questions , first when we have at least (For example 2or 3) which method we need to use (is it the same properties as [link] math.stackexchange.com/questions/242233/… second when we need to use factorial to count in other words using factorial to count number of cases is for Distinguishable or Indistinguishable balls ? –  Hooman Dec 2 '12 at 4:57
    
Do you mean at least $2$ candies to each kid? Give them each $1$, then use the "at least one" candy procedure. For the distinguishable, it gets complicated, might have to use Inclusion/Exclusion. In solving a problem, one uses various tools. I am uncomfortable with the idea of trying to classify problems (here are all the situations where you use a hammer, here are the ones where you use a screwdriver). Much prefer to think here is a problem, now let's play around. –  André Nicolas Dec 2 '12 at 5:09
    
when we need to use factorial to count in other words using factorial to count number of cases is for Distinguishable or Indistinguishable balls ? –  Hooman Dec 2 '12 at 5:14
1  
In the indistinguishable case we used factorial indirectly, through binomial coefficients. In the distinguishable case we didn't. But there is no general rule. –  André Nicolas Dec 2 '12 at 5:17

Let's say you have two boxes, numbered $1$ and $2$, and three balls. For case 1, since you can't tell one ball from another, you can only count how many balls are in each box. The possibilities are $0+3, 1+2, 2+1, 3+0$ for a total of $4$. If each ball is numbered, so you can tell them apart, each ball can go in either box (2 choices 3 times) and you have $2^3=8$ possibilities.

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.