Aaron Williams Created 2026-10-20 Updated 2026-11-05
Aaron Williams is a coauthor of A Hamilton Cycle in the k-Sided Pancake Network. The paper gives a Hamiltonian cycle through a directed graph of coloured permutations and four algorithms that traverse it. An edge reverses an initial segment and changes its colours modulo . A single cycle therefore supplies a systematic generation order in which every coloured permutation appears once.[ref]
Adjacent transposition Created 2026-10-20 Updated 2026-11-05
An adjacent transposition exchanges consecutive positions and in a permutation, leaving the others fixed; as a permutation of positions it is . Every permutation can be sorted using adjacent transpositions. Swapping an out-of-order adjacent pair decreases its inversion number by one because its comparisons with every third entry have the same total before and after the swap. Consequently the minimum number of adjacent transpositions needed to sort a permutation is its inversion number. For
312, the route 312, 132, 123 uses two swaps. Allocation to labelled bins Created 2026-10-18 Updated 2026-10-20
Allocate distinct objects to labelled bins of specified nonnegative sizes , with . Order within a bin is ignored. The number of allocations is the multinomial coefficientTo prove this, order all the objects in a permutation and assign the first to the first bin, the next to the second, and so on. Every allocation comes from exactly internal orderings. These disjoint classes exhaust the permutations, proving the formula by the multiplication principle. Empty bins are allowed because .
For two bins of sizes and , the count is and every allocation has multiplicity in the permutation sample space. Exchanging two equal-sized labelled bins generally gives a different allocation. In contrast, a set partition uses unlabelled nonempty blocks; forgetting bin labels changes the counting problem and must not be done silently.
For an even permutation , its symmetric group class splits into two equal alternating group classes exactly when its symmetric-group centralizer contains no odd permutation. If an odd commuting element exists, an odd conjugator can be multiplied by it to become even; otherwise the index-two subgroup has two conjugation orbits. In cycle notation the splitting types are precisely distinct odd cycle lengths, counting fixed points as length-one cycles: rotating odd cycles is even, whereas an even cycle or the exchange of two equal odd cycles supplies an odd centralizer element.
Alternating group Created 2026-09-24 Updated 2026-11-05
The alternating group is the subgroup of the symmetric group consisting of even permutations, those expressible as an even number of transpositions. It is the kernel of the sign homomorphism , so it is a normal subgroup and has order for .
A three-cycle is even because , and three-cycles generate . For example, is a cyclic group of order three. For , is a nonabelian simple group, a central family in finite group theory and the obstruction behind the general unsolvability of polynomial equations by radicals.
Alternating-group polynomial invariants Created 2026-10-07 Updated 2026-11-05
For the permutation action on coordinates with , every alternating-group invariant is a symmetric polynomial plus the Vandermonde product times a symmetric polynomial. Thus the invariant ring is , where is the discriminant polynomial. The two summands are independent over the symmetric polynomial ring.
An ordinary Specht module of non-self-conjugate shape stays irreducible on the alternating group, and conjugate shapes give the same restriction. A self-conjugate shape splits into two irreducibles of equal degree, interchanged by an odd permutation. The index-two inner-product identity is , and Frobenius reciprocity proves exhaustion. The statement applies for ; is trivial.
Alternating-permutation convolution Created 2026-09-24 Updated 2026-11-05
Let count alternating permutations on labels, with . For ,Count both up-down and down-up permutations of labels. Choose the labels left of the maximum in ways. On either side, the comparison next to the maximum fixes which alternating direction is required, giving choices. Conversely these choices reconstruct exactly one of the two kinds of alternating permutations. Replacing each label by interchanges the two kinds, so their combined count is .
For , the identity reads . The restriction matters: on one label, the two alternating conventions describe the same permutation, and substitution of would incorrectly give .
Anagram Created 2026-10-20 Updated 2026-11-05
An anagram of a finite string is another string with exactly the same number of occurrences of each symbol. Thus and are anagrams; is not. Equivalently, the second string is obtained by a permutation of the positions.
If a length- string has symbol multiplicities , its number of distinct anagrams is the multinomial coefficient . Dividing by the factorials removes position permutations that only exchange equal symbols. The count depends on multiplicities, not the original ordering.
Bernoulli invariant laws of finite symmetric exclusion Created 2026-10-14 Updated 2026-11-05
On a finite graph with symmetric edge-swap rates, the stirring representation of symmetric exclusion transports the occupations by a random permutation. An independent identically distributed Bernoulli distribution occupation field is invariant under every deterministic permutation, and hence under this random permutation when it is independent of the initial field. Therefore the displayed product measure is invariant, including densities zero and one. Equivalently, an edge swap preserves the number of particles and has the same reverse rate, giving detailed balance.
Binary parenthesization 2026-10-14
A binary parenthesization specifies the order of binary operations on a fixed ordered list of operands, combining exactly two existing expressions at each step. It has a full binary tree as its expression structure: operands are leaves and operations are internal vertices. For four operands , the five possibilities are , , , , and .
A binary parenthesization of operands contains binary operations. At the last operation, its left expression can contain operations and its right expression . The Catalan recurrence therefore gives possible evaluation structures. The order of operands stays fixed; this is not a count of their permutations. Even for an associative operation whose result is unchanged, different structures can have different evaluation costs, as in the matrix-chain multiplication problem.[ref]
Bijective Proof Problems by Richard P. Stanley. §5, Problem 154, printed p. 38: binary parenthesizations of n+1 letters
Bit-reversal permutation 2026-11-05
The bit-reversal permutation of writes each index using exactly binary digits, reverses those digits, and interprets the result as another index. Leading zeros matter. Reversing twice restores the original index, so this permutation is an involution.
For , the index order becomes : for example, maps to . It occurs naturally in radix-two Fast Fourier transform implementations. Repeatedly separating even from odd indices consumes the low-order bits first; traversing the resulting recursion tree reverses the order in which the index bits are read. Some implementations permute inputs, others permute outputs, and other layouts avoid an explicit reversal. The discrete Fourier transform itself is independent of this storage choice.[ref]
Notes on the FFT by C. Sidney Burrus. radix-two decimation and digit-reversed ordering
Bollobas set-pairs inequality 2026-10-06
For disjoint pairs such that whenever , the displayed sum is at most one. In a uniformly random permutation, the events that all of precedes all of are disjoint events, and their probabilities are the summands. Taking to be the complement of the members of an antichain recovers the LYM inequality.
Bounded-displacement permutation of the natural numbers Created 2026-09-24 Updated 2026-11-05
A permutation of has bounded displacement if some nonnegative integer satisfiesThe same bound works at every position; each individual difference being finite would impose no restriction. Displacement zero gives the identity permutation.
For displacement at most one, every permutation is a collection of disjoint adjacent transpositions and fixed points. To prove this, inspect the smallest position not yet fixed or paired. Its image must be , and the only still available possible preimage of is . Thus these two positions are exchanged; continue inductively. Conversely, any such disjoint collection satisfies the bound. Independently choosing whether to exchange each pair gives an uncountable set of examples.
The inverse function has the same displacement bound: if , then . If two permutations have bounds , their function composition has bound by the triangle inequality. Thus bounded-displacement permutations form a group under function composition.
Braid group Created 2026-10-06 Updated 2026-11-05
For , the braid group consists geometrically of braids on strands, composed by stacking. Algebraically it is generated by subject to the braid group relations: adjacent generators obey , and nonadjacent generators commute. There is no relation .
Recording only the strand endpoints gives a surjective group homomorphism , sending to the transposition . Its group kernel is the pure braid group, whose strands return to their original endpoints. Thus endpoint permutations discard crossing information. For example, has one generator and no relations, so it is an infinite cyclic group, while its endpoint permutation group is ; the square of its generator has trivial endpoint permutation but is a nontrivial braid. This distinction does not conflict with Cayley's theorem, which realizes every group as some permutation group.
Cayley's theorem 2026-10-14
Every group is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element becomes a permutation of all the group elements, given byFor a finite group of group order , labeling these elements by gives a group embedding into . The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.[ref]
Group Theory (v4.01) by James S. Milne. Theorem 1.22 and Corollary 1.23, printed page 16: left multiplication embeds a group into its symmetric group
The beauty is that the multiplication rule itself supplies a concrete model. Whatever the group elements originally represent, each one rearranges the entire group by multiplication. A product becomes function composition, and no distinctions between group elements are lost. For a finite group, a row of its Cayley table lists the images under one : the multiplication table is already a catalogue of permutations.
Throughout this construction, products of permutations act rightmost first:Thus first multiplies by , then by . This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication instead satisfies with this convention; replacing it by restores the group homomorphism law.[ref]
Group Actions by Keith Conrad. Example 2.10, printed page 7: left multiplication and the reversed composition law for right multiplication
For an explicit cyclic group example, take under addition, using modular arithmetic. Its left regular action consists of . In permutation cycles on the labels ,The function composition sends to , to , to , and to : squaring the four-point permutation cycle produces two disjoint permutation cycles. Also . These four permutations form a cyclic subgroup of , reproducing addition in exactly.
For a nonabelian group example, let , with , , and its identity element. The six group elements are , where and . Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, ; putting here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that . The group generators become group generators of a six-element subgroup of .
Why does a group action here produce a group embedding? Any group action on a set gives a group homomorphism ; it is a group embedding precisely when it is a faithful group action. The group kernel consists of the group elements fixing every point of . In the left regular action, , so fixing the identity element already forces . In fact every stabilizer subgroup is trivial, since forces ; this stronger property makes the left regular action a regular group action.[ref]
Compare two group actions of the same cyclic group . Its left regular action on four labels distinguishes all four group elements. On , the rule defines a transitive group action, but and both fix both points, while and both exchange them. Its group kernel is , so it is not a faithful group action. Its image is a two-element subgroup of , isomorphic to the quotient group rather than to .
The guaranteed number of labels need not be the smallest possible for a faithful group action. The symmetric group naturally acts faithfully on : a permutation fixing all three labels is the identity element. Its left regular action uses six labels instead. Three is the smallest possible here, since and have fewer than six elements and cannot contain an isomorphic copy of . Moreover, in the natural three-point group action, the stabilizer subgroup of is : a faithful group action can have nontrivial point stabilizer subgroups. Cayley's construction supplies a universal model, while a smaller model can reveal particular symmetries.
The proof is short. Each is a bijection with inverse . Associativity givesso is a group homomorphism. If , evaluating both at the identity element gives . Hence is injective, and its image is the required isomorphic subgroup. No finiteness assumption entered the argument.
The historical connection is unusually close to the notation. The opening paragraph of Arthur Cayley's 1854 paper already treats permutations as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on associativity. The modern left regular action shows how that viewpoint reaches every abstract group, by choosing the group itself as the set to be acted on.[ref]
Abstract awakenings in algebra: Early group theory in the works of Lagrange, Cauchy, and Cayley by Janet Heine Barnett. Abstract awakenings in algebra: Early group theory in the works of Lagrange, Cauchy, and Cayley by Janet Heine Barnett, Section 3.1, printed page 50: reproduced opening paragraph of Arthur Cayley's On the theory of groups, as depending on the symbolic equation theta^n = 1; reference 5, printed page 91: original publication in 1854
Centraliser of a fixed-point-free involution Created 2026-10-06 Updated 2026-10-14
Commutation with a fixed-point-free involution preserves its partner relation. A commuting permutation can permute the pairs and independently swap each pair. This gives the permutation wreath product with order .
Centraliser of a transposition 2026-10-06
A permutation commutes with a transposition exactly when it preserves its two-element support as a set. It may swap those two points and independently permute the remaining points. Thus this centraliser has order .
Centralizer Created 2026-09-24 Updated 2026-10-14
The centralizer of an element of a group consists of all elements that commute with :It is the stabilizer subgroup of under the conjugation action, hence a subgroup of . In conjugacy classes of the symmetric group on three letters, the three representative computations areFor the transposition , a commuting permutation must preserve the exchanged pair and fix ; only and do so. For , a commuting permutation is determined by where it sends : the equation forces the images of and , leaving exactly . For , every permutation commutes. These centralizer sizes give conjugacy class sizes .
The centralizer is useful because it measures how much freedom remains after fixing one operation. Its index of a subgroup counts the distinct results of conjugation, and the intersection of all element centralizers is the center of a group. A centralizer need not be an abelian group: even when is a nonabelian group. In an abelian group, all element centralizers equal . These observations also explain why the surrounding group matters: the centralizer of inside the alternating group is the whole , whereas its centralizer inside is a proper subgroup. See McKernan, the centralizer definition preceding lemma 23.6.
For an arbitrary subset , the centralizer of a subset fixes every element of individually under the conjugation action:This is a pointwise stabilizer of the elements of , not of the vertices of a polygon in a geometric realization. In particular, belongs to although its rotation moves every vertex of a polygon of the equilateral triangle. If generates a subgroup , commuting with every element of implies commuting with every product of those elements and their inverse elements; hence . For the triangle rotation subgroup , this gives .
To see the commutation test directly on the equilateral triangle, compare a rotation with the reflection . Their permutations satisfyThe two orders send vertex of a polygon to different places: , but . Thus . By contrast and commute, with . The reflection reverses the chosen rotation while preserving the subgroup of all triangle rotations, so . The distinction is visible before any counting: commuting preserves an operation itself; membership in the normalizer permits exchanging it with another operation in the same subgroup.
Centralizer of a regular permutation subgroup Created 2026-10-14 Updated 2026-11-05
Identify a regular orbit with the group using a chosen base point. A permutation commuting with all left translations satisfies . Thus the centralizer consists of right translations. Defining makes and gives an isomorphism to , rather than an unmentioned reversal of multiplication.


