8 - 2x.Let S be a set. A permutation of S is a function from S to S that is both injective and surjective—in other words, a function that “rearranges” the elements of S. For example, if S = {1, 2, 3}, then the function a : S → S that sends 1 to 3, 2 to 1, and 3 to 2 is a permutation of S; so is the function b that sends 1 to 3, 2 to 2, and 3 to 1; whereas the function c that sends 1 to 3, 2 to 1, and 3 to 1 is not a permutation. An example of a permutation of the set of real numbers ℝ is the function x 8 - 2x.
From the point of view of finite group theory, the most important permutations to study are those of the set In = {1, 2, . . . , n}, where n is a positive integer. Let Sn denote the set of all permutations of In. So, for example, the permutations a and b defined in the previous paragraph lie in S3. To count how many permutations there are altogether in Sn, observe that, for a permutation f : In ∀ In, there are n choices for f(1), then n - 1 choices for f(2) (we can choose anything different from f(1), then n - 2 for f(3), and so on, until we have just 1 choice for f(n). Therefore the total number of permutations in Sn is n(n - 1) (n - 2) ··· 1 = n!.
If f and g are permutations of a set S, their composition f 
g is defined by f g(s) = f(g(s)) for all s ∈ S, and it is quite easy to see that f g is also a permutation of S. It is usual to drop the “” symbol and write just fg instead of f g. For example, if a, b ∈ S3 are as in the first paragraph, then ab ∈ S3 sends 1 to 2, 2 to 1, and 3 to 3, while ba sends 1 to 1, 2 to 3, and 3 to 2. Notice that ab ≠ ba.
For any set S, the identity function ι : S ∀ S, defined by ι(s) = s for all s ∈ S, is a permutation of S; and if f is a permutation of S, then there is an inverse permutation f-1 that sends everything back to where it came from and therefore satisfies ff-1 = f-1f = ι. For example, the inverse of the above permutation a ∈ S3 is the permutation that sends 1 to 2, 2 to 3, and 3 to 1. Also, for any permutations f, g, h of S, we have f(gh) = (fg)h, since both sides send any s ∈ S to f(g(h(s))).
Thus, the set of all permutations of S, together with the BINARY OPERATION [I.2 §2.4] of composition, satisfies the axioms for a GROUP [I.3 §2.1]. In particular, Sn is a finite group of size n!, known as the symmetric group of degree n.
There is a neat way of representing permutations succinctly, known as the cycle notation. It is best explained with an example. Let d ∈ S6 be the permutation 1 3, 2 5, 3 6, 4 4, 5 2, 6 1. We can represent this more economically by writing 1 3 6 1, 2 5 2, and 4 4. We say the symbols 1, 3, 6 form a cycle of d (of length 3); similarly, 2, 5 form a cycle of length 2, and 4 a cycle of length 1. We then compress our notation even further and write d = (136) (25) (4), indicating that each number 1, 3, 6 in the first cycle is sent to the next one, except for the last which is sent back to the first, and likewise for the second and third cycles. This is the cycle notation for d; notice that the cycles have no symbols in common—they are called disjoint cycles. It is not too hard to see that every permutation in Sn can be expressed as a product of disjoint cycles; this is what we mean by the cycle notation for a permutation. For example, in cycle notation, the six permutations of S3 are σ, (12) (3), (13) (2), (23) (1), (123), and (132). (The permutations a and b in the first paragraph are (132) and (13) (2), respectively.) You might like to while away a few minutes by working out the multiplication table of S3.
The cycle-shape of a permutation g is the sequence of numbers we get by writing down the lengths of the disjoint cycles in the cycle notation for g, in decreasing order. For example, the cycle-shape of the permutation (163) (24) (58) (7) (9) in Sg is (3,2,2,1,1), or more succinctly (3, 22, 12).
One can define the powers of a permutation f ∈ Sn in a natural way—namely, f1 = f f2 = ff, f3 = f2f, and so on. For example, if e = (1234) ∈ S4, then e2 = (13) (24), e3 = (1432), and e4 = ι. The order of a permutation f ∈ Sn is defined to be the smallest positive integer r such that fr = ι: that is, the smallest number of times we have to do f to send everything back to where it came from. So the order of the r-cycle e above is 4. In general, the order of an r-cycle (i.e., a cycle of length r) is equal to r, and the order of a permutation in cycle notation is equal to the least common multiple of the lengths of the (disjoint) cycles.
It is often useful to be able to work out the order of a permutation. Here is one such instance. Suppose we shuffle a pack of eight cards in the following way: the pack is divided into two equal parts and then “interlaced,” so that if the original order was 1, 2, 3, 4, . . . , the new order is 1,5,2,6, . . . . How many times must this shuffle be repeated before the cards are again in the original order? Well, the shuffle gives the permutation of the eight card positions sending 1 to 1, 2 to 5, 3 to 2, 4 to 6, and so on, which in cycle notation is (1) (253) (467) (8). This has order 3, so the cards return to their original order after three shuffles. Things get quite interesting if we consider the same problem for different numbers of cards—you might like to try it yourself with fifty-two cards, for instance.
There is one slightly more subtle aspect of permutations which is important for group theory: namely, the theory of even and odd permutations. Again, this is best illustrated by example. Take n = 3, and let xl, x2, x3 be three variables. Let us think of the permutations in S3 as moving these variables around rather than the numbers 1, 2, and 3. So, for instance, we shall take the permutation (132) to send x1 to x3, x2 to x1, and x3 to x2. Now let Δ be the expression Δ (x1 - x2) (x1 - x3) (x2 - x3). We can apply permutations in S3 to Δ in an obvious way: for example, (123) sends Δ to (x2 - x3) (x2 - x1) (x3 - x1). Notice that this is just the expression for Δ with two of the brackets, (x1 - x2) and (x1 - x3), reversed. So (123) sends Δ to Δ. However, if we apply (12) (3) to Δ, we get (x2 - xl)(x2 - x3)(xl - x3) = -Δ. You can see that each permutation in S3 sends Δ to either +Δ or -Δ. Call those permutations that send Δ to +Δ even permutations and those that send Δ to -Δ odd permutations. Check that ι, (123), and (132) are even, while (12) (3), (13) (2), and (23) (1) are odd.
The definition of even and odd permutations for general n is very similar to this example. Let xl, . . . , xn be variables, and regard the permutations in Sn as moving these variables around rather than the symbols 1, 2, . . . , n. Define Δ to be the product of all xi - xj for i < j. Just as in the example, we can apply any permutation g ∈ Sn to Δ, and the result will be either +Δ or -Δ. Define the signature of g to be the number sgn(g) ∈ {+1, -1} such that g(Δ) = sgn(g)Δ. This defines the signature function sgn : Sn ∀ {+1, -1}. Then a permutation g ∈ Sn is even if sgn(g) = +1, and is odd if sgn(g) = -1.
It follows easily from the definition that
sgn(gh) = sgn(g) sgn(h)
for any g, h ∈ Sn, and also that the signature of any 2-cycle is -1. Since an r-cycle (a1 a2 ··· ar) can be expressed as a product (a1 ar) (a1 ar-1)···(a1 a2) of 2-cycles, the signature of the r-cycle is (-1)r-1. Hence, if g ∈ Sn has cycle-shape (r1, r2, . . . , rk), then
sgn(g) = (-1)r1-1(-1)r2-1. . .(-1)rk-1.
This makes it easy to work out the signature of any permutation. For example, the even permutations in S5 are those that have cycle-shape (15), (22, 1), (3, 12), or (5). If you count these, you will find that there are sixty even permutations in S5 altogether, which is exactly half of the total of 5! = 120 permutations in S5. In general, the number of even permutations in Sn is 
n!.
So what is the point of this complicated definition? The answer is that the set of all even permutations in Sn forms a subgroup of size n!, known as the alternating group of degree n, and written as An. The alternating groups are very important examples of finite groups, because of the fact that, for n ≥ 5, An is a simple group—that is, its Only NORMAL SUBGROUPS [I.3 §3.3] are the identity subgroup and An itself (see THE CLASSIFICATION OF FINITE SIMPLE GROUPS [V.7]). For example, A5 is a simple group of size 60, and in fact is the smallest non-Abelian finite simple group.