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)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)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)This is not a permutation since the function is neither one-to-one nor onto. Also, suppose $\psi$ looks like
(4)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.