Fórmula de longitud del anzuelo

Fórmula matemática para el número de cuadros de Young

En matemáticas combinatorias , la fórmula de longitud de gancho es una fórmula para el número de tablas de Young estándar cuya forma es un diagrama de Young dado . Tiene aplicaciones en diversas áreas, como la teoría de la representación , la probabilidad y el análisis de algoritmos ; por ejemplo, el problema de las subsecuencias crecientes más largas . Una fórmula relacionada proporciona el número de tablas de Young semiestándar, que es una especialización de un polinomio de Schur .

Definiciones y declaraciones

Sea una partición de . Es habitual interpretarlo gráficamente como un diagrama de Young , es decir, una matriz justificada a la izquierda de celdas cuadradas con filas de longitudes . Una tabla de Young (estándar) de forma es un relleno de las celdas del diagrama de Young con todos los números enteros , sin repetición, de modo que cada fila y cada columna formen secuencias crecientes. Para la celda en la posición , en la fila y la columna n, el gancho es el conjunto de celdas tales que y o y . La longitud del gancho es el número de celdas en . ${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})}$ ${\displaystyle n=\lambda _{1}+\cdots +\lambda _{k}}$ ${\displaystyle \lambda }$ ${\displaystyle k}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle (i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle H_{\lambda }(i,j)}$ ${\displaystyle (a,b)}$ ${\displaystyle a=i}$ ${\displaystyle b\geq j}$ ${\displaystyle a\geq i}$ ${\displaystyle b=j}$ ${\displaystyle h_{\lambda }(i,j)}$ ${\displaystyle H_{\lambda }(i,j)}$

La fórmula de la longitud del anzuelo expresa el número de cuadros de Young estándar de forma , denotados por o , como ${\displaystyle \lambda }$ ${\displaystyle f^{\lambda }}$ ${\displaystyle d_{\lambda }}$

${\displaystyle f^{\lambda }={\frac {n!}{\prod h_{\lambda }(i,j)}},}$

donde el producto es sobre todas las celdas del diagrama de Young. ${\displaystyle (i,j)}$

Ejemplos

Una tabla que enumera la longitud del gancho de cada celda en el diagrama de Young
${\displaystyle (4,3,1,1)}$

La figura de la derecha muestra las longitudes de los ganchos para las celdas en el diagrama de Young , correspondientes a la partición 9 = 4 + 3 + 1 + 1. La fórmula de longitud de gancho proporciona el número de cuadros de Young estándar como: ${\displaystyle \lambda =(4,3,1,1)}$

${\displaystyle f^{\lambda }={\frac {9!}{7\cdot 5\cdot 4\cdot 3\cdot 2\cdot 2\cdot 1\cdot 1\cdot 1}}=216.}$

Un número catalán cuenta los caminos de Dyck con escalones ascendentes (U) intercalados con escalones descendentes (D), de modo que en cada paso nunca hay más D precedentes que U. Estos están en biyección con los cuadros de Young de forma : un camino de Dyck corresponde al cuadro cuya primera fila enumera las posiciones de los escalones U, mientras que la segunda fila enumera las posiciones de los escalones D. Por ejemplo, UUDDUD corresponde a los cuadros con las filas 125 y 346. ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \lambda =(n,n)}$

Esto demuestra que , por lo tanto, la fórmula del gancho se especializa en la fórmula del producto conocida. ${\displaystyle C_{n}=f^{(n,n)}}$

${\displaystyle C_{n}={\frac {(2n)!}{(n+1)(n)\cdots (3)(2)(n)(n-1)\cdots (2)(1)}}={\frac {(2n)!}{(n+1)!\,n!}}={\frac {1}{n{+}1}}{\binom {2n}{n}}.}$

Historia

Existen otras fórmulas para , pero la fórmula de la longitud del gancho es particularmente simple y elegante. Una fórmula menos conveniente que expresa en términos de un determinante fue deducida 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] ${\displaystyle f^{\lambda }}$ ${\displaystyle f^{\lambda }}$

