How to count the $r$-tuples of subsets of $\{1,\dots,n\}$ that are cyclically disjoint? I want to count the following,
$$\#\{S_1,S_2,\dots, S_r\subseteq[n]\;|\;  S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1 \mbox{ and } S_1\cap S_r=\emptyset\}=A_{n,r},$$
Then $A_{n,1}=2^n$,
$$A_{n,2} =\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}=\sum_{a_1=0}^{n}\binom{n}{a_1}2^{n-a_1}=3^n$$
\begin{align*}
A_{n,3} &=\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=0}^{n-a_2-a_1}\binom{n-a_2-a_1}{a_3}\\
        &=\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}2^{n-a_2-a_1}\\
        &=\sum_{a_1=0}^{n}\binom{n}{a_1}3^{n-a_1}\\
        &=4^n.
 \end{align*}
when counting $A_{n,4}$, the problem comes, I cannot do it like following,
$$A_{n,4} =\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=0}^{n-a_2}\binom{n-a_2}{a_3}\sum_{a_4=0}^{n-a_3-a_1}\binom{n-a_3-a_1}{a_4}$$
instead, for the last term, I need to choose $a_4$ from n- union of $a_1$ and $a_3$
How can I do it? or is there any other method to do it?
 A: The pattern is obvious! $A_{n,4}=7^n$. 
Well, maybe not totally obvious, but here is a proof is by induction.
First, $A_{1,4}=7$ is verified by listing out the possibilities: $(\emptyset,\emptyset,\emptyset,\emptyset),(1,\emptyset,\emptyset,\emptyset),(\emptyset,1,\emptyset,\emptyset),(\emptyset,\emptyset,1,\emptyset),(\emptyset,\emptyset,\emptyset,1),(1,\emptyset,1,\emptyset),(\emptyset,1,\emptyset,1)$
Let $$\mathcal{A}_{n,4}=\{S_1,S_2,S_3,S_4\subseteq[n]\;|\;  S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq 3 \mbox{ and } S_1\cap S_4=\emptyset\},$$ and assume that $A_{n-1,4}=7^{n-1}$.
Let $(S_1,\ldots,S_4)\in \mathcal{A}_{n,4}$. Then deleting $n$ from each $S_i$ gives an element of $\mathcal{A}_{n-1,4}$. Conversely, from a fixed $(S_1,\ldots,S_4)\in \mathcal{A}_{n-1,4}$ we can form an element of $A_{n,4}$ by inserting $n$ into the $S_i$'s. We can:


*

*Insert zero $n$'s in one way.

*Insert one $n$ in $4$ ways.

*Insert two $n$'s in $2$ ways.

*Insert three or four $n$'s in $0$ ways.


So for each $(S_1,\ldots,S_4)\in\mathcal{A}_{n-1,4}$ we can form $7$ elements of $\mathcal{A}_{n,4}$, and each element of $\mathcal{A}_{n,4}$ arises exactly once with this construction. Thus $A_{n,4}=7A_{n-1,4}=7(7^{n-1})=7^n$.
A: Let $B_k$ be the number of subsets of $\mathbb{Z}_n$ that have no consecutive numbers.  As Casteels noted, $A_{n,k}={B_k}^{n}$.
To form a recursion in $k$, I look at subsets of $\{1,\ldots, k\}$, that lack consecutive numbers, and worry about the neighbours $1$ and $k$ later.


*

*Let $C_k$ be the number of these subsets that include both $1$ and $k$.

*Let $D_k$ be the number of these subsets that include $1$ but not $k$.

*Let $E_k$ be the number of these subsets that include $k$ but not $1$.

*Let $F_k$ be the number of these subsets that include neither $1$ nor $k$.


Then we can't have both $1$ and $k$, so $B_k=D_k+E_k+F_k$.
The following recursions happen because we can't have both $k$ and $k+1$:
$$\begin{align}C_{k+1}&=&D_k\\
D_{k+1}&=&C_k+D_k&=&D_{k-1}+D_k\\
E_{k+1}&=&F_k\\
F_{k+1}&=&E_k+F_k&=&F_{k-1}+F_k
\end{align}$$
So they are all Fibonacci-type numbers.  $B_{k+1}=B_k+B_{k-1}$.  ($B_1=2$ might be a special case.)  Other than that, I think they will be 'Lucas numbers'. 
That is, 3,4,7,11,18,29,...
