1. Permutations · Mastering AMC 8

1.10%

Permutations Definition

In this section you will be able to count arrangements by filling slots one at a time and multiplying the choices.

Your bike lock has 3 dials, and each dial shows a digit from 0 to 9. How many codes would a thief have to try? Guess first: is it 30? 100? 1000?

When the order of things matters, we call each arrangement a permutation. The big idea of this chapter is simple: fill the slots one at a time, and multiply the number of choices for each slot.

Exploreplay first, formulas later

Try this: Remove slots until there is just 1. How many passwords? Now add a 2nd slot. What happened to the count?
Try this: Open the tree diagram. Count the branches coming out of each dot. Why do the leaves multiply?
Try this: Make a 3-slot password where each digit must be odd (set every slot to 5 choices). Predict the count before you look.
Try this: Add a 4th slot. Predict the new total before it appears.

Name it

Definition 1.1.1

A permutation is a possible arrangement of objects in a set where the order of the objects matters.

Watch itpredict, then reveal

Example 1.1

How many 3-digit passwords are possible where each digit is a number from 0 to 9?

1
First, how many 1-digit passwords are there?

Predict first:
Your prediction

Try it

Problem 1.6.2

How many 3-digit numbers exist with all odd digits?

Problem 1.6.3

How many 3-digit numbers exist with all even digits?

Contest cornerreal contest problems

Problem 1.6.12

AMC 8

A special type of license plate includes 3 distinct letters at the beginning and 4 single-digit numbers after. How many such license plates exist?

Checkpoint for section 1.1

Get 2 of 3 right to master this section. One try each, no hints.

1.20%

Factorials

In this section you will be able to count the ways to line up n different things with n!, and know 0! to 6! by heart.

Sohil has 4 different wrapping papers and must use all of them, one layer on top of another. Unlike passwords, he can’t use the same paper twice. What changes?

Each time you use something up, the next slot has one fewer choice. Multiplying $4 \times 3 \times 2 \times 1$ comes up so often that it gets its own name and symbol: $4!$ , said “4 factorial”.

Exploreplay first, formulas later

Try this: Put the 4 books on the shelf one at a time. Watch the number under each spot. Why does it shrink by 1?
Try this: Turn on "Show all 24 orders" and press Play. Does every order appear exactly once?
Try this: Set 5 books. Predict how many orders before you place them.
Try this: Try flash-card mode on the factorial table until you know 0! to 6!.

Name it

Definition 1.2.1 · Factorials

A factorial is the product of all positive integers less than or equal to a given positive integer. In other words,

n! = n \times (n-1) \times (n-2) \times \cdots \times 1.

Remark 1.2.2

For math competitions, memorise these factorials. It will save you a lot of time:

$0!$	$1!$	$2!$	$3!$	$4!$	$5!$	$6!$
$1$	$1$	$2$	$6$	$24$	$120$	$720$

Use the flash-card mode in the widget above to practise them.

Definition 1.2.3

Reminder: a permutation is a possible arrangement of objects in a set where the order of the objects matters. Lining up all $n$ objects is the biggest permutation of all.

Theorem 1.2.4

The number of ways of arranging $n$ distinct objects is just

n! = n \times (n-1) \times (n-2) \times \cdots \times 1.

Watch itpredict, then reveal

Example 1.2

Sohil has 1 wrapping paper in each of 4 different colours: red, orange, green and blue. He needs to wrap all of them around a box in any order. How many ways are there for him to do this?

1
Start with the innermost layer. How many ways are there to choose a colour for this layer?

Predict first:
Your prediction

Example 1.3

Find the number of ways to arrange 4 different books on a bookshelf.

1
How many choices are there for the first book on the shelf?

Predict first:
Your prediction

Example 1.4

There are 4 different AMC 8 videos. Every student in the class watches the videos in a different order. What is the maximum number of students in the class?

1
Every student watches all 4 videos. What are we really counting?

Predict first:

open on YouTube

Try it

Problem 1.6.8

Find the number of ways to arrange 5 different books on a bookshelf.

Contest cornerreal contest problems

Problem 1.6.15

AMC 8

The Dragonvale Middle School chess team consists of two boys and three girls. A photographer wants to take a picture of the team to appear in the local newspaper. She decides to have them sit in a row with a boy at each end and the three girls in the middle. How many such arrangements are possible?

Problem 1.6.16

AMC 8

Professor Chang has nine different language books lined up on a bookshelf: two Arabic, three German, and four Spanish. How many ways are there to arrange the nine books on the shelf keeping the Arabic books together and keeping the Spanish books together?

Checkpoint for section 1.2

Get 2 of 3 right to master this section. One try each, no hints.

1.30%

Permutations Fundamentals

In this section you will be able to count ordered choices of k things out of n with the permutations formula.

