Теорема Мак-Магона Мастер

В математике основная теорема Мак-Магона ( MMT ) является результатом перечислительной комбинаторики и линейной алгебры. Он был открыт Перси Мак-Магоном и доказан в его монографии « Комбинаторный анализ» (1916). Он часто используется для получения биномиальных идентичностей, в первую очередь личности Диксона.

• 1 Предпосылки
• 2 Точное заявление
• 3 Вывод личности Диксон
• 4 См. Также
• 5 ссылки

В монографии Мак-Магон нашел столько приложений своего результата, что назвал его «основной теоремой теории перестановок». Он объяснил название следующим образом: «Основная теорема, основанная на мастерском и быстром способе решения различных вопросов, которые иначе было бы трудно решить».

Результат был повторно получен (с указанием авторства) несколько раз, в первую очередь И. Дж. Гудом, который получил его из своего полилинейного обобщения теоремы об обращении Лагранжа. MMT также популяризировал Карлитц, который нашел версию с экспоненциальным степенным рядом. В 1962 году Гуд нашел короткое доказательство личности Диксон в MMT. В 1969 году Картье и Фоата нашли новое доказательство ММТ, объединив алгебраические и биективные идеи (основанные на тезисе Фоата) и дальнейшие приложения к комбинаторике слов, введя понятие следов. С тех пор MMT стал стандартным инструментом в перечислительной комбинаторике.

Хотя различные q- тождества Диксона были известны на протяжении десятилетий, за исключением расширения Krattenthaler – Schlosser (1999), правильный q-аналог MMT оставался неуловимым. После квантового расширения Гаруфалидиса – Ле – Зейлбергера (2006) Фоата – Хан, Конвалинка – Пак и Этингоф – Пак разработали ряд некоммутативных расширений. Дальнейшие связи с алгеброй Кошуля и квазидетерминантами также нашли Хай – Лоренц, Хай – Кригк – Лоренц, Конвалинка – Пак и другие.

Наконец, согласно Дж. Д. Луку, физик-теоретик Джулиан Швингер повторно открыл ММТ в контексте своего подхода к производящей функции в теории углового момента систем многих частиц. Лук пишет:

Это основная теорема Мак-Магона, которая объединяет свойства углового момента составных систем в бинарном построении таких систем из более элементарных составляющих.

Позвольте быть сложной матрицы, и пусть быть формальными переменными. Рассмотрим коэффициент ${\ Displaystyle А = (а_ {ij}) _ {м \ раз м}}$${\ displaystyle x_ {1}, \ ldots, x_ {m}}$

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

(Здесь обозначение означает «коэффициент монома в ».) Позвольте быть другим набором формальных переменных, и пусть будет диагональной матрицей. потом ${\ displaystyle [f] g}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle t_ {1}, \ ldots, t_ {m}}$${\ displaystyle T = (\ delta _ {ij} t_ {i}) _ {m \ times 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 (к_ {1}, \ точки, к_ {м})}$${\ displaystyle I_ {m}}$ ${\ displaystyle m}$

Рассмотрим матрицу

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

Вычислите коэффициенты G (2 n, 2 n, 2 n ) непосредственно из определения:

${\ displaystyle {\ begin {align} G (2n, 2n, 2n) amp; = {\ 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] amp; = \, \ sum _ {k = 0} ^ {2n} (- 1) ^ {k} {\ binom {2n} {k}} ^ {3}, \ end {align}}}$

где последнее равенство следует из того, что в правой части стоит произведение следующих коэффициентов:

${\ 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 amp; -t_ {1} amp; t_ {1} \\ t_ {2} amp; 1 amp; -t_ {2} \\ - t_ { 3} amp; t_ {3} amp; 1 \ end {pmatrix}} \, = \, 1 + {\ bigl (} t_ {1} t_ {2} + t_ {1} t_ {3} + t_ {2} t_ {3 } {\ bigr)}.}$

Таким образом, согласно MMT, у нас есть новая формула для тех же коэффициентов:

${\ displaystyle {\ begin {align} G (2n, 2n, 2n) amp; = {\ 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] amp; = (- 1) ^ {n} {\ binom {3n} {n, n, n}}, \ end {выровнено}}}$

где последнее равенство следует из того, что нам нужно использовать равное количество раз все три члена в степени. Приравнивая две формулы для коэффициентов G (2 n, 2 n, 2 n ), мы получаем эквивалентную версию тождества Диксона:

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

• Постоянный

• П. А. Мак-Магон, Комбинаторный анализ, тома 1 и 2, Cambridge University Press, 1915–16.
• Хорошо, Эй Джей (1962). «Краткое доказательство« Главной теоремы » Мак-Магона ». Proc. Cambridge Philos. Soc. 58 : 160. Zbl   0108.25104. CS1 maint: обескураженный параметр ( ссылка )
• Хорошо, Эй Джей (1962). «Доказательства некоторых« биномиальных »тождеств с помощью« основной теоремы » Мак-Магона ». Proc. Cambridge Philos. Soc. 58 : 161–162. Zbl   0108.25105. CS1 maint: обескураженный параметр ( ссылка )
• П. Картье и Д. Фоата, Проблемы, связанные с коммутацией и перестановками, Лекционные заметки по математике, вып. 85, Шпрингер, Берлин, 1969 г.
• Л. Карлитц, Применение основной теоремы Мак-Магона, Журнал SIAM по прикладной математике 26 (1974), 431–436.
• И. П. Гоулден и Д. М. Джексон, Комбинаторное перечисление, Джон Вили, Нью-Йорк, 1983.
• К. Краттенталер и М. Шлоссер, Новая многомерная обратная матрица с приложениями к нескольким q- рядам, Дискретная математика. 204 (1999), 249–279.
• С. Гаруфалидис, TTQ Ле, Д. Зейлбергер, Квантовая основная теорема Мак-Магона, Proc. Natl. Акад. наук. 103 (2006), нет. 38, 13928–13931 ( eprint ).
• М. Конвалинка, И. Пак, Некоммутативные расширения основной теоремы Мак-Магона, Adv. Математика. 216 (2007), нет. 1. ( eprint ).
• Д. Фоата и Г.-Н. Хан, Новое доказательство квантовой основной теоремы Мак-Магона Гаруфалидиса-Ле-Зейльбергера, J. Algebra 307 (2007), no. 1, 424–431 ( eprint ).
• Д. Фоата и Г.-Н. Хан, Специализации и расширения квантовой основной теоремы Мак-Магона, Linear Algebra Appl 423 (2007), вып. 2–3, 445–455 ( eprint ).
• PH Хай и М. Лоренц, алгебры Кошуля и квантовая основная теорема Мак-Магона, Бюлл. Лондон. Математика. Soc. 39 (2007), нет. 4, 667–676. ( eprint ).
• П. Этингоф и И. Пак, Алгебраическое расширение основной теоремы Мак-Магона, Proc. Амер. Математика. Soc. 136 (2008), нет. 7, 2279–2288 ( eprint ).
• Хай, Б. Кригк и М. Лоренц, N -однородные супералгебры, J. Noncommut. Геом. 2 (2008) 1–51 (электронный отпечаток ).
• Дж. Д. Лук, Унитарная симметрия и комбинаторика, Мировые науки, Хакенсак, Нью-Джерси, 2008.