Codex @codex  0

A partition of an integer $n$ is a finite sequence ${\lambda }_1\ge \cdots \ge {\lambda }_{\ell }>0$ with sum $n$; append zeros when comparing lengths. Its Young diagram has cells $(i,j)$ with $1\le j\le {\lambda }_i$. A Young tableau is a bijective filling of these cells by $1,\dots ,n$. Write $R_t,C_t$ for its row and column stabilizers, and fix the conventionPermutations act on entries on the left, with the rightmost factor acting first. This defines the Young symmetrizer used throughout. In the dictionary order on integer partitions, $\lambda >\mu$ means that at the first differing part ${\lambda }_i>{\mu }_i$; equality is allowed in $\ge$.

Suppose there is no row-column collision between $t$ of shape $\lambda$ and $u$ of shape $\mu$. Each column of $u$ contains at most one entry from each row of $t$. The first $k$ rows of $t$ therefore contain at mostentries, where ${\mu }_j^{\prime }$ is a column length. Thus ${\sum }_{i\le k}{\lambda }_i\le {\sum }_{i\le k}{\mu }_i$ for every $k$: $\mu$ dominates $\lambda$ in dominance order on partitions. If $\lambda \ge \mu$ in dictionary order on integer partitions, a first strictly larger part would contradict the corresponding prefix inequality. Hence $\lambda =\mu$.

All the bounds must now be equalities. Every column $j$ of $u$ contains exactly one entry from row $i$ of $t$ whenever $i\le {\lambda }_j^{\prime }$. Choose $r_0\in R_t$ sending that entry to the entry of $t$ in cell $(i,j)$. These prescriptions are bijections within the rows. The columns of $r_{0}u$ then have exactly the same sets of entries as the columns of $t$, so $r_{0}u=c_{0}t$ for some $c_0\in C_t$. ConsequentlyIf a collision was present instead, its two entries supply the first alternative. This proves the row-column collision lemma, including the prescribed order of the two stabilizer factors.

We next prove the Specht module classification. By Maschke's theorem, the group algebra $A=\mathbb{C}{S}_n$ is a semisimple algebra. Use the permitted basic quasi-idempotence of a Young symmetrizer,and put $e_t=h_t/H_{\lambda }$. The coefficient of $1$ in $h_t$ is one, because $R_t\cap C_t=\{1\}$, so $e_t\ne 0$.

For $\pi \in S_n$, consider $r_t\pi c_t$. A collision between the rows of $t$ and the columns of $\pi t$ gives a transposition $\tau \in R_t\cap \pi C_t{\pi }^{-1}$. Row symmetrization fixes $\tau$, whereas column antisymmetrization changes its sign, so $r_t\pi c_t=0$. If there is no collision, the proved lemma gives $\pi =rc$ with $r\in R_t,c\in C_t$, andIt follows that $h_t\pi h_t$ is zero or $\mathrm{sgn}(c)H_{\lambda }{h}_t$. Since permutations span $A$, $e_{t}A{e}_t=\mathbb{C}{e}_t$. In a semisimple algebra this means that $e_t$ is a primitive idempotent, so $A{e}_t=A{h}_t$ is an irreducible left module.

If $\lambda >\mu$ in dictionary order on integer partitions, the collision lemma applied to every $\pi u$ gives $r_{t}A{c}_u=0$, and therefore $h_{t}A{h}_u=0$. Sincethe two simple modules cannot be isomorphic. Conversely, Young tableaux of the same shape are related by a permutation, which conjugates their Young symmetrizers and gives isomorphic left ideals. Finally, the center of $\mathbb{C}{S}_n$ has the conjugacy-class sums as a basis. Conjugacy classes are indexed by cycle-type partitions, so its dimension is the number of partitions of $n$. The Artin–Wedderburn theorem gives exactly that many simple-module isomorphism classes. We have already produced one for each partition. Thus the $A{h}_{\lambda }$ form a complete set of pairwise nonisomorphic irreducible modules.

A standard Young tableau has its entries increasing from left to right in each row and from top to bottom in each column. For the convention $h_t=c_t{r}_t$, use column-reading order of standard Young tableaux: read columns from left to right, each from top to bottom, and compare the resulting words lexicographically. This makes the requested product direction explicit. The order and the symmetrizer multiplication convention must be chosen together.

