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.
Problem
Source: India Postal Coaching 2014 Set 6 Problem 3
Tags: parameterization, combinatorics unsolved, combinatorics
NoYoo-hooForMe
09.12.2014 21:24
hajimbrak wrote: 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.
I'm not 100% sure what $[n]$ means here--I've never seen the square bracket notation with a single parameter to mean anything other than greatest integer--a definition that doesn't seem to fit here. But let's assume that $[n]$ means the only thing it would seem it reasonably could mean here: $[n]=\{1,2,3,...,n\}$. Perhaps someone can confirm that this understanding is correct. Then we start by consider $n=1$ in which case there are only two possible subsets of $\{1\}$: $\emptyset$ and $\{1\}$.
For $n=1$ we let $U_k$ be the number of sequences ending in $\{1\}$ and $L_k$ be the number of sequences ending in $\emptyset$. Consider $k=2j-1$ for some positive integer $j$. Consider a sequence $S$ of length $2j-1$ and consider how it might be possible to extend $S$ to a sequence of length $2j+1$.
If $S$ ends in $\emptyset$, it may be extended in three ways: $\{1\},\{1\}$ or $\{1\},\emptyset$ or $\emptyset,\emptyset$.
If $S$ ends in $\{1\}$, it may be extended in two ways: $\{1\},\{1\}$ or $\{1\},\emptyset$.
From this the following identities follow:
$U_{2j}=U_{2j-1}+L_{2j-1}$
$L_{2j}=L_{2j-1}$
$U_{2j+1}=U_{2j-1}+L_{2j-1}$
$L_{2j+1}=U_{2j-1}+2L_{2j-1}=U_{2j+1}+L_{2j-1}$
Focusing on just the last two identities for now, let's consider the following sequence:
$U_1,L_1,U_3,L_3,U_5,L_5,U_7,L_7,U_9,L_9,...$
From the last two identities, each element in this sequence is the sum of the previous two elements. Moreover $U_1=1=F_1$ and $L_1=1=F_2$ where $F_i$ denotes the $i$th Fibonacci number. Thus the sequence is just the Fibonacci sequence and:
$U_{2j+1}=F_{2j+1}$
$L_{2j+1}=F_{2j+2}$
Thus the total number of sequences of length $2j+1$ is given by $U_{2j+1}+L_{2j+1}=F_{2j+1}+F_{2j+2}=F_{2j+3}$.
Likewise:
$U_{2j}=U_{2j-1}+L_{2j-1}=F_{2j-1}+F_{2j}=F_{2j+1}$
$L_{2j}=L_{2j-1}=F_{2j}$
Thus the total number of sequences of length $2j$ is given by $U_{2j}+L_{2j}=F_{2j+1}+F_{2j}=F_{2j+2}$.
So regardless of whether $k$ is even or odd the number of sequences of length $k$ for $n=1$ is given by $F_{k+2}$. Considering the case where $n>1$ is then easy. Assignment of each of the $n$ integers $1,2,3,...,n$ to $(T_1,T_2,\ldots,T_k)$ may be done independently giving a total number of sequences matching the problem conditions of $F_{k+2}^n$.
JBL
09.12.2014 22:14
NoYoo-hooForMe wrote: $[n]=\{1,2,3,...,n\}$. Perhaps someone can confirm that this understanding is correct Yes, this is a fairly standard use in combinatorics. And of course your solution is correct.