En matemáticas , la correspondencia Robinson-Schensted-Knuth , también conocida como correspondencia RSK o algoritmo RSK , es una biyección combinatoria entre matrices A con entradas de números enteros no negativos y pares ( P , Q ) de cuadros de Young semiestándar de igual forma, cuyo tamaño es igual a la suma de las entradas de A . Más precisamente, el peso de P viene dado por las sumas de columna de A y el peso de Q por sus sumas de fila. Es una generalización delCorrespondencia Robinson-Schensted , en el sentido de que tomando A como una matriz de permutación , el par ( P , Q ) será el par de cuadros estándar asociados a la permutación bajo la correspondencia Robinson-Schensted.
La correspondencia Robinson-Schensted-Knuth extiende muchas de las propiedades notables de la correspondencia Robinson-Schensted , en particular su simetría: transposición de la matriz A resulta en intercambio de la cuadros P , Q .
La correspondencia Robinson-Schensted-Knuth
Introducción
La correspondencia de Robinson-Schensted es un mapeo biyectivo entre permutaciones y pares de cuadros de Young estándar , ambos con la misma forma. Esta biyección se puede construir usando un algoritmo llamado inserción de Schensted , comenzando con un cuadro vacío e insertando sucesivamente los valores σ 1 ,…, σ n de la permutación σ en los números 1,2,… n ; estos forman la segunda línea cuando σ se da en notación de dos líneas:
.
El primer cuadro estándar P es el resultado de sucesivas inserciones; el otro cuadro estándar Q registra las formas sucesivas de la cuadros intermedio durante la construcción de P .
La inserción de Schensted se generaliza fácilmente al caso donde σ tiene entradas repetidas; en ese caso, la correspondencia producirá un cuadro semiestándar P en lugar de un cuadro estándar, pero Q seguirá siendo un cuadro estándar. La definición de la correspondencia RSK restablece la simetría entre los cuadros P y Q al producir un cuadro semiestándar para Q también.
Matrices de dos líneas
La matriz de dos líneas (o permutación generalizada ) w A correspondiente a una matriz A se define [1] como
en el que para cualquier par ( i , j ) que indexa una entrada A i , j de A , hay A i , j columnas iguales a, y todas las columnas están en orden lexicográfico, lo que significa que
- , y
- Si y luego .
Ejemplo
La matriz de dos líneas correspondiente a
es
Definición de la correspondencia
Al aplicar el algoritmo de inserción de Schensted a la línea inferior de esta matriz de dos líneas, se obtiene un par que consta de un cuadro semiestándar P y un cuadro estándar Q 0 , donde este último se puede convertir en un cuadro semiestándar Q reemplazando cada entrada b de Q 0 por la b -ésima entrada de la línea superior de w A . Se obtiene así una biyección de matrices A a pares ordenados, [2] ( P , Q ) de cuadros de Young semiestándar de la misma forma, en los que el conjunto de entradas de P es el de la segunda línea de w A , y el conjunto de entradas de Q es el de la primera línea de w A . El número de entradas j en P es por lo tanto igual a la suma de las entradas en la columna j de A , y el número de entradas i en Q es igual a la suma de las entradas en la fila i de A .
Ejemplo
En el ejemplo anterior, el resultado de aplicar la inserción de Schensted para insertar sucesivamente 1,3,3,2,2,1,2 en un cuadro inicialmente vacío da como resultado un cuadro P , y un cuadro estándar adicional Q 0 que recodifica las formas sucesivas , dada por
y después de reemplazar las entradas 1,2,3,4,5,6,7 en Q 0 sucesivamente por 1,1,1,2,2,3,3 se obtiene el par de cuadros semiestándar
Definición directa de la correspondencia RSK
La definición anterior utiliza el algoritmo de Schensted, que produce un cuadro de grabación estándar Q 0 , y lo modifica para tener en cuenta la primera línea del arreglo de dos líneas y producir un cuadro de registro semiestándar; esto hace evidente la relación con la correspondencia Robinson-Schensted . Sin embargo, es natural simplificar la construcción modificando la parte de registro de forma del algoritmo para tener en cuenta directamente la primera línea de la matriz de dos líneas; De esta forma se describe habitualmente el algoritmo para la correspondencia RSK. Esto simplemente significa que después de cada paso de inserción de Schensted, el cuadro Q se amplía agregando, como entrada del nuevo cuadrado, la b -ésima entrada i b de la primera línea de w A , donde b es el tamaño actual del cuadro. Que esto siempre produce un cuadro semiestándar se desprende de la propiedad (observada por primera vez por Knuth [2] ) de que para inserciones sucesivas con un valor idéntico en la primera línea de w A , cada cuadrado sucesivo agregado a la forma está en una columna estrictamente al a la derecha del anterior.
A continuación se muestra un ejemplo detallado de esta construcción de ambos cuadros semiestándar. Correspondiente a una matriz
uno tiene la matriz de dos líneas
La siguiente tabla muestra la construcción de ambos cuadros para este ejemplo
Par insertado | ||||||||
PAG | ||||||||
Q |
Propiedades combinatorias de la correspondencia RSK
El caso de las matrices de permutación
Si es una matriz de permutación, luego RSK genera el estándar Young Tableaux (SYT), de la misma forma . Por el contrario, si tienen SYT de la misma forma , luego la matriz correspondiente es una matriz de permutación. Como resultado de esta propiedad, simplemente comparando las cardinalidades de los dos conjuntos en los dos lados del mapeo biyectivo, obtenemos el siguiente corolario:
Corolario 1 : Para cada tenemos dónde medio varía en todas las particiones de y es el número de cuadros de forma estándar de Young .
Simetría
Dejar ser una matriz con entradas no negativas. Suponga que los mapas del algoritmo RSK a luego, el algoritmo RSK mapea a , dónde es la transposición de . [1]
En particular para el caso de matrices de permutación, se recupera la simetría de la correspondencia Robinson-Schensted: [3]
Teorema 2 : Si la permutación corresponde a un triple , luego la permutación inversa ,, corresponde a .
Esto conduce a la siguiente relación entre el número de involuciones en con el número de cuadros que se pueden formar a partir de (Una involución es una permutación que es su propia inversa ): [3]
Corolario 2 : El número de cuadros que se pueden formar a partir de es igual al número de involuciones en .
Prueba : si es una involución correspondiente a , luego corresponde a ; por eso. Por el contrario, si es cualquier permutación correspondiente a , luego también corresponde a ; por eso. Entonces hay una correspondencia uno a uno entre involuciones y cuadros
El número de involuciones en viene dada por la recurrencia:
Dónde . Al resolver esta recurrencia podemos obtener el número de involuciones en,
Matrices simétricas
Dejar y deje que el algoritmo RSK mapee la matriz a la pareja , dónde es un SSYT de forma . [1] Deja donde el y . Entonces el mapa establece una biyección entre matrices simétricas con fila () y SSYT de tipo .
Aplicaciones de la correspondencia RSK
Identidad de Cauchy
La correspondencia Robinson-Schensted-Knuth proporciona una prueba biyectiva directa de la siguiente identidad célebre para funciones simétricas:
dónde son funciones de Schur .
Números de Kostka
Arreglar particiones , luego
dónde y denotar los números de Kostka y es el número de matrices , con elementos no negativos, con fila () y columna () .
Referencias
- ↑ a b c Stanley, Richard P. (1999). Combinatoria enumerativa . 2 . Nueva York: Cambridge University Press. págs. 316–380. ISBN 0-521-55309-1.
- ^ a b Knuth, Donald E. (1970). "Permutaciones, matrices y cuadros de Young generalizados" . Pacific Journal of Mathematics . 34 (3): 709–727. doi : 10.2140 / pjm.1970.34.709 . Señor 0272654 .
- ^ a b Knuth, Donald E. (1973). El arte de la programación informática, vol. 3: Clasificación y búsqueda . Londres: Addison – Wesley. págs. 54–58. ISBN 0-201-03803-X.
- Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de las matemáticas y sus aplicaciones. 108 . Cambridge: Cambridge University Press . págs. 135-162 . ISBN 0-521-86565-4. Zbl 1106.05001 .