Exercise 1976Combinatorics › Binomial coefficientsOlympiadAdded 5 Nov 2026
Sperner's theorem and the LYM inequality
#antichains#double counting#chains#Sperner
Statement
A family of subsets of is an *antichain* if no set of is contained in another. Prove the LYM inequality
and deduce Sperner's theorem: .
Hint
Count pairs (set , maximal chain passing through ).
Show solutionHide solution
Solution
Idea. A maximal chain adds one element at a time, so it corresponds to a permutation; an antichain meets each chain at most once.
LYM. There are maximal chains. Each set of size lies on exactly of them. Since is an antichain, each chain contains at most one member of . Therefore
Dividing by gives .
Sperner. For every , , so
∎
Sharpness. All subsets of size form an antichain of that size.
Lesson. Double count (set, maximal chain) pairs: chains correspond to permutations and give clean factorial weights.