Distinct Objects into Distinct Bins

Distinct objects into distinct bins is a type of problem in combinatorics in which the goal is to count the number of possible distributions of objects into bins.

A distribution of objects into bins is an arrangement of those objects such that each object is placed into one of the bins. In this type of problem, the objects and bins are distinct. This means that it matters which objects go into which bin when counting distributions.

Derrick is eating lunch with his friends, Edward and Francine. Derrick has an apple, a banana, and a cherry in his lunch that he is thinking about sharing. Derrick can give some, all, or none of his fruit away (e.g., he can keep fruit for himself). In how many ways can Derrick distribute his fruit?

---

In this problem, the "distinct objects" are the fruit, and the "distinct bins" they are being distributed to are the people.

This problem can be solved by listing out all the possibilities, but a more efficient way to solve this problem is to use the rule of product. There are 3 possible destinations for the apple, 3 possible destinations for the banana, and 3 possible destinations for the cherry. Because these objects are distributed at the same time, the rule of product is used, and thus there are $3\times 3\times 3=\boxed{27}$ possible distributions of the fruit. $_\square$

In the previous example, there was no regard for fairness when determining the possible distributions of fruit. One of the possible distributions had Derrick keeping all the fruit for himself. Another possible distribution had Derrick giving all the fruit to Francine. In the base case of the "distinct objects into distinct bins" problem, each object is placed independently, and this allows for the distributions to be counted efficiently using the rule of product.

Suppose there are $n$ distinct objects that are to be distributed among $r$ distinct bins. This can be done in precisely $r^n$ ways.

For each object, there are $r$ bins it can be placed into. This placement occurs for each of the $n$ objects. By the rule of product, this can be done in $\underbrace{r \times r \times r \times \cdots \times r} _{n \text{ times}} = r^n$ ways. $_\square$

We have 8 carrots of different sizes and 2 cute bunnies. In how many ways can we feed the bunnies? (The bunnies are very hungry, so they will eat all 8 carrots.)

---

In this question, we can model the carrots as objects and the bunnies as bins. Since they are all distinct, the above formula holds true. Therefore, the total number of ways in which the bunnies can be fed is $2^8 = 256$. $_\square$

Note: If you are familiar with binary numbers, you can think of it this way. Suppose we have an 8-digit binary number--the number of digits corresponds to the number of carrots, and the base of the number corresponds to the number of bunnies. If a digit is 0, it means that a carrot is given to the first bunny; if a digit is 1, it means that a carrot is given to the second bunny. For example, the number 01100001 means that the $2^\text{nd}, 3^\text{rd},$ and $8^\text{th}$ carrots are given to the second bunny. There are a total of $2^8$ 8-digit binary numbers, so the answer is 256.

In how many ways can $5$ balls, each of a different color, be distributed among $3$ distinct urns?

---

In this question, the balls are the objects and the urns are the bins. Since each ball has a different color, they are distinct, and the urns are distinct as well. Therefore, we can use the above formula and see this can be done in $3^5 = 243$ ways. $_\square$

The previous examples and problems covered situations in which all of the objects were distributed. However, what if only some of the objects are distributed? This opens up some interesting possibilities.

Suppose there are $n$ distinct objects, of which $k$ are to be distributed among $r$ distinct bins. This can be done in precisely $\binom{n}{k}r^k$ ways.

Note: $\binom{n}{k}$ is notation for the binomial coefficient.

There are $\binom{n}{k}$ combinations of $k$ objects chosen from $n$ distinct objects. These $k$ objects are then distributed among $r$ distinct bins. For each combination, there are $r^k$ distributions of the $k$ objects among the $r$ bins. Thus, there are a total of $\binom{n}{k}r^k$ distributions of $k$ objects, chosen from $n$ distinct objects, into $r$ distinct bins. $_\square$

Grandpa Joe has $8$ different presents that he is considering giving to his $5$ grandchildren. However, he decides that he'd like to keep $2$ presents for himself. How many ways can he distribute the remaining presents?

---

In this problem, there are $8$ distinct objects, of which $6$ are to be distributed among $5$ distinct bins. Using the above theorem, this can be done in precisely $\binom{8}{6}5^6=28\times15625=\boxed{437500}$ ways. $_\square$

This result is actually more than the number of distributions of $8$ distinct objects into $5$ distinct bins, $5^8=390625$.

More interesting and challenging problems can be made by imposing additional conditions. Generic formula for this type,

In how many ways can $5$ balls, each of a different color, be distributed among $3$ distinct urns such that no urn remains empty?

---

The restriction that no urn is left empty seems harmless, but it makes the problem much more complicated than previous problems and examples in this wiki.

If we use the generic formula we directly get $3^5-3*(3-1)^5+3+0$ . therefore $243-3*32+3 = \boxed{150}$ .

OR

Other way is to solve this problem is by using the principle of inclusion and exclusion.

First, consider what the problem would be without the restriction. Let $U$ be the set of all distributions of $5$ distinct objects into $3$ distinct bins. $|U|=3^5=243$.

Now let $A$ be the set of all distributions of $5$ distinct objects into the $1^\text{st}$ and $2^\text{nd}$ bins. Likewise, let $B$ be the set of all distributions into the $1^\text{st}$ and $3^\text{rd}$ bins, and let $C$ be the set of all distributions into the $2^\text{nd}$ and $3^\text{rd}$ bins.

$A\cup B\cup C$ will be the set of all distributions in which at least one bin is left empty.

Our goal is to find the number of distributions in which no bin is left empty. This will be $|U|-|A\cup B\cup C|$.

$$\text{The goal area is shaded in blue}$$

By the principle of inclusion and exclusion,

$$|A\cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

$|A|$ is the number of distributions of $5$ distinct objects into $2$ distinct bins. This is $|A|=2^5=32$. Without loss of generality, $|A|=|B|=|C|$.

$|A\cap B|$ is the number of distributions of $5$ distinct objects into $1$ distinct bin. This is $|A\cap B|=1$. Without loss of generality, $|A\cap B|=|A\cap C|=|B\cap C|$.

It is not possible for all three bins to be empty, so $|A\cap B\cap C|=0$.

Using the principle of inclusion and exclusion formula,

$$|A\cup B \cup C| =32+32+32-1-1-1+0=93.$$

Therefore, the number of distributions of $5$ distinct balls into $3$ distinct urns in which no urn is left empty is

$$|U|-|A\cup B\cup C|=243-93=\boxed{150}.\ _\square$$

• Distinct Objects into Identical Bins

• Identical Objects into Distinct Bins