Partioning/Enumeration

Question

How many ways can one distribute

A) 15 Balls into 3 bags. Both bag and balls are distinct (labelled) and each bag must contain at least one ball.

B) 10 balls into 3 bags. again both bag and balls are distinct.

Thank you for your wisdom!

Regards

Answer 1

Hint

Try the following procedure:

1. Select how many balls for each bag, say $k_1 + k_2 + k_3 = n$ where $n$ is your number of balls. How many ways are there to do that?
2. Now how many ways are there to select $k_1$ balls from $n$ balls to go in the first bag?
3. How many ways to pick the $k_2$ balls to go into the second bag from $n - k_1$ balls?
4. How many ways to place remaining balls into the third bag?

Now, how many ways total could you perform this procedure in?

Answer 2

First problem: We use Inclusion/Exclusion. Call the bags A, B, and C.

There are $3^{15}$ ways to place the balls into bags, with no restriction. This is because for every one of the balls, we have $3$ choices for the bag it goes into.

However, every bag must contain at least one ball. So we count the number of bad ways to distribute the balls, that is, ways in which one or more bags remain empty.

There are $2^{15}$ distributions in which A is empty. Similarly, there are $2^{15}$ distributions in which B is empty, and $2^{15}$ in which C is empty.

If we calculate the sum $2^{15}+2^{15}+2^{15}$, we will have double-counted the $3$ distributions in which all the balls end up in the same bag.

For example, when we add together the $2^{15}$ for which A is empty, and the $2^{15}$ for which B is empty, we have double counted the distribution in which A and B are both empty, that is, all the balls end up in C.

So the number of bad distributions is $3\cdot 2^{15}-3$, and therefore the required number is $3^{15}-3\cdot 2^{15}+3$.

Second problem: This one is much easier, since there appear to be no restrictions.