How many sequences of length n satisfy these constraints? [closed]

Question

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.

Answer 1

I'm assuming "vector of length $n$" means the number of components is $n$. In this case, the answer is $3^{n-1}$. I will create a bijection between vectors ($n$-tuples) of the form described and words of length $n-1$ on an alphabet of three symbols.

Suppose given a vector $v = (a_1, \ldots, a_n)$ satisfying the three conditions, and consider the sequence $$D(v) = (a_2 - a_1, a_3 - a_2, \ldots, a_n - a_{n-1}).$$ By condition (2), D(v) has all entries equal to 0 or $\pm 1$. Conversely, given a sequence d, the condition $$D(v) = d$$ determines $v$ up to addition of a vector of the form $(a, a, \ldots, a)$. But conditions (1) and (3) exactly state that the minimum component of $v$ must equal $1$; so $D(v)$ uniquely determines $v$.

Thus, $$v \mapsto D(v)$$ is a bijection from the set of vectors we wish to count to the set of $(n-1)$-tuples with each entry $0$ or $\pm 1$.