Number of sequences interpreted with a directed graph. I have a problem with an exercise and no real solution:
Determine for $n\geq 1$ the number $a_n$ of sequences $(S_1,...,S_n)$ of $n$
subsets of the set $\{1,2\}=[2]$, so that $S_1=S_n$ and $S_{i+1}\subseteq S_i$ and $|S_i\backslash S_{i+1}|=1$ or $S_i\subseteq S_{i+1}$ and $|S_{i+1}\backslash S_i|=1$ for all $i\in [n-1]$.
My idea is somehow to identify the sequences with the pathes of an directed graph, but I am not sure how to construct that.
Help is highly appreciated. Many thanks in advance!
 A: If $n$ is even this is clearly impossible.
Let $A_1$ be whatever you want, while $j+1<n$ we can let $A_{j+1}$ be either of the two possible options such that $A_{j+1}\Delta A_j=1$.
When we get to $j+1=n$ then clearly $A_{j+1}$ must be $A_1$, and this will always be possible.
If $A_1$ has only one element then $A_j$ will have $0$ or $2$ elements so we can get to $A_{j+1}=A_n$.
If $A_1$ has $0$ or $2$ elements then $A_j$ will have exactly one element, if $A_1=\varnothing$ then $A_{j+1}$ is just $A_j$ minus that element. and if $A_1=\{0,1\}$ then $A_{j+1}$ is just $A_j$ plus the other element.
Hence the answer is $4\times 2^{n}=2^{n}$ if $n$ is odd and $0$ otherwise. When $n=1$ we get $4$ also, that is the only exception.
A: Moving from $S_i$ to $S_{i + 1}$ you should either include or exclude one of elements 1 and 2. Therefore since $S_1 = S_n$ there should be an even number of “moves” for 1 and an even number of “moves” for 2. This immediately implies that there is no such sequence for odd $n - 1$, i. e. for even $n$. Selecting arbitrary set of even size of moves for 1 can be done in $\frac{2^{n - 1} + [n = 1]}{2}$ ways. Each such way gives a sequence for a fixed $S_1$. Also there are $4$ ways to select $S_1$. So the total answer is
$$[n\text{ is odd}]\cdot 4 \cdot \frac{2^{n - 1} + [n = 1]}{2} = [n\text{ is odd}] \cdot (2^n + 2[n = 1]),$$
where $[P]$ is 1 if $P$ is true and 0 otherwise.
A: There are $4$ possible values for $S_i$ namely $\color{red}{\phi}, \color{blue}{\{1\}} ,  \color{blue}{ \{2\}} , \color{red}{\{1,2\}} $ . Now the first element can be any of these four and there after, the sequence must alternate blue & red ($2$ possiblitities), until the last element which must be the same as the first (and so the length of the sequence must be odd). So $\color{blue}{a_{2n}=0}$ and $\color{red}{a_{2n+1}=2^{2n+1}}$ for $n >1$ and $a_1=4$.
EDIT for Maletisiia :
The number of powers of $2$ are shown below each term (Recall $\color{red}{S_{2n+1}=S_1}$)
\begin{eqnarray*}
\underbrace{\underbrace{\color{red}{S_1}}_{2^2}}_{\color{purple}{2}} \underbrace{\underbrace{\color{blue}{S_2}}_{2^1} \underbrace{\color{red}{S_3}}_{2^1} \cdots \underbrace{\color{blue}{S_{2n}}}_{2^1}}_{\color{purple}{1} \;(2n-1) \;\text{times}} \underbrace{\underbrace{\color{red}{S_1}}_{1}}_{\color{purple}{0}}
\end{eqnarray*}
add these powers of $2$ and we have $\color{purple}{2n+1}$. 
