Hay pingüinos de $k$, $k\ge 3$. Son todos diferentes alturas. ¿De cuántas maneras existen para los pingüinos en una línea, de izquierda a derecha, por lo que no podemos encontrar tres que se arreglan más alto al más corto (de izquierda a derecha orden)? Las triples del pingüino han debe ser adyacente.
Este problema es cortesía de alguien que conoce sólo como "DaMancha."
Bonito problema! Me gustaría ofrecer la combinatoria bijection que he encontrado. No se trata de una rigurosa prueba, pero que debe dar la idea.
Considere la posibilidad de una secuencia $S$ de los pingüinos tal de que no hay tres descendente pingüinos de izquierda a derecha, como se describe anteriormente. Digamos que un pingüino es un líder si es más alto que todos los pingüinos a su izquierda. Una propiedad importante de la secuencia de $S$ es que si un pingüino no es un líder, entonces debe ser más corto que el de todos los pingüinos a su derecha.
Los pingüinos naturalmente se apiñan para el calor hacia la izquierda hacia la más cercana líder; esto organiza en grupos. Por ejemplo, si $S = 31452$, que se encargará de sí mismos,: $$(31)(4)(52)$$ In this notation, the clumps are enclosed in parentheses, and the leaders are the first member of each clump: in this case, $3,4,5$.
Ahora vamos a dibujar los picos y valles de un Catalán de montaña de la gama correspondiente a $S$, como sigue: la altura relativa de cada uno de los líderes con respecto a todos los pingüinos (no sólo los de su grupo) a su derecha determina la altura absoluta de la cima, y el tamaño del grupo determina la profundidad relativa de la siguiente valle por debajo de ese punto.
Por ejemplo, con $(31)(4)(52)$, el primer líder, el 3 es el $3$rd menor de los cinco pingüinos, y está en un grupo de tamaño de $2$. La primera montaña, por tanto, tiene una altura de $3$ y el siguiente valle está a una distancia de $2$ por debajo de ese punto. El próximo líder, 4, es el $2$nd más corta entre el resto de los pingüinos, y está solo en su grupo. Esto indica que la próxima montaña tendrá una altura de $2$, y el siguiente valle va a caer una distancia de $1$. El último líder, 5, es también el $2$nd más corta entre el ahora restantes pingüinos, y está en un grupo de tamaño de $2$, por lo que la última montaña de la altura de la $2$ y el último valle cae una distancia de $2$, como debe ser, de nuevo a nivel del suelo.
He hecho una ilustración mostrando esta correspondencia: los números por encima de las montañas mostrar la altura de los picos y la distancia de los valles por debajo de los picos.
$\hskip2in$
Por cierto, se puede ver que la secuencia de $123 \cdots k$ corresponde a una fila de a $k$ estribaciones de la altura de la $1$, mientras que la secuencia $k123 \cdots (k-1)$ corresponde a uno de los gigantes de la montaña (tal vez la Pica d'Estats?).
Por último, dada una gama de la montaña, es bastante sencillo a la lista fuera de las alturas de los pingüinos; os animo a trabajar en los detalles para usted!
Para mi propio beneficio anoche trabajé a través de un argumento completo demostrando un bijection entre el $321$-evitar las permutaciones de $[n]$ y el Dyck caminos de longitud $2n$. Veo que Théophile ha publicado un encantador dibujo de otro argumento, pero yo lo voy a publicar esto de todos modos, sólo para ser capaz de tener fácil acceso a ella más tarde. Creo que este bijection es esencialmente debido a Krattenthaler.
Deje $\pi=\pi_1\pi_2\dots\pi_n$ ser una permutación de $[n]$. Un número $\pi_k$ es de izquierda a derecha máximo de $\pi$ en la posición $k$ si $\pi_k>\pi_i$$1\le i<k$. Deje $s$ el número de izquierda a derecha maxima; si se producen en las posiciones $k_1<\ldots<k_s$, vamos a $p_\pi=\langle k_1,\dots,k_s\rangle$$m_\pi=\langle\pi_{k_1},\dots,\pi_{k_s}\rangle$. Claramente $\pi_{k_1}<\ldots<\pi_{k_s}=n$, e $k_1=1$. No es difícil ver que $\pi$ $321$- evitar iff la no-maxima se producen en orden creciente de izquierda a derecha. En consecuencia, una $321$-evitar la permutación $\pi$ $n$ está totalmente determinado por $p_\pi$$m_\pi$.
Ejemplo: Si $n=9$, $p_\pi=\langle1,2,5,7\rangle$, y $m_\pi=\langle 2,5,6,9\rangle$, e $\pi$ $321$- evitando, $\pi$ debe tener el esqueleto $25xx6x9xx$, y el resto de los miembros de $[9]$, $1,3,4,7$, y $8$, debe aparecer en ese orden, por lo $\pi$ debe $251364978$.
Desde $k_1$ siempre $1$ $\pi_{k_s}$ siempre $n$, son superfluas. Deje $r=s-1$$i=1,\dots,r$$a_i=\pi_{k_i}$, y deje $a_\pi=\langle a_1,\dots,a_r\rangle$. Será conveniente para cambiar la posición de los números hacia abajo por $1$, por lo que para $i=1,\dots,r$$d_i=k_{i+1}-1$, y deje $d_\pi=\langle d_1,\dots,d_r\rangle$. Tenga en cuenta que $\pi$ es todavía completamente determinado por $n,a_\pi$, e $d_\pi$.
Ejemplo (cont.): Para esta permutación tenemos $a_\pi=\langle2,5,6\rangle$$d_\pi=\langle1,4,6\rangle$.
Ahora voy a mostrar cómo utilizar $a_\pi$ $d_\pi$ a la construcción de un Dyck camino de la longitud de la $2n$. Las secuencias de $a_\pi$ $d_\pi$ son necesariamente aumentando, por lo que puede ser pensado como la secuencia de sumas parciales de positivo secuencias de $\bar a_\pi$$\bar d_\pi$, donde $$\bar a_\pi=\langle a_1,a_2-a_1,a_3-a_2,\dots,a_r-a_{r-1}\rangle=\langle\bar a_1,\dots,\bar a_r\rangle$$ and $$\bar d_\pi=\langle d_1,d_2-d_1,d_3-d_2,\dots,d_r-d_{r-1}\rangle=\langle\bar d_1,\dots,\bar d_r\rangle\;.$$
Los números de $\bar a_i$ $\bar d_i$ es la longitud de la ruta de las subidas y las bajadas, respectivamente, consecutivamente de izquierda a derecha. Que es, el camino comienza con $\bar a_1$ pasos, los cuales son seguidos por $\bar d_1$ pasos, $\bar a_2$ pasos, y así sucesivamente. Esto produce un camino de longitud $a_r+d_r$, que es siempre menor que $2n$, por lo que nos almohadilla con uno más, el pico, que consta de $n-a_r$ hasta los pasos seguidos por $n-d_r$ pasos.
Ejemplo (cont.): Tenemos $\bar a_\pi=\langle 2,3,1\rangle$$\bar d_\pi=\langle 1,3,2\rangle$. Escrito $u$ para un paso y $d$ un paso, tenemos el camino de $uuduuudddudd$. Esto es demasiado corto: $n=9$, por lo que queremos que un Dyck camino de la longitud de la $18$, de modo que la almohadilla con un solo ascenso y descenso, en este caso, cada uno de longitud $3$, para llevarlo a la longitud correcta: $uuduuudddudduuuddd$.
Por supuesto, tenemos que mostrar que este procedimiento está garantizado para producir un Dyck camino, y que cada Dyck camino de la longitud de la $2n$ puede ser obtenido de esta manera.
En orden para $\bar a_\pi$ $\bar d_\pi$ a generar un Dyck ruta, debe ser el caso de que $a_i\ge d_i$$i=1,\dots,r$. Por definición, $\pi_{k_i}$ debe ser el más grande de la $k_{i+1}-1$ números a la izquierda de $\pi_{k_{i+1}}$, por lo que debe ser, al menos,$k_{i+1}-1$, y por lo tanto $a_i=\pi_{k_i}\ge k_{i+1}-1=d_i$, e $\bar a_\pi$ $\bar d_\pi$ generar un Dyck camino.
Por el contrario, considere la posibilidad de un Dyck camino de la longitud de la $2n$ $s$ picos. Claramente $s\le n$. Deje $r=s-1$. Para $i=1,\dots,r$ deje $\bar a_i$ el número de pasos en el $i$-th pico, y deje $\bar d_i$ el número de pasos. Deje $\bar a=\langle\bar a_1,\dots,\bar a_r\rangle$$\bar d=\langle\bar d_1,\dots,\bar d_r\rangle$. Para $i=1,\dots,r$ deje $a_i=\sum_{j=1}^i\bar a_j$$d_i=\sum_{j=1}^i\bar d_j$, y deje $a=\langle a_1,\dots,a_r\rangle$$d=\langle d_1,\dots,d_r\rangle$. Tenga en cuenta que desde que empezamos con un Dyck camino, necesariamente,$a_i\ge d_i$$i=1,\dots,r$.
Queremos construir un $321$-evitar la permutación $\pi$ $[n]$ tal que $a=a_\pi$$d=d_\pi$. Para la construcción de $\pi$, ponemos los números de $a_1,\dots,a_r$, e $n$ en las posiciones $1,d_1+1,\dots,d_r+1$, respectivamente, y rellenar las ranuras restantes con los miembros de $[n]\setminus\{a_1,\dots,a_r,n\}$ dispuestos en orden creciente de izquierda a derecha. Los números de $a_1,\dots,a_r,n$ son distintos, por lo que esta sin duda produce una permutación $\pi$ $[n]$ que $a_\pi=a$$d_\pi=d$; la única pregunta es si $\pi$ $321$- evitar.
La permutación $\pi$ $321$- evitar, si los números de $a_1,\dots,a_r,n$ son de izquierda a derecha maxima. Claramente $n$ es de izquierda a derecha máximo, por lo que considero es uno de los $a_i$: $a_{i+1}$ está en la posición $d_i+1$, lo $a_i$ es de izquierda a derecha máximo iff $a_i\ge\pi_j$$j=1,\dots,d_i$, que por construcción es el caso de la fib $a_i\ge\pi_{d_i}$. La construcción se asegura de que el $\pi_j$ $j=1,\dots,d_i$ $a_1,\dots,a_i$ e las $d_i-i$ más pequeño de los restantes números enteros positivos, por lo $\pi_{d_i}\le d_i\le a_i$, e $\pi$ $321$- evitar.
Esto establece el deseado bijection entre el $321$-evitar las permutaciones de $[n]$ y Dyck, caminos de longitud $2n$. Ya que es bien sabido que hay $C_n$ de este último, donde $C_n$ $n$- th catalán número, se deduce que hay $C_n$ $321$-evitar las permutaciones de $[n]$.
La palabra clave relevante aquí es el patrón de evitar la permutación y esto es en realidad un sorprendentemente gran área de la combinatoria. Este tipo de patrón se denomina 321 y el correspondiente permutaciones son llamados 321-evitar las permutaciones.
Resulta que (xyz)-evitar las permutaciones de $n$ elementos, donde (xyz) es cualquier patrón de longitud $3$, enumerados por el catalán números de $C_n$. Uno puede demostrar que esto ya sea por inducción o por bijecting a otro combinatoria objeto de contado por el catalán números, pero por desgracia he olvidado los detalles de las dos pruebas de...
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
