Permutations of numbers with difference 1 that are lesser than h 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 $
 A: These "permutations" are related to Motzkin paths. Compare this picture with your example.

A: 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.
