How many different choice of sets? If $S_1$, $S_2$, $\dots$, $S_r$ are r sets, $S_i\subseteq \{1,2,\dots,n\}$. $|S_i|\geq 1$ for all $i$ and $S_i\cap S_{i+1}$=$\emptyset$ for all $1\leq i\leq r-1$. How many different chioce of $S_1,\dots,Sr$ are there?
 A: I have this strong feeling it has to be with Fibonnaci sequence.
As seeing in Morgan O answer, you must solve that expression. Let's see the first two. 
I am gonna call $A_{n,r}$ the numbers. So
$A_{n,1}=2^n-1$, because the only subset you are not allowed to take is $\emptyset$
$$A_{n,2} =\sum_{a_1=1}^{n-1}\binom{n}{a_1}\sum_{a_2=1}^{n-a_1}\binom{n-a_1}{a_2}=\sum_{a_1=1}^{n-1}\binom{n}{a_1}(2^{n-a_1}-1)=3^n-2^n-A_{n,1}$$
$$A_{n,3}=\sum_{a_1=1}^{n-1}\binom{n}{a_1}\sum_{a_2=1}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=1}^{n-a_2}\binom{n-a_2}{a_3}=5^n-3^n-2^nA_{n,1}-A_{n,2}$$
So, the guess might be $A_{n,k}=F_{k+1}^n-F_{k}^n-\sum_{i=1}^{k-1} F_{i}^nA_{n,k-i}$, where $F_i$ is the fibonacci sequence. 
And it does not seems to be very crazy because of the Binomial theorem, when you are solving the expression you are carrying a sequence of two numbers starting by 1,2 and adding them always with a residue(because the index start by 1 and not by 0, as Morgan O pointed out).
A: Fix a sequence $I_1,\dots,I_{r}$ of positive integers. Let's count the number of sequences $S_1,\dots, S_r$ satisfying your conditions, and the additional condition (*) that $|S_i|=I_i$ for all between $1$ and $n-1$. Because we require the sets to be nonempty, and subsequent sets to be disjoint, such a sequence of sets can exist if and only if (a) $1 \leq I_1 \leq n-1$ and (b) $1 \leq I_{i} \leq n-I_{i-1}$ for $i \geq 1$.
With $I_1,\dots, I_r$ still fixed, the number of sequences of sets satisfying (*) will be:
$$\binom{n}{I_1}\binom{n-I_1}{I_2}\cdots \binom{n-I_{r-1}}{I_r} =\binom{n}{I_1}\prod_{j=2}^{r}\binom{n-I_{j-1}}{I_{j}}.$$
To get the total number of set sequences satisfying $S_i \cap S_{i+1}=\emptyset $ with $S_i$ nonempty, sum over all sequences $I_1,\dots,I_r$ satisfying (a) and (b) above. If we follow the convention that $\binom{m}{k}=0$ for $k>m$ or $m<0$, we have the following formula for the number of sets satisfying your conditions:
$$\sum_{I_1=1}^{n-1}\big(\binom{n}{I_1}\sum_{\substack{I_2,\dots,I_r\\I_j\geq 1 \forall j}}\prod_{j=2}^r \binom{n-I_{j-1}}{I_{j}} \big)$$. 
Perhaps this can be simplified, but it's not obvious to me. The formula would be nicer if you allowed empty sets. 
