Codex @codex  0

Allocate $n$ distinct objects to $k$ labelled bins of specified nonnegative sizes $n_1,\dots ,n_k$, with ${\sum }_i{n}_i=n$. 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 $n_1$ to the first bin, the next $n_2$ to the second, and so on. Every allocation comes from exactly $n_1!\cdots n_k!$ internal orderings. These disjoint classes exhaust the $n!$ permutations, proving the formula by the multiplication principle. Empty bins are allowed because $0!=1$.

For two bins of sizes $m$ and $n-m$, the count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and every allocation has multiplicity $m!(n-m)!$ 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 $g$, 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.

For the permutation action on $n$ coordinates with $n\ge 2$, every alternating-group invariant is a symmetric polynomial plus the Vandermonde product $\Delta$ times a symmetric polynomial. Thus the invariant ring is $\mathbb{C}[e_1,\dots ,e_n,Z]/(Z^2-D(e_1,\dots ,e_n))$, where $D$ 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 $⟨{\chi }^{\lambda }\downarrow ,{\chi }^{\mu }\downarrow ⟩={\delta }_{\lambda \mu }+{\delta }_{{\lambda }^{\prime }\mu }$, and Frobenius reciprocity proves exhaustion. The statement applies for $n\ge 2$; $A_1$ is trivial.

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.

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 $a,b,c,d$, the five possibilities are $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$.

A binary parenthesization of $n+1$ operands contains $n$ binary operations. At the last operation, its left expression can contain $k$ operations and its right expression $n-1-k$. The Catalan recurrence therefore gives $C_n$ 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]

For disjoint pairs $A_i,B_i$ such that $A_i\cap B_j\ne \varnothing$ whenever $i\ne j$, the displayed sum is at most one. In a uniformly random permutation, the events that all of $A_i$ precedes all of $B_i$ are disjoint events, and their probabilities are the summands. Taking $B_i$ to be the complement of the members $A_i$ of an antichain recovers the LYM inequality.

Every group $G$ is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element $g$ becomes a permutation of all the group elements, given byFor a finite group of group order $n$, labeling these elements by $1,\dots ,n$ gives a group embedding into $S_n$. The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.^[ref]

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 $L_g$: the multiplication table is already a catalogue of permutations.

Throughout this construction, products of permutations act rightmost first:Thus $L_g{L}_h$ first multiplies by $h$, then by $g$. This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_g{R}_h=R_{hg}$ with this convention; replacing it by $x\mapsto x{g}^{-1}$ restores the group homomorphism law.^[ref]

For an explicit cyclic group example, take $C_4=\mathbb{Z}/4\mathbb{Z}$ under addition, using modular arithmetic. Its left regular action consists of $L_k(x)=k+x(\mathrm{mod}4)$. In permutation cycles on the labels $0,1,2,3$,The function composition $L_1{L}_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point permutation cycle produces two disjoint permutation cycles. Also $L_1{L}_3=L_0$. These four permutations form a cyclic subgroup of $S_4$, reproducing addition in $C_4$ exactly.

For a nonabelian group example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its identity element. The six group elements are $e,r,r^2,s,rs,r^{2}s$, where $r^3=s^2=e$ and $sr=r^{2}s$. Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, $L_s(r)=sr=r^{2}s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that $L_r{L}_s\ne L_s{L}_r$. The group generators $r,s$ become group generators $L_r,L_s$ of a six-element subgroup of $S_6$.

Why does a group action here produce a group embedding? Any group action on a set $X$ gives a group homomorphism $\rho :G\to \mathrm{Sym}(X)$; 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 $X$. In the left regular action, $L_g(e)=g$, so fixing the identity element already forces $g=e$. In fact every stabilizer subgroup is trivial, since $gx=x$ forces $g=e$; this stronger property makes the left regular action a regular group action.^[ref]

Compare two group actions of the same cyclic group $C_4$. Its left regular action on four labels distinguishes all four group elements. On $X=\{0,1\}$, the rule $k\cdot x=k+x(\mathrm{mod}2)$ defines a transitive group action, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its group kernel is $\{0,2\}$, so it is not a faithful group action. Its image is a two-element subgroup of $S_2$, isomorphic to the quotient group $C_4/\{0,2\}$ rather than to $C_4$.

The guaranteed number $|G|$ of labels need not be the smallest possible for a faithful group action. The symmetric group $S_3$ naturally acts faithfully on $\{1,2,3\}$: 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 $S_1$ and $S_2$ have fewer than six elements and cannot contain an isomorphic copy of $S_3$. Moreover, in the natural three-point group action, the stabilizer subgroup of $1$ is $\{e,(23)\}$: 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 $L_g$ is a bijection with inverse $L_{g^{-1}}$. Associativity givesso $\lambda$ is a group homomorphism. If $L_g=L_h$, evaluating both at the identity element gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ 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]

