1. Permutations and Combinations · Mastering AMC 10/12

1.10%

Factorials

In this section you will be able to compute factorials quickly and see why n! counts the ways to line up n different things.

How many ways can 5 different books stand on a shelf? Fill the shelf one spot at a time, and watch the choices shrink.

The first spot has 5 choices, the next has 4, and so on down to 1. Multiplying a countdown like $5 \times 4 \times 3 \times 2 \times 1$ comes up so often that it has its own symbol: $5!$ , read “5 factorial”.

Look:a fraction of factorials usually cancels to a short product:

10!/8! = 10 \times 9

.

Exploreplay first, formulas later

Try this: Place the 4 books one at a time. How many choices did each spot have? Why does the number drop by 1 each time?
Try this: Set 5 books. Predict the number of orders before you place them, then check.
Try this: Open the factorial table. How many times bigger is 7! than 6!? What about 10! compared with 9!?

Name it

Definition 1.1.1 · Factorial

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.

Checkpoint for section 1.1

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

1.20%

Permutations Basics

In this section you will be able to count arrangements in a line, around a circle, and of k objects chosen from n.

Seat 5 friends in a row, then around a round table. Why does the round table give fewer seatings?

In a row, $5! = 120$ seatings. At a round table, turning everyone one seat to the left keeps every neighbor the same, so those seatings are not new. The trick: fix one person at the top and arrange everyone else.

When you only fill some of the positions, stop the countdown early. That is the permutations formula below.

Exploreplay first, formulas later

Try this: Press Rotate 5 times. Did anyone get new neighbors? 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

Definition 1.2.1 · Permutation

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

Theorem 1.2.2 · Number of Orderings of Objects

The number of ways of arranging $n$ objects in a line is $n!$ .

The number of ways of arranging $n$ objects in a circle, where rotations of the same arrangement aren't considered distinct, is $(n-1)!$ .

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

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

Theorem 1.2.4 · Permutations Formula

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

{}^{n}P_{k} = \frac{n!}{(n-k)!}.

Pick 3 officers from 7 people: 7 × 6 × 5 = 7!/4!.

Checkpoint for section 1.2

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

1.30%

Permutations with Restrictions

In this section you will be able to count arrangements with rules by filling the most restrictive spot first.

How many 4 digit numbers have an odd first digit, three even digits after it, and no repeated digits?

Rules make some spots pickier than others. Fill the pickiest spot first. Then every other spot has a fixed number of choices, no matter what you picked before, and you can just multiply.

Look:if a spot’s number of choices “depends”, change the order in which you fill the spots.

Exploreplay first, formulas later

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

Try this: Fill the odd slot first, then the even slots. Did the odd digit use up any even choice?
Try this: Now turn off the rule on the first digit. Why do the counts start to depend on each other?
Try this: Example 1.3 below: which slot is the most restrictive? Fill it first and watch the other counts settle down.

Watch itpredict, then reveal

Example 1.1

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

1
How many choices does the first digit have?

Predict first:
Your prediction

Example 1.2

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?

1
Without the condition, how many seatings are there?

Predict first:
Your prediction

Example 1.3

Omega Learn

How many 6 digit numbers exist such that all the digits are distinct, its 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): ?e.g. 867924

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

Example 1.4

Peter is packing his pencil case for the AMC 12. He must pack 3 distinct pencils, 2 distinct erasers, and 2 distinct markers in some order. However, he will not put an item in his case if there are already more of that type of item than any other type of item. (E.g. Peter will not put another pencil in his case if there are already more pencils than markers or more pencils than erasers in the case.) How many different orders are there for Peter to put items in his case?

1
Peter can only add a type that is tied for the fewest items in the case. What must his first 3 items be?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Contest cornerreal contest problems

Problem 1.7.3

AMC 10

A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2 letters, also not necessarily distinct. These six characters may appear in any order, except that the two letters must appear next to each other. How many distinct license plates are possible?

Problem 1.7.6

AMC 10

