Hispanopedia Wiki
Articulo de referencia

El teorema maestro de MacMahon

En matemáticas, el teorema maestro de MacMahon ( MMT ) es un resultado de combinatoria enumerativa y álgebra lineal . Fue descubierto por Percy MacMahon y demostrado en su monog...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas, el teorema maestro de MacMahon ( MMT ) es un resultado de combinatoria enumerativa y álgebra lineal . Fue descubierto por Percy MacMahon y demostrado en su monografía Análisis combinatorio (1916). Se utiliza frecuentemente para derivar identidades binomiales, en particular la identidad de Dixon .

Fondo

En la monografía, MacMahon encontró tantas aplicaciones para su resultado que lo denominó "un teorema maestro en la teoría de permutaciones". Explicó el título de la siguiente manera: "un teorema maestro por la forma magistral y rápida en que aborda diversas cuestiones que, de otro modo, serían difíciles de resolver".

El resultado fue derivado nuevamente (con la debida atribución) en varias ocasiones, sobre todo por I.J. Good , quien lo obtuvo a partir de su generalización multilineal del teorema de inversión de Lagrange . El MMT también fue popularizado por Carlitz , quien halló una versión en serie de potencias exponenciales . En 1962, Good encontró una demostración breve de la identidad de Dixon a partir del MMT. En 1969, Cartier y Foata hallaron una nueva demostración del MMT combinando ideas algebraicas y biyectivas (basadas en la tesis de Foata) y aplicaciones adicionales a la combinatoria de palabras , introduciendo el concepto de trazas . Desde entonces, el MMT se ha convertido en una herramienta estándar en la combinatoria enumerativa.

Aunque se conocen diversas identidades q -Dixon desde hace décadas, a excepción de una extensión de Krattenthaler-Schlosser (1999), el análogo q propio de la MMT seguía siendo esquivo. Tras la extensión cuántica de Garoufalidis-Lê-Zeilberger (2006), Foata-Han, Konvalinka-Pak y Etingof-Pak desarrollaron varias extensiones no conmutativas . Hai-Lorentz, Hai-Kriegk-Lorenz, Konvalinka-Pak y otros también encontraron conexiones con el álgebra de Koszul y los cuasideterminantes .

Finalmente, según JD Louck, el físico teórico Julian Schwinger redescubrió la MMT en el contexto de su enfoque de función generadora para la teoría del momento angular de sistemas de muchas partículas . Louck escribe:

Es el Teorema Maestro de MacMahon el que unifica las propiedades del momento angular de los sistemas compuestos en la formación binaria de dichos sistemas a partir de constituyentes más elementales. [ 1 ]

Declaración

DejarA=(aij)metro×metro{\displaystyle A=(a_{ij})_{m\times m}}Sea una matriz compleja y dejemos queincógnita1,…,incógnitametro{\displaystyle x_{1},\ldots ,x_{m}}sean variables formales. Para cualquier secuencia de enteros no negativosk1,…,kmetro{\displaystyle k_{1},\dots ,k_{m}}Consideremos el coeficiente asociado de un polinomio:

GRAMO(k1,…,kmetro)=[incógnita1k1⋯incógnitametrokmetro]∏i=1metro(∑j=1metroaijincógnitaj)ki.{\displaystyle G(k_{1},\dots ,k_{m})\,=\,{\bigl [}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}{\bigr ]}\,\prod _{i=1}^{m}\left(\sum _{j=1}^{m}a_{ij}x_{j}\right)^{k_{i}}.}

