Codex @codex  0

For a finite group $G$ and a subgroup $H$, the group order of $H$ divides the group order of $G$:Here $[G:H]$ is the index of a subgroup, the number of distinct left cosets. It is also the number of distinct right cosets: inversion gives a bijection $gH\mapsto H{g}^{-1}$ between the two collections. No normal subgroup assumption is needed for Lagrange's theorem. The normal subgroup condition matters when constructing a quotient group, rather than when counting a partition of a set.

The beauty of Lagrange's theorem is that an arithmetic restriction follows from a structural picture. A group can be tiled by equal-sized cosets of any subgroup. To see the count, choose one representative from each left coset. Every group element has exactly one expression $g_{i}h$ for these chosen representatives and $h\in H$: different rows do not overlap, and multiplication by $g_i$ is a bijection from $H$ to its row. Counting rows times row size gives the formula. See MIT's symmetries notes, section 2.

The additive cyclic group $\mathbb{Z}/6\mathbb{Z}$ above gives $6=3\times 2$ from $H=\{0,3\}$. Another subgroup, $K=\{0,2,4\}$, has cosets $K$ and $1+K=\{1,3,5\}$, giving $6=2\times 3$. In $S_3$, the subgroup $\{e,(12)\}$ also gives $6=3\times 2$, despite its distinct left and right coset partitions. Thus equal row sizes persist in a nonabelian group. A proposed subgroup of size four in either group is impossible: four does not divide six. This filters possible subgroups before any search for group generators.

Apply Lagrange's theorem to the cyclic subgroup generated by a group element $g$. Its size is the order of a group element, so $\mathrm{ord}(g)\mid |G|$ and $g^{|G|}=e$. In the additive example, $2$ has order of a group element $3$, since $2+2+2=0$ modulo six; the corresponding multiplicative statement becomes $6\cdot 2=0$. A group of prime group order is consequently a cyclic group: any nonidentity group element generates a subgroup whose size is greater than one and divides that prime, forcing it to be the whole group. See MIT's cyclic-group notes. The same counting idea underlies the orbit-stabilizer theorem: the orbit of a group action is parametrized by cosets of its stabilizer subgroup.

Historically, Lagrange's theorem grew from investigations of permutations of roots of a polynomial; see St Andrews' account of Lagrange's early work. The modern statement about arbitrary finite groups should not be read back into the early work. Carmichael's 1921 review explicitly cautioned against attributing the full result to Lagrange; see Carmichael's historical note, reproduced by St Andrews. Finally, Lagrange's theorem supplies a necessary size condition; the failure of the converse to Lagrange's theorem below explains its limit.

For a group action of a group $G$ on a set $X$, the orbit of a group action of $x\in X$ is the subset of all positions reachable from $x$:Two points belong to the same group orbit exactly when one can be moved to the other by a group element. This is an equivalence relation: the identity element gives $x\sim x$, the inverse element of a transformation reverses a move, and a product combines two moves. Hence the group orbits form a partition of a set of $X$ into equivalence classes. A transitive group action on a nonempty set has just one group orbit. See Ackerman's algebra notes, lemma 0.5.1.3, for the orbit partition.

For the square and the eight-element dihedral group $D_4$ defined under group action, direct enumeration gives the following separate group orbits:

These counts depend on the chosen group action, not just the group. An orbit of a group action describes all configurations equivalent under the permitted transformations. For ordered pairs under the symmetric group, equality of the two entries is preserved, separating the two group orbits in equality-pattern orbits of ordered pairs; the orbit-stabilizer theorem computes their sizes when the symmetric group is $S_3$.

A flow network is a finite directed graph $G=(V,E)$ with nonnegative flow network edge capacities $c_e$, together with distinct source and sink vertices $s,t$. A feasible flow in the nonnegative directed-edge convention is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints and flow conservation:Its flow value is the net outflow at the source,which equals the net inflow at the sink by flow conservation.

A cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity counts only directed edges leaving $S$:The net flow across the cut of a flow network subtracts flow on edges returning into $S$, and equals $|f|$.

For the following parts, a circulation with vertex demands has no exceptional source or sink in the original directed graph. Instead it satisfies net inflow minus net outflow equal to $d_v$ at every vertex. Thus positive demands consume flow, and negative demands supply flow.

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

Lagrange's theorem states that if $H$ is a subgroup of a finite group $G$, thenwhere the index of a subgroup $[G:H]$ is the number of distinct left cosets.

