En matemáticas combinatorias , la fórmula de la longitud del gancho es una fórmula para el número de cuadros de Young estándar cuya forma es un diagrama de Young dado . Tiene aplicaciones en diversas áreas como teoría de la representación , probabilidad y análisis de algoritmos ; por ejemplo, el problema de las subsecuencias crecientes más largas . Una fórmula relacionada cuenta el número de cuadros de Young semi-estándar, que es una especialización de un polinomio de Schur .
Definiciones y declaración
Dejar ser una partición de. Es costumbre interpretargráficamente como un diagrama de Young , es decir, una matriz justificada a la izquierda de celdas cuadradas con filas de longitudes . Un cuadro joven (estándar) de forma es un relleno del celdas del diagrama de Young con todos los enteros , sin repetición, de modo que cada fila y cada columna forman secuencias crecientes. Para la celda en posición, en el th fila y a columna, el gancho es el conjunto de celdas tal que y o y . La longitud del gancho es el número de celdas en .
La fórmula de la longitud del gancho expresa el número de cuadros de forma estándar de Young , denotado por o , como
donde el producto está sobre todas las celdas del diagrama de Young.
Ejemplos de
La figura de la derecha muestra las longitudes de los ganchos para las celdas en el diagrama de Young , correspondiente a la partición 9 = 4 + 3 + 1 + 1. La fórmula de la longitud del gancho da el número de tableaux estándar de Young como:
Un número catalán cuenta los caminos de Dyck con pasos subiendo (U) intercalados con pasos que van hacia abajo (D), de modo que en cada paso nunca hay más D anteriores que U. Estos están en biyección con los cuadros de formas de Young: un camino de Dyck corresponde al cuadro cuya primera fila enumera las posiciones de los pasos en U, mientras que la segunda fila enumera las posiciones de los pasos en D. Por ejemplo, UUDDUD corresponde a los cuadros con las filas 125 y 346.
Esto muestra que , por lo que la fórmula del gancho se especializa en la conocida fórmula del producto
Historia
Hay otras fórmulas para , pero la fórmula de la longitud del anzuelo es particularmente simple y elegante. Una fórmula menos conveniente que expresaen términos de un determinante fue deducido independientemente por Frobenius y Young en 1900 y 1902 respectivamente usando métodos algebraicos. [1] [2] MacMahon encontró una prueba alternativa para la fórmula de Young-Frobenius en 1916 usando métodos de diferencia. [3]
La fórmula de la longitud del gancho en sí fue descubierta en 1953 por Frame, Robinson y Thrall como una mejora de la fórmula de Young-Frobenius. Sagan [4] describe el descubrimiento de la siguiente manera.
Un jueves de mayo de 1953, Robinson estaba de visita en Frame en la Universidad Estatal de Michigan. Al discutir el trabajo de Staal (un estudiante de Robinson), Frame se vio obligado a conjeturar la fórmula del gancho. Al principio Robinson no podía creer que existiera una fórmula tan simple, pero después de probar algunos ejemplos se convenció y juntos probaron la identidad. El sábado acudieron a la Universidad de Michigan, donde Frame presentó su nuevo resultado tras una conferencia de Robinson. Esto sorprendió a Thrall, que estaba en la audiencia, ¡porque acababa de demostrar el mismo resultado el mismo día!
A pesar de la simplicidad de la fórmula de la longitud del gancho, la prueba Frame-Robinson-Thrall no es muy reveladora y no proporciona ninguna intuición sobre el papel de los ganchos. La búsqueda de una explicación breve e intuitiva acorde con un resultado tan simple dio lugar a muchas pruebas alternativas. [5] Hillman y Grassl dieron la primera prueba que ilumina el papel de los anzuelos en 1976 al demostrar un caso especial de la fórmula del contenido del anzuelo de Stanley , que se sabe que implica la fórmula de la longitud del anzuelo. [6] Greene , Nijenhuis y Wilf encontraron una prueba probabilística usando el anzuelo en el que las longitudes del gancho aparecen naturalmente en 1979. [7] Remmel adaptó la prueba original Frame-Robinson-Thrall en la primera prueba biyectiva para la fórmula de la longitud del gancho en 1982. [8] Franzblau y Zeilberger descubrieron por primera vez una prueba biyectiva directa en 1982. [9] Zeilberger también convirtió la prueba del anzuelo Greene-Nijenhuis-Wilf en una prueba biyectiva en 1984. [10] Una biyección directa más simple fue anunciado por Pak y Stoyanovskii en 1992, y su prueba completa fue presentada por la pareja y Novelli en 1997. [11] [12] [13]
Mientras tanto, la fórmula de la longitud del gancho se ha generalizado de varias formas. RM Thrall encontró el análogo a la fórmula de la longitud del gancho para los cuadros jóvenes desplazados en 1952. [14] Sagan dio una prueba de paso del gancho desplazado para la fórmula de la longitud del gancho para cuadros jóvenes desplazados en 1980. [15] Sagan y Yeh probaron la fórmula de la longitud del gancho. para árboles binarios que usaban el hook walk en 1989. [16] Proctor dio una generalización poset (ver más abajo).
Prueba probabilística
Argumento heurístico de Knuth
La fórmula de la longitud del gancho se puede entender intuitivamente usando el siguiente argumento heurístico, pero incorrecto, sugerido por DE Knuth . [17] Dado que cada elemento de un cuadro es el más pequeño en su gancho y llena la forma del cuadro al azar, la probabilidad de que la celdacontendrá el elemento mínimo del anzuelo correspondiente es el recíproco de la longitud del anzuelo. Multiplicando estas probabilidades por todas y da la fórmula. Este argumento es falaz ya que los eventos no son independientes.
Sin embargo, el argumento de Knuth es correcto para la enumeración de etiquetas en árboles que satisfacen propiedades de monotonicidad análogas a las de un cuadro de Young. En este caso, los eventos de 'gancho' en cuestión son de hecho eventos independientes.
Prueba probabilística usando el anzuelo
Ésta es una prueba probabilística encontrada por C. Greene , A. Nijenhuis y HS Wilf en 1979. [18] Definir
Deseamos demostrar que . Primero,
donde la suma corre sobre todos los diagramas de Young obtenido de eliminando una celda de la esquina. (La entrada máxima del cuadro de formas de Young ocurre en una de sus celdas de esquina, por lo que eliminarlo da un cuadro joven de forma .)
Definimos y , por lo que es suficiente mostrar la misma recurrencia
lo que implicaría por inducción. La suma anterior se puede ver como una suma de probabilidades escribiéndola como
Por lo tanto, debemos demostrar que los números definir una medida de probabilidad en el conjunto de diagramas de Young con . Esto se hace de manera constructiva mediante la definición de una caminata aleatoria, llamada caminata de gancho , en las celdas del diagrama de Young., que finalmente selecciona una de las celdas de esquina de (que están en biyección con diagramas para cual ). El anzuelo se define por las siguientes reglas.
- Elija una celda uniformemente al azar de células. Empiece la caminata aleatoria desde allí.
- Sucesor de la celda actual se elige uniformemente al azar del anzuelo .
- Continúe hasta llegar a una celda de la esquina .
Proposición: para una celda de esquina determinada de , tenemos
dónde .
Dado esto, sumando todas las celdas de las esquinas da como se afirma.
Conexión a representaciones del grupo simétrico
La fórmula de la longitud del gancho es de gran importancia en la teoría de la representación del grupo simétrico. , donde el numero se sabe que es igual a la dimensión de la compleja representación irreducible asociado a .
Discusión detallada
Las complejas representaciones irreductibles del grupo simétrico están indexados por particiones de (ver módulo de Specht ). Sus personajes están relacionados con la teoría de funciones simétricas a través del producto interno Hall:
dónde es la función de Schur asociada a y es la función simétrica de suma de potencias de la partición asociado al ciclo de descomposición de . Por ejemplo, si luego .
Desde la permutación de identidad tiene la forma en notación cíclica, , la fórmula dice
La expansión de las funciones de Schur en términos de funciones simétricas monomiales utiliza los números de Kostka :
Entonces el producto interior con es , porque . Tenga en cuenta que es igual a , así que eso de considerar la representación regular de, o combinatoriamente de la correspondencia Robinson-Schensted-Knuth .
El cálculo también muestra que:
Esta es la expansión de en términos de funciones de Schur usando los coeficientes dados por el producto interno, ya que . La igualdad anterior se puede probar también verificando los coeficientes de cada monomio en ambos lados y usando la correspondencia Robinson-Schensted-Knuth o, más conceptualmente, observando la descomposición de por irreducible módulos, y tomando personajes. Véase la dualidad Schur-Weyl .
Prueba de la fórmula del gancho con la fórmula de Frobenius [19]
Por las consideraciones anteriores
así que eso
dónde es el determinante de Vandermonde .
Para la partición , definir por . Para lo siguiente, necesitamos al menos tantas variables como filas en la partición, por lo que a partir de ahora trabajamos con variables .
Cada termino es igual a
(Ver función de Schur .) Dado que el vector es diferente para cada partición, esto significa que el coeficiente de en , denotado , es igual a . Esto se conoce como la Fórmula del carácter de Frobenius , que da una de las primeras pruebas. [20]
Solo queda simplificar este coeficiente. Multiplicar
y
llegamos a la conclusión de que nuestro coeficiente como
que se puede escribir como
La última suma es igual al siguiente determinante
qué columna se reduce a un determinante de Vandermonde , y obtenemos la fórmula
Tenga en cuenta que es la longitud del gancho del primer cuadro en cada fila del diagrama de Young, y esta expresión se transforma fácilmente en la forma deseada : uno muestra , donde este último producto pasa por el la fila del diagrama de Young.
Conexión a las subsecuencias crecientes más largas
La fórmula de la longitud del gancho también tiene aplicaciones importantes para el análisis de las subsecuencias crecientes más largas en permutaciones aleatorias. Si denota una permutación uniformemente aleatoria de orden , denota la longitud máxima de una subsecuencia creciente de , y denota el valor esperado (promedio) de , Anatoly Vershik y Sergei Kerov [21] e independientemente Benjamin F. Logan y Lawrence A. Shepp [22] demostraron que cuando es largo, es aproximadamente igual a . Esto responde a una pregunta planteada originalmente por Stanislaw Ulam . La prueba se basa en traducir la pregunta a través de la correspondencia de Robinson-Schensted a un problema sobre la forma límite de un cuadro de Young aleatorio elegido de acuerdo con la medida de Plancherel . Dado que la definición de medida de Plancherel involucra la cantidad, la fórmula de la longitud del gancho se puede utilizar para realizar un análisis asintótico de la forma límite y, por lo tanto, también responder a la pregunta original.
Las ideas de Vershik-Kerov y Logan-Shepp fueron refinadas más tarde por Jinho Baik, Percy Deift y Kurt Johansson, quienes pudieron lograr un análisis mucho más preciso del comportamiento limitante de la longitud máxima de la subsecuencia creciente, demostrando un resultado importante ahora conocido como el teorema de Baik-Deift-Johansson. Su análisis nuevamente hace un uso crucial del hecho de que tiene una serie de buenas fórmulas, aunque en lugar de la fórmula de la longitud del gancho hizo uso de una de las expresiones determinantes.
Fórmulas relacionadas
La fórmula para el número de cuadros de formas de Young se derivó originalmente de la fórmula determinante de Frobenius en relación con la teoría de la representación: [23]
Las longitudes de los ganchos también se pueden utilizar para dar una representación del producto a la función generadora para el número de particiones del plano inverso de una forma determinada. [24] Si λ es una partición de algún número entero p , se obtiene una partición de plano inverso de n con forma λ completando las casillas del diagrama de Young con números enteros no negativos de modo que las entradas se sumen an y no sean decrecientes a lo largo de cada fila y hacia abajo en cada columna. Las longitudes del ganchose puede definir como con cuadros de Young. Si π n denota el número de particiones en el plano inverso de n con forma λ , entonces la función generadora se puede escribir como
Stanley descubrió otra fórmula para la misma función generadora. [25] En general, si es cualquier poset con elementos, la función generadora para reversa -particiones es
dónde es un polinomio tal que es el número de extensiones lineales de.
En el caso de una partición , estamos considerando el poset en sus celdas dado por la relación
- .
Entonces, una extensión lineal es simplemente un cuadro de Young estándar, es decir
Prueba de fórmula de gancho usando la fórmula de Stanley
Combinando las dos fórmulas para las funciones generadoras tenemos
Ambos lados convergen dentro del disco de radio uno y la siguiente expresión tiene sentido para
Sería violento enchufar 1, pero el lado derecho es una función continua dentro del disco unitario y un polinomio es continuo en todas partes, así que al menos podemos decir
Aplicando la regla de L'Hôpital veces da como resultado la fórmula de la longitud del gancho
Fórmula de longitud de gancho de tableaux semi-estándar
El polinomio de Schur es la función generadora de cuadros jóvenes semiestándar con forma y entradas en . Especializándonos esto para da el número de tableaux semi-estándar, que se pueden escribir en términos de longitudes de gancho:
El diagrama de Young corresponde a una representación irreductible del grupo lineal especial , y el polinomio de Schur es también el carácter de la matriz diagonal actuando sobre esta representación. La especialización anterior es, por tanto, la dimensión de la representación irreducible, y la fórmula es una alternativa a la fórmula de dimensión de Weyl más general .
Podemos refinar esto tomando la especialización principal de la función de Schur en las variables :
dónde para la partición conjugada .
Fórmula de forma sesgada
Hay una generalización de esta fórmula para formas sesgadas, [26]
donde la suma se toma sobre los diagramas excitados de forma y cajas distribuidas según .
Generalización para d -posets completos
Los diagramas jóvenes se pueden considerar como ideales de orden finito en el posety los tableaux estándar de Young son sus extensiones lineales . Robert Proctor ha dado una generalización de la fórmula de la longitud del gancho para contar extensiones lineales de una clase más grande de posets generalizando tanto árboles como diagramas de sesgo. [27] [28]
Referencias
- ^ G. Frobenius. Uber die charaktere der symmetrischer gruppe, Preuss. &anuncio. Sem. sitz. (1900), 516–534.
- ^ A. Young. Análisis cuantitativo sustitucional II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397.
- ^ PA MacMahon. "Análisis combinatorio", Cambridge Univ. Press, Londres / Nueva York, 1916; reimpreso por Chelsea, Nueva York, 1960.
- ^ Sagan, Bruce (2001). El grupo simétrico. Representaciones, algoritmos combinatorios y funciones simétricas, 2ª edición . Springer-Verlag. ISBN 0-387-95067-2.
- ^ Knuth, Donald (1973). El arte de la programación informática, volumen 3: clasificación y búsqueda, tercera edición, Addison-Wesley, p. 63
- ^ AP Hillman y RM Grassl. Particiones de plano inverso y números de gancho de cuadro, J. Comb. Teoría, Ser. A 21 (1976), 216-221.
- ^ Greene, C., Nijenhuis, A. y Wilf, HS (1979). Prueba probabilística de una fórmula para el número de cuadros de Young de una forma determinada. Avances en matemáticas 31, 104–109.
- ^ JB Remmel. Demostraciones biyectivas de fórmulas para el número de cuadros de Young estándar, Álgebra lineal y multilineal 11 (1982), 45–100.
- ^ Franzblau, DS y Zeilberger, D. (1982). Una prueba biyectiva de la fórmula de la longitud del gancho. J. Algoritmos 3, 317–343.
- ^ D. Zeilberger. Una biyección de ganchos cortos inspirada en la prueba de Greene-Nijenhuis-Wilf, Discrete Math. 51 (1984), 101-108.
- ^ Pak, IM y Stoyanovskii, AV (1992). Una prueba biyectiva de la fórmula de la longitud del gancho. Funct. Anal. Apl. 24.
- ^ Novelli, J.-C., Pak, IM y Stoyanovskii, AV (1997). Una prueba biyectiva directa de la fórmula de la longitud del gancho. Matemáticas discretas e informática teórica 1, 1997, 53–67.
- ^ Sagan, Bruce (2001). El grupo simétrico. Representaciones, algoritmos combinatorios y funciones simétricas, 2ª edición . Springer-Verlag. ISBN 0-387-95067-2.
- ^ RM Thrall. Un problema combinatorio, Michigan Math. J. 1 (1952), 81–88.
- ^ Sagan, B. Sobre la selección de un cuadro de Young cambiado al azar. J. Algoritmos 1, 3 (1980), 213-234.
- ^ Sagan, BE y Yeh, YN Algoritmos probabilísticos para árboles. Fibonacci Quart. 27, 3 (1989), 201-208.
- ^ Knuth, Donald (1973), El arte de la programación informática, Volumen 3: Clasificación y búsqueda, 3ª edición , Addison-Wesley, p. 63, ISBN 0-201-03803-X.
- ^ Greene, C., Nijenhuis, A. y Wilf, HS (1979). Prueba probabilística de una fórmula para el número de cuadros de Young de una forma determinada. Avances en matemáticas 31, 104–109.
- ^ Fulton, William, 1939- (1991). Teoría de la representación: un primer curso . Harris, Joe, 1951-. Nueva York: Springer-Verlag. págs. 49–50. ISBN 0387974954. OCLC 22861245 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ W. Fulton, J. Harris. Teoría de la representación: un primer curso Springer-Verlag, Nueva York, 1991
- ^ Vershik, AM; Kerov, CV (1977), "Asintótica de la medida Plancheral del grupo simétrico y una forma limitante para cuadros de Young", Dokl. Akad. Nauk SSSR 233: 1024–1027
- ^ BF Logan y LA Shepp, Un problema variacional para cuadros jóvenes aleatorios, Advances in Mathematics 26 (1977), no. 2, 206–222.
- ^ Knuth, Donald (1973), The Art of Computer Programming , 3 (1 ed.), Addison – Wesley, págs. 61–62
- ^ Stanley, Richard P. (1971), "Teoría y aplicaciones de particiones planas, 2", Estudios en matemáticas aplicadas , 50 : 259–279, doi : 10.1002 / sapm1971503259
- ^ RP Stanley, Tesis de doctorado "Estructuras ordenadas y particiones", Universidad de Harvard, 1971
- ^ Morales, AH, Pak, I. y Panova, G. Fórmulas de gancho para formas sesgadas I. q-análogos y biyecciones, Journal of Combinatorial Theory, Ser. A , vol. 154 (2018), 350-405.
- ^ Proctor, Robert (1999). "Clasificación de diagrama de Dynkin de celosías de Bruhat minúsculas λ y de posets d-completos" . Revista de combinatoria algebraica . 9 : 61–94. doi : 10.1023 / A: 1018615115006 .
- ^ Kim, Jang Soo; Yoo, Meesue (2019). "Propiedad de longitud de gancho de posets d-complete a través de q-integrals". Revista de Teoría Combinatoria, serie A . 162 : 167-221. arXiv : 1708.09109 . doi : 10.1016 / j.jcta.2018.11.003 .
enlaces externos
- Las matemáticas sorprendentes de las subsecuencias crecientes más largas por Dan Romik. Contiene discusiones sobre la fórmula de la longitud del gancho y varias de sus variantes, con aplicaciones a las matemáticas de las subsecuencias crecientes más largas.