La fórmula de la longitud del anzuelo 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 visitando a Frame en la Universidad Estatal de Michigan. Mientras discutían el trabajo de Staal (un estudiante de Robinson), Frame llegó a la conclusión de que se trataba de 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 demostraron la identidad. El sábado fueron a la Universidad de Michigan, donde Frame presentó su nuevo resultado después de una conferencia de Robinson. Esto sorprendió a Thrall, que estaba entre el público, porque él 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 de 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 que se ajuste a un resultado tan simple dio lugar a muchas pruebas alternativas. ^[5] Hillman y Grassl dieron la primera prueba que ilumina el papel de los ganchos en 1976 al demostrar un caso especial de la fórmula de contenido del gancho de Stanley , que se sabe que implica la fórmula de la longitud del gancho. ^[6] Greene , Nijenhuis y Wilf encontraron una prueba probabilística usando el paseo del gancho en el que las longitudes del gancho aparecen naturalmente en 1979. ^[7] Remmel adaptó la prueba original de Frame–Robinson–Thrall en la primera prueba biyectiva para la fórmula de la longitud del gancho en 1982. ^[8] Una prueba biyectiva directa fue descubierta por primera vez por Franzblau y Zeilberger en 1982. ^[9] Zeilberger también convirtió la prueba del paseo del gancho de Greene–Nijenhuis–Wilf en una prueba biyectiva en 1984. ^[10] Una biyección directa más simple fue anunciada por Pak y Stoyanovskii en 1992, y su prueba completa fue presentada por la pareja y Novelli en 1997. ^{[11] [12] [4]}

Mientras tanto, la fórmula de longitud de gancho se ha generalizado de varias maneras. RM Thrall encontró el análogo a la fórmula de longitud de gancho para tablas de Young desplazadas en 1952. ^[13] Sagan proporcionó una prueba de caminata de gancho desplazada para la fórmula de longitud de gancho para tablas de Young desplazadas en 1980. ^[14] Sagan y Yeh demostraron la fórmula de longitud de gancho para árboles binarios utilizando la caminata de gancho en 1989. ^[15] Proctor proporcionó una generalización de conjuntos parciales (ver más abajo).

Prueba probabilística

El argumento heurístico de Knuth

