Answer 1: We could just list the ways. (This is called the brute force method!) JIM MJI IJM JMI MIJ IMJ There are six ways. Answer 2: Use the multiplication principle: We have three slots to fill: ___ ___ ___ The first task is to fill the first slot with a letter. There are 3 ways to complete this task. The second task is to fill the second slot. There are 2 ways to complete this task. (Once the first slot is filled, there are only two choices of letter to use for the second slot.) The third task is to fill the third slot. There is only 1 way to complete this task (once slots one and two are filled). By the multiplication principle, there are \(3 \times 2 \times 1 = 6\) ways to complete this job.
Answer: The brute force method wouldn’t be fun this time. But if we think of this as a counting problem with five tasks – place a first letter, place a second letter, and so on – we see that there must be \(5 \times 4 \times 3 \times 2 \times 1 = 120\) arrangements of the letters of JAMES.
When playing with these problems it is clear that the following definition is needed: Definition: For a given counting number \(N\), the product of integers from \(1\) to \(N\) is called factorial and is denoted \(N!\). These factorial numbers grow very large very quickly: \(1! = 1\) \(2! = 2 \times 1 = 2\) \(3! = 3 \times 2 \times 1 = 6\) \(4! = 4 \times 3 \times 2 \times 1 = 24\) \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\) \(6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\) \(7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040\) \(8! = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320\) (Does the definition given make sense for \(1!\) ? Does it worry you I write the products from \(N\) down to \(1\) instead of from \(1\) up to \(N\)?)
ON A CALCULATOR the factorial feature is usually hidden under the some PROBABILITY menu.
The factorials arise as answers to word rearrangement problems. For example, there are \(6 \times 5 \times 4 \times 3 \times 2 \times 1 = 6!\) ways to arrange the letters of BOVINE. So far all is fine and dandy. We can rearrange the letters of JIM and of JAMES and of other words. But we were lucky. What if my name were BOB? How might we handle repeated letters?
Answer exercise 11. It can be done easily via brute force. Do you think there might be another way to tackle this problem?
Try answering this one too. Does listing all the possibilities seem fun? Here’s one way to think of this problem … APPROACH 1: Think of this as a five-stage multitask. We have six slots: _ _ _ _ _ _ . Task 1: Assign the letter H to a slot. There are \(6\) ways to accomplish this task. Task 2: Assign the letter O to a slot. With the H in position, there are \(5\) ways to accomplish this task. Task 3: Assign the letter U to a slot. With the H and O in place, there are \(4\) ways to accomplish this task. Task 4: Assign the letter E to a slot. There are \(3\) ways to accomplish this task. Task 5: Assign the two Ss to slots. As there are only two slots left, there is only \(1\) way to accomplish this task. By the multiplication principle there are \(6 \times 5 \times 4 \times 3 \times 1\) arrangements of the letters HOUSES. This approach works well, at least for HOUSES. But it is not very helpful, however, for words (names) like ABBA and MISSISSIPPI. (Try it!) Allow me to suggest a second approach that does generalize nicely. It uses a useful strategy in problem-solving: CAN I CONVERT THE PROBLEM TO SOMETHING I HAVE SOLVED BEFORE? APPROACH 2: The problem with HOUSES is that it has repeat letters. What if it didn’t have repeat letters? Suppose the Ss were distinguishable, written, say, as S1 and S2. Then the problem is easy to answer: There are \(6!\) ways to rearrange the letters HOUS1ES2 . The list of arrangements might begin: HOUS1ES2 HOUS2ES1 OHUS1S2E OHUS2S1E S1S2UEOH S2S1UEOH etc. But notice, if the Ss are no longer distinguishable, then pairs in this list of answers “collapse” to give the same arrangement. We must alter our answer by a factor of two and so the number of arrangements of the word HOUSES is: \(\dfrac{6!}{2}=360.\) This agrees with the answer \(6 \times 5 \times 4 \times 3 \times 1\).
Answer: If the three Es are distinct – written E1 , E2 , and E3 , say – then there are \(6!\) ways to rearrange the letters CHE1E2S E3. But the three Es can be rearranged \(3! = 6\) different ways within any one particular arrangement of letters. These six arrangements would be seen as the same if the Es were no longer distinct: Thus we must divide our answer of \(6!\) by \(3!\) to account for the groupings of six that become identical. There are thus \(\dfrac{6!}{3!} = \dfrac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 6 \cdot 5 \cdot 4 = 120\) ways to arrange the letters of CHEESE. COMMENT: The number of ways to rearrange the letters HOUSES is \(\dfrac{6!}{2!}\). The “2” on the denominator is really \(2!\).
Answer: If the Es were distinguishable and the Ss were distinguishable, then we’d be counting the ways to arrange seven distinct letters: There are \(7!\) ways to arrange the letters of \(CHE_{1}E_{2}S_{1}E_{3}S_{2}\). As before there are \(3!\) ways to arrange the Es in any particular configuration. These groups of \(3!\) will “collapse” to the same arrangement if we remove the subscripts from the Es. But these new arrangements also collapse in pairs once we remove the subscripts from the Ss. So we need to take our answer of \(7!\) and divide it by \(3!\) and again by \(2!\) : \(\dfrac{7!}{3!} \div 2!\). BE SURE TO UNDERSTAND WHY THIS EQUALS \(\dfrac{7!}{3!2!}\). (which is much easier to read!)
|