Théorème principal de MacMahon

En mathématiques, le théorème principal de MacMahon (MacMahon's master theorem ou MMT) est un résultat mêlant combinatoire énumérative (en) et algèbre linéaire. Il a été découvert par Percy MacMahon et prouvé dans sa monographie Analyse combinatoire (1916). Il est souvent utilisé pour dériver des identités binomiales, notamment l'identité de Dixon.

Contexte

Dans la monographie Analyse combinatoire, MacMahon a trouvé tellement d'applications de son résultat qu'il l'a désigné comme « un théorème essentiel de la théorie des permutations » (a master theorem in the Theory of Permutations). Il a expliqué cette appellation de la façon suivante : « un théorème essentiel pour la manière magistrale et rapide avec laquelle il traite diverses questions difficiles à résoudre autrement ».

Le théorème (MMT) a été redémontré à plusieurs reprises (tout en l'attribuant à MacMahon), notamment par Irving John Good qui l'a déduit de sa généralisation multilinéaire du théorème d'inversion de Lagrange. Le MMT a également été popularisé par Carlitz qui en a trouvé une version en série génératrice exponentielle. En 1962, Good trouva une façon courte de déduire l'identité de Dixon à partir du MMT. En 1969, Pierre Cartier et Dominique Foata ont trouvé une nouvelle preuve de MMT en combinant des idées algébriques et bijectives (élaborées à partir de la thèse de Foata) et de nouvelles applications à la combinatoire des mots, introduisant le concept de traces. Depuis, le MMT est devenu un outil standard en combinatoire énumérative.

Bien que diverses q-identités de Dixon soient connues depuis des décennies, le q-analogue approprié du MMT reste insaisissable, à l'exception d'une extension de Krattenthaler-Schlosser (1999). Après la version quantique de Garoufalidis-Lê-Zeilberger (2006), un certain nombre de généralisation non commutatives ont été développées par Foata-Han, Konvalinka-Pak et Etingof-Pak. D'autres liens avec les algèbres de Koszul (en) et les quasi-déterminants (en) ont également été établis par Hai-Lorentz, Hai-Kriegk-Lorenz, Konvalinka -Pak et d'autres.

Enfin, d'après James D. Louck, le physicien théoricien Julian Schwinger a redécouvert le MMT dans le cadre de son approche de la théorie du moment cinétique des systèmes avec de nombreuses particules (en) par les fonctions génératrices. Louck écrit :

« It is the MacMahon Master Theorem that unifies the angular momentum properties of composite systems in the binary build-up of such systems from more elementary constituents[1]. »

« C'est le théorème principal de MacMahon qui unifie les propriétés relatives au moment cinétique des systèmes composites dans la construction binaire de tels systèmes à partir de constituants plus élémentaires. »

Énoncé précis

Soit A = ( a i j ) m × m {\displaystyle A=(a_{ij})_{m\times m}} une matrice complexe et soient x 1 , … , x m {\displaystyle x_{1},\ldots ,x_{m}} des indéterminées. On considère un coefficient

G ( k 1 , … , k m ) = [ x 1 k 1 ⋯ x m k m ] ∏ i = 1 m ( a i 1 x 1 + ⋯ + a i m x m ) k i . {\displaystyle G(k_{1},\dots ,k_{m})\,=\,{\bigl [}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}{\bigr ]}\,\prod _{i=1}^{m}{\bigl (}a_{i1}x_{1}+\dots +a_{im}x_{m}{\bigl )}^{k_{i}}.}

(Ici la notation [ f ] g {\displaystyle [f]g} désigne le coefficient du monôme f {\displaystyle f} dans g {\displaystyle g} .) On se donne une autre famille d'indéterminées t 1 , … , t m {\displaystyle t_{1},\ldots ,t_{m}} et on forme la matrice diagonale T = ( δ i j t i ) m × m {\displaystyle T=(\delta _{ij}t_{i})_{m\times m}} . Alors

∑ ( k 1 , … , k m ) G ( k 1 , … , k m ) t 1 k 1 ⋯ t m k m = 1 det ( I m − T A ) , {\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)}},}

où la somme porte sur toutes les m {\displaystyle m} -listes d'entiers naturels ( k 1 , … , k m ) {\displaystyle (k_{1},\dots ,k_{m})} et I m {\displaystyle I_{m}} désigne la matrice identité de taille m {\displaystyle m} .

Dérivation de l'identité de Dixon

On considère la matrice

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

On calcule les coefficients G(2n, 2n, 2n) directement d'après la définition :

G ( 2 n , 2 n , 2 n ) = [ x 1 2 n x 2 2 n x 3 2 n ] ( x 2 − x 3 ) 2 n ( x 3 − x 1 ) 2 n ( x 1 − x 2 ) 2 n = ∑ k = 0 2 n ( − 1 ) k ( 2 n k ) 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}}}

