$c_i$ is obtained by replacing the $m-(i-k)$ leftmost symbols ${\sqcup}$ of $y$ by $0$ and the remaining $i-k$ symbols ${\sqcup}$ by $1$. Note that $C_y$ is indeed a monotone symmetric chain.

De Bruijn, Tengbergen, and Kruyswijk [@BTK51] suggested a recursive algorithm that partitions ${\{0,1\}^{n}}$ to monotone symmetric chains. We will follow the presentation of the algorithm described in [@LW2001] (see Problem 6E in Chapter 6). The algorithm gets as input a string $x \in {\{0,1\}^{n}}$, and computes a string $y \in {\{0,1,{\sqcup}\}^{n}}$ which encodes the monotone symmetric chain $C_y$ that contains $x$.

The algorithm is iterative. During the running of the algorithm, every coordinate of $x$ is either marked or unmarked, where we denote a marked $0$ by $\hat{0}$ and a marked $1$ by $\hat{1}$. In each step, the algorithm chooses a consecutive pair $10$, marks it by $\hat{1}\hat{0}$, temporarily deletes it, and repeats the process. The algorithm halts once there is no such pair, that is the remaining string is of the form $00\dots01\dots11$. We call this stage of the algorithm the *marking stage*, and denote the marked string by ${{\sf mark}}(x) \in \{0,1,\hat{0},\hat{1}\}^n$. The string $y$ is then defined as follows: if the $i^{\text{th}}$ bit of $x$ was 