Fórmula de longitud del gancho

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

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 da el número de cuadros de Young semiestándar, que es una especialización de un polinomio de Schur .

Definiciones y declaración

Sea una partición de . Se acostumbra interpretar gráficamente como un diagrama de Young , es decir, una matriz de celdas cuadradas justificadas a la izquierda con filas de longitudes . Un cuadro de formas de Young (estándar) 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 posición , en la ésima fila y la ésima columna, el gancho es el conjunto de celdas tales que y o y . La longitud del gancho es el número de celdas que hay . ${\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 gancho expresa el número de cuadros de forma estándar de Young , 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 está sobre todas las celdas del diagrama de Young. ${\displaystyle (i,j)}$

Ejemplos

Un cuadro 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 los ganchos proporciona el número de cuadros estándar de Young 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 que suben (U) intercalados con escalones que bajan (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 forma 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 corresponden 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 conocida fórmula del producto. ${\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 longitud del anzuelo es particularmente simple y elegante. Frobenius y Young dedujeron de forma independiente una fórmula menos conveniente que se expresa en términos de un determinante en 1900 y 1902, respectivamente, utilizando métodos algebraicos. ^{[1] [2]} MacMahon encontró una prueba alternativa para la fórmula de Young-Frobenius en 1916 utilizando métodos diferentes. ^[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. 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 demostraron la identidad. El sábado fueron a la Universidad de Michigan, donde Frame presentó su nuevo resultado tras una conferencia de Robinson. ¡Esto sorprendió a Thrall, que estaba entre el público, 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 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 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 de anzuelos de Stanley , que se sabe que implica la fórmula de longitud del anzuelo. ^[6] Greene , Nijenhuis y Wilf encontraron una prueba probabilística utilizando el recorrido del gancho en el que las longitudes de los ganchos aparecen de forma natural en 1979. ^[7] Remmel adaptó la prueba original de Frame-Robinson-Thrall a 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 recorrido del gancho de 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] [4]}

Mientras tanto, la fórmula de la longitud del anzuelo se ha generalizado de varias maneras. RM Thrall encontró el análogo a la fórmula de longitud del gancho para cuadros de Young desplazados en 1952. ^[13] Sagan dio una prueba de recorrido del gancho desplazado para la fórmula de longitud del gancho para cuadros de Young desplazados en 1980. ^[14] Sagan y Yeh demostraron la fórmula de longitud del gancho para árboles binarios utilizando la caminata de gancho en 1989. ^[15] Proctor dio una generalización poset (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 un cuadro es el más pequeño en su gancho y llena la forma del cuadro 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 etiquetas en árboles que satisfacen propiedades de monotonicidad análogas a las de un cuadro de Young. En este caso, los eventos "gancho" en cuestión son en realidad eventos independientes.

Prueba probabilística mediante el recorrido 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 demostrarlo . Primero, ${\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 abarca todos los diagramas de Young obtenidos eliminando una celda de la esquina. (La entrada máxima del cuadro de forma de Young se produce en una de sus celdas de las esquinas, por lo que al eliminarla se obtiene un cuadro de forma de Young ). ${\displaystyle \mu }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$

Definimos y , por lo que basta con 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 se puede ver 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 de 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 del 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. Elija una celda uniformemente al azar de las celdas. Comienza la caminata aleatoria desde allí. ${\displaystyle |\lambda |}$
2. El sucesor de la celda actual se elige uniformemente al azar del gancho . ${\displaystyle (i,j)}$ ${\displaystyle H_{\lambda }(i,j)\setminus \{(i,j)\}}$
3. Continúe hasta llegar a una celda de la 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)\}}$

Dado esto, la suma de todas las celdas de las esquinas da como se afirma. ${\displaystyle (a,b)}$ ${\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1}$

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 se sabe que el número es igual a la dimensión de la representación compleja irreducible asociada al mismo . ${\displaystyle S_{n}}$ ${\displaystyle f^{\lambda }}$ ${\displaystyle V_{\lambda }}$ ${\displaystyle \lambda }$

Discusión detallada

Las representaciones complejas irreductibles 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 del ciclo 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 de 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 funciones de Schur en términos de funciones simétricas monomio utiliza los números de Kostka :

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

Entonces el producto interno con es , porque . Tenga en cuenta que es igual a , de modo que al considerar la representación regular de , o combinatoriamente de la correspondencia 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 utilizando 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 por módulos irreducibles y tomando caracteres. Véase dualidad 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 haya 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]}$

(Ver función de Schur ). Dado que el vector es diferente para cada partición, esto significa que el coeficiente de in , denotado , es igual a . Esto se conoce como la fórmula del carácter de Frobenius y proporciona una de las primeras pruebas. ^[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 se puede escribir 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]}$

Esta ú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]}$

cuya columna se reduce 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}).}$

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 a la forma deseada : se muestra , donde el último producto pasa por la octava fila 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 a subsecuencias crecientes más largas.

