Math Core

Almost no AMC counting problem asks "how many ways to arrange $n$ things?" and stops there. There is always a catch: two people who must sit together, two letters that can't touch, a digit that can't be zero. This module is a toolkit of standard moves for handling restrictions quickly and without overcounting.

The basic tools

You already know the two building blocks:

Permutations (order matters): the number of ways to arrange $k$ of $n$ distinct objects in a row is $n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}$ .
Combinations (order doesn't matter): the number of ways to choose $k$ of $n$ distinct objects is $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

When some objects are identical, divide out the rearrangements that look the same. A word with $n$ letters in which one letter repeats $a$ times, another $b$ times, and so on has

$\frac{n!}{a!\,b!\,\cdots}$

distinct arrangements. For example, BANANAS has $\dfrac{7!}{3!\,2!} = 420$ arrangements.

Every restriction technique below is a way of turning a restricted problem back into one of these.

Move 1: Handle the most restrictive choice first

When filling slots one at a time, fill the pickiest slot first. To count four-digit odd numbers with distinct digits, the units digit has the tightest rule (it must be odd), and the thousands digit has the next tightest (it can't be $0$ ). Choose them in that order: $5$ choices for the units digit, then $8$ for the thousands digit (not $0$ , not the units digit), then $8$ and $7$ for the middle two. That gives $5 \cdot 8 \cdot 8 \cdot 7 = 2240$ .

If you had started from the thousands digit, the number of choices for the units digit would depend on whether the thousands digit was odd, and you'd need casework.

Move 2: Glue objects that must be together

If some objects must be adjacent, glue them into a single block, arrange the block with everything else, then multiply by the number of ways to arrange the objects inside the block.

Move 3: Use gaps for objects that must be apart

If certain objects must not be adjacent, first arrange the other objects. They create gaps (including the two ends), and you place the separated objects into distinct gaps. With $m$ objects in a row there are $m + 1$ gaps.

Move 4: Count the complement

"At least one" and "not all" are signals to count what you don't want and subtract from the total:

$\#(\text{good}) = \#(\text{all}) - \#(\text{bad}).$

For "these two are not adjacent," you can either use gaps or subtract the glued count from the total. Pick whichever is shorter.

The restriction toolkit

Pickiest first: fill the most restricted slot before the others.
Together: glue into a block, then multiply by the internal arrangements.
Apart: arrange the others, then drop the separated objects into distinct gaps.
At least one / not: count the complement and subtract.
Round tables: fix one person's seat to remove rotations, so $n$ people can be seated in $(n-1)!$ ways.

Worked example: Glue

In how many ways can $7$ people stand in a row if Ana and Ben must stand next to each other?

Glue Ana and Ben into one block. Now there are $6$ units to arrange: $6! = 720$ ways. Inside the block they can stand as AB or BA, so multiply by $2$ . The answer is $2 \cdot 720 = 1440$ .

Worked example: Gaps with repeated letters

How many arrangements of the letters of COUNTING have no two vowels adjacent?

The vowels are O, U, I (all different). The consonants are C, N, T, N, G, with N repeated. Arrange the consonants first: $\dfrac{5!}{2!} = 60$ ways. They create $6$ gaps:

$\_\ C\ \_\ N\ \_\ T\ \_\ N\ \_\ G\ \_$

Put the three distinct vowels into three different gaps, where order matters: $6 \cdot 5 \cdot 4 = 120$ ways. The answer is $60 \cdot 120 = 7200$ .

Worked example: At least one of each

A committee of $4$ is chosen from $6$ boys and $5$ girls. How many committees include at least one boy and at least one girl?

The bad committees are all boys or all girls. Total: $\dbinom{11}{4} = 330$ . All boys: $\dbinom{6}{4} = 15$ . All girls: $\dbinom{5}{4} = 5$ . The answer is $330 - 15 - 5 = 310$ .

Common mistake

A common wrong approach to "at least one boy and one girl" is: pick a boy ( $6$ ways), pick a girl ( $5$ ways), then pick any $2$ of the remaining $9$ ( $36$ ways), for $1080$ . This counts the same committee many times, because any boy on the committee could have been "the chosen boy." When you see "at least," reach for the complement.

Worked example: A round table

Four couples sit at a round table with $8$ seats. Rotations of the same seating count as the same. In how many ways can they sit if every couple sits together?

Glue each couple into a block. Four blocks around a round table: fix one block's position and arrange the other three, $3! = 6$ ways. Each couple can sit in $2$ orders, giving $2^4 = 16$ . The answer is $6 \cdot 16 = 96$ .

Tip

Choosing $k$ numbers from $\{1, 2, \dots, n\}$ with no two consecutive is a gaps problem in disguise: the answer is $\dbinom{n-k+1}{k}$ . Think of the $n - k$ unchosen numbers in a row; the $k$ chosen ones go into the $n - k + 1$ gaps, at most one per gap.

Practice

Practice 1

How many four-digit positive integers are odd and have four distinct digits?

Practice 2

Six different books are placed on a shelf. In how many orders can they be placed if two particular books must not be next to each other?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

In how many ways can $3$ numbers be chosen from $\{1, 2, 3, \dots, 20\}$ so that no two of the chosen numbers are consecutive?

Practice 4

How many distinct arrangements of the letters of BANANAS have the two N's not next to each other?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

Five students, including Ava and Bo, line up for a photo. Ava refuses to stand first in line and Bo refuses to stand last. How many lineups are possible?

Practice 6

How many five-digit positive integers have digits that are strictly decreasing from left to right (such as $97410$ )?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

Five men and five women sit at a round table with $10$ seats so that men and women alternate. Seatings that are rotations of each other are the same. How many seatings are there?

Practice 8

A path on a grid starts at $(0, 0)$ and moves one unit right or one unit up at each step until it reaches $(6, 4)$ . How many such paths do not pass through the point $(3, 2)$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 9

How many $4$ -element subsets $\{a, b, c, d\}$ of $\{1, 2, \dots, 12\}$ have the property that any two of their elements differ by at least $3$ ?

Real contest practice

2015 AMC 10A, Problem 10: rearrangements of four letters with an adjacency restriction.
2017 AMC 10A, Problem 19: seating five people in a row when some pairs refuse to sit together.