El número de posibles secuencias

Question

Deje $(a_1,...,a_{10})$ ser una secuencia con $a_i \in \{1,...,10\}$ y las siguientes propiedades:

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

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

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

Cuántas secuencias con estas propiedades existen? Es posible generalizar esto para cualquier $n$ en lugar de $10$?

He intentado buscar en los diferentes casos para valores de partida: Para $a_1=\{1,10\}$ sólo hay una posible secuencia de cada uno. Para $a_1=\{2,9\}$ hay 9 posibles seuqences cada uno, porque tiene 9 posibilidades para $1$ o $10$ y el resto de las secuencias es clara. Pero para $a_i=\{3,4,5,6,7\}$ no sé cómo ir uno con esa forma de pensar. Alguien puede darme una pista?

Answer 1

Algunos extensa sugerencias:

1. Por inducción tenemos $$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. Usted puede y debe ir hacia abajo exactamente $k:=a_1 - 1$ veces. Por lo tanto, queremos saber en que $k$ índices de ir hacia abajo. Así que, básicamente, nos cuentan los subconjuntos de a $\{1, \dotsc, 9\}$ $k$ elementos (que es bien conocido).

Answer 2

Para el conjunto de $\{1,2,\ldots,n\}$, vamos a $N_k(n)$ el número de posibles secuencias de $(a_1,a_2,\ldots,a_n)$ tal que $a_k=n$. Es fácil ver que

$$\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}$$

Se sigue por la inducción que, por $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}$$

y por lo tanto el número total de posibles secuencias es

$$N_1(n)+N_2(n)+\cdots+N_n(n)=1+1+2+4+\cdots+2^{n-2}=2^{n-1}$$

Answer 3

Deje $N(k)$ el número de maneras de acabar con un $\{a_1,...., a_k\} = \{1,2,...k\}$.

Ahora, si usted tiene $\{a_1,...., a_k\} = \{1,2,...k\}$ $a_k = 1$ o $a_k = k$ (sino $a_1$ puede ser cualquier cosa). Después de todo, usted no puede tener el grupo de $a_i < m$ y un grupo de $a_j > m$ sin algunas de las $a_l = m$.

Ahora el número de maneras en las $\{a_1,....., a_k\} = \{1,2,...k\}$ $a_k = k$ el número de maneras en $\{a_1,..., a_{k-1}\} = \{1,....,k-1\}$ e hay $N(k-1)$ maneras de hacer que

Y el número de maneras en las $\{a_1,....., a_k\} = \{1,2,...k\}$ $a_k = 1$ el número de maneras en $\{a_1,..., a_{k-1}\} = \{2,....,k\}$. Y hay muchas maneras de hacer eso, ya que hay formas de hacer las $b_i = a_i -1$$\{b_1,....,a_{k-1}\} = \{1,....,k-1\}$. Y hay $N(k-1)$ a hacerlo.

Por lo $N(k) = 2N(k-1)$ y $N(1) = 1$ ( $\{a_1\} = \{1\} \iff a_1 =1$ ) inductivamente $N(k) = 2^{k-1}$