In a partition of the subsets of $\{1,2,…,n\}$ into symmetric chains, how many chains have only $k$ subset in them?
For a chain $A_1\subseteq A_2\subseteq …A_l$ in the partition, we have $|A_1|+|A_l|=n$ and $|A_i|+1=|A_{i+1}|$.
I tried to solve it using recursive rule like $(n,k)=(n-1,k-1)+(n-1,k+1)$, and got $(n,k)=\sum_{i=0}^{n-1}{n-1 \choose i}(1,k-(n-1)+2i)$. However, my solution gets wrong result in some case since it doesn't consider about the $(1,2)$'s under $(x,0)$ in the binary tree.
I've got a solution from classmates (as shown in the picture) but we don't understand where does $2|A_1|+l-1=n$ come from (Thanks to phichar, now we know).
But I'm not sure how can we make sure the subset of size (n floor(n/2)) and (n ceil(n/2)) always appear together(Ohh because of the symmetric, I'm an idiot)?
Any idea about the problem? Thanks!
Best Answer
Notice that $A_{\ell}$ contains inside $A_1$ and every step that you take, i.e., $\ell -1,$ you are adding a new element hence $|A_{\ell}|=|A_1|+\ell -1$ so if you add in both sides, you get $$|A_1|+|A_{\ell}|=2|A_1|+\ell-1$$