permutation (original) (raw)

The number of permutations of a set with n elements is n! (see the rule of product).

A permutation can also be seen as a bijective function of a set into itself. For example, the permutation A⁢B⁢C↦C⁢A⁢B could be seen a function f:{A,B,C}→{A,B,C} that assigns:

In fact, every bijection of a set into itself gives a permutation, and any permutation gives rise to a bijective function.

Therefore, we can say that there are n! bijective functions from a set with n elements into itself.

Using the function approach, it can be proved that any permutation can be expressed as a composition of disjoint cycles and also as composition of (not necessarily disjoint) transpositions.

Moreover, if σ=τ1⁢τ2⁢⋯⁢τm=ρ1⁢ρ2⁢⋯⁢ρn are two factorization of a permutation σ into transpositions, then m and n must be both even or both odd. So we can label permutations as even or odd depending on the number of transpositions for any decomposition.