Number of subsets from an ordered set where adjacent elements may or may not be tied together Assume we have an ordered set $S$ with a finite number of elements $S=\{1,2,3,\ldots,N\}$. I need to know the number of subsets where adjacent elements from the original set may either be tied together as one "unit" shown with a "-" between them or separate elements shown as "," as normally in a subset.
For instance, with 2 elements, if $S=\{1,2\}$ this number is 5 where the 5 subsets are: $\{\},\{1\},\{2\},\{1,2\}$ and $\{1-2\}$.
And with 3 elements, if $S=\{1,2,3\}$ there are 13 subsets of this kind: $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1-2\}, \{1,3\}, \{2,3\}, \{2-3\}, \{1,2,3\}, \{1-2,3\}, \{1,2-3\}$ and $\{1-2-3\}$.
With 4 elements I have counted this number to be 34. What is this number in the general case of $N$ elements, where $S=\{1,2,3,\ldots,N\}$ and can a formula be given?

Let $a_n$ be the count of these listings for given $n$.
Then $a_n$ is obtained as sum of those listings not ending in $n$ (there are $a_{n-1}$ of these), those ending in "$,n$" (there are $a_{n-1}$ of these), and those anding in "${-}n$" (there are $a_{n-1}-a_{n-2}$ of these).
Hence we have the recursion
$$a_n=3a_{n-1}-a_{n-2}. $$
The general solution to this is 
$$a_n=\alpha_1 \lambda_1^n+\alpha_2\lambda_2^n $$
where $\lambda_{1,2}$ are the roots of $x^2-3x+1=0$. So $\lambda_{1,2}=\frac{3\pm\sqrt{5}}{2}$. We determine $\alpha_{1,2}$ so that the result matches $a_0=1$, $a_1=2$. This leads to $\alpha_{1,2}=\frac{5\pm\sqrt 5}{10}$ so that
$$ a_n=\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt 5}{10}\cdot\left(\frac{3-\sqrt{5}}{2}\right)^n.$$
As the second summand is always between $0$ and $1$, we might as well say
$$ a_n=\left\lceil\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n\right\rceil.$$

Remark. In particular, the formualas above lead to $a_4=34$, not $30$. Indeed, here's the list:
$$\begin{matrix}\{\}&
\{1\}&
\{2\}&
\{1,2\}&
\{1-2\}\\
\{3\}&
\{1,3\}&
\{2,3\}&
\{2-3\}&
\{1,2,3\}\\
\{1-2,3\}&
\{1,2-3\}&
\{1-2-3\}&
\{4\}&
\{1,4\}\\
\{2,4\}&
\{1,2,4\}&
\{1-2,4\}&
\{3,4\}&
\{3-4\}\\
\{1,3,4\}&
\{1,3-4\}&
\{2,3,4\}&
\{2-3,4\}&
\{2,3-4\}\\
\{2-3-4\}&
\{1,2,3,4\}&
\{1-2,3,4\}&
\{1,2-3,4\}&
\{1-2-3,4\}\\
\{1,2,3-4\}&
\{1-2,3-4\}&
\{1,2-3-4\}&
\{1-2-3-4\}& 
\end{matrix}$$
