How many are the permutations of $n$ numbers where the first and last number are $1$, the difference between the numbers is $1$ and the numbers are lesser than h?
For example, for $n = 5$ and $h = 6$ $(h > 4)$ the permutations are $9$:
$ 1-2-3-2-1 $
$ 1-2-2-2-1 $
$ 1-2-2-1-1 $
$ 1-1-2-2-1 $
$ 1-2-1-2-1 $
$ 1-2-1-1-1 $
$ 1-1-2-1-1 $
$ 1-1-1-2-1 $
$ 1-1-1-1-1 $
On
You can think of the sequences you are counting as walks on the graph whose vertices are $\{1,2,\dots,h-1\}$, where two vertices $i$ and $j$ are adjacent when $|i-j|\le 1$, and where the walk starts and ends at $1$. It is well known that the number of walks in a graph is found by examining powers of its adjacency matrix. In this case, the adjacency matrix . Putting this all together, $$ \text{# of sequences with}=(A^{n-1})_{1,1} %\begin{bmatrix} %1&1&0&\dots&&0\\ %1&1&1&0&\dots&0\\ %0&1&1&1&\ddots&\vdots\\ %\vdots&0&1&1&\ddots&0\\ %&\vdots&\ddots&\ddots&1&1\\ %0&0&\dots&0&1 &1 %\end{bmatrix}^n $$ where $A$ is the $(h-1)\times (h-1)$ matrix which has ones on the main diagonal, also just above and below the main diagonal, and zeroes elsewhere. The subscript $1,1$ means the number occurs in the first row and column of that matrix power.
Here is a Wolfram|Alpha computation showing this in action for the case $n=5,h=5$, which is equivalent to the example in your post. Note the first row/column of the result is a $9$, corresponding to the $9$ paths you listed.
These "permutations" are related to Motzkin paths. Compare this picture with your example.