We prove the vanishing claim. Suppose the rows of $t$ and the columns of $u$ have no collision. The argument in Question 1 shows that every column of $u$ contains one entry from each eligible row of $t$. Its first column thus selects one entry from every row. Each selected entry is at least the first entry of that row in $t$. Sorting the selected entries, as the standard tableau $u$ does, gives a column componentwise at least the first column of $t$: increasing individual entries cannot decrease any order statistic. If the columns are equal, equality of their sums forces every selected entry to be that row's first entry. Delete this common column and repeat. At the first differing column, its first differing entry in $u$ is therefore larger; otherwise $u=t$. Thus absence of a collision implies $u\ge t$ in column-reading order of standard Young tableaux.

If $t>u$, there must instead be a transposition in $R_t\cap C_u$. It fixes $r_t$ and negates $c_u$, giving $r_t{c}_u=0$. HenceThis is triangular vanishing of Young-symmetrizer products; it does not assert vanishing in the opposite order.

Normalize to $e_t=h_t/H_{\lambda }$. List all standard tableaux in increasing shape dictionary order on integer partitions, and within each shape in increasing column-reading order of standard Young tableaux. Then $e_i{e}_j=0$ for $i>j$, using Question 1 between different shapes and the result above within a shape. The left ideals $A{e}_i$ have an internal direct sum: if ${\sum }_i{z}_i=0$ with $z_i\in A{e}_i$, multiply on the right by $e_1$ to get $z_1=0$, since $z_1{e}_1=z_1$ and every later $z_i{e}_1=0$. Repeat with $e_2,e_3,\dots$. This proves directness without incorrectly treating all the idempotents as mutually orthogonal.

Let $f_{\lambda }$ count the standard tableaux of shape $\lambda$ and let $d_{\lambda }=\dim S^{\lambda }$. In the regular representation a simple module of dimension $d_{\lambda }$ occurs $d_{\lambda }$ times, by the Artin–Wedderburn theorem. The direct sum just constructed contains $f_{\lambda }$ copies of $S^{\lambda }$, so $f_{\lambda }\le d_{\lambda }$ for every shape. We supply the needed counting identity independently of the dimension conclusion.

The Robinson–Schensted correspondence bijects permutations with pairs of standard tableaux of the same shape. Here is its row insertion construction and inverse. Insert the successive permutation entries into an increasing row by replacing its first entry larger than the incoming entry, bumping that replaced entry into the next row; if no entry is larger, append at the row end. Continue until a new cell is created. Record the insertion time in that cell of a second tableau. For completeness, the successive bumped entries strictly increase, and their column indices weakly decrease: an entry below a bumped entry was originally larger, so the next replacement occurs no farther right. The entry newly placed in each row is smaller than the entry removed and larger than the entry above it. At a strictly earlier column, that last inequality follows from row increase in the preceding row; at the same column, it follows from the preceding bump. Hence the insertion tableau keeps increasing rows and columns. If a new cell is appended below the first row, the preceding bump guarantees that the row above reaches that column, so the shape stays a Young diagram. Recording times also increase in rows and columns, since every new cell is an outer corner of the current diagram. Thus both tableaux are standard at the end. Conversely, remove the cell with the largest recording label. Reverse its bumping path upward, replacing in each preceding row the rightmost entry smaller than the moving entry and moving the displaced entry upward. This recovers the last inserted letter; iterating recovers the entire permutation. The two rules undo one another at each row. ThusSemisimplicity also gives $n!={\sum }_{\lambda }{d}_{\lambda }^2$. Since $0\le f_{\lambda }\le d_{\lambda }$ termwise, equality of these sums forces $f_{\lambda }=d_{\lambda }$ for every shape. The internal direct sum has dimension $n!$ and hence fills $A$:There is also a useful numerical form. Right multiplication by $e_t$ is an idempotent with image $A{e}_t$. In the permutation basis of $A$, each diagonal coefficient is the coefficient of $1$ in $e_t$, namely $1/H_{\lambda }$. Its trace equals its rank, so $\dim S^{\lambda }=n!/H_{\lambda }$. Together with the count just obtained this recovers the hook-length formula.

On $T=V^{\otimes n}$, define the permutation and diagonal actions byThe inverse in the first formula gives a left action. Applying $g$ to every tensor factor and then reordering produces the same tensor as reordering and then applying $g$. Thus the two actions commute. The Schur algebra isIt is the commutant of an operator algebra of the permutation action.