Each square in a $3 \times 3$ grid of squares is colored red, white, blue, or green so that every $2 \times 2$ square contains one square of each color. One such coloring is shown on the right below. How many different colorings are possible?

Checkpoint for section 1.3

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

1.40%

Word Rearrangements

In this section you will be able to count rearrangements of words with repeated letters, glued blocks and alphabetical positions.

COMPUTER has 8 different letters. MISSISSIPPI doesn’t. What changes when letters repeat?

Swapping two identical letters gives the same word. So if you count as if every letter were different, each word gets counted too many times: once for every way to shuffle its repeated letters. Divide those repeats out.

The same trick works for anything with repeats: tiles, cubes, even the columns a marksman shoots at.

Exploreplay first, formulas later

720 labeled arrangements

6! = 720

These 12 labeled versions all spell the same word (first 6 shown):

BA₁N₁A₂N₂A₃
BA₁N₂A₂N₁A₃
BA₁N₁A₃N₂A₂
BA₁N₂A₃N₁A₂
BA₂N₁A₁N₂A₃
BA₂N₂A₁N₁A₃

3 As can swap places in 3! = 6 ways; 2 Ns can swap places in 2! = 2 ways. Turn the labels off and they collapse into one.

Tip: click (or press Enter on) one tile, then another, to swap them.

Try this: Turn on "Pretend duplicates are different" and label the A's 1, 2, 3. How many labeled words spell the same BANANA?
Try this: Turn the labels off. Which division just happened?
Try this: Type MISSISSIPPI. Predict the count with the formula before you press Use it.

Name it

Theorem 1.4.1 · Word Rearrangements

The number of ways to order a word is

\frac{n!}{d_1! \times d_2! \times d_3! \times \cdots}

where $n$ is the number of letters and $d_1, d_2, d_3, \ldots$ are the number of times each letter that occurs more than once appears in the word.

Remark 1.4.2

This is not only true for words! The number of ways of arranging objects (or anything else) with repeats is given by the same formula. In Example 1.6 the "letters" are the names of the columns.

Remark 1.4.3

Don't forget to add 1 to the number of words before USAMO in alphabetical order!

Watch itpredict, then reveal

Example 1.5

How many ways are there to rearrange the letters in COMPUTER such that the C, O, M, and P stay together (not necessarily in the same order)?

1
How should we deal with the condition that C, O, M and P must stay together?

Example 1.6

AIME

In a shooting match, eight clay targets are arranged in two hanging columns of three targets each and one column of two targets. A marksman is to break all the targets according to the following rules:

The marksman first chooses a column from which a target is to be broken.
The marksman must then break the lowest remaining target in the chosen column.

If the rules are followed, in how many different orders can the eight targets be broken?

1
Inside one column, can the marksman choose which target breaks first?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 1.7

AMC 10

Using the letters A, M, O, S, and U, we can form five-letter "words". If these "words" are arranged in alphabetical order, then the "word" USAMO occupies position

(A) $112$
(B) $113$
(C) $114$
(D) $115$
(E) $116$

1
In alphabetical order the letters are A, M, O, S, U. Which words come before USAMO because of their first letter? How many are there?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 1.7.1

AMC 10

How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are indistinguishable.)

Problem 1.7.2

AMC 10

A child builds towers using identically shaped cubes of different colors. How many different towers with a height of 8 cubes can the child build with 2 red cubes, 3 blue cubes, and 4 green cubes? (One cube will be left out.)

Problem 1.7.11

AMC 12Challenge

How many 15-letter arrangements of 5 A's, 5 B's, and 5 C's have no A's in the first 5 letters, no B's in the next 5 letters, and no C's in the last 5 letters?

Checkpoint for section 1.4

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

1.50%

Combinations

In this section you will be able to count selections where order doesn't matter, and combine several choices.

A company picks 2 managers from 6 applicants. Is “Ana, then Ben” a different choice from “Ben, then Ana”?

