Permutation

Definition 1. A function ƒ:A→Bis called
1) injective (or one-to-one) if ƒ(x)=ƒ(y) for some x,y∈Anecessarily implies that x=y
2) surjective (or onto) if for each b∈B there exists a∈A such that ƒ(a)=b
3) bijective if ƒ is both injective and surjective.

Definition 2. Let ƒ:A→B and g:B→C be functions. Then, the composition of functions, denoted ƒ∘g, is a function from A to C defined as

(g∘ƒ)*(x)≝g(ƒ(x)) for all x∈A.

Lemma 1. Let ƒ:A→B, g:B→C and h:C→D be functions. Then:
1) h∘(g∘ƒ)=(h∘g)∘ƒ, that is, function composition is associative;
2)if ƒ and g are injective then g∘ƒ is injective;
3)if ƒ and g are surjective then g∘ƒ is surjective;
4)if ƒ and g are bijective then g∘ƒ is bijective.
Proof. 1) By Definition 2, for any x∈A we have
{[(h∘(g∘ƒ))*(x)=h((g∘ƒ)*(x))=h(g(ƒ(x)))],[((h∘g)∘ƒ)*(x)=(h∘g)*(ƒ(x))=h(g(ƒ(x)))])⇒(h∘(g∘ƒ))*(x)=((h∘g)∘ƒ)*(x)
2) If (g∘ƒ)*(x)=(g∘ƒ)*(y) for some x,y∈A then (since g is injective) we have ƒ(x)=g(y)which implies (since f is injective) that x=y.
3) Let c be an element of C. Then (since g is surjective) there exists b∈B such that g(b)=c. Since ƒ is surjective, there exists a∈A such that ƒ(a)=b. Therefore, we have (g∘ƒ)*(a)=g(ƒ(a))=g(b)=c.
4) Follows immediately from 2), 3) and Item 3 of Definition 1.