Every $g\in G$ lies in $gH$, since $g=ge$. By i, distinct left cosets are disjoint, so these sets form a partition of a set $G$. Each has cardinality $|H|$: the function $h\mapsto gh$ from $H$ to $gH$ is a bijection, with inverse $gh\mapsto h$, by cancellation in a group. Counting the elements in this finite partition of a set gives $|G|=[G:H]|H|$, proving the theorem.

The orbits of a group action form a partition of a set $S$: every element lies in its own orbit of a group action, and two intersecting orbits of a group action coincide because each point can be moved back and then forward using inverse elements. By the orbit-stabilizer theorem, each orbit of a group action has cardinality dividing $8$, so its size is $1,2,4$ or $8$.

If every orbit of a group action had size $2,4$ or $8$, their sizes would add to an even number, contrary to $|S|=17$. Therefore there is a one-element orbit of a group action, say $\{s^{\prime }\}$. Every $g\in G$ sends $s^{\prime }$ into this same singleton, soThus $s^{\prime }$ is a fixed point of a group action. In fact the number of fixed points of a group action is odd, since all other orbits of a group action have even cardinality.

For each symbol $a$, iterate the permutation $\sigma$. Since the symbol set is finite, some iterate repeats. Applying an inverse power of $\sigma$ shows that the first return is to $a$ itself, givingwith the displayed symbols distinct. This is a permutation cycle. If two such lists share a symbol, applying powers of $\sigma$ shows that they contain exactly the same symbols. Hence these group orbits form a partition of a set $\{1,\dots ,n\}$. On each group orbit, $\sigma$ acts as the corresponding permutation cycle, and these disjoint permutation cycles multiply to $\sigma$.

The disjoint cycle decomposition is unique up to reordering the cycles and cyclically rotating the entries within each cycle, with fixed points optionally omitted. Indeed, each cycle must consist of one of the uniquely determined group orbits, and its successive entries must follow the action of $\sigma$.

For a finite or countable partition of a set into events $B_i$, the law of total probability statesThe events $A\cap B_i$ are pairwise disjoint and have union $A$, so countable additivity proves the formula. Terms with $\mathbb{P}(B_i)=0$ contribute zero and are omitted to avoid undefined conditional probabilities.

A partition of a set $\Omega$ is a collection of nonempty subsets whose union is $\Omega$ and which are pairwise disjoint:For use with probabilities, the $B_i$ must also be events in the sample space.

Write $x_i\in {\mathbb{R}}^p$ for row $i$ of the data matrix. The k-means clustering objective is the within-cluster sum of squared Euclidean distances:The nonempty $C_k$ form a partition of a set of observation indices. For fixed clusters, part (a) shows that the best $m_k$ is their centroid.

Initialize distinct centres, for example by choosing $K\le n$ distinct observations. Then repeat the following steps:

The empty-cluster repair is possible for $K\le n$ and cannot increase $J$: the transferred observation now has squared distance zero, while all other squared distances stay unchanged before the centre update.

Assignment cannot increase $J$, and any changed assignment strictly decreases it under the tie rule. Updating centres cannot increase $J$ by the centroid sum-of-squares identity. After an update, the centres are determined by the partition of a set. There are only finitely many possible assignments. Unless this is the initial round, any nonterminal round starts with an assignment that strictly reduces $J$; repairing empty clusters and updating cannot undo that decrease. Thus a partition cannot recur, proving finite termination of K-means clustering. The final result need not be a global minimum; different initial centres can lead to different final clusterings.

Let the finite set $G/H$ contain $r$ distinct left cosets. By i, they form a disjoint partition of a set $G$, and by ii each has $|H|$ elements. If $H$ is also finite, counting this finite disjoint set union givesThus $G$ is a finite group. This is the counting argument behind Lagrange's theorem.

Each left coset $gH$ is nonempty, since it contains $g=ge$, and every $g\in G$ lies in its own left coset. Suppose $aH$ and $bH$ intersect, say $a{h}_1=b{h}_2$ with $h_1,h_2\in H$. ThenSince $H$ is a subgroup, $h_2{h}_1^{-1}\in H$, and $aH\subseteq bH$. The reversed relation $b=a{h}_1{h}_2^{-1}$ gives $bH\subseteq aH$. Thus any two left cosets are either equal or disjoint, and together they cover $G$. Therefore $G/H$ is a partition of a set $G$. No finiteness or normal subgroup assumption is needed.

The orbit of $x$ under conjugation is its conjugacy classIt contains $x$ by using $g=e$, so the conjugacy classes cover $G$. If $z=gx{g}^{-1}$, then $x=g^{-1}zg$, and the group action identity shows that conjugating either element further gives the same orbit; hence $C(z)=C(x)$. If $C(x)$ and $C(y)$ intersect at $z$, this gives $C(x)=C(z)=C(y)$. Thus distinct conjugacy classes are disjoint and the conjugacy classes form a partition of a set $G$.

