Combinatorics Progress
Completed0/11
0 completed0 in progress
Distinguishability
Distinguishability in combinatorics beyond the depth of school.
Author: Jaden Park
When distributing a group of things to another group of things, you need to consider the distinguishability of the objects. If they are distinguishable, you also need to consider if duplicates are allowed.
For each item, there are choices. This means there is a total of ways.
For each item, there are choices. This means there is a total of ways.
The following is a technique that has many names. The most notable ones are "stars and bars" and "balls and urns".
Basically, if you have indistinguishable items and you want to distribute it to distinguishable containers, then there are
ways to do so.
The proof behind this technique can be found online. You can also find videos demonstrating the technique with animations.
This is the worst one out of the ones as there's not formula and you're forced to do case checking.
When you are distributing indistinguishable items into indistinguishable groups, you're looking at a form of partitioning. This is a classic problem in combinatorics, where the focus is on counting the ways to divide a set of identical objects into groups without distinguishing between the groups.
For example, if you have indistinguishable items and you want to distribute them into indistinguishable groups, the problem becomes one of finding the number of partitions of into at most parts.
Here's an example worked through.
Let's say we have indistinguishable items and we want to distribute them into indistinguishable groups.
In this case, the possible distributions or partitions are:
Therefore, there are ways to distribute indistinguishable items into indistinguishable groups.
This is the reverse of the stars and bars technique. We are basically indistinguishable objects to distinguishable objects instead.
The the number of ways to distribute this is
This situation is trickier because it involves placing distinct items into indistinguishable groups without any repetition. Since the groups are indistinguishable, we care more about the composition of the groups rather than their order.
One way to approach this is to consider each distinct item and the group it could belong to. However, since no duplicates are allowed and the groups are indistinguishable, we're essentially looking at the number of ways to partition a set of distinguishable items into any number of groups.
This problem can be solved with the use of Stirling numbers of the second kind, which count the number of ways to partition of a set of objects to non-empty groups.
Here's an example worked through.
Let's consider distinguishable items (a red, blue, and green ball) that we want to distribute into any number of indistinguisable groups without duplicates.
There are three different possible cases.
1. All in one group : This is the simplest case. All items are together, and since the groups are indistinguishable, there's only way to do this.
2. Each in its own group : Every item is in a separate group. Since the groups are indistinguishable and each item must be in its own group, there's still only way to organize this.
3. Two items in one group, and the other in a separate group : This scenario requires a bit more thought. You're choosing items to be together and leaving the third one out. While it seems there could be several ways based on which two items you pick, the key is in recognizing that the groups are indistinguishable.
Here are the different possibilities:
For each choice, there's only way to distribute once you've selected the pair because of the indistinguishability of the groups. However, since there are distinct pairs possible, this gives us ways in total for this partition.
Therefore, there are a total of distinct ways to distribute.