Let $(a_1,...,a_{10})$ be a sequence with $a_i \in \{1,...,10\}$ and the following properties:

$i)$ $a_1\in\{1,...,10\}$

$ii)$ $a_i\neq a_j \ \forall i,j\in \{1,...,10\}$ with $i\neq j$

$iii)$ $a_i\in \{a_1\pm 1,...,a_{i-1}\pm1\}\cap\{1,...,10\} \quad \forall i\in \{2,...,10\}$

How many sequences with these properties exist? Is it possible to generalize this for any $n$ instead of $10$?

I tried looking at the different cases for starting values: For $a_1=\{1,10\}$ there is only one possible sequence each. For $a_1=\{2,9\}$ there are 9 possible seuqences each, because you have 9 possibilities for $1$ or $10$ and the rest of the sequences is clear. But for $a_i=\{3,4,5,6,7\}$ I don't know how to go one with that way of thinking. Can someone give me a hint?

  • $\begingroup$ Is it mod arithmetic; i.e., if $a_i$ is 1 is $a_{i+1}$ allowed to be 10, and if $a_i$ is 10, can $a_{i+1}$ be 1? $\endgroup$ – Mike Apr 18 '18 at 18:09
  • $\begingroup$ No, that is not the case. $\endgroup$ – Tobi92sr Apr 18 '18 at 18:16
  • $\begingroup$ Isn't condition i) redundant? $\endgroup$ – user251257 Apr 18 '18 at 18:17
  • $\begingroup$ I think i) is saying $a_1$ has no restrictions on choice. ii) any following a_i is restricted in that it must be distinct from any of the previous iii) when combined with ii) says that all $a_1... a_k$ will be a block of consecutive letters and $a_{k+1}$ will be either be one less than the minimum or one more than the max. $\endgroup$ – fleablood Apr 18 '18 at 21:29

Some extensive hints:

  1. By induction we have $$A_i := \{ a_1, \dotsc, a_i \} = \{ \min A_i, \min A_i + 1, \dotsc, \max A_i \}.$$ Thus, $a_{i+1} = \min A_i - 1$ or $\max A_i + 1$.

  2. You can and must go down exactly $k:=a_1 - 1$ times. Thus, we want to know at which $k$ indices we go down. So basically we count the subsets of $\{1, \dotsc, 9\}$ with $k$ elements (which is well-known).


For the set $\{1,2,\ldots,n\}$, let $N_k(n)$ be the number of allowable sequences $(a_1,a_2,\ldots,a_n)$ such that $a_k=n$. It is easy to see that

$$\begin{align} N_1(n+1)&=N_1(n)\\ N_2(n+1)&=N_1(n)\\ N_3(n+1)&=N_1(n)+N_2(n)\\ N_4(n+1)&=N_1(n)+N_2(n)+N_3(n)\\ &\,\,\vdots\\ N_{n+1}(n+1)&=N_1(n)+N_2(n)+\cdots+N_n(n) \end{align}$$

It follows by induction that, for $n\ge2$,

$$\begin{align} N_1(n)=N_2(n)&=1\\ N_3(n)=1+1&=2\\ N_4(n)=1+1+2&=4\\ &\,\,\vdots\\ N_n(n)=1+1+2+4+\cdots+2^{n-3}&=2^{n-2} \end{align}$$

and thus the total number of allowable sequences is



Let $N(k)$ be the numbers of ways to end up with a $\{a_1,...., a_k\} = \{1,2,...k\}$.

Now if you have $\{a_1,...., a_k\} = \{1,2,...k\}$ then $a_k = 1$ or $a_k = k$ (but $a_1$ may be anything). After all, you can't have group of $a_i < m$ and a group of $a_j > m$ without some $a_l = m$.

Now the numbers of ways $\{a_1,....., a_k\} = \{1,2,...k\}$ and $a_k = k$ are the number of ways $\{a_1,..., a_{k-1}\} = \{1,....,k-1\}$ and there are $N(k-1)$ ways to do that

And the numbers of ways $\{a_1,....., a_k\} = \{1,2,...k\}$ and $a_k = 1$ are the number of ways $\{a_1,..., a_{k-1}\} = \{2,....,k\}$. And there are as many ways to do that as there are ways to do $b_i = a_i -1$ so $\{b_1,....,a_{k-1}\} = \{1,....,k-1\}$. And there are $N(k-1)$ to do that.

So $N(k) = 2N(k-1)$ and as $N(1) = 1$ (as $\{a_1\} = \{1\} \iff a_1 =1$) inductively $N(k) = 2^{k-1}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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