3.2.1: Counting with Indistinguishable Objects - Optional Material

Learning Objectives

• Develop and use counting methods with at least some indistinguishable objects in a situation

Counting Situation with Indistinguishable Objects

In the previous counting examples, we were dealing with counting the number of outcomes that can occur when working with distinct objects: the objects were all different from each other in the selection. We now address a situation where some of the objects are the same (indistinguishable).

Consider the possible ways we can arrange five coins, two of which are indistinguishable gold (\(G)\) coins and three are indistinguishable silver (\(S)\) coins (we compare this with our Example \(\PageIndex{2.1}\) in which all five coins were distinguishable). Our previous work demonstrated that five distinguishable coins can be arranged in \(5!\) \(=120\) ways. However, in the case of indistinguishable coins, an order of GSSGS would be counted multiple times using our factorial counting approach. Using our same reasoning and computation adjustment in developing a combination count, we adjust the size of the total ordered count of \(5!\) by scaling down by the number of ways the two gold coins could be placed (there are \(2!\) such ways) and the number of ways the three silver coins could be placed (there are \(3!\) such ways). There are \( \frac{5!}{2! \cdot 3!}\) \(= \frac{120}{12}\) \(=10 \) ways we can arrange two indistinguishable gold coins with three indistinguishable silver coins. We might list all ten possibilities to verify our computational reasoning.

In this case of just two groups of indistinguishable objects, we might notice that this computation is technically the same as our combination method \( \sideset{_{5}}{_{2}}C \) \(=\frac{5!}{2! \cdot (5-2)!}.\) If we have two types of indistinguishable objects in our collection of five, with two being of one type, the remaining three must be of the other kind. In this situation, counting the number of ways we can select objects from among five with the order not mattering (i.e., a combination) is the same as counting the number of ways we can place two indistinguishable gold coins among five positions. The situations sound different, but the counting is the same.

Now, we can generalize beyond having two indistinguishable objects with the new counting method called the Permutation Rule with Some Objects Indistinguishable. In general, if there are \(n\) objects to order where all \(n\)-objects are among precisely one of the \(k\)-indistinguishable groups of \(n_1\) alike, \(n_2\) alike,\( \ldots\), \(n_k\) alike, then the number of recognizable different sequences (or permutations) of all \(n\) objects can be determined by\[ \nonumber \frac{n!}{n_{1}!\cdot n_{2}! \cdots n_{k}!}.\]Suppose we have ten coins, five of which are gold, two are silver, and three are copper. How many ways can these ten coins be arranged, given that each of the coins within the three metal groups is indistinguishable from the other? Using our recently developed counting strategy, we have \( \frac{10!}{5!\cdot 2! \cdot 3!}\) \(=\frac{3,628,800}{120 \cdot 2 \cdot 6}\) \(=2,520\) different distinguishable arrangements of these coins. Remember, in this calculation, we are taking all possible ordered arrangements as if we could tell the difference in the tens coins and scaling down using division by the number of arrangements each specific group can take.

Text Exercise \(\PageIndex{1}\)

Determine the number of outcomes for each of these situations.

1. Ben was born on \(10/20/2004.\) He wishes to use these \(8\) digits of his birth date to form a security code for a door lock. How many different door locks can he make from his birth date digits?

Answer

We notice that Ben has only four distinguishable digits in his \(8\)-digit birth date, namely zeros, ones, twos, and fours. We also notice there are \(4\) zeros, \(1\) one, \(2\) twos, and \(1\) four in that date. To make an \(8\)-digit code by different arrangements of these digits from his birth date, we count by computing \( \frac{8!}{4! \cdot 1! \cdot 2! \cdot 1!}\) \(=\frac{40,320}{24 \cdot 1 \cdot 2 \cdot 1}\) \(=840\) different codes. We notice that there are not very many different possibilities. If someone knew Ben was using the digits of his birth date, a computer program could quickly produce and possibly apply \(840\) codes to breach his security.

2. Mikala tosses a fair coin \(9\) times. What is the probability that her \(9\) tosses will yield exactly \(3\) heads and \(6\) tails?

Answer

First, we notice we are asked a probability question with a fair coin. We use the classical method to determine this probability since each outcome is equally likely; we must determine the total number of outcomes possible and the number of those outcomes that match our desired event description. When a coin is tossed \(9\) times, we know by our simple multiplication rule that there are \(2 \cdot 2 \cdots 2\) \(= 2^{9}\) \(= 512\) different outcomes in the ordered sample space. However, the tosses that involve \(3\) heads and \(6\) tails can happen in multiple ways, such as HHTTTHTTT or TTTHHHTTT. We must count the number of ways we can sequence \(3\) heads among the \(9\) positions (notice this is the same as asking for the number of ways we can sequence \(6\) tails among the \(9\) positions since the coin can only land either on heads or tails. There is no third indistinguishable outcome group). The three heads in any position cannot be distinguished and the six tails cannot be distinguished, so there are \( \frac{9!}{3! \cdot 6!}\) \(=\frac{362,880}{6 \cdot 720}\) \(=84\) ways to have \(9\) tosses that results in \(3\) heads and \(6\) tails. Mikala has the probability of \( \frac{84}{512}\) \(\approx 16.41\%\) of such an outcome. Again, we note that in this situation of "two-indistinguishable groups among all \(n\) trials", we could have computed our combination count \(\sideset{_{9}}{_{3}}C \) or \(\sideset{_{9}}{_{6}}C \) and received the same count of \(84.\)

3. Lanee has twelve cows to use in a study to compare three different diets, \(\text{A},\) \(\text{B},\) and \(\text{C}.\) Each of the diets is to be used on four of the cows. How many ways can the diets be assigned to the twelve cows?

Answer

We might first notice that a possible assignment of the diets to an ordering of the twelve cows could be:\[ \nonumber \text{A B C A B C A B C A B C}.\]A different assignment could be:\[ \nonumber \text{A A B B C C C C B B A A}.\]By these two examples, we see that a count of the number of ways in which we can assign the letters to twelve positions (representing the cows) will answer the question. There are \( \frac{12!}{4! \cdot 4! \cdot 4!}\) \(=\frac{479,001,600}{24 \cdot 24 \cdot 24}\) \(=34,650\) ways Lanee might assign the diets.

As a side note, some will call this the method of Distinguishable Permutations because we are counting the number of arrangements that can be distinguished from each other. If you have some indistinguishable objects, as we discussed above, some of the orders are not distinguishable due to some of the objects being indistinguishable. We only want to count distinguishable orderings, hence the terminology Distinguishable Permutations.