Permutation

Definition · applies to arrangements of objects · also called arrangement, ordered selection

Elementary

A permutation of a list of items is another list that has the same objects in a different order.

High school

Consider a set of $n$ objects and a number $k \leq n$. A permutation of $k$ of the $n$ objects is an ordered list of $k$ different objects from the set, in which the order of the objects matters.

Undergraduate (combinatorics)

Consider a set $S$ with $n$ elements and a number $k \leq n$. A $k$-permutation of $S$ is an injective function

\[\sigma : \setdef{1, \dots, k} \to S,\]

which lists the elements $\sigma(1), \dots, \sigma(k)$ in order. A permutation of $S$ is an $n$-permutation of $S$, which is the same as a bijective function from $\setdef{1, \dots, n}$ to $S$.

Examples

Examples

• Electing a president and a vice president from a club of $10$ members High school
  Each outcome of electing a president and a vice president from $10$ members is a permutation of $2$ of the members, because the outcome lists who is president first and who is vice president second.
• The ordered list $(A, B)$ of $2$ of the letters $A$, $B$, and $C$ High school
  The ordered list $(A, B)$ is a permutation of $2$ of the letters $A$, $B$, and $C$, because it lists $2$ different letters in order. The list $(B, A)$ is a different permutation.

Non-examples

Things that may be mistaken for examples.

• Choosing a committee of $2$ members from a club of $10$ members High school
  A committee of $2$ members chosen from $10$ members is not a permutation, because the order does not matter: Ana and Ben is the same committee as Ben and Ana.
• Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters High school
  A draw of $6$ lottery numbers from $49$ is not a permutation, because a ticket wins with the right numbers in every order of drawing.
• The set $\setdef{A, B}$ of $2$ of the letters $A$, $B$, and $C$ High school
  The set $\setdef{A, B}$ is not a permutation, because a set does not list its elements in an order: $\setdef{A, B}$ and $\setdef{B, A}$ are the same set.

Properties

• The number of permutations of $k$ of $n$ objects is $P(n, k) = n! / (n - k)!$, and the number of permutations of all $n$ objects is $n!$.

Notes

In algebra, a permutation of a set $S$ is a bijection from $S$ to $S$, and the permutations of $\setdef{1, \dots, n}$ form the symmetric group $S_n$.

Distinctions involving this term

• Permutation vs. combination: Many counting problems choose $k$ different objects from a set of $n$ objects, and the result is either a permutation or a combination. A permutation is an ordered list of the chosen objects, so $(A, B)$ and $(B, A)$ are different permutations. A combination is the set of the chosen objects, with no order, so $\setdef{A, B}$ and $\setdef{B, A}$ are the same combination. For the numbers of permutations and combinations, see $P(n, k)$ vs. $\binom{n}{k}$.

All definitions · All distinctions · All examples