Difference between revisions of "Distinguishability"

Latest revision as of 10:36, 31 July 2024

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.

Distinguishable to distinguishable, with duplicates

For each of the $k$ things, there are $n$ choices, for a total of $\underbrace{n\cdot n\cdot\cdots\cdot 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\cdot\cdots\cdot 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 4; this case has $\binom{n + k - 1}{k-1}$ ways. Now we can just switch the $n$ and the $k$ , so there are $\binom{k+n-1}{n-1}$ 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 $n$ indistinguishable objects that one wants to distribute to $k$ distinguishable containers, then there are $\binom{n + k - 1}{k - 1}$ ways to do so.

Imagine that there are $k - 1$ dividers, denoted by $\mid$ , and $n$ objects, denoted by $\star$ , so we have $\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}$ and $\underbrace{\star\star\star\cdots\star\star\star}_n$ . Then, label the regions formed by the dividers, so we get $1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k$ (since there are $k-1$ dividers) and our $n$ objects $\underbrace{\star\star\star\cdots\star\star\star}_n$ . We can now see that there are $k$ distinct regions (corresponding to the $k$ distinguishable objects) in which we can place our $n$ identical objects (corresponding to the $n$ indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are $\binom{n+k-1}n=\binom{n + k - 1}{k - 1}$ arrangements of the $n$ stars and the $(k - 1)\ \mid\text{'s}$ by basic permutations with repeated items. Note: the number of stars that appears in each of the regions $1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k$ represents the number of indistinguishable objects (the $n$ stars) given to a particular distinguishable object (of the $k$ dividers). For example, if we're distributing $9$ stars to $5$ kids, then one arrangement is $\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star$ corresponding to $1$ star to the first kid, $0$ to the second, $3$ to the third, $3$ to the fourth, and $2$ to the fifth.

One 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.

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.

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 $1+3+6=10$ cases. Note that the best way this solution can be illustrated is by a chart.

@@ Line 2: / Line 2: @@
 ==Distinguishable to distinguishable, with duplicates==
 For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.
 ==Distinguishable to distinguishable, without duplicates==
 For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.
 ==Distinguishable to indistinguishable, with duplicates==
-This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}k</math> ways (notice the difference between this and 6). This works because in every distribution, since the number of indistinguishable objects <math>k</math> is fixed, it only matters how many times each of the <math>n</math> distinguishable objects were used. If we let the number of times each of the <math>n</math> distinguishable objects were used be nonnegative <math>a_1,a_2,\ldots,a_n</math>, then we must have <math>a_1+a_2+\cdots+a_n=k</math>, which, as seen in 6, has <math>\binom{k+n-1}{n-1}=\binom{n+k-1}k</math> solutions.
+This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 4; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.
-==Distinguishable to indistinguishable, without duplicates==
+==Indistinguishable to distinguishable ([[Stars and bars|Balls and Urns]]/[[Stars and bars|Sticks and Stones]]/[[Stars and bars|Stars and Bars]])==
-This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.
+This is the "Balls and Urns" technique. In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable containers, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.
-For example, if <math>(n,k) = (5,3)</math>, then our partitions are:
+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> by basic permutations with repeated items. '''Note:''' 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). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.
-<math>\{5,0,0\}</math>--this case has <math>1</math> way.
-<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.
-<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.
-<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.
-<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.
-Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.
+One 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.
-All of these problems are similar to this one in that you divide them up into smaller counting problems.
 ==Indistinguishable to indistinguishable==
@@ Line 25: / Line 20: @@
 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 (Balls and Urns)==
-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> by basic permutations with repeated items. '''Note:''' 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). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.
+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.
-One 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.
+In total we have <math>1+3+6=10</math> cases. Note that the best way this solution can be illustrated is by a chart.
+[[Category:Combinatorics]]

Page

Toolbox

Search