Math Core

A permutation is an arrangement of objects in order: runners on a podium, books on a shelf, letters in a word. Permutations are the multiplication principle applied to one special situation, and they come with a few standard tricks (blocks, gaps, repeated letters, round tables) that appear again and again in contests.

Arranging everything

To line up $5$ different books, there are $5$ choices for the first spot, $4$ for the second, and so on: $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ .

Definition

Factorial

For a positive integer $n$ , $n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$ is the number of ways to arrange $n$ different objects in a row. By convention $0! = 1$ .

Useful values: $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ , $7! = 5040$ .

Arranging some of them

If only $k$ of the $n$ objects are placed in order, stop the product after $k$ factors:

$P(n, k) = \underbrace{n \cdot (n-1) \cdots (n-k+1)}_{k \text{ factors}} = \frac{n!}{(n-k)!}.$

For example, a club of $10$ members can choose a president, a vice president and a treasurer in $10 \cdot 9 \cdot 8 = 720$ ways. The offices are different, so order matters.

Repeated objects

How many ways can you arrange the letters of $\text{LEVEL}$ ? If all five letters were different, there would be $5! = 120$ arrangements. But swapping the two L's, or the two E's, gives the same word. Each word was counted $2! \cdot 2! = 4$ times, so there are $120 \div 4 = 30$ distinct arrangements.

Arrangements with repeats

The number of ways to arrange $n$ objects where one kind repeats $a$ times, another $b$ times, and so on, is

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

Together and apart

Worked example: Glue them together

Five friends, including Ana and Bo, line up for a photo. In how many arrangements are Ana and Bo next to each other?

Glue Ana and Bo into a single block. Now arrange $4$ units (the block and the other three friends): $4! = 24$ ways. Inside the block, Ana and Bo can be in $2$ orders. Total: $24 \cdot 2 = 48$ .

Worked example: Keep them apart

In how many of the arrangements above are Ana and Bo not next to each other?

Count all arrangements and subtract the ones where they are together: $5! - 48 = 120 - 48 = 72$ .

Worked example: Around a table

In how many ways can $6$ people sit at a round table, if two seatings count as the same when everyone has the same left and right neighbors (that is, rotations are the same)?

In a row there are $6! = 720$ seatings. Around a table, each seating can be rotated to $6$ positions that all look the same, so there are $720 \div 6 = 120$ seatings.

Another way to see it: seat one person anywhere to "anchor" the table, then arrange the other $5$ in the remaining seats in order: $5! = 120$ .

Common mistake

With repeated letters, don't subtract the repeats; divide. Each distinct word is counted once for every way of shuffling the identical letters among themselves.

Tip

For a digit or letter restriction (the number must be odd, a vowel must come first), fill the restricted position first, then arrange the rest. If the objects include repeats, split into cases by what goes in the restricted position.