Distinguishable Permutations
A common textbook question asks students to find the number of permutations for the letters in the word ‘BANANA’. Since there are 6 letters in the word BANANA, n=6. The total number of permutations is given by 6!, thus there are 720 arrangements for the letters. However, some of the permutations look the same. For example, BANANA and BANANA look the same, but the first and second ‘N’ swapped places, so they count as two permutations. How do we account for these duplications? How many distinguishable permutations, permutations that are look different from others, are there?
One way to compute the number of distinguishable permutations for the letters in ‘BANANA’ is to begin by counting the how many times each letter appears in the word. ‘B’ appears 1 time, ‘N’ appears 2 times, and ‘A’ appears 3 times. To find how many ways to arrange these letters, begin by selecting a letter. Suppose we started with placing ‘B’ into any of the six spaces. Next, we could find how many pairs of places to put the two ‘N’ letters. This is a combination problem that can be computed by taking ⧠5C⧠2 =10. Finally there is only 1 way left to place all three ‘A’ letters to fill in the remaining slots. Multiplying the ways to arrange ‘B’, two ‘N’, and three ‘A’ letters gives the total number of 6∙10∙1=60 distinguishable permutations. This is not the way our textbooks introduce and explain how to compute distinguishable permutations when there is repetition of items since this topic is introduced prior to combinations.
The textbook way of approaching the BANANA problem also begins by counting the number of letter repetitions. Since we know how many times a letter repeats, ni, we need to take ni! to find the number of ways we can permute that specific letter with its other identical letters. With the example, we have 3 ‘A’, 1 ‘B’, and 2 ‘N’ giving n1=3, n2=1, and n3=2. Taking n1!=3!=6 tells us that there are 6 copies of each distinct permutation that look identical only because the three ‘A’ letters are interchanged with one another. Likewise, n3!=2!=2 tells us that there are 2 copies of each distinct permutation that look identical due to the two ‘N’ letters interchanging. Since there is only 1 ‘B’, giving n2!=1, this does not increase the number of indistinguishable permutations. We multiply n1! ∙ n2! ∙ n3! together by using the Fundamental Counting Principle to find the total number of copies of each distinguishable permutation. Thus there are n1! ∙ n2! ∙ n3! = (6)(1)(2)=12 copies of each distinguishable permutation. Dividing by the total number of permutations, we find a total of 720/12=60 distinct permutations for the letters in ‘BANANA’.
The textbook method uses the formal definition which states: Suppose a set of n elements has n1 of one kind of elements, n2 of a second kind, n3of a third kind, and so on, with n = n1 + n2 + n3 + ⋯ + nk. Then the number of distinguishable permutations of the n objects is n! / (n1 + n2 + n3 + ⋯ + nk). This is sometimes also called a multinomial coefficient. In the textbook, no explanation as to why we divide by ni! for 1≤i≤k is provided. The textbook just expects us to follow along. Why do we need to divide by the product of each element’s number of repetitions? I plan to show my students the first solution approach to the BANANA problem and have them compare the 60 to the 60!/(3!∙1!∙2!) computed using the general rule.
Comments: