Permutations - Permutations in Combinatorics

Permutations in Combinatorics

In combinatorics a permutation of a set S with n elements is a listing of the elements of S in some order (each element occurring exactly once). This can be defined formally as a bijection from the set { 1, 2, ..., n } to S. Note that if S equals { 1, 2, ..., n }, then this definition coincides with the definition in group theory. More generally one could use instead of { 1, 2, ..., n } any set equipped with a total ordering of its elements.

One combinatorial property that is related to the group theoretic interpretation of permutations, and can be defined without using a total ordering of S, is the cycle structure of a permutation σ. It is the partition of n describing the lengths of the cycles of σ. Here there is a part "1" in the partition for every fixed point of σ. A permutation that has no fixed point is called a derangement.

Other combinatorial properties however are directly related to the ordering of S, and to the way the permutation relates to it. Here are a number of such properties.