A club of 7 people needs a president, a vice president and a secretary. Being president is not the same job as being secretary, so the order of picking matters. How many ways can the club fill the jobs?

This time we stop early: we only fill 3 positions, not all 7. So we multiply just the first 3 numbers of the countdown.

Exploreplay first, formulas later

Try this: Fill the 3 positions from 7 people. How many choices did each position have?
Try this: Set k equal to n. What do you get? (Hint: it's a factorial!)
Try this: Turn on Show the formula and press Cancel. Which numbers survive?

Name it

Theorem 1.3.1 · Permutations Formula

The number of ways to order $k$ objects out of $n$ total objects is

{}^{n}P_{k} = \frac{n!}{(n-k)!} = n \times (n-1) \times (n-2) \times \cdots \times (n-(k-1)).

Watch itpredict, then reveal

Example 1.5

Sam has 5 different stamps and is making a Christmas card where he puts 3 different stamps in a line. How many different Christmas card designs can he make?

1
How many choices are there for the first stamp in the line?

Predict first:
Your prediction

open on YouTube

Example 1.6

Evaluate ${}^{7}P_{3}$ .

1
Compare ${}^{7}P_{3}$ with the formula ${}^{n}P_{k}$ . What are $n$ and $k$ ?

Predict first:
Your prediction: nYour prediction: k

Example 1.7

Find the number of ways of selecting a president, vice president, and secretary from a group of 7 people.

1
How can we approach the problem?

Try it

Problem 1.6.1

Evaluate ${}^{6}P_{3}$ and ${}^{7}P_{2}$ .

Problem 1.6.5

If you have Alice, Betty, and Chase and you need to choose two of them to be the president and vice president of the math club, how many ways are there to do this?

Problem 1.6.6

Find the number of ways of selecting a president, vice president, and secretary from a group of 8 people.

Problem 1.6.9

How many ways are there to pick your favorite and second favorite book amongst 5 books?

Problem 1.6.10

There are 10 students at a math contest. How many ways are there to select the first, second, and third place winners?

Problem 1.6.13

There is a school race with 12 students. How many different ways are there to award the gold, silver, and bronze medals if no ties are possible?

Checkpoint for section 1.3

Get 2 of 3 right to master this section. One try each, no hints.

1.40%

Digit Permutations

In this section you will be able to count numbers with digit rules, starting with the most restrictive digit.

Passwords, licence plates, phone numbers: all “fill in the slots” problems. But numbers have a trap: the first digit can’t be 0.

Digit problems come with rules: odd, even, all different, no leading zero. The trick is to fill the pickiest slot first, so every slot’s number of choices stays fixed.

Look:if a slot’s number of choices depends on what you picked earlier, change the order you fill the slots in.

Exploreplay first, formulas later

digits4

1st digit

9

choices

2nd digit

9

choices

3rd digit

8

choices

4th digit

7

choices

9 × 9 × 8 × 7 = 4,536

Computer check (listing every one): 4,536e.g. 4136

Try this: With 4 distinct digits, why does the first slot have 9 choices and not 10?
Try this: Turn on "Start from the right". What goes wrong with the first digit?
Try this: Still starting from the right, press the "step" badge on the 1st digit until it is step 1 again. Does "it depends" go away?
Try this: Turn on Palindrome. Which slots stop being free choices?

Name it

Remark 1.4.1

Generally, in these problems we want to handle the most restrictive conditions first. In Example 1.8, if we started at the units digit, we would have trouble counting the options for the thousands digit (is 0 already used or not?). Then we would need casework, a more advanced technique that comes in a later chapter.

Watch itpredict, then reveal

Example 1.8

How many 4-digit numbers have all digits distinct?

digits4

1st digit

9

choices

2nd digit

9

choices

3rd digit

8

choices

4th digit

7

choices

9 × 9 × 8 × 7 = 4,536

Computer check (listing every one): 4,536e.g. 6705

1
For the first digit, how many choices do we have?

Predict first:
Your prediction

Example 1.9

How many 4-digit numbers exist such that the first digit is odd and the other 3 digits are even and all digits distinct?

digits4

1st digit

5

choices

2nd digit

5

choices

3rd digit

4

choices

4th digit

3

choices

5 × 5 × 4 × 3 = 300

Computer check (listing every one): 300e.g. 9260

1
How many choices are there for the first digit? For the 2nd digit?

Predict first:
Your prediction: 1st digitYour prediction: 2nd digit

Example 1.10

How many 5-digit palindromes are there? A palindrome is a number that reads the same forward and backward.

digits5

1st digit

9

choices

2nd digit

10

choices

3rd digit

10

choices

4th digit

1

copy of 2nd

5th digit

1

copy of 1st

9 × 10 × 10 × 1 × 1 = 900

Computer check (listing every one): 900e.g. 16561

1
A 5-digit palindrome looks like $ABCBA$ . Which digits can you choose freely?

Predict first:

open on YouTube

Example 1.11

Omega Learn

How many 6-digit numbers exist such that all the digits are distinct, the first 2 digits are 6 or more, the last 2 digits are 5 or less, and the 3rd digit is a nonzero multiple of 7?

digits6

1st digit

4

choices

2nd digit

3

choices

3rd digit

?

it depends (0–1)

4th digit

7

choices

5th digit

?

it depends (5–6)

6th digit

?

it depends (4–5)

It depends! Some slots change with earlier picks.

Computer check (listing every one): 900e.g. 687301

Look: when you fill the slots in this order, the number of choices for some slot changes depending on what you picked before. Try filling the most restrictive slot first.

1
Which digit is the most restrictive? How many choices does it have?

Predict first:
Your prediction

open on YouTube

Try it

Problem 1.6.4

How many 3-digit odd numbers are there with distinct digits?

Problem 1.6.7

Find the number of 3-digit numbers with all of its digits distinct.

Problem 1.6.11

How many 4-digit numbers are not palindromes? A palindrome is a number that reads the same forward and backward.

Contest cornerreal contest problems

Problem 1.6.14

AMC 8

How many integers between 1000 and 9999 have four distinct digits?

Checkpoint for section 1.4

Get 2 of 3 right to master this section. One try each, no hints.

1.50%

Circular Arrangements

In this section you will be able to count seatings around a round table, where turning the table doesn't make a new seating.

Five friends sit around a round pizza table. If everyone shifts one seat to the left, is that a new seating? Everyone still has the same neighbours, so no!

At a round table, only who sits next to whom matters. The trick: fix one person in place and arrange everyone else around them.

Exploreplay first, formulas later

Try this: Press Rotate 5 times. Did anyone get a new neighbour? So how many line-ups give the same table?
Try this: Turn on "Pin Alex to the top". How many people are left to arrange? Does that match (5 − 1)! = 24?
Try this: Turn on "Mirror images count as the same" and press Mirror. Why do we divide by 2?

Name it

Theorem 1.5.1 · Circular Arrangements

The number of ways of arranging $n$ objects in a circle, where rotations of the same arrangement aren't considered distinct, is

(n-1)!

If reflections (mirror images) of the same arrangement aren't considered distinct either, it is

\frac{(n-1)!}{2}.

Watch itpredict, then reveal

Example 1.12

How many ways are there to arrange 5 people in a circle if rotations are not counted as distinct orientations?

1
When people sit in a circle, what trick takes care of rotations?

Example 1.13

Omega Learn

How many ways are there to arrange 5 people around a circle such that 2 of the people, Alex and Bob, must sit next to each other? Note that rotations are not counted as distinct orientations.

1
Glue Alex and Bob together into one block. How many "units" sit around the table now?

Predict first:
Your prediction

open on YouTube

Example 1.14

Omega Learn

Gauss, Pauli, Einstein, Newton, Edison, and Faraday are sitting at a circular table. Einstein, Newton, and Faraday are enemies, so they refuse to sit next to each other. With this condition, how many ways are there for the 6 physicists to sit at the table if rotations are not counted as distinct orientations?

The enemies are Einstein, Newton and Faraday. Swap seats to find a seating where no two enemies touch.

1
Without the enemy rule, how many seatings are there?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 1.6.19

Omega Learn Math Competition

Alice, Bob, Claire, Dave, and Emma are sitting around a round table. Alice refuses to sit next to Bob. How many different ways can they sit around the table? (Rotations of the same arrangement are not considered different.)

Checkpoint for section 1.5

Get 2 of 3 right to master this section. One try each, no hints.

1.6

Practice Problems

In this section you will be able to mix every trick from this chapter on contest problems.

Time to mix it all up! These problems use slots, factorials, the permutations formula, digit rules and round tables, sometimes all at once. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Mixed practice

Problem 1.6.20(additional)

Omega Learn

7 people are lining up for a photograph. If the 2 tallest people must be at the 1st and 7th positions in any order and the shortest person must be in the center, how many ways are there for them to line up?

Contest cornerreal contest problems

Problem 1.6.17

MATHCOUNTS

How many permutations of the digits 1, 2, 3, 4 have 1 before 3 and 2 before 4? One such permutation is 2134.

Problem 1.6.18

AMC 10

Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of 5 chairs under these conditions?

Problem 1.6.21(additional)

EMCC 2014

Five distinct boys and four distinct girls are going to have lunch together around a table. They decide to sit down one by one under the following conditions: no boy will sit down when more boys than girls are already seated, and no girl will sit down when more girls than boys are already seated. How many possible sequences of taking seats exist?