Permutation Of A Set

Return to Glossary.

Formal Definition


A permutation of a set $A$ is a function $\phi:A \rightarrow A$ that is both one-to-one and onto.

Informal Definition


Essentially, a permutation is an ordering of the elements within the set.

Example(s)


Suppose that $A = {1, 2, 3, 4 ,5}$. One permutation of the set $A$ would look like

(1)
\begin{align} 1 \rightarrow 3 \\ 2 \rightarrow 5 \\ 3 \rightarrow 1 \\ 4 \rightarrow 4 \\ 5 \rightarrow 2 \end{align}

Suppose that $\sigma$ is the permutation given by equation (2). We write $\sigma$ in a more standard notation, changing the columns to rows in parentheses and omitting the arrows, as

(2)
\begin{align} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \end{align}

so that $\sigma(1)= 3, \; \sigma(2) = 5,$ and so on.

Non-example(s)


Let $A = {1,2,3,4,5}$ and let $\tau$ and $\psi$ be functions with $A$ being the domain of each. Now suppose $\tau$ is as follows:

(3)
\begin{align} \tau = \begin{pmatrix}1&2&3&4&5 \\ 1&4&4&2&3 \end{pmatrix} \end{align}

This is not a permutation since the function is neither one-to-one nor onto. Also, suppose $\psi$ looks like

(4)
\begin{align} \psi = \begin{pmatrix}1&2&3&4&5 \\ 4&5&6&1&3 \end{pmatrix} \end{align}

Even though this function is one-to-one, it is not a function mapping elements of $A$ to other elements of $A$ since $6 \notin A$, so $\psi$ is not a permutation of A either.

Additional Comments


A permutation can be the identity function as well.
A permutation is even if it can be expressed as an even number of traspositions. Otherwise, it is odd.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License