Por favor, dar una combinatoria prueba de lo siguiente:
El número de pares de $(A, B)$ de las permutaciones del conjunto $\{ 1, 2,\ldots,n \}$, que tienen un total de $n+1$ ciclos y su composición $AB$ es la permutación $(123 \ldots n)$, es el $n$th catalán número.
Tomar un avión árbol con $n+1$ vértices, tomar un desdoblamiento y asociar a cada vértice de la permutación cíclica que los cambios de los bordes adyacentes de forma cíclica.
Los productos de los ciclos de cada desdoblamiento dar las dos permutaciones.
Esta es una restricción de un bijection por Cori para planas de los mapas.
El producto deseado $(123\ldots n)$ aumenta el $n-1$ elementos y se reduce sólo a uno. El número de elementos aumenta es en la mayoría de la suma de los números de elementos aumenta por cada factor. Cada una de las $k$-ciclo de una permutación aumenta en la mayoría de las $k-1$ elementos. La suma de las longitudes de todos los ciclos en $A$ $B$ juntos es $2n$. Desde allí se $n+1$ ciclos en total, en la mayoría de las $2n-(n+1)=n-1$ elementos puede ser mayor. Ya que queremos aumentar el $n-1$ elementos, el $k$-ciclos en $A$ $B$ cada incremento $k-1$ elementos, es decir, deben cíclicamente permutar los elementos de su órbita. Por lo tanto, cada partición de $\{ 1, 2,\ldots,n \}$ de los rendimientos en la mayoría de los que uno de los candidatos para $B$, es decir, la permutación que cíclicamente permutes cada uno de los bloques de la partición.
Sin embargo, no todos estos candidatos son adecuados. De hecho, precisamente las permutaciones que cíclicamente permutar cada bloque de un noncrossing partición son adecuados. Para ver esto, consideremos, en primer lugar, la representación de una permutación $B$ (en rojo) junto con el correspondiente factor de $A=(123\ldots n)B^{-1}$ (en verde):
Los puntos fijos son los que no se muestran. Tenga en cuenta que todos los ciclos de ejecución de las agujas del reloj como se debe. Un noncrossing partición con $k$ bloques (correspondiente a una permutación $B$ $k$ de los ciclos) particiones el círculo en $n-k+1$ a las regiones fuera de los bloques: Hay una región, para empezar, y cada una de las $k$-ciclo divide una región en $k$ piezas. Como se puede convencer a sí mismo de la ilustración, el factor de $A$, que se tiene que mover cada elemento para el sucesor de su preimagen en $B$, contiene un ciclo para cada región fuera de los bloques de $B$. Así, el número total de ciclos en $A$ $B$ $k+(n-k+1)=n+1$ como se requiere. Tenga en cuenta que $A$ también cíclicamente permutes cada bloque de un noncrossing partición.
Ahora considere esta representación de una permutación $B$ que cíclicamente permutes cada bloque de un cruce de la partición (en rojo), de nuevo junto con el correspondiente factor de $A=(123\ldots n)B^{-1}$ (en verde):
Tenga en cuenta que ahora las flechas de $A$ no formulario de la izquierda ciclos. A ver que ellos no pueden, tomar cualquier flecha $r$ $B$ que se cruza con otra flecha de $B$, dicen, $5\to0$, y encontrar la flecha $s$ que cruza el más cercano a su origen, en este caso $2\to8$. Visto a lo largo de $r$, $s$ debe ir a la izquierda, ya que es parte de un sentido de las agujas del ciclo. (Si es parte de una $2$-ciclo, se puede recoger la flecha que va hacia la izquierda.) Ahora tome la flecha $t$ $A$ que obtiene el compuesto con $s$, en este caso $8\to3$. Cruza $r$ más cerca del origen de $r$ $s$ hace, o que puede terminar en el origen de $r$ (en este caso $5$). Cualquier sentido de las agujas del ciclo de $A$ contiene $t$ tendría que incluir una flecha $u$ $A$ que cualquiera de las cruces $r$ aún más cerca de su origen, o que empieza en el origen de $r$. Luego en la flecha de $B$ que obtiene el compuesto con $u$ entre $r$ aún más cerca de su origen, lo cual es imposible, por supuesto, o extremo en el origen de $r$. Esto último no es posible también porque esta flecha se viene desde el lado equivocado de la $r$ para formar un sentido de las agujas del ciclo de con $r$.
En resumen, los posibles valores de $B$ son precisamente las permutaciones que cíclicamente permutar cada bloque de un noncrossing partición de $\{1,\dotsc,n\}$. Es bien conocido para los que saben que el noncrossing particiones de $\{1,\dotsc,n\}$ son contados por los números de catalán; un bijection con Dyck caminos se exhibe aquí (sección 3, página 5).
El catalán número, $C_n$, es el número de arraigada árboles binarios con $n+1$ hojas (y, por tanto, $n$ no se va). Etiqueta de la raíz $1$ y el otro no se va con los valores de$2$$n$. Deje $\mathcal{T}$ ser el conjunto de la etiqueta árboles binarios. Hay $C_n$ maneras de escoger el árbol y $(n-1)!$ diferentes etiquetados, por lo $|\mathcal{T}|=(n-1)!C_n$.
Por permutación $A$, vamos a $c(A)$ el número de ciclos en $A$. Deje $\mathcal{P}$ el conjunto de pares ordenados de permutaciones $(A,B)$ $\{1,2,...,n\}$ tal que $c(A)+c(B)=n+1$ $AB$ $n$- ciclo. El número de elementos en $\mathcal{P}$ $(n-1)!$ multiplicado por el número de $(A,B)$$AB=(123...n)$.
Queremos encontrar una correspondencia 1-1 entre el$\mathcal{T}$$\mathcal{P}$.
Dado un árbol binario T, romper el árbol a la izquierda-sala de flechas, y convertir cada flecha en un ciclo de $A$. Luego romper el árbol en derecho-sala de flechas, y hacer $B$.
Cada hoja del árbol es un "terminal" de exactamente una de las flechas, de manera que los ciclos de $A$ $B$ agregar el número de hojas, que es $n+1$.
Por ejemplo, con $n=4$ si $3$ es el hijo de izquierda $1$, $2$ el derecho del niño de $1$, e $4$ la izquierda hijo de $2$, entonces obtenemos $A=(13)(24)$, e $B=(12)(3)(4)$.
Usted puede demostrar que el producto $AB$ $n$- ciclo por recursión, señalando que $1(AB)^r$ paseos primero un lado del árbol, luego el otro.
Un par de $(A,B)$ no puede resultar de dos diferentes etiquetados árboles, ya que el par $(A,B)$ codifica el árbol, dado que la raíz es $1$. Esencialmente, se construye un grafo dirigido $G$ $n$ nodos con bordes $(k,kA)$ color $L$ y los bordes $(k,kB)$ color $R$. Ahora, si $(A,B)$ resultó de un árbol de $T$, $G$ es equivalente a $T-\{\text{leaves}\} $ mediante la eliminación de la orilla $(k,kA)$ si la distancia en $G$ $1$ $k$es mayor que o igual a la distancia de$1$$kA$. Así, podemos ver que los diferentes etiquetados árboles de rendimiento diferentes pares de $(A,B)$.
Estoy seguro de cómo hacerlo de la siguiente parte.
Por último, tenemos que demostrar que esto es en. Dado un par de $(A,B)\in \mathcal{P}$, debemos mostrar cómo obtener la correspondiente etiqueta de árbol. Ciertamente no puede lastimar para que se inició con el gráfico de $G$ que hemos definido anteriormente. A continuación, necesitamos utilizar el hecho de que $AB$ $n$- ciclo a demostrar que nos puede quitar el $n+1$ bordes para obtener un árbol binario hunde sus raíces en la $1$. Para ello, cada arista eliminada tendría que ser de un ciclo diferente de $A$ o $B$, ya que un árbol no puede tener un ciclo. También tendríamos que quitar los dos bordes en $1$ y un borde en cada uno de los otros nodos de $2,...,n$, de lo contrario el resultado en forma de grafo dirigido no es un árbol binario.
Mi conjetura es que primero quite los dos bordes en $1$, para luego determinar borde para quitar entrar en el nodo $1(AB)^{k+1}$ recursivamente basado en los bordes restantes en esa etapa. Este, a continuación, elimina el requisito de $n+1$ bordes. Cómo definir el paso recursivo no es todavía evidente.
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.