où la dernière égalité provient du fait qu'au membre de droite on a le produit des coefficients suivants :

[ x 2 k x 3 2 n − k ] ( x 2 − x 3 ) 2 n ,     [ x 3 k x 1 2 n − k ] ( x 3 − x 1 ) 2 n ,     [ x 1 k x 2 2 n − k ] ( x 1 − x 2 ) 2 n , {\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},}

qui sont calculés à l'aide de la formule du binôme de Newton. D’autre part, on peut calculer explicitement le déterminant :

det ( I − T A ) = det ( 1 − t 1 t 1 t 2 1 − t 2 − t 3 t 3 1 ) = 1 + ( t 1 t 2 + t 1 t 3 + t 2 t 3 ) . {\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 )}.}

Ainsi, par le MMT, on a une nouvelle expression de ces mêmes coefficients :

G ( 2 n , 2 n , 2 n ) = [ t 1 2 n t 2 2 n t 3 2 n ] ( − 1 ) 3 n ( t 1 t 2 + t 1 t 3 + t 2 t 3 ) 3 n = ( − 1 ) n ( 3 n n , n , n ) , {\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}}}

où la dernière égalité vient du fait qu'il faut utiliser le même nombre de fois les trois facteurs de la puissance. En comparant les deux expressions des coefficients G(2n, 2n, 2n), on obtient une version équivalente de l'identité de Dixon :

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

Voir aussi

Article connexe

Notes et références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « MacMahon's master theorem » (voir la liste des auteurs).
  1. ↑ James D. Louck, Unitary symmetry and combinatorics, Singapour, World Scientific, , viii (ISBN 978-981-281-472-2)
  • Percy Alexander MacMahon, Combinatory analysis, vol. 1 et 2, Cambridge University Press, 1915-1916 (lire en ligne)
  • I. J. Good, « A short proof of MacMahon's 'Master Theorem' », Proceedings of the Cambridge Philosophical Society, vol. 58, no 1,‎ , p. 160 (DOI 10.1017/S0305004100036318, Bibcode 1962PCPS...58..160G, zbMATH 0108.25104, S2CID 124876088)
  • I.J. Good, « Proofs of some 'binomial' identities by means of MacMahon's 'Master Theorem' », Proceedings of the Cambridge Philosophical Society, vol. 58, no 1,‎ , p. 161-162 (DOI 10.1017/S030500410003632X, Bibcode 1962PCPS...58..161G, zbMATH 0108.25105, S2CID 122896760)
  • Pierre Cartier et Dominique Foata, Problèmes combinatoires de commutation et réarrangements, vol. 85, Berlin, Springer, coll. « Lecture Notes in Mathematics », (lire en ligne)
  • Leonard Carlitz, « An Application of MacMahon's Master Theorem », SIAM Journal on Applied Mathematics, vol. 26,‎ , p. 431-436
  • Ian Goulden et David M. Jackson, Combinatorial Enumeration, New York, John Wiley,
  • Christian Krattenthaler et M. Schlosser, « A new multidimensional matrix inverse with applications to multiple q-series », Discrete Mathematics, vol. 204,‎ , p. 249-279 (lire en ligne)
  • S. Garoufalidis, T. T. Q. Lê et Doron Zeilberger, « The Quantum MacMahon Master Theorem », Proceedings of the National Academy of Sciences of the United States of America, vol. 103, no 38,‎ , p. 13928-13931 (arXiv 0303319, lire en ligne)
  • M. Konvalinka et Igor Pak, « Non-commutative extensions of the MacMahon Master Theorem », Advances in Mathematics, vol. 216, no 1,‎ (arXiv 0607737)
  • Dominique Foata et G.-N. Han, « A new proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem », Journal of Algebra, vol. 307, no 1,‎ , p. 424-431 (arXiv 0603464)
  • Dominique Foata et G.-N. Han, « Specializations and extensions of the quantum MacMahon Master Theorem », Linear Algebra and its Applications, vol. 423, nos 2-3,‎ , p. 445-455 (arXiv 0603466)
  • P.H. Hai et M. Lorenz, « Koszul algebras and the quantum MacMahon master theorem », Bulletin of the London Mathematical Society, vol. 39, no 4,‎ , p. 667-676 (arXiv 0603169)
  • Pavel Etingof et Igor Pak, « An algebraic extension of the MacMahon master theorem », Proceedings of the American Mathematical Society, vol. 136, no 7,‎ , p. 2279-2288 (arXiv 0608005)
  • P. H. Hai, B. Kriegk et M. Lorenz, « N-homogeneous superalgebras », Journal of Noncommutative Geometry, vol. 2,‎ , p. 1-51 (arXiv 0704.1888)
  • J. D. Louck, Unitary symmetry and combinatorics, Hackensack, NJ, World Scientific,
  • icône décorative Portail des mathématiques