La fórmula de la longitud del gancho se puede entender intuitivamente utilizando el siguiente argumento heurístico, pero incorrecto, sugerido por DE Knuth . ^[16] Dado que cada elemento de una tabla es el más pequeño en su gancho y llena la forma de la tabla al azar, la probabilidad de que la celda contenga el elemento mínimo del gancho correspondiente es el recíproco de la longitud del gancho. Multiplicando estas probabilidades por todas y se obtiene la fórmula. Este argumento es falaz ya que los eventos no son independientes. ${\displaystyle (i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$

Sin embargo, el argumento de Knuth es correcto para la enumeración de los etiquetados en árboles que satisfacen propiedades de monotonía análogas a las de una tabla de Young. En este caso, los eventos "gancho" en cuestión son, de hecho, eventos independientes.

Prueba probabilística utilizando el método del gancho

Esta es una prueba probabilística encontrada por C. Greene , A. Nijenhuis y HS Wilf en 1979. ^[7] Definir

${\displaystyle e_{\lambda }={\frac {n!}{\prod _{(i,j)\in Y(\lambda )}h_{\lambda }(i,j)}}.}$

Deseamos demostrar que ... En primer lugar, ${\displaystyle f^{\lambda }=e_{\lambda }}$

${\displaystyle f^{\lambda }=\sum _{\mu \uparrow \lambda }f^{\mu },}$

Esquinas del diagrama de Young (5,3,2,1,1)

donde la suma se ejecuta sobre todos los diagramas de Young obtenidos al eliminar una celda de esquina. (La entrada máxima de la tabla de Young de forma ocurre en una de sus celdas de esquina, por lo que al eliminarla se obtiene una tabla de Young de forma .) ${\displaystyle \mu }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$

Definimos y , por lo que es suficiente mostrar la misma recurrencia ${\displaystyle f^{\emptyset }=1}$ ${\displaystyle e_{\emptyset }=1}$

${\displaystyle e_{\lambda }=\sum _{\mu \uparrow \lambda }e_{\mu },}$

lo que implicaría por inducción. La suma anterior puede verse como una suma de probabilidades escribiéndola como ${\displaystyle f^{\lambda }=e_{\lambda }}$

${\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1.}$

Por lo tanto, necesitamos demostrar que los números definen una medida de probabilidad en el conjunto de diagramas de Young con . Esto se hace de manera constructiva definiendo un recorrido aleatorio, llamado recorrido en gancho , en las celdas del diagrama de Young , que finalmente selecciona una de las celdas de las esquinas de (que están en biyección con diagramas para los cuales ). El recorrido en gancho se define mediante las siguientes reglas. ${\displaystyle {\frac {e_{\mu }}{e_{\lambda }}}}$ ${\displaystyle \mu }$ ${\displaystyle \mu \uparrow \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \mu \uparrow \lambda }$

1. Seleccione una celda de manera uniforme y aleatoria . Comience el recorrido aleatorio desde allí. ${\displaystyle |\lambda |}$
2. El sucesor de la celda actual se elige de manera uniforme y aleatoria a partir del gancho . ${\displaystyle (i,j)}$ ${\displaystyle H_{\lambda }(i,j)\setminus \{(i,j)\}}$
3. Continúa hasta llegar a una celda de esquina . ${\displaystyle {\textbf {c}}}$

Proposición: Para una celda de esquina dada de , tenemos ${\displaystyle (a,b)}$ ${\displaystyle \lambda }$

${\displaystyle \mathbb {P} \left({\textbf {c}}=(a,b)\right)={\frac {e_{\mu }}{e_{\lambda }}},}$

dónde . ${\displaystyle \mu =\lambda \setminus \{(a,b)\}}$

Teniendo esto en cuenta, al sumar todas las celdas de las esquinas se obtiene el resultado afirmado. ${\displaystyle (a,b)}$ ${\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1}$

Conexión con representaciones del grupo simétrico

La fórmula de la longitud del gancho es de gran importancia en la teoría de representación del grupo simétrico , donde se sabe que el número es igual a la dimensión de la representación irreducible compleja asociada a . ${\displaystyle S_{n}}$ ${\displaystyle f^{\lambda }}$ ${\displaystyle V_{\lambda }}$ ${\displaystyle \lambda }$

Discusión detallada

Las representaciones irreducibles complejas del grupo simétrico están indexadas por particiones de (ver módulo Specht ). Sus caracteres están relacionados con la teoría de funciones simétricas a través del producto interno de Hall: ${\displaystyle V_{\lambda }}$ ${\displaystyle \lambda }$ ${\displaystyle n}$

${\displaystyle \chi ^{\lambda }(w)=\langle s_{\lambda },p_{\tau (w)}\rangle ,}$

donde es la función de Schur asociada a y es la función simétrica de suma de potencias de la partición asociada a la descomposición cíclica de . Por ejemplo, si entonces . ${\displaystyle s_{\lambda }}$ ${\displaystyle \lambda }$ ${\displaystyle p_{\tau (w)}}$ ${\displaystyle \tau (w)}$ ${\displaystyle w}$ ${\displaystyle w=(154)(238)(6)(79)}$ ${\displaystyle \tau (w)=(3,3,2,1)}$

Dado que la permutación identidad tiene la forma en notación cíclica, , la fórmula dice ${\displaystyle e}$ ${\displaystyle e=(1)(2)\cdots (n)}$ ${\displaystyle \tau (e)=(1,\ldots ,1)=1^{(n)}}$

${\displaystyle f^{\lambda }\,=\,\dim V_{\lambda }\,=\,\chi ^{\lambda }(e)\,=\,\langle s_{\lambda },p_{1^{(n)}}\rangle }$

La expansión de las funciones de Schur en términos de funciones simétricas monomiales utiliza los números de Kostka :

${\displaystyle s_{\lambda }=\sum _{\mu }K_{\lambda \mu }m_{\mu },}$

Entonces el producto interno con es , porque . Nótese que es igual a , de modo que al considerar la representación regular de , o combinatoriamente a partir de la correspondencia de Robinson–Schensted–Knuth . ${\displaystyle p_{1^{(n)}}=h_{1^{(n)}}}$ ${\displaystyle K_{\lambda 1^{(n)}}}$ ${\displaystyle \langle m_{\mu },h_{\nu }\rangle =\delta _{\mu \nu }}$ ${\displaystyle K_{\lambda 1^{(n)}}}$ ${\displaystyle f^{\lambda }=\dim V_{\lambda }}$ ${\displaystyle \textstyle \sum _{\lambda \vdash n}\left(f^{\lambda }\right)^{2}=n!}$ ${\displaystyle S_{n}}$

El cálculo también muestra que:

${\displaystyle (x_{1}+x_{2}+\cdots +x_{k})^{n}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }.}$

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 puede demostrarse también comprobando los coeficientes de cada monomio en ambos lados y usando la correspondencia de Robinson–Schensted–Knuth o, más conceptualmente, observando la descomposición de por módulos irreducibles y tomando caracteres. Véase dualidad de Schur–Weyl . ${\displaystyle p_{1^{(n)}}}$ ${\displaystyle \langle s_{\mu },s_{\nu }\rangle =\delta _{\mu \nu }}$ ${\displaystyle V^{\otimes n}}$ ${\displaystyle GL(V)}$

Prueba de la fórmula del gancho utilizando la fórmula de Frobenius

Fuente: ^[17]

Por las consideraciones anteriores

${\displaystyle p_{1^{(n)}}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }}$