(Aquí la notación[F]gramo{\displaystyle [f]g}significa "el coeficiente de monomio"F{\displaystyle f}engramo{\displaystyle g}".) Dejart1,…,tmetro{\displaystyle t_{1},\ldots ,t_{m}}sea ​​otro conjunto de variables formales, y dejemos queT=diagramo(t1,…,tmetro){\displaystyle T=\mathrm {diag} (t_{1},\dots ,t_{m})}Sea una matriz diagonal . Entonces

∑(k1,…,kmetro)GRAMO(k1,…,kmetro)t1k1⋯tmetrokmetro=1det(Imetro−TA),{\displaystyle \sum _{(k_{1},\dots ,k_{m})}G(k_{1},\dots ,k_{m})\,t_{1}^{k_{1}}\cdots t_{m}^{k_{m}}\,=\,{\frac {1}{\det(I_{m}-TA)}},}

donde la suma se extiende sobre todos los vectores enteros no negativos(k1,…,kmetro){\displaystyle (k_{1},\dots ,k_{m})}, yImetro{\displaystyle I_{m}}denota la matriz identidad de tamañometro{\displaystyle m}.

Interpretación combinatoria

Para calcularGRAMO(k1,…,kmetro){\displaystyle G(k_{1},\dots ,k_{m})}Se puede construir la siguiente matriz repetida:A=[[a11⋯a1metro⋮⋮a11⋯a1metro]⋮[ametro1⋯ametrometro⋮⋮ametro1⋯ametrometro]]{\displaystyle A={\begin{bmatrix}{\begin{bmatrix}a_{11}&\cdots &a_{1m}\\\vdots &&\vdots \\a_{11}&\cdots &a_{1m}\end{bmatrix}}\\\vdots \\{\begin{bmatrix}a_{m1}&\cdots &a_{mm}\\\vdots &&\vdots \\a_{m1}&\cdots &a_{mm}\end{bmatrix}}\end{bmatrix}}}donde eli{\displaystyle i}-fila deA{\displaystyle A}se repite paraki{\displaystyle k_{i}}veces. Luego, se construyen todas las formas posibles de elegir exactamente un elemento por fila, de manera que se elijan los elementos de la primera columna.k1{\displaystyle k_{1}}veces, se seleccionan los elementos de la segunda columna.k2{\displaystyle k_{2}}veces, y así sucesivamente. Finalmente, para cada una de estas maneras, se multiplican los elementos escogidos, y la suma de todos estos productos esGRAMO(k1,…,kmetro){\displaystyle G(k_{1},\dots ,k_{m})}.

Aplicaciones

CuandoA{\displaystyle A}es la identidad, esto da una identidad de serie geométrica multivariada:∏i=1metro11−ti=∑k1,…,kmetro≥0t1k1⋯tmetrokmetro{\displaystyle \prod _{i=1}^{m}{\frac {1}{1-t_{i}}}=\sum _{k_{1},\ldots ,k_{m}\geq 0}t_{1}^{k_{1}}\cdots t_{m}^{k_{m}}}Configuraciónt1,…,tmetro=1{\displaystyle t_{1},\dots ,t_{m}=1}, obtenemos una expresión∑(k1,…,kmetro)GRAMO(k1,…,kmetro)=1det(Imetro−A){\displaystyle \sum _{(k_{1},\dots ,k_{m})}G(k_{1},\dots ,k_{m})\,=\,{\frac {1}{\det(I_{m}-A)}}} DejarA=(011101110){\displaystyle A={\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}}}, entoncesGRAMO(norte,norte,norte)=[incógnita1norteincógnita2norteincógnita3norte](incógnita2+incógnita3)norte(incógnita1+incógnita3)norte(incógnita1+incógnita2)norte{\displaystyle G(n,n,n)=\left[x_{1}^{n}x_{2}^{n}x_{3}^{n}\right]\left(x_{2}+x_{3}\right)^{n}\left(x_{1}+x_{3}\right)^{n}\left(x_{1}+x_{2}\right)^{n}}es el número de trastornos de la palabraincógnita1norteincógnita2norteincógnita3norte{\displaystyle x_{1}^{n}x_{2}^{n}x_{3}^{n}}, es decir, formas de permutar el3norte{\displaystyle 3n}símbolos deincógnita1norteincógnita2norteincógnita3norte{\displaystyle x_{1}^{n}x_{2}^{n}x_{3}^{n}}, de tal manera que cadaincógnita1{\displaystyle x_{1}}terrenos en el lugar previamente ocupado por algunosincógnita2{\displaystyle x_{2}}oincógnita3{\displaystyle x_{3}}, etc. Según el teorema maestro de MacMahon,GRAMO(norte,norte,norte)=∑k=0norte(nortek)3=[t1nortet2nortet3norte]11−t1t2−t1t3−t2t3−2t1t2t3{\displaystyle G(n,n,n)=\sum _{k=0}^{n}{\binom {n}{k}}^{3}=[t_{1}^{n}t_{2}^{n}t_{3}^{n}]{\frac {1}{1-t_{1}t_{2}-t_{1}t_{3}-t_{2}t_{3}-2t_{1}t_{2}t_{3}}}}

La identidad de Dixon

Consideremos una matriz

A=(01−1−1011−10).{\displaystyle A={\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}}.}

Calcula los coeficientes G (2 n ,  2 n ,  2 n ) directamente a partir de la definición:

