Number of permutations
High school
Consider integers $n$ and $k$ such that $0 \leq k \leq n$. The number of permutations $P(n, k)$, read “$n$ permute $k$,” is the number of permutations of $k$ of $n$ objects, that is, the number of ordered lists of $k$ different objects chosen from $n$ objects:
\[P(n, k) = n (n - 1) \cdots (n - k + 1) = \frac{n!}{(n - k)!}.\]Examples
Worked examples
-
Choosing $2$ of the $3$ letters $A$, $B$, and $C$
: $P(3, 2) = 6$
High school
Choosing $2$ of the letters $A$, $B$, $C$ in order gives $P(3, 2) = 3 \cdot 2 = 6$ permutations, because there are $3$ choices for the first letter and then $2$ for the second. The six permutations are $AB$, $BA$, $AC$, $CA$, $BC$, and $CB$.
-
Electing a president and a vice president from a club of $10$ members
: $P(10, 2) = 90$
High school
Electing a president and a vice president from $10$ members has $P(10, 2) = 10 \cdot 9 = 90$ outcomes, because there are $10$ choices for president and then $9$ for vice president.
Properties
- The product $n (n - 1) \cdots (n - k + 1)$ counts the choices one position at a time: there are $n$ choices for the first object, $n - 1$ for the second, and so on, down to $n - k + 1$ for the $k$th.
- The number of permutations of all $n$ objects is $P(n, n) = n!$.
- Each combination of $k$ objects can be put in order in $k!$ ways, so $P(n, k)$ is $k!$ times the binomial coefficient: \[P(n, k) = k! \binom{n}{k}.\]
Notes
The number $P(n, k)$ is also written ${}n P_k$ (read “$n$ P $k$,” as on a calculator) or $n^{\underline{k}}$, the _falling factorial, read “$n$ to the $k$ falling.”
Distinctions involving this term
- Number of permutations vs. binomial coefficient: Many counting problems ask how many ways there are to choose $k$ different objects from a set of $n$ objects. If the order of the chosen objects matters, then the answer is the number of permutations $P(n, k)$, read “$n$ permute $k$”: \[P(n, k) = \frac{n!}{(n - k)!}.\] If the order does not matter, then the answer is the binomial coefficient $\binom{n}{k},$ read “$n$ choose $k$”: \[\binom{n}{k} = \frac{n!}{k! \, (n - k)!}.\] Each combination of $k$ objects can be put in order in $k!$ ways, so $P(n, k) = k! \binom{n}{k}$.