de modo que

${\displaystyle \Delta (x)p_{1^{(n)}}=\sum _{\lambda \vdash n}\Delta (x)s_{\lambda }f^{\lambda }}$

¿Dónde está el determinante de Vandermonde ? ${\displaystyle \Delta (x)=\prod _{i<j}(x_{i}-x_{j})}$

Para la partición , defina for . Para lo siguiente, necesitamos al menos tantas variables como filas en la partición, por lo que a partir de ahora trabajaremos con variables . ${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})}$ ${\displaystyle l_{i}=\lambda _{i}+k-i}$ ${\displaystyle i=1,\ldots ,k}$ ${\displaystyle n}$ ${\displaystyle x_{1},\cdots ,x_{n}}$

Cada término es igual a ${\displaystyle \Delta (x)s_{\lambda }}$

${\displaystyle a_{(\lambda _{1}+k-1,\lambda _{2}+k-2,\dots ,\lambda _{k})}(x_{1},x_{2},\dots ,x_{k})\ =\ \det \!\left[{\begin{matrix}x_{1}^{l_{1}}&x_{2}^{l_{1}}&\dots &x_{k}^{l_{1}}\\x_{1}^{l_{2}}&x_{2}^{l_{2}}&\dots &x_{k}^{l_{2}}\\\vdots &\vdots &\ddots &\vdots \\x_{1}^{l_{k}}&x_{2}^{l_{k}}&\dots &x_{k}^{l_{k}}\end{matrix}}\right]}$

(Véase la función de Schur ). Puesto 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 proporciona una de las primeras demostraciones. ^[17] ${\displaystyle (l_{1},\ldots ,l_{k})}$ ${\displaystyle x_{1}^{l_{1}}\cdots x_{k}^{l_{k}}}$ ${\displaystyle \Delta (x)p_{1^{(n)}}}$ ${\displaystyle \left[\Delta (x)p_{1^{(n)}}\right]_{l_{1},\cdots ,l_{k}}}$ ${\displaystyle f^{\lambda }}$

Sólo queda simplificar este coeficiente. Multiplicando

${\displaystyle \Delta (x)\ =\ \sum _{w\in S_{n}}\operatorname {sgn}(w)x_{1}^{w(1)-1}x_{2}^{w(2)-1}\cdots x_{k}^{w(k)-1}}$

