Relación entre árboles ordenados y particiones enteras

Question

He descubierto que existe una biyección entre las particiones enteras y los árboles ordenados enraizados con raíces de grado 2 o mayor. La demostración rigurosa es complicada, pero la idea principal es que tomas el diagrama de Young de una permutación y lo encierras en un triángulo rectángulo isósceles de modo que la hipotenusa del triángulo toque justo el borde 'irregular' del diagrama, luego colapsas el espacio negativo en el triángulo a lo largo de la hipotenusa. Las 'esquinas' negativas en el diagrama de Young corresponden a hojas en el árbol, y sus profundidades corresponden a la distancia desde la hipotenusa.

Por ejemplo -

    0
   / \
  0   0
 / \
0   0

corresponde a

   []
   []
 [][]

También he notado que agregar un bloque al diagrama de Young, lo cual necesariamente ocurre en una esquina negativa, es equivalente a tomar una hoja del árbol y moverla un paso más cerca de la raíz:

              0
  []         /|\
[][]        0 0 0
[][]       /
          0

Por lo tanto, dado un conjunto de árboles con el mismo número de vértices en cada profundidad, es necesario que sus diagramas de Young correspondientes tengan el mismo número de casillas en ellos, es decir, sus particiones correspondientes son del mismo entero. Sin embargo, no es el caso que todas las particiones de un entero en particular correspondan a árboles con el mismo número de vértices en cada profundidad, o incluso árboles con el mismo número de vértices en general, y de la misma manera, árboles con el mismo número total de vértices pueden corresponder a particiones de enteros diferentes.

Esta observación me llevó a la pregunta: ¿Hay alguna manera de saber, dado una partición, cuántos vértices hay en el árbol correspondiente sin hacer algo equivalente a encontrar el árbol en sí? Y, ¿esta biyección es significativa de una conexión subyacente más profunda entre las particiones y los árboles, o solo es una coincidencia?

EDITAR: para aclarar esperanzadamente mi explicación anterior, aquí está la versión un poco más larga con imágenes:

Answer 1

Wow, gracias por una explicación tan clara. Creo que encontrar la respuesta fue mucho más rápido que el tiempo que tomaste para dibujar ese bonito diagrama. Además, los ejemplos del diagrama estaban incompletos; tu respuesta a mi comentario realmente hizo una diferencia importante en la corrección de mi algoritmo.

Entonces, los vértices del grafo se dividen en: 1) Nodo raíz. Este se incluye por defecto.

2) Nodos hoja. Estos corresponden al número de ángulos rectos que apuntan hacia adentro en tu diagrama.

3) Nodos no hoja. Estos corresponden a ángulos rectos en tu diagrama.

Advertencia importante: al contar los nodos no hoja, los cuentas una vez cuando desciendes y una vez más cuando subes. Por lo tanto, debes dividir el número de ángulos rectos que obtienes entre 2 para obtener el número real de nodos no hoja. Esto es análogo a contar solo los ángulos rectos que apuntan hacia adentro en tu diagrama.

De manera similar, para asegurarte de obtener el número correcto, debes contar los nodos de borde dos veces. Esto corresponde a contar el número de ángulos rectos dentro de todo tu triángulo, no solo en el Diagrama de Young.

Tu ejemplo [r denota ángulo recto interno; , denota ángulo recto]:

|,
|,
|r                   
|[]r  ,  ,
|[] [] [] []r
|[] [] [] [] [],
|[] [] [] [] [],
|[] [] [] [] []r  ,  ,
|__ __ __ __ __ __ __ __

Así, 4 ángulos rectos y 8 ángulos rectos = 4 hojas, 8/2 = 4 no hojas, y siempre 1 raíz.