Permutations and Combinations

2.2 STEP TWO: Word Games

Lesson materials located below the video overview.

My name is JIM. In how many ways can I arrange the letters of my name?

 

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

P12001

By the multiplication principle, there are \(3 \times 2 \times 1 = 6\) ways to complete this job.

 

Actually, my formal name is JAMES. In how many ways can one arrange the letters of my proper first name?

 

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.

 

Exercise 9: In how many ways can one arrange the letters BOVINE ?

 

Exercise 10: In how many ways can one arrange the letters FACETIOUSLY?(What is unusual about the vowels of this word? Find another word in the English language with this property!)

 

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\)?)

 

What is the first factorial larger than a million? A billion?

 

ON A CALCULATOR the factorial feature is usually hidden under the some PROBABILITY menu.

 

What is the largest factorial your calculator can handle?

 

 

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?

 

 

Exercise 11: How many ways are there to arrange the letters BOB? Assume the Bs are indistinguishable?In how many ways can one rearrange the letters of ABBA?

 

Answer exercise 11. It can be done easily via brute force. Do you think there might be another way to tackle this problem?

 

In how many ways can one arrange the letters HOUSES?

 

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\).

 

How many ways are there to rearrange the letters of the word CHEESE?

 

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:

P12002

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!\).

 

Explain why the number of ways to arrange the letters of the word CHEESES is \(\dfrac{7!}{3!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.

P12003

But these new arrangements also collapse in pairs once we remove the subscripts from the Ss.

P12004

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!)

 

Exercise 12: In how many ways can one arrange the letters CHEEEEESIESSTT? (Be sure to understand why the answer is \(\dfrac{14!}{6!3!2!}\)).

 

Please join the conversation on Facebook and Twitter and kindly share this page using the buttons below.


Share on FacebookTweet about this on Twitter

Resources

resources

Books

Take your understanding to the next level with easy to understand books by James Tanton.

BROWSE BOOKSarrow

resources

Guides & Solutions

Dive deeper into key topics through detailed, easy to follow guides and solution sets.

BROWSE GUIDESarrow

light bulb

Donations

Consider supporting G'Day Math! with a donation, of any amount.

Your support is so much appreciated and enables the continued creation of great course content. Thanks!

heart

Ready to Help?

Donations can be made via PayPal and major credit cards. A PayPal account is not required. Many thanks!

DONATEarrow