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 possible distributions of the fruit.
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 distinct objects that are to be distributed among distinct bins. This can be done in precisely ways.
For each object, there are bins it can be placed into. This placement occurs for each of the objects. By the rule of product, this can be done in ways.
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 .
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 and carrots are given to the second bunny. There are a total of 8-digit binary numbers, so the answer is 256.
In how many ways can balls, each of a different color, be distributed among 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 ways.
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)?
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 distinct objects, of which are to be distributed among distinct bins. This can be done in precisely ways.
Note: is notation for the binomial coefficient.
There are combinations of objects chosen from distinct objects. These objects are then distributed among distinct bins. For each combination, there are distributions of the objects among the bins. Thus, there are a total of distributions of objects, chosen from distinct objects, into distinct bins.
Grandpa Joe has different presents that he is considering giving to his grandchildren. However, he decides that he'd like to keep presents for himself. How many ways can he distribute the remaining presents?
In this problem, there are distinct objects, of which are to be distributed among distinct bins. Using the above theorem, this can be done in precisely ways.
This result is actually more than the number of distributions of distinct objects into distinct bins, .
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.
More interesting and challenging problems can be made by imposing additional conditions. Generic formula for this type,
In how many ways can balls, each of a different color, be distributed among 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 . therefore .
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 be the set of all distributions of distinct objects into distinct bins. .
Now let be the set of all distributions of distinct objects into the and bins. Likewise, let be the set of all distributions into the and bins, and let be the set of all distributions into the and bins.
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 .
is the number of distributions of distinct objects into distinct bins. This is . Without loss of generality, .
is the number of distributions of distinct objects into distinct bin. This is . Without loss of generality, .
It is not possible for all three bins to be empty, so .
Using the principle of inclusion and exclusion formula,
Therefore, the number of distributions of distinct balls into distinct urns in which no urn is left empty is
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?