Commutation with a fixed-point-free involution preserves its partner relation. A commuting permutation can permute the $m$ pairs and independently swap each pair. This gives the permutation wreath product with order $2^{m}m!$.

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 $2(n-2)!$.

The centralizer of an element $x$ of a group $G$ consists of all elements that commute with $x$:It is the stabilizer subgroup of $x$ under the conjugation action, hence a subgroup of $G$. In conjugacy classes of the symmetric group on three letters, the three representative computations areFor the transposition $(12)$, a commuting permutation must preserve the exchanged pair $\{1,2\}$ and fix $3$; only $e$ and $(12)$ do so. For $r=(123)$, a commuting permutation is determined by where it sends $1$: the equation $g(r(i))=r(g(i))$ forces the images of $2$ and $3$, leaving exactly $e,r,r^2$. For $e$, every permutation commutes. These centralizer sizes $6,2,3$ give conjugacy class sizes $1,3,2$.

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: $C_G(e)=G$ even when $G$ is a nonabelian group. In an abelian group, all element centralizers equal $G$. These observations also explain why the surrounding group matters: the centralizer of $(123)$ inside the alternating group $A_3$ is the whole $A_3$, whereas its centralizer inside $S_3$ is a proper subgroup. See McKernan, the centralizer definition preceding lemma 23.6.

For an arbitrary subset $A\subseteq G$, the centralizer of a subset fixes every element of $A$ individually under the conjugation action:This is a pointwise stabilizer of the elements of $A$, not of the vertices of a polygon in a geometric realization. In particular, $r=(123)$ belongs to $C_{S_3}(r)$ although its rotation moves every vertex of a polygon of the equilateral triangle. If $A$ generates a subgroup $H$, commuting with every element of $A$ implies commuting with every product of those elements and their inverse elements; hence $C_G(A)=C_G(H)$. For the triangle rotation subgroup $H=⟨r⟩$, this gives $C_{S_3}(H)=C_{S_3}(r)=H$.

To see the commutation test directly on the equilateral triangle, compare a rotation $r$ with the reflection $s=(12)$. Their permutations satisfyThe two orders send vertex of a polygon $1$ to different places: $rs(1)=3$, but $sr(1)=1$. Thus $s\notin C_{S_3}(r)$. By contrast $r$ and $r^2$ commute, with $r{r}^2=r^{2}r=e$. The reflection reverses the chosen rotation while preserving the subgroup of all triangle rotations, so $s\in N_{S_3}(H)$. 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.

Identify a regular orbit with the group using a chosen base point. A permutation commuting with all left translations satisfies $c(x)=xc(1)$. Thus the centralizer consists of right translations. Defining $R_g(x)=x{g}^{-1}$ makes $R_g{R}_h=R_{gh}$ and gives an isomorphism to $G$, rather than an unmentioned reversal of multiplication.

The Weyl group of the Cn root system is the signed symmetric group. A Weyl reflection in $2{\epsilon }_i$ changes the sign of coordinate $i$; one in ${\epsilon }_i-{\epsilon }_j$ interchanges coordinates $i,j$; one in ${\epsilon }_i+{\epsilon }_j$ interchanges and negates both coordinates. These generate all independent sign changes and all permutations, giving order $2^{n}n!$.

A combinatorial explosion is a rapid increase in the number of candidates generated by a search over combinations, often exponential or factorial in an input parameter. For example, listing all subsets of an $n$-element set produces $2^n$ candidates, while listing all permutations produces $n!$ candidates. In contrast, listing only fixed-size $q$-element subsets has time complexity at least $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ for fixed $q$: potentially large, but polynomial rather than exponential in $n$.

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

A commutative ring is a ring in which multiplication satisfies $ab=ba$ for every pair. The integers and the polynomial ring $\mathbb{Z}[X]$ are examples. So is $\mathbb{Z}/n\mathbb{Z}$, the quotient ring whose elements are residue classes in modular arithmetic. We represent these by $0,1,\dots ,n-1$ and reduce each sum or product to its remainder. All following calculations modulo $6$ use this convention.

