1
$\begingroup$

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,

2 Answers 2

5

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.

  • 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.2012-12-02
0

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.