マクマホンのマスター定理

数学において、マクマホンのマスター定理（MMT ）は、列挙的組合せ論と線型代数学における帰結です。パーシー・マクマホンによって発見され、彼のモノグラフ『組合せ解析』 （1916年）で証明されました。二項式恒等式、 特にディクソンの恒等式を導くためによく用いられます

背景

マクマホンはモノグラフの中で、彼の研究結果の多くの応用を発見し、「順列理論におけるマスター定理」と呼んだ。彼はタイトルを次のように説明した。「マスター定理とは、そうでなければ解決が難しい様々な問題を、見事かつ迅速に扱うことから名付けられた。」

この結果は（帰属表示付きで）何度も再導出されているが、最も有名なのは IJ Goodによるもので、彼はこれをラグランジュの逆定理の多重線型一般化から導出している。MMTはまた、指数級数版を発見したCarlitzによっても普及した 。1962年、GoodはMMTからDixonの恒等式の簡潔な証明を見つけた。1969年、CartierとFoataは、代数的および単射的なアイデア（Foataの論文に基づく）と、単語の組合せ論へのさらなる応用を組み合わせ、痕跡の概念を導入することで、MMTの新しい証明を見つけた。それ以来、MMTは列挙組合せ論における標準的なツールとなっている。

クラッテンターラー・シュロッサー拡張（1999年）を除き、様々なq-ディクソン恒等式が数十年前から知られていましたが、MMTの適切なq-類似体は未だ解明されていませんでした。ガロウファリディス・レー・ツァイルバーガーによる量子拡張（2006年）の後、フォアタ・ハン、コンヴァリンカ・パク、エティンゴフ・パクによって多くの非可換拡張が開発されました。コシュル代数や準行列式とのさらなる関連性も、ハイ・ローレンツ、ハイ・クリーク・ローレンツ、コンヴァリンカ・パクらによって発見されました。

最後に、JD Louckによれば、理論物理学者ジュリアン・シュウィンガーは、多粒子系の角運動量理論における生成関数アプローチの文脈でMMTを再発見した。Louckは次のように書いている。

マクマホンマスター定理は、より基本的な構成要素から構成される二成分系における複合系の角運動量特性を統一するものである。^{[ 1 ]}

声明

を複素行列とし、を形式変数とする。任意の非負整数列 に対して、対応する多項式の 係数を考える。${\displaystyle A=(a_{ij})_{m\times m}}$ ${\displaystyle x_{1},\ldots,x_{m}}$ ${\displaystyle k_{1},\dots,k_{m}}$

${\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}}.}$

（ここで、 という表記は「における単項式の係数」を意味します。） を別の形式変数の集合とし、 を対角行列とします。すると、 ${\displaystyle [f]g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle t_{1},\ldots,t_{m}}$ ${\displaystyle T=\mathrm {diag} (t_{1},\dots ,t_{m})}$

${\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)}},}$

ここで、和はすべての非負整数ベクトル にわたって実行され、サイズ の単位行列を表します。 ${\displaystyle (k_{1},\dots,k_{m})}$ ${\displaystyle I_{m}}$ ${\displaystyle m}$

組合せ論的解釈

を計算するには、次の繰り返し行列を構築できます。ここで、の - 行目は回繰り返されます。次に、1 列目の要素が 回選択され、2 列目の要素が 回選択されるなど、行ごとに正確に 1 つの要素を選択するすべての可能な方法を構築します。最後に、そのような方法ごとに、選択された要素を掛け合わせ、これらすべての積の合計はです ${\displaystyle G(k_{1},\dots ,k_{m})}$ $${\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}}}$$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle k_{i}}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle G(k_{1},\dots ,k_{m})}$

応用

が恒等式であるとき、これは多変数等比級数の恒等式を与えます。を設定すると、式 が得られます。 とすると、 は単語 の順序の入れ替えの数、つまりの記号を並べ替える方法の数です。これにより、 はそれぞれ、以前にまたはなどが占めていた場所に配置されます。マクマホンのマスター定理により、${\displaystyle A}$ $${\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}}}$$ ${\displaystyle t_{1},\dots ,t_{m}=1}$ $${\displaystyle \sum _{(k_{1},\dots ,k_{m})}G(k_{1},\dots ,k_{m})\,=\,{\frac {1}{\det(I_{m}-A)}}}$$ ${\displaystyle A={\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}}}$ ${\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}}$ ${\displaystyle x_{1}^{n}x_{2}^{n}x_{3}^{n}}$ ${\displaystyle 3n}$ ${\displaystyle x_{1}^{n}x_{2}^{n}x_{3}^{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ $${\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}}}}$$

