Number of Symmetric Chains of Length $n +1 - 2i$ in $\mathcal P(\{1,2, \dots , n\})$

Question

I am having trouble understanding the function to count the number of symmetric chains in $\mathcal P(\{1,2, \dots, n\})$ that I have in my notes.

In my notes, we have defined a symmetric chain ( in $\mathcal P(\{1,2, \dots, n\})$ ) to be a chain of sets $\mathcal C = \{C_i, C_{i+1}, \dots, C_{n-i}\}$ such that $|C_j| = j$.

Given this, my notes go on to say that for $0 \leq i \leq \frac{n}{2}$, the number of symmetric chains with $n + 1 - 2i $ sets is $l(n,i) = \binom {n}{i} - \binom{n}{i-1}$.

However, I am having a lot of trouble understanding why this is true, and in particular what these binomial coefficients are representing. Further, I suspect that this might be wrong as I have tested some small cases, and assuming that I'm understanding what it means for a chain to be a symmetric chain, then it doesn't seem to work in the cases $n=4, \; i = 1,2$.

Any clarification or correction with regards to this formula would be very much appreciated, thank you!

Answer 1

I agree with Jamie Radcliffe. Let $[n]:=\{1,2,\ldots,n\}$ and $\mathcal{P}_n$ denote the power set $\mathcal{P}\big([n]\big)$. Suppose that $\mathcal{P}_n$ has a decomposition into pairwise disjoint symmetric chains $$\mathcal{P}_n=\bigcup_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor}\,\bigcup_{r=1}^{t_k}\,\mathcal{C}_k^r\,,$$ where $\mathcal{C}_k^1,\mathcal{C}_k^2,\ldots,\mathcal{C}_k^{t_k}$ are symmetric chains of length $n+1-2k$ for each $k=0,1,2,\ldots,\left\lfloor\frac{n}{2}\right\rfloor$. For example, when $n=4$, we have $$\begin{align}\mathcal{P}_4&=\big\{\emptyset,\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\big\} \\ &\phantom{aaaaa}\cup\big\{\{2\},\{2,3\},\{2,3,4\}\big\}\cup\big\{\{3\},\{3,4\},\{3,4,1\}\big\}\cup\big\{\{4\},\{4,1\},\{4,1,2\}\big\} \\ &\phantom{aaaaa}\cup\big\{\{1,3\}\big\}\cup\big\{\{2,4\}\big\}\,.\end{align}$$

We shall prove that $$t_k=l(n,k)=\binom{n}{k}-\binom{n}{k-1}\text{ for every }k=0,1,2,\ldots,\left\lfloor\frac{n}{2}\right\rfloor$$ by induction on $k$. We start with $t_0=1=l(n,0)$. This is trivial because $\emptyset\in\mathcal{P}_n$ has to be in exactly one symmetric chain.

Now, suppose that $k\in\Biggl\{1,2,\ldots,\left\lfloor\frac{n}2\right\rfloor\Biggr\}$ and that $t_j=l(n,j)$ for all $j=0,1,2,\ldots,k-1$. The number of $k$-subsets of $[n]$ that already lie in some $\mathcal{C}_j^s$ with $j<k$ is $$\sum_{j=0}^{k-1}\,t_j=\sum_{j=0}^{k-1}\,l(n,j)=\sum_{j=0}^{k-1}\,\Biggl(\binom{n}{j}-\binom{n}{j-1}\Biggr)=\binom{n}{k-1}\,.$$ Hence, there are exactly $\displaystyle\binom{n}{k}-\binom{n}{k-1}=l(n,k)$ subsets of $[n]$ of size $k$ left. Each of these subsets must belong in exactly one symmetric chain of length $n+1-2k$. Therefore, $$t_k=l(n,k)\,,$$ as desired.

Answer 2

The number of symmetric chains is much higher. You have $n \choose i$ ways to choose $C_i$. Then you choose the $n-2i$ elements that will get added, but you choose them in order, so the total number of chains is $${n \choose i}{n-i \choose n-2i}(n-2i)!$$ For example, if $n=6, i=2$ we have ${6 \choose 2}=15$ ways to choose $C_2$, then $4$ ways to choose the element to add to make $C_3$, and $3$ ways to choose the element to add to make $C_4$, for a total of $15 \cdot 4 \cdot 3=180$. The above formula gives $15 \cdot 6 \cdot 2=180$