y

${\displaystyle p_{1^{(n)}}\ =\ (x_{1}+x_{2}+\cdots +x_{k})^{n}\ =\ \sum {\frac {n!}{d_{1}!d_{2}!\cdots d_{k}!}}x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots x_{k}^{d_{k}}}$

concluimos que nuestro coeficiente como

${\displaystyle \sum _{w\in S_{n}}\operatorname {sgn}(w){\frac {n!}{(l_{1}-w(1)+1)!\cdots (l_{k}-w(k)+1)!}}}$

que puede escribirse como

${\displaystyle {\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\sum _{w\in S_{n}}\operatorname {sgn}(w)\left[(l_{1})(l_{1}-1)\cdots (l_{1}-w(1)+2)\right]\left[(l_{2})(l_{2}-1)\cdots (l_{2}-w(2)+2)\right]\left[(l_{k})(l_{k}-1)\cdots (l_{k}-w(k)+2)\right]}$

La última suma es igual al siguiente determinante

${\displaystyle \det \left[{\begin{matrix}1&l_{1}&l_{1}(l_{1}-1)&\dots &\prod _{i=0}^{k-2}(l_{1}-i)\\1&l_{2}&l_{2}(l_{2}-1)&\dots &\prod _{i=0}^{k-2}(l_{2}-i)\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&l_{k}&l_{k}(l_{k}-1)&\dots &\prod _{i=0}^{k-2}(l_{k}-i)\end{matrix}}\right]}$

que se reduce en columna a un determinante de Vandermonde , y obtenemos la fórmula

${\displaystyle f^{\lambda }={\frac {n!}{l_{1}!\,l_{2}!\cdots l_{k}!}}\prod _{i<j}(l_{i}-l_{j}).}$

Nótese 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 : se muestra , donde el último producto se extiende sobre la fila n del diagrama de Young. ${\displaystyle l_{i}}$ ${\displaystyle {\frac {n!}{\prod h_{\lambda }(i,j)}}}$ ${\displaystyle \textstyle l_{i}!=\prod _{j>i}(l_{i}-l_{j})\cdot \prod _{j\leq \lambda _{i}}h_{\lambda }(i,j)}$ ${\displaystyle i}$

Conexión con las subsecuencias crecientes más largas

La fórmula de longitud de gancho también tiene aplicaciones importantes para el análisis de subsecuencias crecientes más largas en permutaciones aleatorias. Si denota una permutación aleatoria uniforme de orden , denota la longitud máxima de una subsecuencia creciente de , y denota el valor esperado (promedio) de , Anatoly Vershik y Sergei Kerov ^[18] e independientemente Benjamin F. Logan y Lawrence A. Shepp ^[19] demostraron que cuando es grande, 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 una tabla de Young aleatoria elegida de acuerdo con la medida de Plancherel . Dado que la definición de la medida de Plancherel involucra la cantidad , la fórmula de longitud de gancho puede usarse para realizar un análisis asintótico de la forma límite y, por lo tanto, también responder a la pregunta original. ${\displaystyle \sigma _{n}}$ ${\displaystyle n}$ ${\displaystyle L(\sigma _{n})}$ ${\displaystyle \sigma _{n}}$ ${\displaystyle \ell _{n}}$ ${\displaystyle L(\sigma _{n})}$ ${\displaystyle n}$ ${\displaystyle \ell _{n}}$ ${\displaystyle 2{\sqrt {n}}}$ ${\displaystyle f^{\lambda }}$

Las ideas de Vershik-Kerov y Logan-Shepp fueron refinadas posteriormente por Jinho Baik, Percy Deift y Kurt Johansson, quienes lograron un análisis mucho más preciso del comportamiento limitante de la longitud máxima creciente de la subsecuencia, demostrando un resultado importante que ahora se conoce como el teorema de Baik-Deift-Johansson. Su análisis nuevamente hace un uso crucial del hecho de que tiene varias fórmulas buenas, aunque en lugar de la fórmula de la longitud del gancho hizo uso de una de las expresiones determinantes. ${\displaystyle f^{\lambda }}$

Fórmulas relacionadas

La fórmula para el número de cuadros de Young de forma se derivó originalmente de la fórmula determinante de Frobenius en conexión con la teoría de la representación: ^[20] ${\displaystyle \lambda }$

${\displaystyle f(\lambda _{1},\ldots ,\lambda _{k})={\frac {n!\,\Delta (\lambda _{k},\lambda _{k-1}+1,\ldots ,\lambda _{1}+k-1)}{\lambda _{k}!\,(\lambda _{k-1}+1)!\cdots (\lambda _{1}+k-1)!}}.}$

Las longitudes de gancho 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 dada. ^[21] Si λ es una partición de algún entero p , una partición del plano inverso de n con forma λ se obtiene rellenando los recuadros del diagrama de Young con números enteros no negativos de modo que las entradas se sumen a n y no sean decrecientes a lo largo de cada fila y hacia abajo en cada columna. Las longitudes de gancho se pueden definir como con las tablas de Young. Si π _n denota el número de particiones del plano inverso de n con forma λ , entonces la función generadora se puede escribir como ${\displaystyle h_{1},\dots ,h_{p}}$

${\displaystyle \sum _{n=0}^{\infty }\pi _{n}x^{n}=\prod _{k=1}^{p}(1-x^{h_{k}})^{-1}}$

Stanley descubrió otra fórmula para la misma función generadora. ^[22] En general, si es cualquier conjunto parcial con elementos, la función generadora para particiones inversas es ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A}$

