Problem

Source: India Postal Coaching 2014 Set 6 Problem 3

Tags: parameterization, combinatorics unsolved, combinatorics



Fix positive integers $k$ and $n$.Derive a simple expression involving Fibonacci numbers for the number of sequences $(T_1,T_2,\ldots,T_k)$ of subsets $T_i$ of $[n]$ such that $T_1\subseteq T_2\supseteq T_3\subseteq T_4\supseteq\ldots$. Moderator says: and the original source for this one is Richard Stanley, Enumerative Combinatorics vol. 1 (1st edition), exercise 1.15.