Lesson 3

Lesson 3: Problems Involving Permutations

Focus

Morse code is a method of transmitting messages using a series of clicks and pauses, short and long sounds, or flashes of light. The order and duration of the dots (called dits) and dashes (called dahs) are used to decipher the message.

Use Morse code to decipher the following; then check your answers.

The order of the dots, dashes, and spaces determine what word or letter of the alphabet is being represented. If the order of letters in a Morse code transmission is out of order, the message will be misunderstood or incorrect.

As you continue to work with permutations, you will need to remember that the order of the objects that are selected will play an important role in whether or not the solution is correct. Always ask yourself, “How does the order of the objects affect my answer?”

Lesson Outcome

At the end of this lesson, you will be able to determine the number of permutations of objects when not all objects are being arranged, some objects are identical, and there are conditions on the permutations.

Lesson Question

In this lesson you will investigate the following question: How can you determine the number of permutations when not all objects need to be arranged or when some of the objects are identical?

Assessment

Your assessment may be based on a combination of the following tasks:

• completion of the Lesson 3 Assignment (Download the Lesson 3 Assignment and save it in your course folder now.)
• course folder submissions from Try This and Share activities
• additions to Formula Sheet
• work under Project Connection

Discover

You have used factorial notation to determine the number of permutations of n items taken n at a time, but what happens if you are only going to arrange a subset of them? Remember a subset contains only some of the elements of the set.

Try This 1

Go to the Permutations gizmo at Learn Alberta.

Screenshot reprinted with

permission of ExploreLearning

1. Change the “Number of tiles in box” and “Number of draws from box” to complete a chart similar to the following. Use the list or tree tab to view the possible permutations.
   
   

   Number of Tiles in Box	Number of Draws from Box	Total Number of Possible Permutations	List Possible Permutations
   2	2	2	AE, EA
   2	1	2	A, E
   3	3
   3	2
   3	1
   4	4		Do not list.
   4	3		Do not list.
   4	2		Do not list.
   4	1
   5	5		Do not list.
   5	4		Do not list.
   5	3		Do not list.
   5	2		Do not list.
   5	1

2. In Lesson 2 you always determined the number of permutations using the entire set of objects. What was different in this activity as compared to the permutations you calculated in Lesson 2?
3. Describe any patterns you noticed in the chart. Explain why the patterns might exist.
4. Do AEI and IEA each count as one possible permutation? Did the order that the tiles were arranged in affect the number of possible permutations?

Save your responses in your course folder.

Explore

In Try This 1, you discovered different ways of calculating the number of permutations: you used lists, tree diagrams, and the fundamental counting principle. You also calculated the number of arrangements when you used all the tiles and when you only used some of the tiles.

Another way to calculate the number of permutations is by drawing blanks to represent the problem.

In how many ways can horses finish first, second, and third if there are 10 horses in the race?

You can draw blanks to represent finishing first, second, and third.

Assuming every horse is equally likely to win, you know that the first position can be filled in 10 ways, the second-place finisher could be any of the 9 remaining horses, and, finally, the third-place finisher could be any of the remaining 8 horses. Applying the fundamental counting principle, the number of ways the first, second, and third place positions could be filled is 10 × 9 × 8 or 720 different ways.

Notice that the order of the finish is important. If horses A, B, and C finish in that order, it is a different result from a finish of C, B, and A—even though the arrangement contains all the same horses.

Try This 2

You know that if you are trying to find the number of ways all 10 horses could finish, it would be 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1. Because you are only interested in the first three places, you only have 10 × 9 × 8. Is there a way to represent this in factorial notation?

1. Why are only three terms, 10 × 9 × 8, used to find the solution?
2. The expression 10 × 9 × 8 is no longer multiplied by the remaining factors, 7 × 6 × 5 × 4 × 3 × 2 × 1. Explain a process that can be used to remove these factors.
3. Write 7 × 6 × 5 × 4 × 3 × 2 × 1 in factorial notation.
4. Write 10 × 9 × 8 as a quotient using factorial notation.
5. Determine an expression for the denominator that uses the total number of horses, 10, and the number 3 that represents finding the first, second, and third finishers.

Save your responses in your course folder.

Share 1

With a group or partner, share your solutions to questions 4 and 5. How do your quotients compare?

Based on your solution to question 5, find a general expression for the number of permutation of n objects arranged r at a time.

If required, place a summary of your discussion in your course folder.

In Try This 2, you may have found that the problem can be represented by

When generalized for n objects taken r at a time, the total number of permutations is .

In the next Try This, you will use the tile data you collected in Discover to work with the permutations formula.

Try This 3

Retrieve your chart from Try This 1. Add one extra column, to the chart as shown.

1. Determine which column represents n and which column represents r.
2. Complete the chart by calculating  for the remaining rows. Show your work.  
3. In what instances could n! only be used to calculate the number of permutations, and when must  be used? Provide an example from the chart.

Save your responses in your course folder.

In Try This 3, you may have noticed that the  column and the total number of possible permutations are the same. This formula provides you with a way to calculate the permutations without the need for tree diagrams or lists. You will discover that the formula can be used to solve a variety of problems in Self-Check 1.

Self-Check 1

