Assume n is an even integer. For an odd integer m, a sequence of m sets S1,…,Sm ⊆ [n] is a graceful chain of length m if…

Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if:

1. $S_1 \subset S_2 \subset \dots \subset S_m$
2. For every $1 \le i \le m − 1$ we have $|S_{i+1}| = |S_i| + 1$
3. $|S_m| + |S_1| = n$.

Show that it is possible to decompose the $2^n$ subsets of $[n]$ using $\binom{n}{\frac{n}2}$ graceful chains.

Note: Of course, the chains do not have to be of the same length. Also, recall that by decomposition we mean that each of the $2^n$ sets $S \subseteq [n]$ should appear in exactly one of the graceful chains.

• What are your thoughts? – Zev Chonoles Jun 18 '15 at 9:20