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

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.

• Does "vector of length $n$" mean square root of the sum of the squares of the components is $n$? or does it mean the number of components is $n$? – Gerry Myerson Sep 4 '14 at 1:59
• What is "absolute value difference"? – Alexey Ustinov Sep 4 '14 at 3:38
• If you write "integer sequences", then the first condition is unnecessary. – Christian Stump Sep 4 '14 at 4:25
• it means number of components is n. or the cardinality is n. The absolute value difference is the abs(a-b). – Qin Jianbin Sep 4 '14 at 5:30
• The condition 1 is to restrain the maximum value and minimum value. – Qin Jianbin Sep 4 '14 at 5:32

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$.