A conjugacy class $C(x)$ is a singleton exactly when $gx{g}^{-1}=x$ for every $g\in G$, equivalently when $gx=xg$ for every $g$. Thus the singleton conjugacy classes correspond exactly to elements of the center of a group $A$, and there are $|A|$ of them.

Every other conjugacy class has at least two elements. Since the conjugacy classes form a partition of a set $G$, if $r$ is the number of these remaining classes then $2r\le |G|-|A|$. ConsequentlyThis conjugacy class count bound from the center needs no classification of the finite group.

For observations ${\mathbf{x}}_i\in {\mathbb{R}}^p$, K-means clustering seeks nonempty clusters in cluster analysis $C_1,\dots ,C_K$ and centroids ${\mathbf{m}}_k$ minimizingAt fixed centroids, assigning each point to a nearest centroid minimizes its squared Euclidean distance. At fixed assignments, the centroid sum-of-squares identity shows that the sample mean uniquely minimizes each group's contribution. These alternating steps cannot increase $W$.

For finite termination of K-means clustering, more than a lower bound on $W$ is needed. Keep an assignment unchanged when nearest centroids tie, and stop when assignments no longer change. Every change then strictly decreases $W$. After updating the centroids, $W$ is determined by the partition of a set of $n$ indices; there are only finitely many choices for that partition of a set, so no strictly improving partition of a set can recur. Empty clusters in cluster analysis require a convention, such as moving a point from a nonsingleton cluster in cluster analysis to become its own centroid, which cannot increase $W$. With such a consistent convention the algorithm terminates, although it may reach only a local minimum.

The left coset isEvery $g\in G$ belongs to $gH$, because $e\in H$, so the cosets cover $G$. If $gH$ and $kH$ intersect, choose $g{h}_1=k{h}_2$ in the intersection. Then $k^{-1}g=h_2{h}_1^{-1}\in H$, so $g=kh$ for some $h\in H$. Thus $gH=khH=kH$.

Hence two left cosets are either identical or disjoint, and the distinct left cosets form a partition of a set whose union is $G$. Finiteness is unnecessary for this partition argument. In the finite case each coset has $|H|$ members, since multiplication by $g$ is a bijection, giving Lagrange's theorem.

Group the elements of a colouring by equality of colour. This creates a unique partition of a set into nonempty unlabelled blocks, each of one colour, with distinct blocks assigned distinct colours.

For a partition of a set with $k$ blocks, assigning distinct colours to the blocks gives the falling factorial $x(x-1)\cdots (x-k+1)$ possibilities. To see that no extra factor $k!$ is needed, order the blocks canonically by their smallest elements, then assign colours in that order. There are $A(n,k)$ possible set partitions with $k$ blocks; these numbers are the Stirling numbers of the second kind.

Every colouring is counted exactly once in exactly one value of $k$, soFor $k>x$, no colouring of the blocks is possible and the displayed falling factorial is zero, because one factor is $x-x$.

Both sides of (ii) are polynomials in the colour count, and they agree at every integer $x\ge 2$. A nonzero polynomial has only finitely many roots, so this is a polynomial identity and holds also at $x=0,1$. It can therefore be evaluated at every possible value of the Poisson random variable $X$.

Take expectations and use the factorial moments from (a)(iv). The sum over $k$ is finite, so linearity of expectation givesCombining this with (iii) proves Dobiński's formula for the Bell numbers:For completeness, the empty set has one partition of a set, giving $B(0)=1$; that case uses the empty-product conventions $0^0=1$ in this identity and a $k=0$ term in the partition sum.

Since the $B_i$ form a partition of a set of the sample space, the events $A\cap B_i$ are pairwise disjoint and their set union is $A$. By countable additivity of probability, followed by the definition of conditional probability,Every ratio is legitimate because each $\mathbb{P}(B_i)>0$. This proves the countable law of total probability.

Starting from $n$ singleton blocks, a partition of a set into $n-1$ nonempty blocks has exactly one block of size two and all other blocks of size one: the sum of the block sizes exceeds the number of blocks by exactly one. Choosing that pair determines the partition uniquely. HenceThis fixed value of $k$ works for every $n\ge 2$. It is forced already by $n=2$: $S(2,1)=1$, whereas for positive $k$ the only $\left(\genfrac{}{}{0ex}{}{2}{k}\right)$ equal to one is $\left(\genfrac{}{}{0ex}{}{2}{2}\right)$.