${\displaystyle {\frac {P(x)}{(1-x)(1-x^{2})\cdots (1-x^{n})}}}$

donde es un polinomio tal que es el número de extensiones lineales de . ${\displaystyle P(x)}$ ${\displaystyle P(1)}$ ${\displaystyle A}$

En el caso de una partición , estamos considerando el conjunto ordenado en sus celdas dado por la relación ${\displaystyle \lambda }$

${\displaystyle (i,j)\leq (i',j')\iff i\leq i'\qquad {\textrm {and}}\qquad j\leq j'}$.

Por lo tanto, una extensión lineal es simplemente una tabla de Young estándar, es decir ${\displaystyle P(1)=f^{\lambda }}$

Prueba de la fórmula del gancho utilizando la fórmula de Stanley

Combinando las dos fórmulas para las funciones generadoras tenemos

${\displaystyle {\frac {P(x)}{(1-x)(1-x^{2})\cdots (1-x^{n})}}=\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})^{-1}}$

Ambos lados convergen dentro del disco de radio uno y la siguiente expresión tiene sentido para ${\displaystyle |x|<1}$

${\displaystyle P(x)={\frac {\prod _{k=1}^{n}(1-x^{k})}{\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})}}.}$

Sería violento introducir 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

${\displaystyle P(1)=\lim _{x\to 1}{\frac {\prod _{k=1}^{n}(1-x^{k})}{\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})}}.}$

Aplicando la regla de L'Hôpital se obtiene la fórmula de la longitud del gancho. ${\displaystyle n}$

${\displaystyle P(1)={\frac {n!}{\prod _{(i,j)\in \lambda }h_{(i,j)}}}.}$

Fórmula de longitud de gancho para cuadros semiestándar

El polinomio de Schur es la función generadora de tablas de Young semiestándar con forma y entradas en . Al especializarlo en se obtiene la cantidad de tablas semiestándar, que se pueden escribir en términos de longitudes de gancho: ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{k})}$ ${\displaystyle \lambda }$ ${\displaystyle \{1,\ldots ,k\}}$ ${\displaystyle x_{i}=1}$

${\displaystyle s_{\lambda }(1,\ldots ,1)\ =\ \prod _{(i,j)\in \mathrm {Y} (\lambda )}{\frac {k-i+j}{h_{\lambda }(i,j)}}.}$