ディクソンの恒等式

行列を考える

${\displaystyle A={\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}}.}$

定義から直接 係数G (2 n , 2 n , 2 n )を計算する

${\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}}}$

ここで最後の等式は、右側に次の係数の積があるという事実から導かれます。

${\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},}$

これらは二項定理から計算されます。一方、行列式を明示的に計算することもできます。

${\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 )}.}$

したがって、MMTによれば、同じ係数に対して新しい式が得られます。

${\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}}}$

ここで最後の等式は、べき乗の3つの項を全て同じ回数使用する必要があるという事実から導かれます。係数G (2 n , 2 n , 2 n )の2つの式を等しくすると、ディクソンの恒等式と同等の式が得られます。

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

参照

• 永久

参考文献

1. Louck, James D. (2008).ユニタリー対称性と組み合わせ論. シンガポール: World Scientific. pp. viii. ISBN 978-981-281-472-2.

• PAマクマホン著『組み合わせ分析』第1巻と第2巻、ケンブリッジ大学出版局、1915-16年
• グッド、IJ (1962) 「マクマホンの『マスター定理』の簡潔な証明」ケンブリッジ哲学協会紀要. 58 (1): 160. Bibcode : 1962PCPS ... 58..160G . doi : 10.1017/ S0305004100036318 . S2CID  124876088. Zbl 0108.25104  .
• グッド、IJ (1962) 「マクマホンの『マスター定理』によるいくつかの『二項式』恒等式の証明」ケンブリッジ哲学協会紀要. 58 (1 ) : 161– 162.書誌コード: 1962PCPS...58..161G . doi : 10.1017/ S030500410003632X . S2CID  122896760. Zbl 0108.25105  .
• P. Cartierおよび D. Foata、「交換と配置の問題の組み合わせ」、「数学の講義ノート」、第 1 号。 85、シュプリンガー、ベルリン、1969 年。
• L. Carlitz、「マクマホンのマスター定理の応用」、SIAM Journal on Applied Mathematics 26 (1974)、431–436。
• IP GouldenとDM Jackson、「Combinatorial Enumeration」、John Wiley、ニューヨーク、1983 年。
• C. Krattenthalerと M. Schlosser、 「多重q級数への応用を伴う新しい多次元行列逆行列」、Wayback Machineに 2011-07-24 でアーカイブ、Discrete Mathematics 204 (1999)、249–279。
• S. Garoufalidis、TTQ Lê、D. Zeilberger、「量子マクマホンマスター定理」、米国科学アカデミー紀要103 (2006)、第38号、13928–13931 ( eprint )。
• M. Konvalinka とI. Pak、「マクマホンマスター定理の非可換拡張」、Advances in Mathematics 216 (2007)、第1号。( eprint )。
• D. Foata と G.-N. Han、「Garoufalidis-Lê-Zeilberger 量子マクマホンマスター定理の新しい証明」、 Journal of Algebra 307 (2007)、第 1 号、424–431 ( eprint )。
• D. Foata と G.-N. Han、「量子マクマホンマスター定理の特殊化と拡張」、線形代数とその応用423 (2007)、第 2 ～ 3 号、445 ～ 455 ( eprint )。
• PH HaiとM. Lorenz、「Koszul代数と量子マクマホンマスター定理」、 Bull. Lond. Math. Soc. 39 (2007), no. 4, 667–676. ( eprint )。
• P. Etingofと I. Pak、「マクマホンマスター定理の代数的拡張」、 アメリカ数学会紀要 136 (2008)、第 7 号、2279–2288 ( eprint )。
• PH Hai, B. KriegkおよびM. Lorenz, N同次超代数, J. Noncommut. Geom. 2 (2008) 1–51 ( eprint ).
• JD Louck、「ユニタリ対称性と組み合わせ論」、World Sci.、ハッケンサック、ニュージャージー、2008 年。