Difference between revisions of "Distinguishability"
(→Indistinguishable to distinguishable (Balls and Urns)) |
m (→Indistinguishable to distinguishable (Balls and Urns)) |
||
Line 26: | Line 26: | ||
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so. | This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so. | ||
− | Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math>, which is our desired amount. Note that the number of stars that | + | Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math>, which is our desired amount. Note that the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). |
One common problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math> which has <math>\binom{n + k - 1}{k - 1}</math> solutions. | One common problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math> which has <math>\binom{n + k - 1}{k - 1}</math> solutions. |
Revision as of 23:11, 2 March 2009
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
- 1 Distinguishable to distinguishable, with duplicates
- 2 Distinguishable to distinguishable, without duplicates
- 3 Distinguishable to indistinguishable, with duplicates
- 4 Distinguishable to indistinguishable, without duplicates
- 5 Indistinguishable to indistinguishable
- 6 Indistinguishable to distinguishable (Balls and Urns)
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 6; this case has
ways (notice the difference between this and 6).
Distinguishable to indistinguishable, without duplicates
This is probably the most tedious cases, as it involves the most casework. One way is to first find all the partitions (refer to 5) of with
addends, (i.e. all solutions to
in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.
For example, if , then our partitions are:
--this case has
way.
--we choose one of
to be the "
", so there are
ways.
--we choose three objects to be the "
's" (the rest are determined after this), so there are
ways for this.
--again, we choose three objects to be the "
's" (the rest are determined after this), so there are
ways for this.
--first, we choose one object to be the "
", which has
ways. Then, we can choose any two of the remaining four to be one of the "
's", and there are
ways for this. However, we must divide this by
, since the two "
's" are interchangeable, and the total for this case is
.
Adding up, we get ways.
All of these problems are similar to this one in that you divide them up into smaller counting problems.
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.
Indistinguishable to distinguishable (Balls and Urns)
This is "Balls and Urns". In general, if one has indistinguishable objects that one wants to distribute to
distinguishable objects, 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
, which is our desired amount. Note that 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).
One common problem that can be solved by this is finding the number of solutions to , where
which has
solutions.