Distinguishability
When distributing things to other things, one has to consider the distinguishability of the objects (i.e. if they're distinguishable or not). If the things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.
Contents
[hide]Distinguishable to distinguishable, with duplicates
For each of the things, there are choices, for a total of ways.
Distinguishable to distinguishable, without duplicates
For each of the things, there are choices, for a total of ways.
Distinguishable to indistinguishable, with duplicates
This is "reverse" Balls and Urns, or essentially distributing indistinguishable objects to distinguishable objects. Refer to 4; this case has ways. Now we can just switch the and the , so there are ways.
Indistinguishable to distinguishable (Balls and Urns/Sticks and Stones/Stars and Bars)
This is the "Balls and Urns" technique. In general, if one has indistinguishable objects that one wants to distribute to distinguishable containers, then there are ways to do so.
Imagine that there are dividers, denoted by , and objects, denoted by , so we have and . Then, label the regions formed by the dividers, so we get (since there are dividers) and our objects . We can now see that there are distinct regions (corresponding to the distinguishable objects) in which we can place our identical objects (corresponding to the indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are arrangements of the stars and the by basic permutations with repeated items. Note: the number of stars that appears in each of the regions represents the number of indistinguishable objects (the stars) given to a particular distinguishable object (of the dividers). For example, if we're distributing stars to kids, then one arrangement is corresponding to star to the first kid, to the second, to the third, to the fourth, and to the fifth.
One problem that can be solved by this is finding the number of solutions to , where , which has solutions.
Indistinguishable to indistinguishable
This is part of the partition problem. Imagine that you are finding the number of solutions to , where are indistinguishable.
This can be done with casework; the method is best explained with an example: say that . Our partitions are then , so there are partitions.
This idea could also be used to solve problems like how many ways can one pay 51 cents with quarters, dimes, and pennies?
You can solve the problem as below using casework where your cases are the amounts of quarters. For each case, the amount of ways is equivalent to the amount of dimes you can use as the rest of the money can be paid by pennies.
Case 1: 2 quarters
In this case, you cannot use any dimes, leaving only 1 case.
Case 2: 1 quarter
In this case, you can have either 0, 1, or 2 dimes, leaving 3 cases.
Case 3: No quarters
In this case, you can use up to 5 dimes, leaving 6 cases.
In total we have cases. Note that the best way this solution can be illustrated is by a chart.