Permutations

In one sentence: A permutation is one way of picking some items and lining them up in a set order, and this formula counts how many such lineups exist.

$P(n, k) = \frac{n!}{(n-k)!}$

Read it out loud: “P of n, k, equals n factorial, divided by n minus k factorial. P is the number of permutations, n is how many different items there are, and k is how many of them you pick and line up in order. Factorial means multiply a whole number by every whole number below it, down to 1.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Factorial, $n!$: $n!$ is read ‘n factorial’. It means multiply $n$ by every whole number below it, down to 1. For example $4! = 4 \times 3 \times 2 \times 1 = 24$ , and $5! = 120$ . Factorials grow very fast: $10! = 3,628,800$ . By a rule everyone agrees on, $0! = 1$ , which keeps formulas like this one working.
Powers, like $10^{4}$: $10^{4}$ is read ‘ten to the power 4’. The small raised number says how many times to multiply the number by itself, so $10^{4} = 10 \times 10 \times 10 \times 10 = 10000$ . In the same way $3^{2} = 9$ . Powers come up when each spot has the same number of choices, as in a PIN code.
Order matters: Two lineups count as different when they put the same items in a different order. If runners A, B and C finish in that order, that is a different result from B, A, C, even though the same three runners are involved. A permutation counts these ordered lineups, while a combination ignores the order.
Multiplying counts of choices: When a choice is made in several steps, the number of ways is the number of options at each step multiplied together. If a shirt comes in 3 colors and 2 sizes, there are $3 \times 2 = 6$ shirts in total. This multiplying of choices is the main idea behind every permutation count.
Subtracting, like $n - k$: $n - k$ is the number of items left over after $k$ of them are chosen. If there are 8 runners and 3 places on the podium, then $8 - 3 = 5$ runners are not on the podium. This leftover count appears in the bottom of the formula.
No repeats: The permutation formula assumes that each item can be used only once. A choice can repeat when the same item may be used again, such as a digit in a PIN, where the digit 7 can appear twice. When repeats are allowed, the counting rule is different, as the mistakes section explains.

What each symbol means

Symbol	Meaning
$P(n, k)$	The number of permutations: how many different ordered ways there are to choose and line up $k$ items out of $n$ different items. It is a count of arrangements, so it has no unit. For $n = 8$ and $k = 3$ , it equals 336.
$n$	The number of different items available to choose from, a whole number such as 8 runners. It counts the items in the full pool, so it has no unit. It is always 0 or more.
$k$	The number of spots you fill in order, a whole number such as 3 places on a podium. When items cannot repeat, $k$ cannot be bigger than $n$ , because there would not be enough items to fill the spots.
$n!$	The factorial of $n$ , the product of every whole number from $n$ down to 1. For example $8! = 40320$ . It counts the ways to line up all $n$ items in a single row, so it has no unit.
$(n-k)!$	The factorial of the items left over, which is $n - k$ . For 8 runners and 3 spots, $(8 - 3)! = 5! = 120$ . Dividing by it cancels the extra orderings of the items that are not in the chosen spots.

The formula piece by piece

$n$: The number of different items available. In the podium example, $n = 8$ runners. Each spot can be filled by any runner who is still available, and the number of available runners goes down as spots are filled.
$k$: The number of spots you fill, in order. For a podium with gold, silver and bronze, $k = 3$ . It is a whole number from 0 up to $n$ , because with no repeats you cannot fill more spots than there are items.
$n-k$: The number of items left over after the $k$ spots are filled. For 8 runners and 3 spots, that is $8 - 3 = 5$ runners who are not on the podium. The bottom of the fraction uses this leftover count.
$n!$: The number of ways to line up all $n$ items in a single row. For 8 runners, $8! = 40320$ ways. It is the count before any spots are cut off, because every item is used in every position.
$(n-k)!$: The number of ways to line up the leftover items. When $n!$ is divided by $(n-k)!$ , the factors from $n - k$ down to 1 cancel, and only the factors for the $k$ filled spots remain.
$P(n, k) = \frac{n!}{(n-k)!}$: In one plain sentence: the number of ordered ways to choose and line up $k$ items from $n$ different items, with no repeats, equals $n$ factorial divided by the factorial of $n$ minus $k$ .

What the formula is doing, and why

What goes in and what comes out. You put in two whole numbers: $n$ , the number of different items, and $k$ , the number of spots to fill. You get out a count of the ordered ways to fill the spots without repeats. Order matters, so the lineup $ABC$ is different from $BCA$ . The answer is a whole number with no unit.

Why multiply the choices? Fill the spots one at a time. The first spot can take any of the $n$ items. The second spot can take any of the other $n - 1$ items, because the first item is already used. The third spot has $n - 2$ choices, and the $k$ th spot has $n - k + 1$ choices. Multiply all the choices together to get $n(n-1)(n-2)\cdots(n-k+1)$ .

