# 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\)

#### Contents

## Base Case for Distinct Objects into Distinct Bins

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\)

Discount Al's Thrift Shop is having a one-day going-out-of-business sale in which everything must go!

Al only has four distinct things left in his shop.

All the years that Al has been in business, he's only ever had four distinct customers, and he does not expect that to change today

At the end of the day, the bank representative will come to foreclose the shop, and he will take whatever is left.

How many ways can Al's things be sold to his customers (or taken by the bank)?

## Distributing Part of a Set of Objects

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\).

At a farm auction, various pieces of farm equipment and livestock are bid on and sold.

Today, there are 7 distinct items up for auction, and there are 3 farmers bidding on them. One of the farmers declares that he will be bid on *at least* 2 of the items (not specifying which ones), and he *won't* be outbid.

If this farmer is telling the truth, then how many ways can the items be distributed among farmers?

Assume that all items are sold.

## Distribution into Non-empty Bins

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 onebin is left empty.Our goal is to find the number of distributions in which

\[\text{The goal area is shaded in blue}\]nobin is left empty. This will be \(|U|-|A\cup B\cup C|\).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\]

Sri and Godfrey are marooned on a desert island.

Together, they have a toothbrush, a calculator, a volleyball, an mp3 player, a kite, and a shovel.

They decide to distribute these objects randomly among themselves. However, they agree that each person should get at least one object.

How many ways can the objects be distributed among Sri and Godfrey?

It is the end of the school year, and a teacher is giving out awards to her 3 students. She has 6 distinct awards (for grades, attendance, generosity, etc.) to give out, and she will give each award to the student who is most deserving.

However, she knows that her students can be rather immature, and one of them might throw a fit if he or she doesn't get an award. She secretly decides to make sure that each student gets at least one award (even if he or she doesn't deserve it).

How many ways can the awards be distributed among the students if all of the awards are given?

## See Also

**Cite as:**Distinct Objects into Distinct Bins.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/distinct-objects-into-distinct-bins/