GRAMO(2norte,2norte,2norte)=[incógnita12norteincógnita22norteincógnita32norte](incógnita2−incógnita3)2norte(incógnita3−incógnita1)2norte(incógnita1−incógnita2)2norte=∑k=02norte(−1)k(2nortek)3,{\displaystyle {\begin{aligned}G(2n,2n,2n)&={\bigl [}x_{1}^{2n}x_{2}^{2n}x_{3}^{2n}{\bigl ]}(x_{2}-x_{3})^{2n}(x_{3}-x_{1})^{2n}(x_{1}-x_{2})^{2n}\\[6pt]&=\,\sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3},\end{aligned}}}

donde la última igualdad se deduce del hecho de que en el lado derecho tenemos el producto de los siguientes coeficientes:

[incógnita2kincógnita32norte−k](incógnita2−incógnita3)2norte,  [incógnita3kincógnita12norte−k](incógnita3−incógnita1)2norte,  [incógnita1kincógnita22norte−k](incógnita1−incógnita2)2norte,{\displaystyle [x_{2}^{k}x_{3}^{2n-k}](x_{2}-x_{3})^{2n},\ \ [x_{3}^{k}x_{1}^{2n-k}](x_{3}-x_{1})^{2n},\ \ [x_{1}^{k}x_{2}^{2n-k}](x_{1}-x_{2})^{2n},}

que se calculan a partir del teorema del binomio . Por otro lado, podemos calcular el determinante explícitamente:

det(I−TA)=det(1−t1t1t21−t2−t3t31)=1+(t1t2+t1t3+t2t3).{\displaystyle \det(I-TA)\,=\,\det {\begin{pmatrix}1&-t_{1}&t_{1}\\t_{2}&1&-t_{2}\\-t_{3}&t_{3}&1\end{pmatrix}}\,=\,1+{\bigl (}t_{1}t_{2}+t_{1}t_{3}+t_{2}t_{3}{\bigr )}.}

Por lo tanto, mediante la MMT, tenemos una nueva fórmula para los mismos coeficientes:

GRAMO(2norte,2norte,2norte)=[t12nortet22nortet32norte](−1)3norte(t1t2+t1t3+t2t3)3norte=(−1)norte(3nortenorte,norte,norte),{\displaystyle {\begin{aligned}G(2n,2n,2n)&={\bigl [}t_{1}^{2n}t_{2}^{2n}t_{3}^{2n}{\bigl ]}(-1)^{3n}{\bigl (}t_{1}t_{2}+t_{1}t_{3}+t_{2}t_{3}{\bigr )}^{3n}\\[6pt]&=(-1)^{n}{\binom {3n}{n,n,n}},\end{aligned}}}

donde la última igualdad se deduce del hecho de que necesitamos usar un número igual de veces los tres términos en la potencia. Ahora, igualando las dos fórmulas para los coeficientes G (2 n ,  2 n ,  2 n ) obtenemos una versión equivalente de la identidad de Dixon:

∑k=02norte(−1)k(2nortek)3=(−1)norte(3nortenorte,norte,norte).{\displaystyle \sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}^{3}=(-1)^{n}{\binom {3n}{n,n,n}}.}

Véase también

Referencias

  1. ↑ Louck, James D. (2008). Simetría unitaria y combinatoria . Singapur: World Scientific. págs.  viii. ISBN 978-981-281-472-2.
Lecturas relacionadas
6 articulos
Combinatoria enumerativaLa combinatoria enumerativa es un área de la combinatoria que se ocupa del número de formas en que se pueden formar ciertos patrones. Dos ejemplos ...Álgebra linealEn el espacio euclidiano tridimensional , estos tres planos representan soluciones de ecuaciones lineales y su intersección representa el conjunto ...Percy Alexander MacMahonPercy Alexander MacMahonPercy Alexander MacMahon (26 de septiembre de 1854 - 25 de diciembre de 1929) fue un matemático inglés , especialmente conocido en relación con las...{\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}.}Dixon's identityIn mathematics, Dixon's identity (or Dixon's theorem or Dixon's formula) is any of several different but closely related identities proved by A. C....IJ BuenoIJ BuenoIrving John Good (9 de diciembre de 1916 – 5 de abril de 2009) [1] [2] fue un matemático británico que trabajó como criptólogo en Bletchley Park co...{\displaystyle z=f(w)}Teorema de inversión de LagrangeEn análisis matemático , el teorema de inversión de Lagrange , también conocido como fórmula de Lagrange-Bürmann , proporciona la expansión en seri...