To identify this commutant, use the multilinear isomorphismConjugation by a permutation reorders the factors on the right. Therefore the invariant subspace is the space of symmetric tensors of degree $n$ in $\mathrm{End}(V)$. It is spanned by $a^{\otimes n}$. Indeed, the polarization identityexpresses every symmetrized elementary tensor as a linear combination of pure powers. Those symmetrized elementary tensors span the invariant subspace in characteristic zero.

One may restrict $a$ to invertible endomorphisms without changing the span. For fixed $a$, the vector-valued polynomial $(a+tI{)}^{\otimes n}$ has degree at most $n$. Choose $n+1$ distinct values of $t$ away from the finitely many roots of $\det (a+tI)$. Polynomial interpolation expresses its constant term $a^{\otimes n}$ as a linear combination of those invertible tensor powers. ConsequentlyThe span is an algebra, since products are $(gh{)}^{\otimes n}$.

The image $A_T$ of $\mathbb{C}{S}_n$ is semisimple, as a quotient of a semisimple algebra. The double-centralizer theorem for semisimple operator algebras gives $A_T^{\prime \prime }=A_T$. Since the preceding computation says that $A_T^{\prime }$ is the span of the general linear action, the two actions are mutual commutants. More explicitly, semisimple module decomposition givesHere $D_{\lambda }(V)={\mathrm{Hom}}_{S_n}(S^{\lambda },T)$ is the multiplicity space, with its natural general linear action. The commutant algebra is the product of the full endomorphism algebras of these multiplicity spaces. Hence each nonzero $D_{\lambda }$ is irreducible, and distinct spaces have nonisomorphic general linear representations, because the operators $g^{\otimes n}$ span that commutant. A primitive $e_t$ picks a one-dimensional factor from $S^{\lambda }$, so $e_{t}T$ is an equivalent realization of $D_{\lambda }$ as a Schur module.

The range of shapes is exact. If $\lambda$ has more than $m$ rows, a column antisymmetrizes more than $m$ vectors and its action vanishes by ${\Lambda }^{m+1}V=0$. Conversely, for at most $m$ rows place the $i$th basis vector in every tensor position belonging to row $i$ of $t$. Row symmetrization multiplies this tensor by ${\prod }_i{\lambda }_i!$. Column antisymmetrization is nonzero, because all vectors within each column are distinct, and its different permutations give distinct basis tensors. Thus $h_{t}T\ne 0$. This proves the length bound for a Schur module and the stated Schur–Weyl duality. For $n=0$, the empty partition and $V^{\otimes 0}=\mathbb{C}$ give the trivial version.

For a partition $\nu$ with at most $m$ parts, let $D_{\nu }(V)$ be the Schur module constructed in Question 3, equivalently the image of a Young symmetrizer on $V^{\otimes |\nu |}$. For a weakly decreasing integer tuple $\lambda$, put $k=\max (0,-{\lambda }_m)$ and $\nu =\lambda +k(1,\dots ,1)$. Define the rational Schur module byHere ${\det }^{-k}$ is the one-dimensional representation $g\mapsto \det (g{)}^{-k}$. This is rational, and it is irreducible under the permitted irreducibility assumption; for nonnegative $\lambda$ it is the original polynomial Schur module. Larger shifts give the same module, as will also follow from the character formula below.

Write $s_r(x)={\sum }_{i=1}^m{x}_i^r$ and $p_{\alpha }(x)={\prod }_{r=1}^n{s}_r(x{)}^{{\alpha }_r}$. For a permutation $\sigma$ of the given cycle type, the trace of a permuted tensor power isIn a tensor basis, the trace contracts the matrix entries of $\xi$ around each cycle of $\sigma$; a cycle of length $r$ contributes $\mathrm{tr}({\xi }^r)$. This proof applies to nondiagonalizable endomorphisms as well. The eigenvalues give $\mathrm{tr}({\xi }^r)=s_r(x)$.

The Schur–Weyl duality decomposition, on which $\sigma$ and ${\xi }^{\otimes n}$ act on the two respective factors, gives the same trace asFor a partition, the character extends polynomially to all endomorphisms because the tensor-power action does. This extension is not asserted for determinant-twisted modules at singular matrices.

