Difference between revisions of "Distinguishability"

Revision as of 14:46, 1 February 2009

When distributing $n$ things to $k$ other things, one has to consider the distinguishability of the objects (i.e. if they're distinguishable or not). If the $n$ 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.

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 $k$ things, there are $n$ choices, for a total of $\underbrace{n\cdot n\cdots n\cdot n}_k= n^k$ ways.

Distinguishable to distinguishable, without duplicates

For each of the $n$ things, there are $k$ choices, for a total of $\underbrace{k\cdot k\cdots k\cdot k}_n = k^n$ ways.

Distinguishable to indistinguishable, with duplicates

This is "reverse" Balls and Urns, or essentially distributing $k$ indistinguishable objects to $n$ distinguishable objects. Refer to 6; this case has $\binom{n + k - 1}k$ 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 $n$ with $k$ addends, (i.e. all solutions to $a_1 + a_2 + \cdots + a_k = n$ 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 $(n,k) = (5,3)$ , then our partitions are: $\{5,0,0\}$ --this case has $1$ way. $\{4,1,0\}$ --we choose one of $n$ to be the " $1$ ", so there are $5$ ways. $\{3,2,0\}$ --we choose three objects to be the " $3$ 's" (the rest are determined after this), so there are $\binom53 = 10$ ways for this. $\{3,1,1\}$ --again, we choose three objects to be the " $3$ 's" (the rest are determined after this), so there are $\binom53 = 10$ ways for this. $\{2,2,1\}$ --first, we choose one object to be the " $1$ ", which has $5$ ways. Then, we can choose any two of the remaining four to be one of the " $2$ 's", and there are $\binom42 = 6$ ways for this. However, we must divide this by $2$ , since the two " $2$ 's" are interchangeable, and the total for this case is $5\cdot6\cdot\frac12 = 15$ .

Adding up, we get $1 + 5 + 10 + 10 + 15 = 41$ 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 $a_1 + a_2 + \cdots + a_k = n$ , where $a_1,a_2,\ldots,a_k$ are indistinguishable.

This can be done with casework; the method is best explained with an example: say that $(n,k) = (5,3)$ . Our partitions are then $\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}$ , so there are $5$ partitions.

Indistinguishable to distinguishable (Balls and Urns)

This is "Balls and Urns". In general, if you have $n$ indistinguishable objects that you want to distribute to $k$ distinguishable objects, there are $\binom{n + k - 1}{k - 1}$ ways to do so.

Imagine that there are $k - 1$ dividers $\mid$ and $n$ objects $\star$ , so we have $\mid\mid\mid\cdots\mid\mid\mid$ and $\star\star\star\cdots\star\star\star$ . Then, label the areas formed by the dividers, so we get $1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k$ and our $n$ objects $\star\star\star\cdots\star\star\star$ . We can now see that there are $k$ distinct regions in which we can place our $n$ identical objects (so this is is analogous to the original problem), and there are $\binom{n + k - 1}{k - 1}$ arrangements of the $n$ stars and the $(k - 1)\ \mid\text{'s}$ .

One common problem that can be solved by this is finding the number of solutions to $a_1 + a_2 + \cdots + a_k = n$ , where $a_1,a_2,\ldots,a_n\ge0$ which has $\binom{n + k - 1}{k - 1}$ solutions.

@@ Line 23: / Line 23: @@
 This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.
-==Indistinguishable to distinguishable==
+==Indistinguishable to distinguishable (Balls and Urns)==
 This is "Balls and Urns". In general, if you have <math>n</math> indistinguishable objects that you want to distribute to <math>k</math> distinguishable objects, there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.

Page

Toolbox

Search