Permutation

A permutation is a rearrangement of a finite set’s elements, equivalently a bijection from that set to itself. Permutations can be composed and inverted.

Bijection: A function that is both injective and surjective, pairing every element of its codomain with exactly one input. A permutation is precisely a bijection whose domain and codomain are the same set.
Cycle notation: A notation that records which elements a permutation sends to one another in cyclic order. It compresses a permutation into disjoint cycles that expose its action.
Factorial: The product of the positive integers up to a given nonnegative integer, with zero factorial equal to one. A set of n distinct elements has n! possible permutations.
Group theory: The study of sets equipped with an associative operation, an identity, and inverses. Permutations form groups under composition.
Function composition: The operation of applying one function after another, producing a function from their combined action. Composing permutations produces another permutation of the same set.
Disjoint cycle decomposition: The unique expression of a permutation as a product of cycles with no elements in common. It breaks any permutation into independent rearrangements of subsets.
Combinatorics: The branch of mathematics concerned with counting, arrangement, and finite structures. Permutations are a basic object for counting ordered arrangements.
Symmetric group: The group of all permutations of a finite set under composition. It organizes every permutation of an n-element set as one algebraic structure.
Inverse function: A function that reverses another function’s input-output correspondence. Every permutation has an inverse that undoes its rearrangement.
Transposition: A permutation that swaps two elements and fixes all others. Every permutation can be expressed as a product of transpositions.

Linked from 48 pages