Definition 3. A function ƒ:[n]→[n] is called a permutation on n elements if ƒ is bijective. The set of all permutations on n elements we denote (S_n). For example, functions (ƒ_1),(ƒ_2):[3]→[3] defined by (ƒ_1)(1)=2, (ƒ_1)(2)=3,(ƒ_1)(3)=1 and (ƒ_2)(1)=3,(ƒ_2)(2)=2,(ƒ_2)(3)=1 are elements of (S_3). One way to denote a permutation ƒ∈(S_n) is to use so called two-line notation. In two-line notation (or two-row notation) of a permutation ƒ∈(S_n), one lists the elements of [n] in the first row, and for each one its image bellow it in the second row, that is
(1) ƒ=[[(i_1),(i_2),(i_3),…,(i_n)],[ƒ((i_1)),ƒ((i_2)),ƒ((i_3)),…,ƒ((i_n))]]
where ((i_1),(i_2),(i_3),…,(i_n)) is an ordered list of elements of [n] in which each element of [n] occurs only once. For example, functions (ƒ_1),(ƒ_2)∈(S_3) from above can be written in two-line notation in one of the following ways:
(ƒ_1)=[[1,2,3],[2,3,1]]=[[1,3,2],[2,1,3]]=[[3,2,1],[1,3,2]]=[[2,1,3],[3,2,1]]=[[2,3,1],[3,1,2]]=[[3,1,2],[1,2,3]]
and
(ƒ_2)=[[1,2,3],[3,2,1]]=[[1,3,2],[3,1,2]]=[[3,2,1],[1,2,3]]=[[2,1,3],[2,3,1]]=[[2,3,1],[2,1,3]]=[[3,1,2],[1,3,2]]
Note that
1. in the first row of two-line notation (1), the elements of [n] may appear in any order;
2. n distinct objects can be arranged in an ordered line in n! ways.
This immediately implies the following:
Statement 1. There are n! permutation in (S_n) and each of these permutations can be written in two-line notation (1) in n! ways.
For example, there are 3!=6 elements in (S_3)
[[1,2,3],[1,2,3]],[[1,2,3],[1,3,2]],[[1,2,3],[2,1,3]],(ƒ_1)=[[1,2,3],[2,3,1]],(ƒ_2)=[[1,2,3],[3,2,1]],[[1,2,3],[3,1,2]]
Let us calculate (ƒ_1)∘(ƒ_2) and (ƒ_2)∘(ƒ_1). We have
((ƒ_1)∘(ƒ_2))*(1)=(ƒ_1)((ƒ_2)(1))=(ƒ_1)(3)=1
((ƒ_1)∘(ƒ_2))*(2)=(ƒ_1)((ƒ_2)(2))=(ƒ_1)(2)=2
((ƒ_1)∘(ƒ_2))*(3)=(ƒ_1)((ƒ_2)(3))=(ƒ_1)(1)=3
and
((ƒ_2)∘(ƒ_1))*(1)=(ƒ_2)((ƒ_1)(1))=(ƒ_2)(2)=2
((ƒ_2)∘(ƒ_1))*(2)=(ƒ_2)((ƒ_1)(2))=(ƒ_2)(3)=1
((ƒ_2)∘(ƒ_1))*(3)=(ƒ_2)((ƒ_1)(3))=(ƒ_2)(1)=3
that is
(ƒ_1)∘(ƒ_2)=[[1,2,3],[1,3,2]] and (ƒ_2)∘(ƒ_1)=[[1,2,3],[2,1,3]].
Theorem 1. Let (S_n) be the set of all permutation on n elements. Then
1) ƒ∘g∈(S_n) for any ƒ,g∈(S_n);
2)h∘(g∘ƒ)=(h∘g)∘ƒ for any ƒ,g,h∈(S_n);
3)(S_n) has a special permutation called the identity permutation, denoted id_n, such that
ƒ∘id_n=id_n∘ƒ=ƒ for any ƒ∈(S_n);
4) for each ƒ∈(S_n) there exists an element in (S_n), denoted (ƒ^-1), called the inverse of ƒ, such that
ƒ∘(ƒ^-1)=(ƒ^-1)∘ƒ= id_n;
5) if n≥3, the composition of permutations of (S_n) is not commutative, that is, there are (ƒ_1),(ƒ_2)∈(S_n) such that (ƒ_1)∘(ƒ_2)≠(ƒ_2)∘(ƒ_1)
Proof. 1) Since, by Definition 3, ƒ and g are bijections, the statement follows immediately from item 4 of Lemma 1.
2) Since, by Definition 3, ƒ,g and h are functions, the statement follows immediately from item1 of Lemma 1.
3) It is straightforward to check that the identity permutation of (S_n), id_n, should be defined as id_n(i)=i, for i∈[n], that is
id_n=[[(i_1),(i_2),(i_3),…,(i_n)],[(i_1),(i_2),(i_3),…,(i_n)]]
4) If ƒ∈(S_n) is defined by (1) then it is straightforward to check that the inverse of ƒ,(ƒ^-1), should be defined as
(4) [[ƒ((i_1)),ƒ((i_2)),ƒ((i_3)),…,ƒ((i_n))],[(i_1),(i_2),(i_3),…,(i_n)]]
5) The statement follows immediately from (2).
Remark. Theorem 1 means that (S_n) forms a non-commutative group with respect to composition of functions, ∘. This group is called full symmetry group of n-element set.

Definition 4. Let ((k_1),(k_2),…,(k_n)) be an ordered list of the elements of [n] such that each element of [n] occurs (in the list) only once. The ordered pair of elements ((k_(i_1)),(k_(i_2))) is called an inversionof the list if (i_1)<(i_2) and (k_(i_1))>(k_(i_2)). For example, the pairs (4,3)=((k_1),(k_2)), (3,1)=((k_2),(k_3)),(3,2)=((k_2),(k_4)),(4,1)=((k_1),(k_3)) and (4,2)=((k_1),(k_4)) are all the inversions of the ordered list (4,3,1,2,5)=((k_1),(k_2),(k_3),(k_4),(k_5)).

