Our goal is to prove a version of Sperner's theorem for multisets. A $k$-multiset is a collection of elements, where one element may appear up to $k$ times. A $k$-multiset of $[n]=\{1,\ldots,n\}$ can be viewed as a vector $x\in\{0,1,\ldots,k\}^n$, where $x_i$ is the multiplicity of element $i$ in the set. For example, the vector $x=(0,2,0,1,0,3)$ corresponds to $3$-multiset $\{2,2,4,6,6,6\}$ in $[6]=\{1,\ldots,6\}$.
A multiset $x$ is a subset of a multiset $y$ if $x_i\leq y_i$ for all $i$. Otherwise the sets are incomparable. Let $f(n,k)$ denote the largest number of incomparable $k$-multisets of $\{1,\ldots,n\}$.
Theorem (Sperner): $f(n,1)$ equals to the number $\tbinom{n}{\lfloor n/2\rfloor}$ of vectors $x\in \{0,1\}^n$ such that $x_1+\cdots+x_n=\lfloor n/2\rfloor$.We extend this to the case $k=2$.
Theorem: $f(n,2)$ equals to the number of vectors $x\in \{0,1,2\}^n$ such that $x_1+\cdots+x_n=n$.That is, $f(n,2)$ equals to the coefficient of $z^n$ after expressing $(1+z+z^2)^n$ as the sum of terms.
We need some versions of Hall's Marriage theorem. Exercise 5.6 in the book claims the following.
Lemma 1: Let $G$ be a bipartite graph with bipartition $A,B$. Let $a$ be the minimum degree of a vertex in $A$, and $b$ the maximum degree of a vertex in $B$. If $a\geq b>0$ then there exists a matching of $A$ into $B$.We will need the following refined version of this fact.
Lemma 2: Let $G$ be a bipartite graph with bipartition $A,B$. Suppose that: (i) there are no isolated vertices in $A$, and that (ii) the degree of every vertex $v\in B$ is at most the minimum degree of vertices incident to $v$. Then there exists a matching of $A$ into $B$.Proof: We are going to remove some edges, and then apply Lemma 1. Suppose not all vertices in $A$ have the same degree. Let $U\subseteq A$ be the vertices in $A$ all of maximal degree; let $k$ be this degree. If all vertices in $B$ have degree $< k$, then we can remove one incident edge for each of these vertices, and the conditions of Lemma 2 are still fulfiled.
So suppose some vertices $v_1,\ldots,v_p$ in $B$ have degree $k$. By (ii), each of these vertices can have at most $|N(v_i)|\leq k$ neighbors in $A$. Apply Lemma 1 to the graph with parts $A'=\{v_1,\ldots,v_q\}$ and $B'=N(v_1)\cup \cdots\cup N(v_p)$; we can do this, because all vertices in $A$ have degree $\leq k$. This gives us a matching from $A'$ into $B'$. Remove from the original graph all edges of this matching. The resulting graph satisfies both conditions (i) and (ii), but all vertices in $B$ now have degree $< k$. If a vertex $u\in U$ on the left side was matched, then its degree drops from $k$ to $k-1$. To achieve this for all vertices in $U$, just drop arbitrary one incident edge for each non-matched vertex in $U$.
When proceeding in this way, we will evetually reach a graph in which all vertices in $A$ have the same nonzero degree, and we can apply Lemma 1 for this graph. $\Box$
We now turn to the proof of our Theorem. The proof is similar to that of Sperner's theorem via Hall's theorem. The size of a $2$-multiset $x\in\{0,1,2\}^n$ is the sum of its components, that is, the total number of elements counting with multiplicities. Hence, the size lies between $0$ and $2n$. The idea is similar to that of ``push to the middle level'' in the original Sperner's proof: having an arbitrary family of $m >n$ or $m < n$ pairwise incomparable multisets, try to associate with it a family of $m$ distinct incoparable multisets of size exactly $n$.
Suppose we are given a collection of $m$ pairwise incomparable $2$-multisets. Let $x_1,\ldots,x_q\in\{0,1,2\}^n$ be the multisets in our collection of maximal size; let this size be $k$, and assume that $k >n$. Consider the bipartte graph whose left part is $A=\{x_1,\ldots,x_q\}$ and right part $B$ consists of all multisets which can be obtained from some vector $x\in A$ by subtracting $1$ from some its nonzero component. (This corresponds to removing one element.)
Since the size $k$ is strictly grater than the number $n$ of coordinates, in every vector $x\in A$ the number $2$'s is strictly grater than the number of $0$'s. The degree of $x\in A$ is the number of $1$'s and of $2$'s, whereas the degree of $y\in B$ is the number of $1$'s and of $0$'s. Hence, for every vertex $x\in A$, the number of edges leaving $x$ is at least the number of edges entering any its neighbor. We thus can apply Lemma 2, and obtain a matching $(x_1,y_1),\ldots,(x_q,y_q)$ from $A$ into $B$. Replace now the old multisets $x_1,\ldots,x_q$ in our collection by the multisets $y_1,\ldots,y_q$. We have the same number $m$ of pairwise incomparable multisets, but this time of size at most $k-1$.
Arguing in this way we can achieve that every multiset in the actual collection is of size $\leq n$. In a similar way we can achieve that every multiset has size $\geq n$. $\Box$
N.B. A yet another short proof of Sperner's theorem was told me 21.10.2012 by Tomas Juskevicius, see this his note. This inductive argument seems to extend also to $k$-multisets with $k>2$. Thomas wrote me: "The point is that all these results can be obtained from a single LYM inequality for multisets (proof does not differ from the plain, it seems)". He pointed to the reference [1] in this paper.