No: both give the same pair of managers. When order doesn’t matter, every group shows up $k!$ times among the ordered picks, so divide by $k!$ . That is “ $n$ choose $k$ ”.

Exploreplay first, formulas later

Try this: Count the ordered picks of 2 managers. Then press "Order doesn't matter". How big is each pile?
Try this: Set k = 3. How many ordered picks collapse into one group now? Why 3! ?
Try this: In the Pascal triangle under the theorem, find C(8, 3) and C(8, 5). Why are they equal?

Name it

Definition 1.5.1 · Combination

A combination is a possible arrangement in a collection of items where the order of the selection does not matter.

Remark 1.5.2

Usually, the words "permute", "order does matter", etc. mean a permutation, while the words "choose", "select", "order doesn't matter", etc. mean a combination.

Theorem 1.5.3 · Combinations Formula

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

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}.

This is usually read " $n$ choose $k$ ".

Pascal's triangle: row 8 holds C(8, 0) to C(8, 8). Look: C(8, 3) and C(8, 5) mirror each other.

Watch itpredict, then reveal

Example 1.8

Omega Learn

There are 6 experienced applicants and 7 inexperienced applicants applying for a job. Out of the experienced applicants, 2 managers are selected. Out of all of the other applicants who aren't selected for a manager (both experienced and inexperienced), 4 other employees are selected. How many ways are there to do this?

1
First, how many ways are there to select the 2 managers?

Predict first:
Your prediction

Example 1.9

Omega Learn

You have 12 different energy bars that you need to give to 3 people: Alice, Betty, and Chase. Alice needs 3 bars, Betty needs 4 bars, and Chase needs 5 bars. How many ways are there to distribute the 12 bars to satisfy their requirements?

1
Start with Alice. How many ways are there to choose her 3 bars?

Predict first:
Your prediction

open on YouTube

Example 1.10

EMCC

How many ways are there to place 4 balls into a $4 \times 6$ grid such that no column or row has more than one ball in it? (Rotations and reflections are considered distinct.)

1
The grid has 4 rows. How many of the rows get a ball?

Predict first:
Your prediction

open on YouTube

Example 1.11

Robert has 4 indistinguishable gold coins and 4 indistinguishable silver coins. Each coin has an engraving of one face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the 8 coins.

1
First, deal with the colors. How many ways are there to arrange the 4 gold and 4 silver coins?

Predict first:
Your prediction

Try it

Problem 1.7.12(additional)

Omega Learn

12 astronauts applied to go on a mission to explore Mars. 2 different rockets will be sent from Earth: one carrying 3 people and another carrying 4. Out of the 12 astronauts, 4 of them are very experienced so they must go on either rocket. How many ways are there to place the astronauts in the rockets?

Contest cornerreal contest problems

Problem 1.7.4

AMC 10

At a gathering of 30 people, there are 20 people who all know each other and 10 people who know no one. People who know each other hug, and people who do not know each other shake hands. How many handshakes occur within the group?

Problem 1.7.8

AMC 10

Values for $A, B, C$ , and $D$ are to be selected from $\{1, 2, 3, 4, 5, 6\}$ without replacement (i.e. no two letters have the same value). How many ways are there to make such choices so that the two curves $y = Ax^2 + B$ and $y = Cx^2 + D$ intersect? (The order in which the curves are listed does not matter; for example, the choices $A = 3, B = 2, C = 4, D = 1$ is considered the same as the choices $A = 4, B = 1, C = 3, D = 2$ .)

Problem 1.7.9

AIME

A game uses a deck of $n$ different cards, where $n$ is an integer and $n \geq 6$ . The number of possible sets of 6 cards that can be drawn from the deck is 6 times the number of possible sets of 3 cards that can be drawn. Find $n$ .

Problem 1.7.10

AMC 10A

What is the number of ways the numbers from 1 to 14 can be split into 7 pairs such that for each pair, the greater number is at least 2 times the smaller number?

Checkpoint for section 1.5

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

1.60%

Subsets

