Let $\mathbb{S} =\{a_1,\ a_2,\ \cdots,\ a_n\}$ be a permutation of $\{1,\ 2,\ \cdots,\ n\}$ which satisfies the condition that for every $a_i$, $(i=1$, $2$, $\cdots$, $n)$, there exists an $a_j$ where $i< j \le n$ such that $a_j=a_i+1$ or $a_j=a_i-1$. Find the number of such $\mathbb{S}$.
Let the desired count be $S_n$.
When $n=1$, the answer is $S_1=1$. When $n=2$, the answer is $S_2=2$.
When $n > 2$, let's consider the value of $a_1$. If $a_1=1$ or $a_1=n$, then the remaining $(n-1)$ elements have $S_{n-1}$ ways all of which satisfy the condition when prefixed with $a_1$.
If $a_1 = k$ which is neither $1$ or $n$, then $(k+1)$ must be placed after $a_1$ because there is no element before $a_1$. Meanwhile, $(k+2)$ must be placed after $(k+1)$ because $(k-1)$ is already placed before $k$. Repeating this process will lead to the conclusion that $a_n > a_1 = k$.
At the same time, $(k-1)$ must be placed after $a_1$ too because there is no element before $a_1$. It follows that $(k-2)$ must be placed after $(k-1)$ because otherwise there will be no element after $(k-1)$ which differs it by just $1$. Repeating this process will yield that $a_n < a_1 = k$. This contradicts to the earlier conclusion. This means that $a_1$ must be either $1$ or $n$ or $$S_n=2S_{n-1}\implies \boxed{S_n=2^{n-1}}$$