El número de permutaciones de $\{1,2,\ldots,n\}$ que tienen exactamente una subida (subida).

Question

Sloane del OEIS A000295 cuenta el número de $n$-permutaciones con exactamente un ascenso. Por ejemplo, $a(3)=4$ porque tenemos: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ donde he marcado el único ascenso con $\wedge$.

La misma secuencia también cuenta el número de longitud de $n$ binario palabras que contienen al menos dos $1$'s. Por ejemplo, $a(3)=4$ ya tenemos: $011, 101, 110, 111.$

Hay una simple bijection entre estas dos clases?

La fórmula para la secuencia es $a(n) = 2^n - n - 1$. Veo cómo se cuenta el número de binario palabras. Hay una combinatoria derivación de esta fórmula lo que demuestra que lo que cuenta es el número de n-permutaciones?

Tanto la exponencial y ordinaria funciones de generación de la secuencia dada. De nuevo, entiendo que sus simbólico de derivación para la enumeración de tales binario palabras, pero puede que estas funciones se derivan simbólicamente teniendo en cuenta la estructura de tales n-permutaciones?

Answer 1

Deje $f(n,k)$ contar el número de permutaciones en $S_n$ con exactamente $k-1$ ascensiones. Yo reclamo que $$\tag 1 f(n,k)=(n-k+1) f(n-1,k-1)+k f(n-1,k)$$

Si podemos demostrar esto, poniendo a $k=2$ da $f(n,2)=n-1+2 f(n-1,2)$, es decir, si $x_n$ indica el número de permutaciones de $n$ con exactamente un ascenso, $x_n-2x_{n-1}=n-1$. Entonces, esto puede ser usado para demostrar la fórmula de decir por inducción, o mediante el uso de funciones de generación. Se que vamos a intentar demostrar $(1)$.

Supongamos que tenemos una permutación de $n-1$ letras con $k-1$ ascensiones. El de la imagen como $k$ monotono bloques de $B_1,\ldots,B_k$. A continuación, podemos introducir $n$ exactamente $k$ formas tales que no ascenso, se añade, a saber, en primer lugar en cada una de las $k$ bloques. Ahora supongamos que tenemos una permutación de $n-1$ letras con $k-2$ ascensiones. A continuación, podemos introducir $n$ $n-k+1$ formas de agregar exactamente un ascenso, es decir, después de cualquier elemento de cada una de las $k-1$ bloques que no es el elemento protagonista.

En el primer caso, estamos en la obtención de una permutación en $S_n$ donde $n$ se coloca en la cadena de $\dots a_i n a_{i+1}\dots$$a_i<a_{i+1}$. En el segundo caso, estamos obteniendo una permutación donde $n$ se coloca en la cadena de $\dots a_i na_{i+1}\dots$$a_i > a_{i+1}$. Estos son los dos únicos casos posibles que nos enfrentamos cuando se mira en una permutación, el anterior simplemente se observa estamos dividiendo $S_n$ en los dos casos, tomando nota de cada fibra en la surjection tiene exactamente $k$ o $n-k+1$ elementos, lo que demuestra la demanda.

Answer 2

Utilizamos el hecho de que podemos obtener la misma relación de recurrencia $a(n) = a(n-1) + 2^{n-1} - 1$ para ambos casos.

• En el caso de las permutaciones, de esta de la siguiente manera:

Si n es el primer elemento de la permutación, debe haber exactamente una ascensión entre otros. Esto nos da la una(n-1) plazo.

Si n no es el primer elemento, a continuación, el elemento antes de que esto es menos de lo que es. Lo que en sí añade un ascenso. Así que no debe haber ninguna otra ascenso. Si fijamos que los elementos de venir antes de n y los que vengan después, su orden es fijo (cada uno de estos grupos debe ser en orden decreciente). Así que para cada uno de los otros (n-1) elementos, podemos elegir de qué lado de la n es, dándole $2^{n-1}$ a la cuenta. Tenemos que excluir el caso en que todos ellos vienen después, porque ya hemos dicho que n no es el primer elemento.

• En el caso de los binarios de palabras, de esta de la siguiente manera:

Si el primer elemento es 0, entonces los otros debe tener al menos dos. Esto le da a la una(n-1) plazo.

Si el primer elemento es 1, entonces los otros puede ser cualquier cosa, excepto para la cadena con todos los ceros.

Ahora, podemos usar la forma similar de obtener la relación de recurrencia para obtener un bijection.

Para llegar desde binario palabras a las permutaciones, hacer esto:

• si la primera letra es 0, entonces en la permutación que el primer elemento es n. Ahora de forma recursiva bajar a la (n-1) caso.

• si la primera letra es 1, entonces para cada una de las otras cartas, si $a_i$ es 1, entonces (i-1) antes de n en la permutación. Otra cosa (i-1) viene después de n en la permutación. Dada esta partición, la permutación es bien definido.

Podemos ver fácilmente cómo invertir el este.

Permítanme dar un ejemplo para esto:

Supongamos que voy a empezar con la cadena binaria 011010. Esto corresspond 6-elemento de permutación. Vamos a encontrar.

La primera letra es 0, por lo que en la permutación de la primera carta es 6.

Siguiente carta es de 1. Así que la permutación de {1, 2, 3, 4, 5} que sigue 6 se encuentra de la siguiente manera.

Considere la posibilidad de la cadena de 1010. Esto significa que: 1 llegará antes de las 5 2 es después de las 5 3 es antes de las 5 4 es después de las 5

Así que la permutación de {1, 2, 3, 4, 5} es {3, 1, 5, 4, 2}. Añadir 6 en el principio de conseguir {6, 3, 1, 5, 4, 2}

Answer 3

Imagínese tratando de construir una permutación de longitud n que tiene exactamente un ascenso. Si el conjunto de los números antes de la ascensión punto a y el conjunto de los números después de la ascensión punto B, el orden en el que tenemos que colocar los elementos de a y B en la permutación es único. Por lo tanto, la permutación puede ser identificado de forma única mediante una subdivisión de n en 2 conjuntos a y B.

(Acabamos de elegir un subconjunto de {1, ..., n}, dar B el resto, anote los elementos de Una en orden descendente y, a continuación, escribir los elementos de B en en orden descendente).

Sin embargo, no todas esas divisiones puede conducir a una válida de permutación. Si todos los elementos de a son mayores que todos los elementos de B, la permutación construido de esta manera no tendrá un ascenso. Hay n+1 maneras de elegir una A. (Porque significa la elección de Un = {k, k+1, k+2, ..., n}) (Incluyendo los casos en los que Una está vacía o B está vacío.)

Answer 4

Permutaciones como palabras, una permutación con exactamente una subida es la concatenación de dos secuencias decrecientes con cada símbolo en $[n] = \{1,2,\ldots,n\}$ ocurrir exactamente una vez. Llamar a estos conjuntos de elementos en estas secuencias $A$ y $B$.

Para cada permutación, construir una cadena binaria $x$ tal que iff de $x_1 = 1$$1 \in A$y $2,\ldots,n$, $x_i = 1$ iff $i-1$y $i$ están en grupos diferentes.

EDICIÓN: Debe ser $1 \in A$, no $1 \in B$.