Yo por desgracia se quedó atascada, pero estoy saliendo de mi trabajo aquí de todos modos en caso de que esto ayude a alguien más. Feliz eliminar esta si la comunidad siente que no es digno de ser una respuesta.
Su primer enlace hace referencia a un libro que proporciona un bijection entre los dos siguientes sets.
- desordenada arraigada árboles binarios con $n+1$ etiquetado hojas
- elecciones de $\{1,\ldots,2n\}$
Tenga en cuenta que un árbol binario con $n+1$ hojas se han $2n$ no de los nodos raíz, lo que sugiere que la anterior bijection consiste en el etiquetado de la no-nodos raíz de un árbol. De hecho, esto es lo que el libro describe.
Voy a aplazar los detalles del libro, pero aproximadamente el bijection es como sigue. Tome un árbol binario con $n+1$ etiquetado de las hojas. Vamos a la etiqueta el resto de los que no son root nodos con $n+2,\ldots,2n$, de la siguiente manera.
- Considerar todos sin etiqueta no-nodos raíz, cuyos dos hijos son etiquetados, y la etiqueta como $n+2$ el que tiene un hijo con el más pequeño de la etiqueta.
- Repita este procedimiento y la etiqueta de la siguiente nodo como $n+3$, y así sucesivamente.
Luego de convertir estos nodos etiquetados para una coincidencia en $\{1, \ldots, 2n\}$, acaba de tomar cada par de hermanos de los nodos etiquetas como un par en su coincidencia.
Aquí está un ejemplo del libro, al $n=6$. Trate de comenzar con sólo el $7$ deja la etiqueta y, a continuación, completar el etiquetado para el resto de los no-nodos raíz.
![enter image description here]()
Tenga en cuenta que uno necesita para comprobar que se trata de un bijection; no voy a hacerlo aquí.
Ahora, vamos a considerar tu pregunta original, que pide un bijection entre los dos siguientes sets.
- desordenada arraigada árboles binarios con $n+1$ etiquetado de las hojas, y la hoja de "$1$" a distancia $k$ desde la raíz
- elecciones de $\{1, \ldots, 2n\}$ $k$ terminal closers
Desafortunadamente, lo anterior bijection no resolver inmediatamente el problema. Por ejemplo, la coincidencia de $(1,2),(3,4),(5,6)$ tiene una terminal cercana, pero en el árbol correspondiente, otorgado por la bijection, hoja de $1$ es la distancia a $2$ desde la raíz.
Por lo tanto, yo sospechaba que uno puede encontrar algunos intermedio bijection que, cuando se combina con el árbol de coincidencia de bijection descrito anteriormente, va a producir su deseado bijection de estos dos últimos sets. Pero era fracasado en encontrar uno que trabajó.
Algunos comentarios finales y posibles bijection bloques de construcción:
- Uno puede considerar $k$ inicial de abridores, en lugar de $k$ terminal closers
- Uno puede considerar la profundidad de algunos otros de la hoja, en lugar de la hoja de $1$
- Más generalmente, se puede permutar los elementos de la coincidencia de antes/después de usar el árbol de coincidencia de bijection.
- El árbol correspondiente a una coincidencia con $k$ terminal closers tiene una ruta de acceso $\text{root} \to 2n \to (2n-1) \to \cdots \to (2n-k+1)$, y el nodo $2n-k$ es un hermano de uno de estos nodos.