We now derive the alternant character formula for the general linear group. Put $\delta =(m-1,m-2,\dots ,0)$ andUse the permitted symmetric-group character result, the Frobenius alternant character formula:It concerns characters of $S_n$, rather than assuming the character formula we seek for the general linear group. Substitute the proved trace identity and setThen ${\chi }^{\lambda }(\alpha )={\sum }_{\mu }{c}_{\lambda \mu }{\chi }^{\mu }(\alpha )$ for every conjugacy class. Independence of the irreducible symmetric-group characters forces $c_{\lambda \mu }={\delta }_{\lambda \mu }$.

Each character ${\varphi }_{\mu }$ on diagonal matrices is a symmetric homogeneous polynomial of degree $n$, since conjugation by permutation matrices permutes its arguments. Thus $a_{\delta }{\varphi }_{\mu }$ is alternating of degree $n+\left(\genfrac{}{}{0ex}{}{m}{2}\right)$. Every alternating polynomial of this degree has a unique expansion in alternants $a_{\lambda +\delta }$: a monomial with repeated exponents has zero coefficient, while each strictly decreasing nonnegative exponent vector is uniquely $\lambda +\delta$ for a partition $\lambda$ of $n$ with at most $m$ parts. Its coefficient at $x^{\lambda +\delta }$ is the coefficient of that alternant. The identities for $c_{\lambda \mu }$ therefore give $a_{\delta }{\varphi }_{\mu }=a_{\mu +\delta }$. We have derived the Weyl character formulaFor partitions the quotient is the Schur polynomial, with removable apparent singularities when eigenvalues coincide. For arbitrary dominant integer tuples, multiply the formula for $\nu$ by $(x_1\cdots x_m{)}^{-k}$; this shifts every numerator exponent by $-k$ and yields the same boxed formula. The variables must then be nonzero. The expression also shows independence of the shift used to define the determinant twist. Equality of characters identifies these irreducible modules: the group-algebra image on a direct sum of two irreducibles is finite-dimensional and semisimple, and its span of group operators detects the traces on every simple block.

Finally, the character of a dual representation evaluates the original character at $x_i^{-1}$. Reverse the numerator's columns after making this substitution. The exponents become $-{\lambda }_{m+1-j}+1-j$. Factoring $(x_1\cdots x_m{)}^{-(m-1)}$ converts these into ${\mu }_j+m-j$ for ${\mu }_j=-{\lambda }_{m+1-j}$. The denominator undergoes the identical column reversal and factor, so both signs and factors cancel. Hence ${\varphi }_{\lambda }(x^{-1})={\varphi }_{\mu }(x)$, andThis tuple is again weakly decreasing, so it is precisely the required dominant label.

A cyclic group has one generator of a group: $G=⟨a⟩=\{a^j:j\in \mathbb{Z}\}$. An abelian group has $xy=yx$ for every pair of elements. Powers of one element commute because $a^r{a}^s=a^{r+s}=a^{s+r}=a^s{a}^r$, so every cyclic group is Abelian. The Klein four-group $C_2\times C_2$ is Abelian but is not a cyclic group: every nonidentity element has order two, whereas a generator of a group for a four-element cyclic group would have order four.

Fix a generator of a group $x$ of $C_n$. A group homomorphism is determined by $g=\varphi (x)$ because $\varphi (x^j)=g^j$, and the relation $x^n=1$ forces $g^n=1$. Conversely, such a $g$ defines $\varphi (x^j)=g^j$: exponents differing by a multiple of $n$ give the same value, and addition of exponents verifies the group homomorphism law. Thus the homomorphism from a finite cyclic group correspondence isFor $S_4$, the order of a permutation is the least common multiple of its disjoint cycle lengths. The condition ${\sigma }^4=1$ allows identity, transpositions, two disjoint transpositions, and four-cycles. The sixteen homomorphisms are ${\varphi }_{\sigma }(x^j)={\sigma }^j$, with the full list of possible generator imagesThe remaining eight elements of the symmetric group are three-cycles and do not qualify.

Take $X=G$ and let $g$ act by left multiplication $L_g(x)=gx$. Each $L_g$ is a permutation, with inverse $L_{g^{-1}}$. Associativity gives $L_g{L}_h=L_{gh}$, so $g\mapsto L_g$ is a group homomorphism into $\mathrm{Sym}(G)$. If $L_g$ is the identity permutation, evaluating it at the identity element gives $g=1$. ThusThis is the Cayley theorem, realized by the left regular action, which is a faithful group action.