1. In how many ways can the president, vice-president, and secretary of the student council be selected from 30 people? Leave your answer in factorial form. Answer
2. How many 4-letter permutations can be formed from the word travel? State your answer in factorial notation and then evaluate. Answer
3. Consider the NHL playoffs. There are 15 teams in the Western Conference.
   
   
   
   Jupiterimages/Brand X Pictures/
   Thinkstock
   
   
   In the quarterfinals, the first-place team plays the eighth-place team, the second-place team plays the seventh-place team, the third-place team plays the sixth-place team, and, finally, the fourth-place team plays the fifth-place team.
   
   
   Western Conference Quarterfinal
   Playoff Format
   
   1st Place vs. 8th Place
   2nd Place vs. 7th Place
   3rd Place vs. 6th Place
   4th Place vs. 5th Place
   
   
   
   1. In how many ways can the top eight positions be filled? Answer
   2. Does it matter in which order you placed the teams—in other words, do you have to fill the first-place team first, the second-place team second, and so on? Answer
   3. Represent your solution using factorial notation. Answer

When presented with permutation questions, it is important to be able to identify n (i.e., the total number of objects there are to select from) and r (i.e., the number of objects being selected each time). Some questions will require you to do a little deciphering of the wording to find these values.

Consider the following scenario: There are 6 people boarding an empty bus that has 30 seats. In how many different ways may the people be seated?

If you would like to solve this by drawing blanks, draw your blanks for the elements that are most restricted. In this case, there are fewer people than seats; so draw the blanks to represent each person and then fill in the blanks with the number of seats they may choose from.

bus: iStockphoto/Thinkstock

Since the first person who gets on the bus has 30 seats to choose from, 30 is placed in the first blank. Now that a seat is taken, the second person has 29 seats to choose from, and so on.

Completing this solution by filling in all of the blanks, you get 30 × 29 × 28 × 27 × 26 × 25 or 427 518 000 ways.

If you chose factorial notation to solve this question, you would use the following formula:

In this example, n is 30 and represents the total number of seats; and r is 6 and represents the number of people who choose a seat. You are finding the number of ways of choosing 6 items (r) from 30 items (n). Using the formula, you would get the following:

Drawing blanks and determining the number of ways they could be filled works well when there is a small number of items being arranged; however, if there is a large number of items to be arranged, drawing blanks can be a tedious and time-consuming method.

For example, imagine that 100 people line up for 50 audition spots on a talent show. In how many ways can the 50 audition spots be filled? You could draw 50 blanks and work to fill them in, but you also know a formula that can be used to determine the number of permutations.

There are a total of 100 items, so n = 100. From these 100 items, only 50 are taken at a time, so r = 50. Use the formula to calculate the number of permutations.

You may recall that 69! is the largest factorial that can be calculated using a calculator. To get around this issue, many graphing calculators are programmed to determine the number of permutations using a different notation, nPr, where

• n is still the total number of objects
•  r is the number of objects you want in each arrangement

To calculate  you would use 100P50.

Investigate how to perform this on your calculator. You may need to reference the calculator�s guide or ask your teacher for assistance.

Self-Check 2

Some permutation problems involve more than one case. When more than one case is involved, you must calculate the number of permutations in each case and add them together. Here is an example involving cases.

Now that you have used the permutation formula, you may be asked to solve equations where n or r needs to be calculated. The solution to these questions will sometimes be very similar to ones you worked with in Lesson 2.

Watch Solving Permutations 1 and Solving Permutations 2 that demonstrate how to solve nP2 = 6 and 8Pr = 56.

Self-Check 4

You can use the permutation formula when there is a specified number of objects and, therefore, no repetitions. For example, if you need to create a 4-digit code for your phone and no repetitions are allowed, there are 10P4 = 5040 possible codes. If, however, repetitions are allowed, then there are 10 choices for each of the 4 spaces, so the total number of codes would be 10 × 10 × 10 × 10 = 10 000.

Often when working with permutations, there are some restrictions on where things can be placed. For example, in calculating the number of phone numbers available, you cannot use a 0 in the first space. Assuming you can use any of the other digits in any of the other spaces, your calculation of the total number of 7-digit phone numbers would look like this:

9 10 10 10 10 10 10

This gives you a total of 9 000 000 possible 7-digit phone numbers.

What happens if the items are not all different? Does this influence the number of permutations?

Sara and Mark are in math class, and their teacher asks them to figure out how many different ways the letters in their own names can be arranged. Sara can only come up with 12 arrangements, but Mark can figure out 24 arrangements. They both have 4 letters in their name. Why did they get different answers? Is one student right and one student wrong?

Complete the next Try This activity to explore this idea.

Try This 4

From doing Try This 4, you may have discovered that the number of permutations of n objects where r are identical, another s are identical, another t are identical, and so on, is

Now go back and think about the example with Sara and Mark. Why did they get different answers even though they have the same number of letters in their names? Sara has 12 arrangements since the letter A is used twice in her name. She could find the number of arrangements by using the repetitions formula Mark has no repeating letters, so the number of arrangements he can find is 4! or 24.

The idea of repeated elements can be used in other permutation problems as in the next Try This.

Try This 5

After their math class, Sara and Mark are going to his house to study for an upcoming math test. They wonder if they can use the concepts they learned in math class to figure out the number of routes they have to choose from in order to get from the school to his house. Mark’s house is 4 blocks east and 2 blocks south of the school. Since they don’t want to travel any extra distance, Sara and Mark plan to walk only east or south. Can you help them determine the number of routes?

Connect

Lesson 3 Assignment

Lesson 3 Summary

In this lesson you learned how to find the number of permutations of objects in several ways, including making a list, drawing a tree diagram, drawing blanks, using the fundamental counting principle, and using the permutation formula nPr. You learned that there are fewer permutations if there are identical items and that some methods are better and more efficient than others, depending upon the question posed.

The order the objects are placed is important when determining permutations. In the next lesson you will look at methods for counting ways of arranging objects when the order is not important.