Why the factorial form? $n!$ is the product of all $n$ numbers. Dividing by $(n-k)!$ removes the factors from $n - k$ down to 1, which leaves exactly the $k$ factors from $n$ down to $n - k + 1$ . Those are the choices we multiplied. Two edge cases check the formula. When $k = n$ , every item is used, and the answer is $n!$ . When $k = 0$ , nothing is picked, and the answer is 1, the single empty lineup.

When does it not apply? The formula is only for items that cannot repeat. If repeats are allowed, such as the digits in a PIN, every spot has all $n$ choices again, and the answer is $n^{k}$ . Also, $k$ cannot be bigger than $n$ when there are no repeats, because there would not be enough items to fill the spots.

An everyday picture

Think of a playlist. You have 10 songs and want to play 3 of them, in order. The first slot has 10 choices, the second has 9 songs left, and the third has 8 left. The playlist that plays A, B, C is different from the one that plays B, A, C, even though both use the same songs. So the count is $10 \cdot 9 \cdot 8 = 720$ playlists, which is $P(10, 3)$ .

Worked example: Podium places in an 8-runner race

Eight runners race. The top three finishers take gold, silver and bronze. Those are different places, so the order of the three names matters. Here $n = 8$ runners and $k = 3$ podium places. We want $P(8, 3)$ , the number of different ways to fill the three places.

Write the formula and put in the numbers. The formula says $P(n, k) = \frac{n!}{(n-k)!}$ . With $n = 8$ and $k = 3$ , the bottom becomes $(8 - 3)! = 5!$ , so $P(8, 3) = \frac{8!}{5!}$ .
Compute the factorials. $8! = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320$ . And $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ . Both start at a top number and multiply down to 1, so the bottom factorial is part of the top one.
Divide. $\frac{40320}{120} = 336$ . The division removes the $5!$ part of $8!$ , so all that is left is $8 \times 7 \times 6$ , one factor for each of the three spots.
Check by filling the spots. Gold can go to any of the 8 runners. Silver can go to any of the 7 runners who are left. Bronze can go to any of the 6 runners who are still left. So $8 \times 7 \times 6 = 336$ , which matches the formula.
Cross-check with groups. Ignoring order, there are 56 different groups of 3 runners. Each group can be arranged in $3! = 6$ orders, such as gold, silver, bronze in six ways. So $56 \times 6 = 336$ , which again gives 336 different podium results.

Answer: There are 336 different podium results from 8 runners. Each different order of the top three is a different result.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Ignoring order. Counting the podium as a set of three runners gives a smaller number, because gold, silver, bronze and bronze, silver, gold are different results. When order does not matter, use combinations instead.
Multiplying $n$ by $k$ . $P(8, 3)$ is $8 \times 7 \times 6 = 336$ , not $8 \times 3 = 24$ . Count down from $n$ for $k$ spots, one spot at a time.
Using this formula when items can repeat. The digits in a PIN can repeat, so the right count is $10^{4} = 10000$ options, not $P(10, 4) = 5040$ .
Asking for more items than exist. With 3 items and no repeats, there is no way to line up 5 of them, so $P(3, 5)$ does not exist. Make sure $k \le n$ .

Where you will meet it

Race results and rankings, where first, second and third place are different outcomes.
Counting anagrams, which are rearrangements of letters. The word CAT has $3! = 6$ arrangements of its three different letters: CAT, CTA, ACT, ATC, TAC and TCA.
Brute-force search in computing, which means trying every possibility one by one. A program can try every order of a list of distinct stops on a delivery route to find the shortest route.
Counting codes or passwords that cannot repeat a character, where the first character has $n$ choices and the next has one fewer.

Questions people ask

What is the difference between a permutation and a combination?

In a permutation the order matters, so the lineup ABC is different from BCA. In a combination the order does not matter, so ABC and BCA are the same group. Each group of $k$ items can be lined up in $k!$ orders, so the number of combinations is $\frac{P(n, k)}{k!}$ .

Why is $0! = 1$?

It is a rule that keeps formulas like this one working. With $k = n$ , the formula gives $P(n, n) = \frac{n!}{0!}$ . That must equal $n!$ , because every item is used. The only value of $0!$ that makes this true is 1.

How many ways can I arrange all $n$ items?

There are $n!$ ways. Five books on a shelf can be arranged in $5! = 120$ orders. That is the same as $P(5, 5)$ , because all five books are used and the shelf is filled in every possible order.

Big O Notation: Big O notation is a way to say that one function never grows faster than another, once the input is big enough.
Bits Needed: This formula counts the fewest bits you need so that every one of N items gets its own pattern of 0s and 1s.
Sum of the First n Integers: This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.