Orderings, cycle decomposition, and fixed-point-free arrangements
A permutation is a rearrangement of objects. The number of ways to arrange n distinct objects is n! (n factorial), which grows explosively: 5! = 120, 10! = 3,628,800. Permutations are more than just counts -- they have rich internal structure revealed by cycle decomposition.
In this lesson, you will see all permutations of a small set, discover derangements (permutations with no fixed points), and learn to decompose any permutation into its cycle structure.
For small n, we can list every possible arrangement. Watch how the number of permutations grows factorially: from 2 arrangements of 2 elements to 120 arrangements of 5 elements. Each permutation is a complete reordering where every element appears exactly once.
A permutation is an ordered arrangement. For n elements, there are n! permutations. Click any row to highlight it, or press auto-play to cycle through.
Key insight: The factorial n! counts permutations because we have n choices for the first position, n-1 for the second, n-2 for the third, and so on: n! = n × (n-1) × (n-2) × ... × 1.
A derangement is a permutation where no element remains in its original position. The classic example: if n people each put their hat in a pile and randomly grab one, what is the probability that nobody gets their own hat? The answer converges rapidly to 1/e ≈ 36.8%.
A derangement is a permutation where no element appears in its original position. Red-crossed circles mark fixed points. As n grows, !n/n! approaches 1/e ≈ 0.3679. Formula: !n = n! × sum of (-1)^k/k! for k = 0 to n.
Key insight: The number of derangements !n = n! × Σ(-1)ᵏ/k! for k from 0 to n. The ratio !n/n! converges to 1/e so quickly that rounding to the nearest integer gives the exact count for n ≥ 1.
Every permutation can be uniquely decomposed into disjoint cycles. A cycle (a b c) means a → b → c → a. Fixed points are 1-cycles. This decomposition reveals the algebraic structure of permutations and connects to group theory. Build a permutation by clicking elements and see its cycles emerge.
Every permutation decomposes into disjoint cycles. Click "Build Permutation" then click elements to define where each maps. Colored arcs show cycle structure.
Key insight: Cycle decomposition is unique (up to ordering of cycles and starting point within each cycle). The cycle type -- the multiset of cycle lengths -- determines the conjugacy class in the symmetric group S_n.