La fórmula de la longitud del gancho también tiene aplicaciones importantes para el análisis de subsecuencias crecientes más largas en permutaciones aleatorias. Si denota una permutación de orden uniformemente aleatoria , 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 ]} demostró 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 Robinson-Schensted a un problema sobre la forma límite de un cuadro aleatorio de Young elegido según la medida de Plancherel . Dado que la definición de medida de Plancherel implica la cantidad , la fórmula de longitud del gancho se puede utilizar para realizar un análisis asintótico de la forma límite y así responder también 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 posteriormente refinadas 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, lo que demuestra un resultado importante ahora conocido. como el teorema de Baik-Deift-Johansson. Su análisis vuelve a hacer un uso crucial del hecho de que tiene varias buenas fórmulas, aunque en lugar de la fórmula de la longitud del anzuelo utilizó una de las expresiones determinantes. ${\displaystyle f^{\lambda }}$

Fórmulas relacionadas

La fórmula para el número de cuadros de forma de Young se derivó originalmente de la fórmula determinante de Frobenius en relació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 los ganchos también se pueden utilizar para dar una representación del producto a la función generadora del número de particiones del plano inverso de una forma determinada. ^[21] Si λ es una partición de algún número entero p , una partición de plano inverso de n con forma λ se obtiene completando los cuadros en el diagrama de Young con números enteros no negativos de modo que las entradas sumen n y no sean decrecientes. a lo largo de cada fila y hacia abajo en cada columna. Las longitudes de los ganchos se pueden definir como en los cuadros 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 hay algún poset 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 poset 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'}$.

Entonces una extensión lineal es simplemente un cuadro estándar de Young, 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 insertar 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)}})}}.}$

La aplicación de los tiempos de la regla de L'Hôpital produce la fórmula de la longitud del anzuelo ${\displaystyle n}$

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

Fórmula de longitud de gancho de cuadro semiestándar

El polinomio de Schur es la función generadora de cuadros de Young semiestándar con forma y entradas en . Al especializarse en esto, se obtiene el número de cuadros 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 irreductible, 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 sesgada

Existe una generalización de esta fórmula para formas sesgadas, ^[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 según . ${\displaystyle \lambda }$ ${\displaystyle \mu }$

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

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

¿Dónde 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-postets completos

Los diagramas de Young pueden considerarse ideales de orden finito en el poset , y los cuadros de Young estándar son sus extensiones lineales . Robert Proctor ha dado una generalización de la fórmula de longitud del gancho para contar extensiones lineales de una clase más grande de posets que generalizan tanto árboles como diagramas sesgados. ^{[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. joven. Análisis cuantitativo de sustitución II, Proc. Matemáticas de Londres. Sot., Ser. 1, 35 (1902), 361–397.
3. PA MacMahon. “Análisis combinatorio”, Universidad de Cambridge. 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: clasificación y búsqueda, tercera edición, Addison – Wesley, pág. 63
6. Hillman, AP; Grassl, RM (1976). "Particiones del plano inverso y números de ganchos del cuadro". Revista de teoría combinatoria . 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 determinada". 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 cuadros estándar de Young, Linear and Multilinear Algebra 11 (1982), 45-100.
9. Franzblau, DS y Zeilberger, D. (1982). Una prueba biyectiva de la fórmula de la longitud del gancho. J. Algoritmos 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. Función. Anal. Aplica. 24.
12. 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.
13. RM esclavo. Un problema combinatorio, Michigan Math. J. 1 (1952), 81–88.
14. Sagan, B. Sobre la selección de un cuadro de Young desplazado aleatoriamente. J. Algoritmos 1, 3 (1980), 213–234.
15. Sagan, BE y Yeh, YN Algoritmos probabilísticos para árboles. Cuarto de Fibonacci. 27, 3 (1989), 201–208.
16. 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, 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. págs. 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 Plancheral del grupo simétrico y una forma limitante para cuadros de Young", Dokl. Akád. Nauk SSSR 233: 1024-1027
19. Logan, novio; Shepp, LA (1977). "Un problema variacional para cuadros aleatorios de Young". 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 de Matemática Aplicada , 50 : 259–279, doi :10.1002/sapm1971503259
22. RP Stanley, Tesis doctoral "Estructuras y particiones ordenadas", Universidad de Harvard, 1971
23. Morales, Alejandro H.; Pak, Igor ; Panova, Greta (2018). "Fórmulas de gancho para formas sesgadas I. q-análogos y biyecciones". Revista de teoría combinatoria . 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, Álgebra I Analiz , 9.2 (1997), 73-146.
25. Supervisor, Robert (1999). "Clasificación del 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 .
26. Kim, Jang Soo; Yoo, Meesue (2019). "Propiedad de longitud del gancho de posets d-completos mediante integrales q". Revista de teoría combinatoria . 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 subsecuencias crecientes más largas de 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.