La combinatoria de pregunta recuento de cuántas maneras de escribir $1,2,...,n$ con un cierto orden

Question

Una secuencia válida es una secuencia de longitud $n$ a partir de los números de $1,2,...,n$ tal forma que:

1) cada número aparece una vez

2) aparte de que el primer número de la secuencia, cada número de $k$ ha $k-1$ o $k+1$ de su izquierda (no necesariamente adyacentes).

Por ejemplo:

las secuencias de $324156$ $546321$ son válidos. La secuencia de $435126$ no (porque no es $2$ en el lado izquierdo de $1$).

Muestran que el número de secuencias válidas de longitud $n$ $2^{n-1}$

Gustaría si alguien me podría dar un consejo. No se la respuesta, sólo una dirección. Traté de resolverlo con la recurrencia de la relación y de la inducción, pero no funcionó.

Answer 1

Propiedad 1) se corresponde con el hecho de que usted está buscando en permutaciones $\pi \in S_n$.

Propiedad 2) los rendimientos que para cualquier segmento inicial de $\{\pi_1,\ldots,\pi_j\}$ donde $j \leq n$, hay algunos enteros $a,b \in \{1,\ldots,n\}$, de tal manera que $\{\pi_1,\ldots,\pi_j\}=[a,b]\cap\mathbb{Z}$. Además para cada $j$, $a$ disminuye o $b$ aumenta.

Vamos a mostrar que la propiedad por inducción:

El caso base es clara, como $\{\pi_1\}=[\pi_1,\pi_1]\cap\mathbb{Z}$. Ahora para $r \rightarrow r+1$ tenemos un par de casos:

Supongamos primero que $\pi_{r+1}=\pi_z+1$ algunos $z \leq r$. Podemos utilizar la hipótesis de inducción en $\{\pi_1,\ldots,\pi_r\}$ conseguir $\{\pi_1,\ldots,\pi_r\}=[a,b]\cap\mathbb{Z}$.

Si $\pi_z$ no es el elemento maximal de a $\{\pi_1,\ldots,\pi_r\}$ $a\leq \pi_z < b$ e lo $\pi_{r+1}=\pi_z+1 \in [a,b]\cap\mathbb{Z}$. Por lo tanto $\{\pi_1,\ldots,\pi_{r+1}\}=[a,b]\cap\mathbb{Z}$. Esta es claramente una contradicción, como ahora $r=|\{\pi_1,\ldots,\pi_r\}|=|[a,b]\cap\mathbb{Z}|=|\{\pi_1,\ldots,\pi_{r+1}\}|=r+1$.

Por otra parte tenemos a $\{\pi_1,\ldots,\pi_{r+1}\}=([a,\pi_z]\cap\mathbb{Z}) \cup(\{\pi_z+1\})=[a,\pi_z+1]\cap\mathbb{Z}$. Por lo tanto $b$ aumenta en este paso.

El caso de $\pi_{r+1}=\pi_z-1$ algunos $z \leq r$ es muy similar. Vamos a ver que $a$ disminuye en ese paso.

Ahora sabemos muy bien cómo las secuencias mira, en realidad son characterizied por el conjunto de índices $J \subseteq \{2,\ldots,n\}$ que nos dice si queremos disminuir la $a$ en que paso [de lo contrario, aumentar el $b$] (esto deja sólo una posibilidad para $\pi_1$, usted debería ser capaz de trabajar de esto).