In this section you will be able to count subsets with 2 choices per element, and use clever pairings of subsets.

A burger shop offers 8 condiments, and you can take any collection of them. Each condiment is a switch: on or off.

Each element of a set is either in your subset or out of it. Two choices per element, so $2 \times 2 \times \cdots \times 2$ choices in all. That count includes the empty set, where every switch is off.

Exploreplay first, formulas later

Try this: Flip all switches off. Is that a subset? Does it count for a plain burger?
Try this: Turn off "Count the empty set". What changes in the count, and why only by 1?
Try this: Add one more element with the stepper. Why does the number of subsets double?

Name it

Theorem 1.6.1 · Number of Subsets

The number of subsets of a set of size $n$ is $2^n$ .

Watch itpredict, then reveal

Example 1.12

AMC 10

Two subsets of the set $S = \{a, b, c, d, e\}$ are to be chosen so that their union is $S$ and their intersection contains exactly two elements. In how many ways can this be done, assuming that the order in which the subsets are chosen does not matter?

1
Call the subsets $A$ and $B$ . Since $A \cup B = S$ , how many places can each element go?

Predict first:
Your prediction

open on YouTube

Example 1.13

AIME

For $\{1, 2, 3, \ldots, n\}$ and each of its non-empty subsets a unique alternating sum is defined as follows. Arrange the numbers in the subset in decreasing order and then, beginning with the largest, alternately add and subtract successive numbers. For example, the alternating sum for $\{1, 2, 3, 6, 9\}$ is $9 - 6 + 3 - 2 + 1 = 5$ and for $\{5\}$ it is simply $5$ . Find the sum of all such alternating sums for $n = 7$ .

Elements3

Your subset S

{1, 2}

2 − 1 = 1

Partner: S with 3 flipped

{1, 2, 3}

3 − 2 + 1 = 2

Look: the pair adds to 1 + 2 = 3. Adding 3 on top flips every other sign, so everything cancels except 3.

All 4 pairs
S without 3	sum	S with 3	sum	pair
∅	0	{3}	3	3
{1}	1	{1, 3}	2	3
{2}	2	{2, 3}	1	3
{1, 2}	1	{1, 2, 3}	2	3

1
It's possible to add them all by hand, but there's a cleverer way. For $n = 3$ , what is the sum of all alternating sums?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 1.7.7

AMC 10

Henry's Hamburger Haven offers its hamburgers with the following condiments: ketchup, mustard, mayonnaise, tomato, lettuce, pickles, cheese, and onions. A customer can choose one, two, or three meat patties and any collection of condiments. How many different kinds of hamburgers can be ordered?

Checkpoint for section 1.6

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

1.7

Practice Problems

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

Time to mix it all up. These problems use factorials, choose-formulas, word rearrangements and subsets, sometimes all at once. Each one has three hints if you get stuck.

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

Contest cornerreal contest problems

Problem 1.7.5

AMC 10/12

In a table tennis tournament every participant played every other participant exactly once. Although there were twice as many right-handed players as left-handed players, the number of games won by left-handed players was $40\%$ more than the number of games won by right-handed players. (There were no ties and no ambidextrous players.) What is the total number of games played?

Problem 1.7.13(additional)

AIME

Ten points in the plane are given, with no three collinear. Four distinct segments joining pairs of these points are chosen at random, all such segments being equally likely. The probability that some three of the segments form a triangle whose vertices are among the ten given points is $m/n$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

Problem 1.7.14(additional)

AIME

Three numbers, $a_1, a_2, a_3$ , are drawn randomly and without replacement from the set $\{1, 2, 3, \ldots, 1000\}$ . Three other numbers, $b_1, b_2, b_3$ , are then drawn randomly and without replacement from the remaining set of 997 numbers. Let $p$ be the probability that, after suitable rotation, a brick of dimensions $a_1 \times a_2 \times a_3$ can be enclosed in a box of dimensions $b_1 \times b_2 \times b_3$ , with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?