{{short description|Result in enumerative combinatorics and linear algebra}} In mathematics, '''MacMahon's master theorem''' ('''MMT''') is a result in enumerative combinatorics and linear algebra. It was discovered by Percy MacMahon and proved in his monograph ''Combinatory analysis'' (1916). It is often used to derive binomial identities, most notably Dixon's identity.
== Background == In the monograph, MacMahon found so many applications of his result, he called it "a master theorem in the Theory of Permutations." He explained the title as follows: "a Master Theorem from the masterly and rapid fashion in which it deals with various questions otherwise troublesome to solve."
The result was re-derived (with attribution) a number of times, most notably by I. J. Good who derived it from his multilinear generalization of the Lagrange inversion theorem. MMT was also popularized by Carlitz who found an exponential power series version. In 1962, Good found a short proof of Dixon's identity from MMT. In 1969, Cartier and Foata found a new proof of MMT by combining algebraic and bijective ideas (built on Foata's thesis) and further applications to combinatorics on words, introducing the concept of traces. Since then, MMT has become a standard tool in enumerative combinatorics.
Although various ''q''-Dixon identities have been known for decades, except for a Krattenthaler–Schlosser extension (1999), the proper q-analog of MMT remained elusive. After Garoufalidis–Lê–Zeilberger's quantum extension (2006), a number of noncommutative extensions were developed by Foata–Han, Konvalinka–Pak, and Etingof–Pak. Further connections to Koszul algebra and quasideterminants were also found by Hai–Lorentz, Hai–Kriegk–Lorenz, Konvalinka–Pak, and others.
Finally, according to J. D. Louck, the theoretical physicist Julian Schwinger re-discovered the MMT in the context of his generating function approach to the angular momentum theory of many-particle systems. Louck writes:
{{quote|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.<ref>{{cite book|last1=Louck|first1=James D.|title=Unitary symmetry and combinatorics|date=2008|publisher=World Scientific|location=Singapore|isbn=978-981-281-472-2|pages=viii}}</ref>}}
== Statement == Let <math>A = (a_{ij})_{m\times m}</math> be a complex matrix, and let <math>x_1,\ldots,x_m</math> be formal variables. For any sequence of non-negative integers <math>k_1, \dots, k_m</math>, consider the associated coefficient of a polynomial: :<math> 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}. </math> (Here the notation <math>[f]g</math> means "the coefficient of monomial <math>f</math> in <math>g</math>".) Let <math>t_1,\ldots,t_m</math> be another set of formal variables, and let <math>T = \mathrm{diag}(t_1, \dots, t_m)</math> be a diagonal matrix. Then :<math> \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)}, </math> where the sum runs over all nonnegative integer vectors <math>(k_1,\dots,k_m)</math>, and <math>I_m</math> denotes the identity matrix of size <math>m</math>.
=== Combinatorial interpretation === To compute <math> G(k_1,\dots,k_m) </math>, one can construct the following repeated matrix:<math display="block"> 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} </math>where the <math> i </math>-th row of <math> A </math> is repeated for <math> k_i </math> times. Then, one constructs all possible ways to pick exactly one element per row, such that elements in the first column is picked <math> k_1 </math> times, elements in the second column is picked <math> k_2 </math> times, and so on. Finally, for each such way, multiply the elements picked, and the sum of all these products is <math> G(k_1,\dots,k_m) </math>.
== Applications == When <math>A</math> is the identity, this gives a multivariate geometric series identity:<math display="block">\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}</math>Setting <math>t_1, \dots, t_m = 1</math>, we get an expression<math display="block"> \sum_{(k_1,\dots,k_m)} G(k_1,\dots,k_m)\, = \,\frac{1}{\det (I_m - A)}</math> Let <math> A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} </math>, then <math> 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 </math> is the number of derangements of the word <math> x_1^n x_2^n x_3^n </math>, i.e. ways to permute the <math> 3n </math> symbols of <math> x_1^n x_2^n x_3^n </math>, such that each <math> x_1 </math> lands in the location previously occupied by some <math> x_2 </math> or <math> x_3 </math>, etc. By MacMahon's master theorem,<math display="block"> G(n, n, n)=\sum_{k=0}^n\binom{n}{k}^3 = [t_1^nt_2^nt_3^n]\frac{1}{1-t_1 t_2-t_1 t_3-t_2 t_3-2 t_1 t_2 t_3} </math>
=== Dixon's identity === {{main|Dixon's identity}} Consider a matrix :<math> A = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}. </math> Compute the coefficients ''G''(2''n'', 2''n'', 2''n'') directly from the definition:
:<math> \begin{align} 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{align} </math>
where the last equality follows from the fact that on the right-hand side we have the product of the following coefficients: :<math>[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},</math> which are computed from the binomial theorem. On the other hand, we can compute the determinant explicitly: :<math> \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_2t_3\bigr). </math> Therefore, by the MMT, we have a new formula for the same coefficients:
: <math> \begin{align} 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_2t_3\bigr)^{3n} \\[6pt] & = (-1)^{n} \binom{3n}{n,n,n}, \end{align} </math>
where the last equality follows from the fact that we need to use an equal number of times all three terms in the power. Now equating the two formulas for coefficients ''G''(2''n'', 2''n'', 2''n'') we obtain an equivalent version of Dixon's identity:
:<math> \sum_{k=0}^{2n} (-1)^k \binom{2n}{k}^3 = (-1)^{n} \binom{3n}{n,n,n}. </math>
==See also== *Permanent
== References == {{Reflist}} * P.A. MacMahon, ''[http://www.hti.umich.edu/cgi/t/text/text-idx?c=umhistmath;idno=ABU9009 Combinatory analysis]'', vols 1 and 2, Cambridge University Press, 1915–16. * {{cite journal | zbl=0108.25104 | authorlink=I. J. Good | first=I.J. | last=Good | title=A short proof of MacMahon's 'Master Theorem' | journal=Proceedings of the Cambridge Philosophical Society | volume=58 | year=1962 | issue=1 | page=160 | doi=10.1017/S0305004100036318 | bibcode=1962PCPS...58..160G | s2cid=124876088 }} * {{cite journal | zbl=0108.25105 | authorlink=I. J. Good | first=I.J. | last=Good | title=Proofs of some 'binomial' identities by means of MacMahon's 'Master Theorem' | journal=Proceedings of the Cambridge Philosophical Society | volume=58 | year=1962 | issue=1 | pages=161–162 | doi=10.1017/S030500410003632X | bibcode=1962PCPS...58..161G | s2cid=122896760 }} * P. Cartier and D. Foata, [https://www.mat.univie.ac.at/~slc/books/cartfoa.html Problèmes combinatoires de commutation et réarrangements], ''Lecture Notes in Mathematics'', no. 85, Springer, Berlin, 1969. * L. Carlitz, An Application of MacMahon's Master Theorem, ''SIAM Journal on Applied Mathematics'' 26 (1974), 431–436. * I.P. Goulden and D. M. Jackson, ''Combinatorial Enumeration'', John Wiley, New York, 1983. * C. Krattenthaler and M. Schlosser, [http://radon.mat.univie.ac.at/users/kratt/public_html/artikel/minv.ps.gz A new multidimensional matrix inverse with applications to multiple ''q''-series] {{Webarchive|url=https://web.archive.org/web/20110724010545/http://radon.mat.univie.ac.at/users/kratt/public_html/artikel/minv.ps.gz |date=2011-07-24 }}, ''Discrete Mathematics'' 204 (1999), 249–279. * S. Garoufalidis, T. T. Q. Lê and D. Zeilberger, [http://www.pnas.org/content/103/38/13928.full The Quantum MacMahon Master Theorem], ''Proceedings of the National Academy of Sciences of the United States of America'' 103 (2006), no. 38, 13928–13931 ([https://arxiv.org/abs/math/0303319 eprint]). * M. Konvalinka and I. Pak, Non-commutative extensions of the MacMahon Master Theorem, ''Advances in Mathematics'' 216 (2007), no. 1. ([https://arxiv.org/abs/math/0607737 eprint]). * D. Foata and G.-N. Han, A new proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, ''Journal of Algebra'' 307 (2007), no. 1, 424–431 ([https://arxiv.org/abs/math/0603464 eprint]). * D. Foata and G.-N. Han, Specializations and extensions of the quantum MacMahon Master Theorem, ''Linear Algebra and its Applications'' 423 (2007), no. 2–3, 445–455 ([https://arxiv.org/abs/math.CO/0603466 eprint]). * P.H. Hai and M. Lorenz, Koszul algebras and the quantum MacMahon master theorem, ''Bull. Lond. Math. Soc.'' 39 (2007), no. 4, 667–676. ([https://arxiv.org/abs/math/0603169 eprint]). * P. Etingof and I. Pak, An algebraic extension of the MacMahon master theorem, ''Proceedings of the American Mathematical Society'' 136 (2008), no. 7, 2279–2288 ([https://arxiv.org/abs/math/0608005 eprint]). * P.H. Hai, B. Kriegk and M. Lorenz, ''N''-homogeneous superalgebras, ''J. Noncommut. Geom.'' 2 (2008) 1–51 ([https://arxiv.org/abs/0704.1888 eprint]). * J.D. Louck, ''Unitary symmetry and combinatorics'', World Sci., Hackensack, NJ, 2008.
Category:Enumerative combinatorics Category:Factorial and binomial topics Category:Articles containing proofs Category:Theorems in combinatorics Category:Theorems in linear algebra