SAT Counting Problems: Permutations

Permutations On The SAT

Today I would like to talk about some more advanced methods for solving Counting Problems. The content presented here and in next week’s post is meant for more advanced students whose current SAT math score is at least a 600.

Last week we discussed some more basic methods which can be viewed by clicking the following link: Listing and the Counting Principle.

Please quickly review last week’s post before going on to the content below. Five minutes of review will really solidify the concepts from that post and will make the information in this post easier to learn.

Factorials

First let’s discuss factorials. The factorial of a positive integer n, written n!, is the product of all positive integers less than or equal to n.

n! = 1·2·3…n

0! is defined to be 1, so that n! is defined for all nonnegative integers n.

The definition for 0! may seem strange to many of you. Mathematicians have made this definition so that the formula n! = n(n – 1)! will be true for all positive integers n. Note that with this definition 1! = 1·0!

Also, I could make jokes about being really excited about factorials because we use an exclamation point in the definition – but let’s leave these for another day…

Permutations

Now a permutation is just an arrangement of elements from a set. The number of permutations of n things taken r at a time is

$Permutation Formula$

For example, the number of permutations of {1, 2, 3} taken 2 at a time is

$Permutation Example$

These permutations are 12, 21, 13, 31, 23, and 32.

The good news is that on the SAT you do not need to know the permutation formula. You can do this computation very quickly on your graphing calculator. To compute ₃P₂, type 3 into your calculator, then in the Math menu scroll over to Prb and select nPr (or press 2). Then type 2 and press Enter. You will get an answer of 6.

As always, let’s internalize these principles by putting them into practice. Here is a simple SAT problem that can be solved using permutations.

Examples

Four different books are to be stacked in a pile. In how many different orders can the books be placed on the stack?

Okay, now you could imagine stacking the books in different ways. Let’s try this by listing the different permutations. To distinguish the books let’s make one red, one blue, one yellow, and one green. Let’s abbreviate each book’s color by using its first letter.

rbyg rbgy rybg rygb rgby rgyb
bryg brgy byrg bygr bgry bgyr
yrbg yrgb ybrg ybgr ygrb ygbr
grby gryb gbry gbyr gyrb gybr

We now see that there are 24 arrangements.

The thing is that on the actual SAT I would rather not take the time to write out each permutation. There is a chance, under the time pressure of the test, that an error could be made or too much time could be spent checking that I have not duplicated any of the permutations.

Here are two more solutions that are much more efficient.

First we can use the counting principle that we reviewed in last week’s post: There are 4 possible books for the bottom of the stack. After placing the first book, there are 3 possible books that can go on top of the bottom book, then 2 books for the next position, and then 1 book for the top of the stack. Using the counting principle we get a solution of (4)(3)(2)(1) = 24 arrangements.

Or we can solve this problem even faster by using our new knowledge of permutations: There are 4 books, and we are arranging all 4 of them. Therefore there are ₄P₄ = 4! = (1)(2)(3)(4) = 24 arrangements.

I think you would agree that the last solution is much faster than the original solution by listing.

Let’s do one more SAT problem:

Three light bulbs are placed into three different lamps. How many different arrangements are possible for three light bulbs of different colors – one red, one green, and one yellow?

Again, we can list all the possibilities, abbreviating each color by using the first letter.

rgy ryg gry gyr yrg ygr

We can easily see that there are 6 arrangements.

And again, we can also use the counting principle: There are 3 possible lamps to place the red bulb in. After placing the red bulb, there are 2 lamps to place the green bulb in. Finally, there is 1 lamp left to place the yellow bulb in. By the counting principle we get (3)(2)(1) = 6 arrangements.

And finally we can solve this problem very quickly using our knowledge of permutations: There are 3 light bulbs, and we are arranging all 3 of them. So the number of arrangements is ₃P₃ = 3! = 1·2·3 = 6.

There are many more of these types of problems in my 28 SAT Math Lessons Series. Click on the picture below for more information about these books.