Shuffle a deck of cards, scramble a Rubik's cube, or just rearrange the books on a shelf — every one of these is a permutation: a way of moving a finite set of objects around so that each object lands somewhere and no two objects collide. Formally, a permutation of the set \{1, 2, \dots, n\} is a bijection from that set to itself — a rule that sends each label to exactly one label, hitting every label exactly once.

Collect all of these rearrangements together and you get one of the most important objects in algebra: the symmetric group S_n. It is a genuine group — you can compose two shuffles to get a third, "do nothing" is the identity, and every shuffle can be undone — and it is the natural home of the very idea of symmetry. This page is about how to write permutations down efficiently, how to multiply them, and the single most useful number attached to each one: its sign.

How big is S_n? Build a rearrangement one choice at a time: label 1 can go to any of n places, then label 2 to any of the remaining n-1, and so on down to the last label with only 1 place left. Multiplying the choices gives

So S_3 has 3! = 6 elements, S_4 has 4! = 24, and S_5 already has 5! = 120. The factorial explodes fast — a deck of 52 cards has 52! orderings, a number with 68 digits.

Two ways to write a permutation down

The honest, spell-it-all-out way is two-row notation: write the inputs 1, \dots, n along the top and, directly beneath each one, where it goes. For example, in S_4:

reads "1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 4, 4 \mapsto 2". Clear, but bulky. Watch what happens if you follow the trail instead: start at 1, it goes to 3, which goes to 4, which goes to 2, which goes back to 1. One closed loop swallows every element:

This is cycle notation. The bracket (1\ 3\ 4\ 2) means "each listed element maps to the next, and the last wraps back to the first." A cycle listing k elements is called a k-cycle; a 2-cycle like (2\ 5) — which just swaps two elements and leaves everything else alone — has the special name transposition. Any element a permutation leaves fixed is simply omitted from the notation (or written as its own 1-cycle).

Composing permutations — and stating the convention out loud

Because permutations are functions, we can compose them: do one, then another. The one genuine trap in this whole subject is the order of composition, so let us nail down a convention and never waver from it. We treat \sigma\tau as function composition, meaning apply the rightmost permutation first:

Read \sigma\tau right-to-left: \tau acts, then \sigma acts on the result. (Some textbooks use the opposite, left-to-right convention; that is fine too, but you must pick one and announce it — mixing them silently is how answers go wrong.)

Let us multiply two elements of S_3. Take the 3-cycle \sigma = (1\ 2\ 3) and the transposition \tau = (1\ 2). To find \sigma\tau, chase each point through \tau first, then \sigma:

• 1 \xrightarrow{\tau} 2 \xrightarrow{\sigma} 3, so 1 \mapsto 3;
• 2 \xrightarrow{\tau} 1 \xrightarrow{\sigma} 2, so 2 \mapsto 2;
• 3 \xrightarrow{\tau} 3 \xrightarrow{\sigma} 1, so 3 \mapsto 1.

Collecting the trail: \sigma\tau = (1\ 3). Now reverse the order and compute \tau\sigma (apply \sigma first): 1 \mapsto 1, 2 \mapsto 3, 3 \mapsto 2, giving \tau\sigma = (2\ 3). The two products are different:

That is your first hard proof that S_n is non-abelian for n \ge 3: the order in which you shuffle genuinely matters.

Every permutation splits into disjoint cycles

Two cycles are disjoint when they share no elements — like (1\ 3\ 5) and (2\ 4) inside S_5. Disjoint cycles have a lovely property: they commute. Since they touch entirely separate elements, neither can interfere with the other, so it makes no difference which you apply first. (Non-disjoint cycles, as we just saw, need not commute at all.)

The recipe for the first part is exactly the "follow the trail" trick: pick the smallest unused element, chase it round until it loops, close the bracket, then start again with the next unused element. You are guaranteed to exhaust the set, because a bijection can never let two trails merge. The figure below draws a random permutation as arrows and colours each disjoint cycle separately — press Refresh to shuffle a new one.

The sign of a permutation: even or odd

Here is a small miracle. A permutation can be built out of transpositions in many different ways — but whether the number of transpositions is even or odd is the same every single time. That fixed parity is called the sign of the permutation, written \operatorname{sgn}(\sigma):

The rule \operatorname{sgn} = (-1)^{k-1} for a k-cycle follows straight from the decomposition above: a k-cycle is k-1 transpositions, and (-1)^{k-1} just records whether that count is even or odd. A transposition (k=2) is odd; a 3-cycle (k=3) is even; a 4-cycle is odd; and so on, alternating.

Worked example: compute a sign

Find the sign of \sigma = (1\ 3\ 5)(2\ 4) in S_5. It is already written as disjoint cycles, so add up the transpositions each one costs:

• the 3-cycle (1\ 3\ 5) costs 3 - 1 = 2 transpositions (even);
• the transposition (2\ 4) costs 2 - 1 = 1 transposition (odd).

The total is 2 + 1 = 3 transpositions, an odd number, so \operatorname{sgn}(\sigma) = (-1)^3 = -1. The same answer drops out of the homomorphism rule instantly: \operatorname{sgn}(\sigma) = (-1)^{3-1} \cdot (-1)^{2-1} = (+1)(-1) = -1. A quick shortcut for the whole permutation: for a permutation of n points that splits into c disjoint cycles (counting fixed points as 1-cycles), \operatorname{sgn} = (-1)^{\,n - c}.

The alternating group A_n

Because the sign is a homomorphism onto \{+1, -1\}, its kernel — the permutations of sign +1, i.e. the even permutations — is a subgroup. This is the alternating group A_n. Exactly half of all permutations are even (multiplying by any single transposition flips even to odd and back, pairing them up perfectly), so

Thus A_3 has 3 elements (the identity and the two 3-cycles), A_4 has 12, and A_5 has 60. That last one is famous: A_5 is the smallest non-abelian simple group, and its stubborn indivisibility is exactly why there is no formula in radicals for the general quintic equation.

Why symmetric groups are everywhere: Cayley's theorem

The idea is disarmingly simple: let each element g \in G act on the group by "multiply everything on the left by g". Because g has an inverse, this shuffle is a bijection of G — i.e. a permutation of its |G| elements — and composing shuffles matches multiplying in G. So G sits faithfully inside S_{|G|}. The moral is striking: permutation groups are not just one example of a group — up to isomorphism they are the only example. Understand S_n and, in a real sense, you understand every finite group there is.