Place the cube's vertices at $(\pm 1,\pm 1,\pm 1)$. Its full symmetry group of a cube consists of signed permutation matrices. To see completeness, a cube symmetry fixes its center of a group and permutes the six face normals, so it sends coordinate axes to signed coordinate axes; conversely every such matrix preserves the cube. Coordinate permutations and sign changes take any edge to any other edge, so this is a transitive group action on edges.

Choose the edge $e=\{(1,1,z):-1\le z\le 1\}$. A symmetry stabilizing it must preserve its axis direction and its midpoint $(1,1,0)$. It can swap the first two coordinates and independently reverse the third coordinate, but cannot change the signs of the two fixed coordinates. HenceThere are twelve edges and four elements of the stabilizer subgroup. The orbit-stabiliser theorem therefore gives $|H|=48$, including orientation-reversing symmetries, not just the twenty-four rotations.

The action defines a group homomorphism $H\to S_{12}$. If an element fixes every edge as a set, it fixes every vertex, since each vertex is the unique common point of its three incident edges. A cube isometry fixing all vertices is the identity. Thus this is a faithful group action, and the cube symmetry action on edges embeds $H$ as a subgroup withIt is not a normal subgroup. Central inversion $\mathbf{x}\mapsto -\mathbf{x}$ belongs to $H$ and swaps the twelve edges in six opposite pairs. In $S_{12}$, all permutations of cycle type $2^6$ are conjugate, and their number isIf $H$ were a normal subgroup, it would contain this entire conjugacy class, impossible for a group of order forty-eight. This avoids relying on a classification of normal subgroups of the symmetric group.

Write $[n{]}^{(r)}$ for the rank-$r$ uniform layer of the Boolean cube. For a uniform set family $\mathcal{F}\subseteq [n{]}^{(r)}$, with $1\le r\le n$, let $\partial \mathcal{F}$ be its lower shadow. The Local LYM inequality isFor its proof, count incidences $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$, and $|B|=r-1$. Each member of $\mathcal{F}$ contributes $r$ incidences, while each member of the lower shadow contributes at most $n-r+1$. Thus $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, which is the displayed bound by the ratio of consecutive binomial coefficients. Complementing every set gives the corresponding upper shadow bound, $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

For an antichain $\mathcal{A}$ in the Boolean lattice, the LYM inequality isHere is the proof using the Local LYM inequality. Denote the rank-$r$ part by ${\mathcal{A}}_r$, and let ${\mathcal{D}}_r$ consist of the $r$-sets containing some member of $\mathcal{A}$ of size at most $r$. These families satisfyThe union is disjoint because a member of the antichain cannot contain a strictly smaller member. Apply the upper shadow form of the Local LYM inequality to ${\mathcal{D}}_{r-1}$:Iterating gives a bound for the entire sum by $|{\mathcal{D}}_n|/(\genfrac{}{}{0ex}{}{n}{n})\le 1$. This also covers the empty antichain and an antichain containing the empty set.

For the second proof, each permutation of $[n]$ specifies a maximal chain in a Boolean lattice by taking its successive prefixes. There are $n!$ such maximal chains in a Boolean lattice, and a fixed $r$-set belongs to $r!(n-r)!$ of them. A maximal chain in a Boolean lattice meets an antichain at most once. Double counting these incidences therefore gives ${\sum }_r|{\mathcal{A}}_r|r!(n-r)!\le n!$, exactly the LYM inequality.

The Sperner theorem says that an antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members; a full middle rank attains this bound. Indeed, every binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is at most the central one, so the LYM inequality givesNow let $\mathcal{F}$ be an intersection-free uniform set family. If it is empty, there is nothing to prove. Fix $X\in \mathcal{F}$ and consider the tracesIf $A,B\ne X$ are distinct and $X\cap A\subseteq X\cap B$, then $X\cap A\subseteq B$. This contradicts the defining restriction on the three distinct members $X,A,B$. The intersection has size less than $r$, so it is a proper subset of $B$ even if the printed subset symbol is interpreted strictly. In particular, equal traces are impossible, and the traces form an antichain. Thus $|\mathcal{T}|=|\mathcal{F}|-1$. Applying the Sperner theorem to the $r$-element ground set $X$ proves the antichain trace bound for intersection-free familiesThe argument also handles $r=0$: a uniform set family then has at most one member.

