[proofplan] We double-count pairs $(\mathcal{C}, A)$ where $\mathcal{C}$ is a maximal chain in $\mathcal{P}(X)$ and $A \in \mathcal{A} \cap \mathcal{C}$. Since $\mathcal{A}$ is an antichain, each maximal chain contributes at most one such pair, giving an upper bound of $n!$ (the total number of maximal chains). On the other hand, each $A \in \mathcal{A}$ with $|A| = k$ lies in exactly $k!(n-k)!$ maximal chains. Summing over $\mathcal{A}$ and dividing by $n!$ yields the LYM inequality. [Sperner's Theorem](/theorems/2585) follows immediately by bounding each summand. [/proofplan] [step:Count the maximal chains in $\mathcal{P}(X)$ and the chains through a given set] A maximal chain in $\mathcal{P}(X)$ is a sequence $\varnothing = C_0 \subsetneq C_1 \subsetneq \cdots \subsetneq C_n = X$ with $|C_i| = i$ for each $i$. Such a chain is determined by the order in which elements of $X$ are added: at step $i$, the element $C_i \setminus C_{i-1}$ is adjoined. Since $|X| = n$, this is a permutation of $X$, so the total number of maximal chains is $n!$. Now fix a set $A \subseteq X$ with $|A| = k$. A maximal chain passes through $A$ if and only if $A = C_k$ in the chain. The portion of the chain below $A$ is a maximal chain in $\mathcal{P}(A)$, of which there are $k!$ (permutations of $A$). The portion above $A$ is determined by the order of adjunction of the $n - k$ elements of $X \setminus A$, of which there are $(n - k)!$ orderings. By independence of the two portions, the number of maximal chains through $A$ is $k!(n-k)!$. [guided] We set up a double-counting argument. Define the set of pairs \begin{align*} \mathcal{S} = \{(\mathcal{C}, A) : \mathcal{C} \text{ is a maximal chain in } \mathcal{P}(X),\; A \in \mathcal{A} \cap \mathcal{C}\}. \end{align*} We will count $|\mathcal{S}|$ in two ways. First, we need to know two quantities: (1) how many maximal chains exist in $\mathcal{P}(X)$, and (2) how many maximal chains pass through a given set $A$. **Total maximal chains.** A maximal chain $\varnothing = C_0 \subsetneq C_1 \subsetneq \cdots \subsetneq C_n = X$ with $|C_i| = i$ is completely determined by specifying which element is added at each step: $C_i = C_{i-1} \cup \{a_i\}$ where $a_1, a_2, \ldots, a_n$ is a permutation of $X$. Conversely, every permutation of $X$ determines a unique maximal chain. So the number of maximal chains is $n!$. **Maximal chains through $A$ with $|A| = k$.** A maximal chain passing through $A$ must have $C_k = A$. The sub-chain $\varnothing = C_0 \subsetneq C_1 \subsetneq \cdots \subsetneq C_k = A$ is a maximal chain in $\mathcal{P}(A)$, determined by a permutation of $A$: there are $k!$ choices. The sub-chain $A = C_k \subsetneq C_{k+1} \subsetneq \cdots \subsetneq C_n = X$ is determined by the order in which the elements of $X \setminus A$ are adjoined: there are $(n - k)!$ choices. Since these two portions are determined independently — the elements below $A$ and the elements above $A$ do not interact — the total count is $k! \cdot (n - k)!$. [/guided] [/step] [step:Bound $|\mathcal{S}|$ from above using the antichain property] Count $|\mathcal{S}|$ by ranging over maximal chains first. For each maximal chain $\mathcal{C}$, the quantity $|\mathcal{A} \cap \mathcal{C}|$ is the number of elements of $\mathcal{A}$ lying on $\mathcal{C}$. Since $\mathcal{A}$ is an antichain and $\mathcal{C}$ is a chain, $|\mathcal{A} \cap \mathcal{C}| \leq 1$. Summing over all $n!$ maximal chains: \begin{align*} |\mathcal{S}| = \sum_{\mathcal{C}} |\mathcal{A} \cap \mathcal{C}| \leq n!. \end{align*} [guided] This is the step where the antichain hypothesis is used. If $\mathcal{A}$ were not an antichain — say it contained $A \subsetneq B$ — then a maximal chain passing through both $A$ and $B$ would contribute $2$ to the count, and the bound $|\mathcal{S}| \leq n!$ would fail. Since $\mathcal{A}$ is an antichain and $\mathcal{C}$ is a chain, any two elements of $\mathcal{A} \cap \mathcal{C}$ would be both comparable (from $\mathcal{C}$) and incomparable (from $\mathcal{A}$), which is impossible. So $|\mathcal{A} \cap \mathcal{C}| \leq 1$ for each maximal chain $\mathcal{C}$. There are $n!$ maximal chains, each contributing at most $1$ to $|\mathcal{S}|$, giving $|\mathcal{S}| \leq n!$. [/guided] [/step] [step:Compute $|\mathcal{S}|$ from below by summing over elements of $\mathcal{A}$] Count $|\mathcal{S}|$ by ranging over elements of $\mathcal{A}$ first. Each $A \in \mathcal{A}$ with $|A| = k$ lies in exactly $k!(n-k)!$ maximal chains, so it contributes $k!(n-k)!$ pairs to $\mathcal{S}$. Summing: \begin{align*} |\mathcal{S}| = \sum_{A \in \mathcal{A}} |A|!\,(n - |A|)!. \end{align*} Grouping by level, where $a_r = |\mathcal{A} \cap X^{(r)}|$: \begin{align*} |\mathcal{S}| = \sum_{r=0}^{n} a_r \cdot r!(n-r)!. \end{align*} [/step] [step:Combine the two counts and divide by $n!$ to obtain the LYM inequality] From the previous two steps: \begin{align*} \sum_{r=0}^{n} a_r \cdot r!(n-r)! \leq n!. \end{align*} Dividing both sides by $n!$ and using $\frac{r!(n-r)!}{n!} = \frac{1}{\binom{n}{r}}$: \begin{align*} \sum_{r=0}^{n} \frac{a_r}{\binom{n}{r}} \leq 1. \end{align*} Since $a_r = |\mathcal{A} \cap X^{(r)}|$, this is precisely \begin{align*} \sum_{r=0}^{n} \frac{|\mathcal{A} \cap X^{(r)}|}{\binom{n}{r}} \leq 1. \end{align*} [guided] The double-counting gives: \begin{align*} \sum_{r=0}^{n} a_r \cdot r!(n-r)! = |\mathcal{S}| \leq n!. \end{align*} To convert this into the LYM form, divide both sides by $n!$: \begin{align*} \sum_{r=0}^{n} a_r \cdot \frac{r!(n-r)!}{n!} \leq 1. \end{align*} The ratio $\frac{r!(n-r)!}{n!}$ simplifies: since $\binom{n}{r} = \frac{n!}{r!(n-r)!}$, we have $\frac{r!(n-r)!}{n!} = \frac{1}{\binom{n}{r}}$. So: \begin{align*} \sum_{r=0}^{n} \frac{|\mathcal{A} \cap X^{(r)}|}{\binom{n}{r}} \leq 1. \end{align*} This is the LYM inequality. [/guided] [/step] [step:Deduce the Sperner bound as a corollary] Since $\binom{n}{r} \leq \binom{n}{\lfloor n/2 \rfloor}$ for all $0 \leq r \leq n$, we have $\frac{1}{\binom{n}{r}} \geq \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}$ for each $r$. Therefore: \begin{align*} \frac{|\mathcal{A}|}{\binom{n}{\lfloor n/2 \rfloor}} = \sum_{r=0}^{n} \frac{|\mathcal{A} \cap X^{(r)}|}{\binom{n}{\lfloor n/2 \rfloor}} \leq \sum_{r=0}^{n} \frac{|\mathcal{A} \cap X^{(r)}|}{\binom{n}{r}} \leq 1, \end{align*} giving $|\mathcal{A}| \leq \binom{n}{\lfloor n/2 \rfloor}$. [/step]