El diagrama de Young corresponde a una representación irreducible del grupo lineal especial , y el polinomio de Schur es también el carácter de la matriz diagonal que actúa 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 . ${\displaystyle \lambda }$ ${\displaystyle \mathrm {SL} _{k}(\mathbb {C} )}$ ${\displaystyle \mathrm {diag} (x_{1},\ldots ,x_{k})}$

Podemos refinar esto tomando la especialización principal de la función de Schur en las variables  : ${\displaystyle 1,t,t^{2}\!,t^{3}\!,\ldots }$

${\displaystyle s_{\lambda }(1,t,t^{2},\ldots )\ =\ {\frac {t^{n\left(\lambda \right)}}{\prod _{(i,j)\in Y(\lambda )}(1-t^{h_{\lambda }(i,j)})}},}$

donde para la partición conjugada . ${\displaystyle n(\lambda )=\sum _{i}(i{-}1)\lambda _{i}=\sum _{i}{\tbinom {\lambda _{i}'}{2}}}$ ${\displaystyle \lambda '}$

Fórmula de forma oblicua

Hay una generalización de esta fórmula para formas oblicuas, ^[23]

${\displaystyle s_{\lambda /\mu }(1,t,t^{2},\cdots )=\sum _{S\in E(\lambda /\mu )}\prod _{(i,j)\in \lambda \setminus S}{\frac {t^{\lambda _{j}'-i}}{1-t^{h(i,j)}}}}$

donde la suma se toma sobre diagramas excitados de forma y cajas distribuidas de acuerdo a . ${\displaystyle \lambda }$ ${\displaystyle \mu }$

^{Okounkov y Olshanski [24]} dan una variación del mismo tema en la forma

${\displaystyle {\frac {\dim \lambda /\mu }{\dim \lambda }}={\frac {s_{\mu }^{*}(\lambda )}{|\lambda |!/|\mu |!}},}$

donde está la llamada función de Schur desplazada . ${\displaystyle s_{\mu }^{*}}$ ${\displaystyle s_{\mu }^{*}(x_{1},\dots ,x_{n})={\frac {\det[(x_{i}+n-1)!/(\mu _{j}+n-j)!]}{\det[(x_{i}+n-i)!/(n-j)!]}}}$

Generalización ad-Posets completos

Los diagramas de Young pueden considerarse ideales de orden finito en el conjunto parcial , y las tablas de Young estándar son sus extensiones lineales . Robert Proctor ha dado una generalización de la fórmula de longitud de gancho para contar extensiones lineales de una clase más grande de conjuntos parciales generalizando tanto árboles como diagramas oblicuos. ^{[25] [26]} ${\displaystyle \mathbb {N} \times \mathbb {N} }$

Referencias

1. G. Frobenius. Uber die charaktere der symmetrischer gruppe, Preuss. &anuncio. Semana sentarse. (1900), 516–534.
2. A. Young. Análisis sustitucional cuantitativo II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397.
3. PA MacMahon. “Combinatory Analysis”, Cambridge Univ. Press, Londres/Nueva York, 1916; reimpreso por Chelsea, Nueva York, 1960.
4. Sagan, Bruce (2001). El grupo simétrico. Representaciones, algoritmos combinatorios y funciones simétricas, 2.ª edición . Springer-Verlag. ISBN 0-387-95067-2.
5. Knuth, Donald (1973). El arte de la programación informática, volumen 3: Ordenación y búsqueda, 3.ª edición, Addison–Wesley, pág. 63
6. Hillman, AP; Grassl, RM (1976). "Particiones del plano inverso y números de gancho de tabla". Journal of Combinatorial Theory . Serie A. 21 (2): 216–221. doi : 10.1016/0097-3165(76)90065-0 .
7. Greene, Curtis ; Nijenhuis, Albert ; Wilf, Herbert S. (1979). "Una prueba probabilística de una fórmula para el número de cuadros de Young de una forma dada". Avances en Matemáticas . 31 (1): 104–109. doi : 10.1016/0001-8708(79)90023-9 .
8. JB Remmel. Pruebas biyectivas de fórmulas para el número de tablas de Young estándar, Álgebra lineal y multilineal 11 (1982), 45–100.
9. Franzblau, DS y Zeilberger, D. (1982). Una prueba biyectiva de la fórmula de longitud de gancho. J. Algorithms 3, 317–343.
10. Zeilberger, Doron (1984). "Una biyección de longitudes de gancho cortas inspirada en la prueba de Greene–Nijenhuis–Wilf". Matemáticas discretas . 51 (1): 101–108. doi : 10.1016/0012-365X(84)90027-X .
11. Pak, IM y Stoyanovskii, AV (1992). Una prueba biyectiva de la fórmula de la longitud del gancho. Funct. Anal. Appl. 24.
12. Novelli, J.-C., Pak, IM y Stoyanovskii, AV (1997). Una prueba biyectiva directa de la fórmula de longitud de gancho. Matemáticas discretas y ciencias de la computación teórica 1, 1997, 53–67.
13. RM Thrall. Un problema combinatorio, Michigan Math. J. 1 (1952), 81–88.
14. Sagan, B. Sobre la selección de una tabla de Young desplazada aleatoriamente. J. Algorithms 1, 3 (1980), 213–234.
15. Sagan, BE, y Yeh, YN Algoritmos probabilísticos para árboles. Fibonacci Quart. 27, 3 (1989), 201–208.
16. Knuth, Donald (1973), El arte de la programación informática, volumen 3: Ordenación y búsqueda, 3.ª edición , Addison–Wesley, pág. 63, ISBN 0-201-03803-X.
17. Fulton, William, 1939- (1991). Teoría de la representación: un primer curso . Harris, Joe, 1951-. Nueva York: Springer-Verlag. pp. 49-50. ISBN 0387974954.OCLC 22861245  .{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
18. Vershik, AM; Kerov, CV (1977), "Asintótica de la medida de Plancher del grupo simétrico y una forma límite para tablas de Young", Dokl. Akad. Nauk SSSR 233: 1024–1027
19. Logan, BF; Shepp, LA (1977). "Un problema variacional para tablas de Young aleatorias". Avances en Matemáticas . 26 (2): 206–222. doi : 10.1016/0001-8708(77)90030-5 .
20. Knuth, Donald (1973), El arte de la programación informática , vol. 3 (1.ª ed.), Addison–Wesley, págs. 61–62
21. Stanley, Richard P. (1971), "Teoría y aplicaciones de particiones planas, 2", Estudios en Matemáticas Aplicadas , 50 : 259–279, doi :10.1002/sapm1971503259
22. RP Stanley, "Estructuras ordenadas y particiones", tesis doctoral, Universidad de Harvard, 1971
23. Morales, Alejandro H.; Pak, Igor ; Panova, Greta (2018). "Fórmulas de gancho para formas oblicuas I. q-análogos y biyecciones". Journal of Combinatorial Theory . Serie A. 154 : 350–405. arXiv : 1512.08348 . doi : 10.1016/j.jcta.2017.09.002 .
24. Okounkov, A. y Olshanski, G. Funciones de Schur desplazadas, Algebra I Analiz , 9.2 (1997), 73-146.
25. Proctor, Robert (1999). "Clasificación mediante diagrama de Dynkin de redes de Bruhat λ-minúsculas y de conjuntos parciales d-completos". Journal of Algebraic Combinatorics . 9 : 61–94. doi : 10.1023/A:1018615115006 .
26. Kim, Jang Soo; Yoo, Meesue (2019). "Propiedad de longitud de gancho de conjuntos parciales d-completos mediante integrales q". Journal of Combinatorial Theory . Serie A. 162 : 167–221. arXiv : 1708.09109 . doi : 10.1016/j.jcta.2018.11.003 . S2CID  57759574.

Enlaces externos

• Las sorprendentes matemáticas de las subsucesiones crecientes más largas, de Dan Romik. Contiene análisis de la fórmula de la longitud del gancho y varias de sus variantes, con aplicaciones a las matemáticas de las subsucesiones crecientes más largas.