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.

  • $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Sep 4 '14 at 1:59
  • $\begingroup$ What is "absolute value difference"? $\endgroup$ – Alexey Ustinov Sep 4 '14 at 3:38
  • $\begingroup$ If you write "integer sequences", then the first condition is unnecessary. $\endgroup$ – Christian Stump Sep 4 '14 at 4:25
  • $\begingroup$ it means number of components is n. or the cardinality is n. The absolute value difference is the abs(a-b). $\endgroup$ – Qin Jianbin Sep 4 '14 at 5:30
  • $\begingroup$ The condition 1 is to restrain the maximum value and minimum value. $\endgroup$ – 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$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.