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. 



How many sequences of length n satisfy these constraints?
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$.