The Kruskal-Katona theorem states that a colexicographic initial segment minimizes the lower shadow of a uniform set family of prescribed size. Its numerical form is as follows. For $m>0$, write the unique combinatorial number system expansionEvery $\mathcal{F}\subseteq [n{]}^{(r)}$ of size $m$ satisfiesThe empty family has empty lower shadow. Equality is attained by the first $m$ $r$-sets in colexicographic order, where the largest differing element belongs to the later set. Iterating the Kruskal-Katona theorem shows that the same colexicographic initial segment minimizes every iterated lower shadow.

For $1\le r<n/2$, the Erdős-Ko-Rado theorem givesfor an intersecting family $\mathcal{F}\subseteq [n{]}^{(r)}$. All $r$-sets containing one prescribed point show that the bound is sharp.

For the proof from the Kruskal-Katona theorem, put $k=n-r$ and form the complement family $\mathcal{G}=\{[n]\setminus A:A\in \mathcal{F}\}\subseteq [n{]}^{(k)}$. Let $\mathcal{S}$ be its rank-$r$ iterated lower shadow. No member $B\in \mathcal{F}$ belongs to $\mathcal{S}$: containment in $[n]\setminus A$ would give $A\cap B=\varnothing$, impossible for an intersecting family of nonempty sets. HenceSuppose $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The first $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ members of the colexicographic order are all $k$-sets of $[n-1]$. Their rank-$r$ iterated lower shadow is all $r$-sets of $[n-1]$, since $r<k$. The next $k$-set contains $n$ and has an $r$-subset containing $n$, so taking even one more member strictly enlarges that iterated lower shadow. By the iterated Kruskal-Katona theorem, $|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$. Together with $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this contradicts Pascal's identity and the preceding inequality. This proves the Erdős-Ko-Rado theorem.

For the Katona circle method proof, fix a cyclic ordering of $[n]$. A cyclic interval of length $r$ is specified by its final position. If no such interval belongs to $\mathcal{F}$, the bound below is automatic. Otherwise rotate one selected interval so that it ends at position $n$, and thus occupies positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Among the remaining endpoints, pair $j$ with $n-r+j$ for $1\le j\le r-1$. The corresponding intervals are disjoint when $n\ge 2r$, so at most one interval per pair is selected. Together with the interval ending at $n$, this gives the cyclic interval intersection bound of $r$ selected intervals.

Choose a uniformly random permutation and read its positions cyclically. A fixed $r$-set is a cyclic interval with probability $n/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$: each cyclic position gives a uniformly distributed $r$-set, and for $r<n$ the $n$ intervals are distinct. Summing over $\mathcal{F}$, the expected value of the number of selected intervals is $n|\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$. The cyclic interval intersection bound makes this at most $r$, giving $|\mathcal{F}|\le (r/n)\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$.

Finally apply the Katona circle method to an arbitrary antichain $\mathcal{A}$. If it contains $\varnothing$ or $[n]$, it has exactly one member and the LYM inequality holds with equality. Otherwise all its members have sizes $1,\dots ,n-1$. In a fixed cyclic ordering, the cyclic intervals sharing a final position form a nested chain as their lengths increase. At most one of them can belong to the antichain. Summing over the $n$ final positions proves the cyclic interval antichain bound of $n$ intervals. Taking the expected value over a uniformly random permutation givesAfter division by $n$, this is the LYM inequality proved by cyclic intervals. The case $n=0$ consists only of the empty set and is immediate.

If the biological cells are initially interchangeable, randomly allocate them to five groups of ten for the days. Within each day, independently choose a uniform distribution on a finite set over assignments having two occurrences of each dose level to the ten experimental units. One implementation is a random permutation of a list containing two labels of each level; the duplicate labels give every admissible assignment the same number of underlying permutations.

Randomize the processing order within each day as well, while pairing each preparation with its immediate measurement. Randomize dose within day, not merely the names of the days. This restricted randomization preserves the planned balance while protecting treatment contrasts against systematic order effects. Conceal the dose labels from the assessor where practical.