Definition 5. Suppose that a permutation ƒ∈(S_n) is written in the form (1). The sign (or signature or signum) of ƒ, denoted sgn(ƒ), is defined to be
sgn(ƒ)≝(-1)(p(ƒ)+q(ƒ)),
where p(ƒ) and q(ƒ) is the number of inversions in the ordered list ((i_1),(i_2),(i_3),…,(i_n)) and ƒ((i_1)),ƒ((i_2)),ƒ((i_3)),…,ƒ((i_n)), respectively.

Lemma 2. The value of (-1)(p(ƒ)+q(ƒ)) does not depend on the choice of representation of f in the form (1) (that is, Definition 5 is correct).

Theorem 2. For any ƒ,g∈(S_n) we have sgn(ƒ∘g)=sgn(ƒ)⋅sgn(g).
Proof. Let us choose the representations of ƒ and g in the form (1) such that the first row of ƒ is equal to the second row of g, that is ƒ=[[(j_1),(j_2),(j_3),…,(j_n)],[(k_1),(k_2),(k_3),…,(k_n)]] and g=[[(i_1),(i_2),(i_3),…,(i_n)],[(j_1),(j_2),(j_3),…,(j_n)]].
Then we have ƒ∘g=[[(i_1),(i_2),(i_3),…,(i_n)],[(k_1),(k_2),(k_3),…,(k_n)]]. Due to our choice of the representations of ƒ and g, we have p(ƒ)=q(g),p(ƒ∘g)=p(g) and q(ƒ∘g)=q(ƒ), therefore sgn(ƒ∘g)=(-1)(p(ƒ∘g)+q(ƒ∘g))=(-1)(p(g)+q(ƒ))
and
sgn(ƒ)⋅sgn(g)=(-1)(p(ƒ)+q(ƒ))⋅(-1)(p(g)+q(g))=(-1)(p(ƒ)+q(ƒ))⋅(-1)(p(g)+p(ƒ))=(-1)(p(g)+q(ƒ)+2*p(ƒ))=(-1)(p(g)+q(ƒ)).
Thus, sgn(ƒ∘g)=(-1)(p(g)+q(ƒ))=sgn(ƒ)⋅sgn(g).

Definition 6. A permutation ƒ∈(S_n) is called the transposition of elements k,l∈[n] if ƒ(k)=l,ƒ(l)=k and ƒ(i)=i, for i∈[n], i≠k,i≠l
Proposition 1.
1) sgn(id_n)=1
2) sgn(ƒ)=sgn((ƒ^-1)) for any ƒ∈(S_n);
3) if ƒ∈(S_n) is a transposition then sgn(ƒ)=-1
Proof. 1) Since id_n can be written in the form (3), we have p(id_n)=q(id_n). Therefore, by Definition 5, sgn(id_n)=1.
2) Since if ƒ is written in the form (1) then ƒ(-1) can be written as (4), we have p(ƒ(-1))=q(ƒ) and q(ƒ(-1))=p(ƒ) Therefore, by Definition 5, sgn(ƒ(-1))=-1.
3) Suppose that ƒ∈(S_n) is the transposition of elements k,l∈[n]. Then ƒ can be written as ƒ=[[l,k,(i_1),(i_2),…,(i_n-2)],[k,l,(i_1),(i_2),…,(i_n-2)]].
It should be clear that in this case we have either p(ƒ)=p(ƒ)-1 (if l < k) or p(ƒ)=q(ƒ)+1 (ifl > k). In both cases, by Definition 5, sgn(ƒ)=-1.

Definition 7. A permutation ƒ∈(S_n) is called
1) an even permutation if sgn(ƒ)=1
2) an odd permutation if sgn(ƒ)=-1