I want to count the number of unique vectors of length n with the following constraints.

1, each dimension, the values must be a positive integer in the range [1 ~ n]. 2, each adjacent dimension, the absolute value difference must no greater than 1. 3, at least one dimension has the value 1.

The problem is given a vector length n, find a formula f(n) that returns the number of distinct vectors satisfy those 3 constraint.

Any idea?

I want to count the number of unique sequences of length n with the following constraints.

1. Each element of the sequence is an integer in $\lbrace 1,2,\dots,n\rbrace$.
2. Each two adjacent elements of the sequence differ at most by 1.
3. At least one element on the sequence is equal to 1.

The problem is to find a formula f(n) that returns the number of distinct sequences satisfying these 3 constraint.