permutation

A permutation is a rearrangement — a complete reshuffling of a collection where every item moves to a spot and no spot is left empty or doubly filled. Dealing a shuffled deck, reseating a table of guests, or scrambling the letters of a word are all permutations. The key is that nothing is lost or duplicated; the same items end up in a new order.

Formally, a permutation of a set is a bijection from the set to itself: a function that is both one-to-one (no two inputs share an output) and onto (every element is hit). Because of those two properties, every permutation can be undone by an inverse permutation, and composing two permutations gives a third — which is exactly why permutations form the symmetric group.

Mathematicians often write permutations in cycle notation, like (1 3 2), meaning 1 goes to 3, 3 goes to 2, and 2 goes back to 1. Every permutation breaks into disjoint cycles and can be built from simple swaps (transpositions); whether it uses an even or odd number of swaps is a fixed invariant called its parity, which splits Sₙ into “even” and “odd” halves.