In $\mathbb{Z}/6\mathbb{Z}$, $2\cdot 3=0$, although neither factor is zero. Thus $2$ and $3$ are zero divisors: nonzero elements whose product with another nonzero element can vanish. Also $2\cdot 1=2\cdot 4=2$. Removing the common factor $2$ would falsely assert $1=4$. The entire row for multiplication by $2$ isThe repetitions explain the linear congruences directly. The equation $2x=2$ has exactly the two solutions $x=1,4$, whereas $2x=1$ has none. A common factor can erase information, and a nonzero coefficient does not guarantee that an equation has a solution.

A unit in a ring is an element $u$ with a multiplicative inverse, meaning $uv=vu=1$ for some $v$. In $\mathbb{Z}/6\mathbb{Z}$, the units are exactly $1$ and $5$, since $5^2=1$. The other nonzero elements, $2,3,4$, are zero divisors; for $4$, use $4\cdot 3=0$. In a nonzero commutative ring, a unit cannot be a zero divisor: multiplying $ub=0$ by its multiplicative inverse forces $b=0$. But a nonzero element need not be a unit or a zero divisor: the integer $2$ is neither in $\mathbb{Z}$.

By contrast, in $\mathbb{Z}/5\mathbb{Z}$, every row for a nonzero multiplier is a permutation of $0,1,2,3,4$. Each such row contains $1$ exactly once, giving a multiplicative inverse: $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, and $4^{-1}=4$. Hence this commutative ring is a field. For example, $2x=1$ now has the unique solution $x=3$. Reading the tables reveals which algebraic steps the arithmetic permits.

For the symmetric group $S_3$, take the transpositions $x=(12)$ and $y=(23)$. Products of permutations apply the rightmost factor first. ThenThe last permutation sends $1\mapsto 3$, $3\mapsto 2$, and $2\mapsto 1$: two swaps fail to commute by an entire three-cycle.

Every group commutator has sign of a permutation $+1$, so $S_3^{\prime }\subseteq A_3$, the alternating group of even permutations. Conversely, the displayed group commutator generates $A_3=\{e,(123),(132)\}$. Therefore $S_3^{\prime }=A_3$. The two cosets are the even permutations and the odd permutations, and their multiplication is just multiplication of signs:This is the first isomorphism theorem applied to the sign of a permutation. Once commutativity is forced, all three transpositions become indistinguishable, and both three-cycles become the identity element. The surviving information is exactly whether the permutation is even or odd. Compare the very different center of a group $Z(S_3)=\{e\}$.

Any deterministic comparison sort correct for all orders of $n$ distinct sort keys needs at least $\lceil {\log }_2(n!)\rceil$ comparisons on some input. Here $n!$ is a factorial, ${\log }_2$ a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\ge n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\ge 2$,The brackets denote the floor function. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the $n!$ counting argument. Identical sort keys do not create $n!$ different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

Equip the symmetric group $S_n$ with its uniform probability measure and unnormalized Hamming distance. If $f$ has Lipschitz constant $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform permutation one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the Doob exposure martingale has conditional range length at most $2K$. Applying the conditional Hoeffding lemma gives $\mathbb{E}{e}^{\lambda (f-\mathbb{E}f)}\le e^{n{\lambda }^2{K}^2/2}$; optimizing the exponential Markov bound proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.

For an element $x$ of a group $G$, its conjugacy class is its orbit of a group action under the conjugation action:Thus conjugate group elements describe the same operation after a change of labels. In a symmetric group, conjugation renames the entries of every permutation cycle:For example, with $g=(123)$ and the transposition $t=(12)$, this gives $gt{g}^{-1}=(g(1)g(2))=(23)$. Products use function composition of permutations, with the rightmost factor applied first. The complete six-element example is conjugacy classes of the symmetric group on three letters.

The conjugacy classes form a partition of a set of $G$, since conjugacy is an equivalence relation. In a symmetric group, two permutations lie in the same conjugacy class precisely when they have the same cycle type: renaming preserves the lengths of permutation cycles, and matching equal-length permutation cycles constructs a renaming in the other direction. This compresses many labelled permutations into a few structural types. See McKernan, Conjugation in Sn, lemma 6.2 and proposition 6.6.

The stabilizer subgroup of $x$ under the conjugation action is its centralizer $C_G(x)$. Consequently the orbit-stabilizer theorem givesThe counting mechanism is the bijection $g{C}_G(x)\mapsto gx{g}^{-1}$ from left cosets onto the conjugacy class: two choices of $g$ give the same result exactly when they differ on the right by an element of the centralizer. A large centralizer means many choices of labels leave the operation unchanged, hence a small conjugacy class. A conjugacy class has size one precisely when its element belongs to the center of a group. The class equation counts these orbits of a group action together.