Todas las permutaciones de$1,2,...,n$ de modo que cada elemento sea más grande que todos los elementos anteriores o más pequeño que todos los elementos anteriores

Question

Tenemos una secuencia $a_1,a_2,...,a_n$ e $\forall i\in N;~~~ a_i\in\{1,2,3,...,n\}$. Una secuencia es $GOOD$ si tenemos que: Para Cada $k \in N$, tenemos $a_k≥a_i$ por cada $i<k$o $a_k≤a_i$ por cada $i<k$. esto significa que cada elemento es mayor que todos los anteriores elementos o menor que todos los elementos anteriores.

Queremos saber cuántas permutaciones de $1,2,3,...n$ se $GOOD$ ?

Se trataba de una pregunta en un antiguo examen y la respuesta fue, $2^{n-1}$ dijo que en cada elección, podemos poner el más grande o el más pequeño elemento de los números restantes, excepto a la última, tenemos una opción para que la respuesta es $2^{n-1}$. Yo no entiendo completamente esta respuesta. (por ejemplo. si seguimos este algoritmo podría fácilmente llegar al punto en el que no podemos elegir cualquier otro número: $1\to 1, \ n \to ?$ ¿alguien Puede explicar esta respuesta o dar otra respuesta para esta pregunta? Es esta la respuesta correcta?

PS. Cambió la condición para que sea más comprensible.

Answer 1

Pensar sobre la elección de la permutación en orden inverso $a_n,a_{n-1},\dots,a_1$. Cada elemento debe ser más alto o el más pequeño de los elementos no seleccionados previamente, por lo que hay dos opciones para cada uno (excepto para $a_1$, donde el mayor y el menor son los mismos).

Por ejemplo, el último elemento es siempre el $1$ o $n$. Si el último elemento es $1$, luego la segunda a la última es $2$ o $n$. Y así en $\dots$.

Answer 2

Lo que yo creo que la pista está tratando de decir:

Supongamos que nuestra cadena actual es $a_1a_2a_3\cdots a_k$. A continuación, cualquiera de $a_{k+1}$ debe $\max\{a_1, \ldots, a_k\}+1$ o $\min\{a_1, \ldots, a_k\}-1$. Si cualquier otra elección, cualquiera de las $\max\{a_1, \ldots, a_k\}+1$ o $\min\{a_1, \ldots, a_k\}-1$ no será legalmente permitido para ser colocado. Por supuesto, uno debe ser cuidadoso con que cuando alguno de estos valores no existe (es decir, cuando cualquiera de las $1$ o $n$ ya ha sido utilizado). No es claro para mí cómo llenar este hueco.

---

Esto es probablemente el más simple argumento inductivo.

Los casos de Base a $n=2$ son de fácil.

Supongamos que la proposición es verdadera para el caso de $n-1$.

En primer lugar, observe que sólo tenemos dos opción para $a_n$, como siempre debe de ser $1$ o $n$. Si no, entonces ambos $1$ e $n$ aparecen antes de $a_n$ (debido a $n \geq 3$) lo que significa que no puede ser bueno.

Si $a_n = 1$, a continuación, $a_1-1, \cdots a_{n-1}-1$ es una buena secuencia de longitud $n-1$, por lo que hay $2^{n-2}$ opciones para los otros elementos.

Si $a_n = n$, a continuación, $a_1, \cdots a_{n-1}$ es una buena secuencia de longitud $n-1$, por lo que hay $2^{n-2}$ opciones.

En total, hay $2^{n-2} + 2^{n-2} = 2^{n-1}$ opciones.

Answer 3

Tenga en cuenta que los dos primeros elementos de la secuencia deben ser adyacentes entre sí, pero su orden es irrelevante. Así que, dado que una BUENA secuencia $a_1,\ldots,a_n$ de la longitud de la $n$, se pueden generar dos BUENAS secuencias de longitud $n+1$:

$$a_1,a_1+1,b_2,\ldots,b_n$$ y $$a_1+1,a_1,b_2,\ldots,b_n$$

donde $b_i=a_i$ si $a_i<a_1$, e $b_i=a_i+1$ si $a_i>a_1$. Por ejemplo, la secuencia de $23145$ genera $234156$ e $324156$. Así que podemos ver que hay el doble de BUENAS secuencias de longitud $n+1$.

Answer 4

Podemos comprobarlo por una fuerte inducción. Una BUENA secuencia de longitud $n$ con $n$ en la posición $k$ consiste de una BUENA secuencia de los números de $n-k+1$ a $n-1$, seguido por $n$, seguido de los números de $1$ a $n-k$ en orden descendente. Hay una secuencia que se inicia con $n$ y tiene todos los números en orden descendente.

El caso base es $n=1$, donde no se $2^{1-1}=1$ BUENA secuencia. Supongamos que hemos demostrado la existencia de $2^{n-1}$ BUENAS secuencias de $n$ a $m$. A continuación, para $m+1$ tenemos una secuencia que comienza con $m+1$ e $2^{k-2}$ para cada posición $k$ de $2$ través $m+1$ e $$1+\sum_{i=2}^{m+1}2^{i-2}=2^m$$