Перегляд вихідного коду сторінки Діаграма Янга

#redirect [[Діаграма Юнга]]

{{приєднати до|Діаграма Юнга}}

'''Діаграми Юнга'''&nbsp;— [[Комбінаторика|комбінаторний]] об'єкт, що широко використовують, окрім комбінаторики, також у [[Теорія представлень|теорії представлень]] [[Скінченна група|скінченних груп]], зокрема для опису представлень [[Симетрична група|симетричних]] і [[Загальна лінійна група|загальних лінійних]] груп і вивчення їх властивостей. Діаграми Юнга було введено {{нп|Альфред Юнг|Альфредом Юнгом||Alfred Young}}, математиком з [[Кембриджський університет|Кембриджського університету]], 1900 року <ref>{{citation|title=Искусство программирования, Том 3: Сортировка и поиск|first=Дональд Э.|last=Кнут|authorlink=Дональд Кнут|edition=2ое|publisher=Вильямс, Addison-Wesley|year=2005|page=66}}.</ref><ref>{{citation|title=On quantitative substitutional analysis|first=A.|last=Young|journal=Proceedings of the London Mathematical Society|year=1900|volume=33|series=Ser. 1|issue=1|pages=97–145|doi=10.1112/plms/s1-33.1.97}}. </ref>. Згодом 1903 року їх було використано Георгом Фробеніусом для вивчення симетричних груп.

== Означення ==
'' Примітка: в цій статті для діаграм і таблиць використовується спосіб запису, прийнятий в англомовних країнах ''.

=== Діаграми ===
[[Файл:Young diagram for 541 partition.svg|thumb|right|150px|Діаграма Юнга форми (5, 4, 1), Англійська нотація]]
[[Файл:Young diagram for 541 partition french.svg|thumb|right|150px|Діаграма Юнга форми (5, 4, 1), Французька нотація]]

'''Діаграма Юнга''' (також називається '''діаграмою Ферре''' у випадках, коли замість клітинок використовують точки <ref>Р. Стенли Перечислительная комбинаторика. М: Мир, 1990. с. 52.</ref> ) — скінченний набір клітинок, вирівняних по лівій стороні, в якому довжини рядків утворюють незростаючу послідовність (кожен рядок такої ж довжини, як попередній, або коротший). Набір чисел, що складається з довжин рядків, задає [[розбиття числа|розбиття]] {{mvar|''λ''}} невід'ємного [[Ціле число (тип даних)|цілого числа]] {{mvar|''n''}}, яке дорівнює загальній кількості клітинок діаграми. Аналогічно, про конкретно взяте розбиття {{mvar|''λ''}} кажуть, що воно задає форму відповідної діаграми Юнга.

Включення однієї діаграми Юнга в іншу вводить [[частково впорядкована множина|частковий порядок]] на множині всіх розбиттів, що задає структуру, яка називається решіткою Юнга.

Розбиття, що задається [[Транспонована матриця|транспонованою]] діаграмою Юнга, називається розбиттям, ''пов'язаним'' або ''транспонованим'' до {{mvar|''λ''}}.

Загальноприйнято позначати клітини, використовуючи пару цілих чисел, перше з яких позначає номер рядка в діаграмі, а друге&nbsp;— номер стовпця у цьому рядку. Проте, існують два різних поширених варіанти того, як діаграми зображати: або розташовувати наступний рядок під попереднім, або навпаки. Перше зазвичай використовується у англомовних країнах, тоді як другий&nbsp;— серед [[Французька мова|франкомовних]], тому ці варіанти називаються ''англійською нотацією'' і ''французькою нотацією'' відповідно .

Англійська нотація відповідає загальноприйнятій нумерації елементів [[Матриця (математика)|матриць]], а французька ближче до традиційного позначення [[декартові координати|декартових координат]] (хоча для діаграм Юнга вертикальна координата все ж перша). Малюнок справа в англійській нотації зображує діаграму Юнга розбиття (5, 4, 1). Пов'язане розбиття, що вимірює висоти стовпців, рівне (3, 2, 2, 2, 1).

=== Таблиці ===
[[Файл: Young tableaux for 541 partition.svg|thumb|right|150px|Стандартна таблиця Юнга форми (5, 4, 1)]]

'''Таблицею Юнга''' називається діаграма Юнга, клітини якої заповнені символами з якого-небудь ''алфавіту'', який зазвичай вважається [[Цілком впорядкована множина|цілком упорядкованою множиною]]. Найчастіше використовуються [[натуральні числа]]. В класичному застосуванні у теорії представлень симетричних груп, таблиці Юнга заповнені {{mvar|''n''}} різними числами, довільно вписаними в клітини діаграми. Таблиця називається '''стандартною''', якщо числа зростають в кожному рядку і в кожному стовпці. 

Кількість різних стандартних таблиць Юнга з {{mvar|''n''}} елементами описується числом [[інволюція (математика)|інволюцій]] в [[симетрична група|симетричній групі]] порядку {{mvar|''n'' }}:

:1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... ({{OEIS|A000085}}).

В деяких застосуваннях таблиць Юнга використовується різновид, для якого дозволяється повторення деяких чисел (а якісь не використовуються зовсім). Таблиця називається '''напівстандартною''', якщо числа не зменшуються по горизонталі і зростають по вертикалі. Виписуючи, скільки разів кожне число з'явилося в таблиці, ми отримуємо послідовність, що називається '''вагою''' таблиці. Зокрема стандартні таблиці Юнга збігаються з напівстандартними таблицями ваги (1,1, ..., 1). 

=== Варіації === 
Існують варіації означення таблиці: наприклад коли у таблиці числа строго зростають уздовж рядків, і не спадають уздовж стовпців. Таблиці зі спадаючими числами розглядаються в теорії плоских розбиттів. Існують і інші узагальнення, де клітини можуть об'єднуватися до того, як їм призначають числа. 

=== Косі таблиці Юнга === 
[[Файл: Skew tableau 5422-21.svg|thumb|right|150px|Коса таблиця форми (5, 4, 2, 2) / (2, 1), англійська нотація]] 

'''Коса форма''' — це пара розбиття ({{mvar|''λ''}}, {{mvar|''μ''}}), така що діаграма Юнга для {{mvar|''λ''}} містить діаграму для {{mvar|''μ''}}; для цього використовується позначення: {{mvar|''λ''}}/{{mvar|''μ''}}. Якщо {{mvar|''λ''}} = ({{mvar|''λ''<sub>1</sub>}}, {{mvar|''λ''<sub>2</sub>}}, ...) і {{mvar|''μ''}} = ({{mvar|''μ''<sub>1</sub>}}, {{mvar|''μ''<sub>2</sub>}}, ...), то вкладення діаграм означає, що {{mvar|''μ''<sub>''i''</sub>}} ≤ {{mvar|''λ''<sub>''i''</sub>}} для всіх {{mvar|''i''}}. 

'''Коса діаграма''' косої форми {{mvar|''λ''}}/{{mvar|''μ''}} — [[Різниця множин|теоретико-множинна різниця]] діаграм для {{mvar|''λ''}} і для {{mvar|''μ''}}: множина клітин, що належать діаграмі для {{mvar|''λ''}} але не належать діаграмі для {{mvar|''μ''}}. '''Коса таблиця''' форми {{mvar|''λ''}}/{{mvar|''μ''}} одержується за допомогою заповнення клітин відповідної косої діаграми; така таблиця називається напівстандартною, якщо числа не зменшуються по рядках і зростають по стовпцях; напівстандартна таблиця називається стандартною, якщо кожне число від одиниці до кількості клітин зустрічається рівно один раз. 

Тоді як відображення з розбиття в їх діаграми Юнга є ін'єктивним, те ж твердження для відображення з косих форм в косі діаграми не є правильним. Наприклад, коса діаграма, що складається з єдиного квадрата в позиції (2,4) може бути отримана шляхом видалення піддіаграми {{mvar|''μ''}} <math> = (5,3,2,1) </math> з діаграми {{mvar|''μ''}}<math>=(5,3,2,1)</math>, або ще багатьма способами. Взагалі кажучи, будь-яка коса діаграма, для якої множина непустих рядків (або непустих стовпців) не є суцільною, або не містить першого рядка (або першого стовпця), одержується більш ніж з однієї косої форми. Хоча багато властивостей косих таблиць залежать тільки від заповнених квадратів, деякі можуть залежати і від косої форми. Таблиці Юнга можуть бути ототожнені з косими таблицями, для яких розбиття {{mvar|''μ''}} є порожнім (розбиття нуля). 

Будь-яка коса напівстандартна таблиця {{mvar|''T''}} форми {{mvar|''λ''}}/{{mvar|''μ''}}, заповнена додатними цілими числами, породжує послідовність розбиттів (або послідовність діаграм Юнга): перший елемент — це {{mvar|''μ''}}, а ''i''-й одержується додаванням усіх клітинок, що містять число, менше або рівне ''i''; зрештою виходить діаграма {{mvar|''λ''}}. Будь-яка пара сусідніх форм у цій послідовності утворює косу форму, в кожному стовпці якої не більше однієї клітини; такі форми називаються '''горизонтальними смужками'''. Ця послідовність повністю визначає таблицю {{mvar|''T''}}, і іноді в літературі (наприклад, в книзі Макдональда) косі напівстандартні форми визначають як послідовності такого виду. 

== Застосування ==

Діаграми Юнга знаходять численні застосування в [[комбінаторика|комбінаториці]], [[представлення групи|теорії представлень]] і [[алгебрична геометрія|алгебричній геометрії]]. Були досліджені різні способи підрахунку числа діаграм, які привели до визначення і формул для [[многочлени Шура|многочленів Шура]]. Відомі алгоритми, що виконуються безпосередньо на діаграмах, такі як jeu de taquin («гра в [[квач (гра)|квача]]») Шютценбергера і алгоритм Робінсона&nbsp;— Шенстеда. Ласку і Шютценбергер вивчили [[Асоціативність|асоціативний]] добуток на множині напівстандартних діаграм Юнга, що приводить в підсумку до структури, відомої як плактичний моноїд.

У теорії представлень, стандартні таблиці Юнга розміру {{mvar|''k''}} описують базиси незвідних представлень [[симетрична група|симетричної групи]] ''S''<sub>''k''</sub>.

Стандартний мономіальний базис в скінченновимірному незвідному представленні [[загальна лінійна група|загальної лінійної групи]] {{math|''GL''<sub>''n''</sub>}} параметризується множиною напівстандартних таблиць Юнга фіксованої форми над алфавітом {1, 2, …, {{mvar|''n''}}}. З цього факту випливає кілька важливих наслідків для [[теорія інваріантів|теорії інваріантів]], починаючи з робіт Вільяма Ходжа по однорідним координатним кільцям [[грассманіан]]ів, які були продовжені у працях Девіда Айзенбада і Джан-Карло Роти, Корадо де Кончіні, Клаудіо Процезі.

Правило Літтвуда&nbsp;— Річардсона, описуючи (серед іншого) розклад [[тензорний добуток|тензорного добутку]] незвідних представлень {{math|''GL''<sub>''n''</sub>}} на незвідні компоненти, формулюється в термінах певних косих напівстандартних таблиць.

Застосування в алгебричній геометрії зосереджені навколо числення Шуберта на [[Грассманіан|грасманіанах]] і [[многовид прапорів|многовидах прапорів]].

Деякі важливі [[Гомологія (математика)|класи когомологій]] можуть бути представлені за допомогою многочленів Шуберта і описані в термінах діаграм Юнга.

== Застосування в теорії представлень == 

Діаграми Юнга знаходяться у взаємно однозначній відповідності із [[незвідне представлення|незвідними представленнями]] [[симетрична група|симетричної групи]] (над [[комплексне число|комплексними числами]]). Вони надають зручний спосіб задання [[симетризатор Юнга|симетризаторів Юнга]], на основі яких будується теорія представлень симетричної групи. Багато фактів про представлення можуть бути виведені з відповідних діаграм. Нижче наведено два приклади: визначення розмірності представлення і обмежені представлення. 

Діаграми Юнга також параметризують незвідні поліноміальні представлення [[загальна лінійна група|загальної лінійної групи]] {{math|''GL''<sub>''n''</sub>}} (коли вони містять не більше {{mvar|''n''}} непустих рядків), а також незвідні представлення [[спеціальна лінійна група|спеціальної лінійної групи]] {{math|''SL''<sub>''n'' </sub>}} (коли вони містять не більше {{math|''n''-1}} непустих рядків) і незвідні комплексні представлення [[спеціальна унітарна група|спеціальної унітарної групи]] {{math|''SU''<sub>''n''</sub>}} (знову ж таки, коли вони містять не більше {{math |''n''-1}} непустих рядків). 

У цих випадках центральну роль відіграють напівстандартні таблиці з числами, що не є більшими за {{mvar|''n''}} (зокрема, їх кількість визначає розмірність представлень). 

=== Формула гаків === 
[[Файл: Hook length for 541 partition.svg|right|thomb|Довжини гаків для клітинок розбиття ''10 = 5 + 4 + 1' ']] 

Розмірність незвідного представлення {{math|''π''<sub>''λ''</sub>}} (що відповідає розбиттю {{mvar|''λ''}} числа {{mvar |''n''}}) симетричної групи {{math|''S''<sub>''n''</sub>}} дорівнює кількості різних стандартних таблиць Юнга, відповідним діаграмі розбиття. Це число може бути пораховано за допомогою так званої формули гаків. 

'''Довжиною гака''' {{math|hook(''x'')}} клітини {{mvar|''x''}} у діаграмі {{math|''Y''(''λ'')}} форми {{mvar|''λ''}} називається число клітин в тому ж рядку правіше плюс число клітин в тому ж стовпці нижче плюс один (сама клітина). За формулою гаків, розмірність незвідного представлення дорівнює {{math|''n''!}}, поділеному на добуток довжин всіх гаків діаграми:

: <math> \dim \pi_ \lambda = \frac {n!} {\prod_ { x \in Y (\lambda)} \mathrm {hook} (x)}. </math> 

Малюнок справа ілюструє довжини гаків для діаграми розбиття 10 = 5 + 4 + 1. Тому

:<math> \dim \pi_ \lambda = \frac {10!} {7 \cdot5 \cdot 4 \cdot 3 \cdot 1 \cdot 5 \cdot 3 \cdot 2 \cdot 1 \cdot1} = 288. </math> 

Аналогічно, розмірність незвідного представлення {{math|''W''(''λ'')}} групи {{math|GL<sub>''r''</sub>}}, що відповідає розбиттю ''λ'' числа ''n'' ( на не більше ніж ''r'' доданків), дорівнює кількості напівстандартних таблиць форми ''λ'' (що містять тільки числа від 1 до ''r''), яке дається формулою:

: <math> \dim W (\lambda) = \prod_{(i, j) \in Y (\lambda)} \frac {r + ji} {\mathrm {hook} (i, j)}, </math> 

де індекс ''i'' нумерує рядок, а індекс ''j'' нумерує стовпець клітини. <ref>{{cite book|author=Predrag Cvitanović |year=2008 |title=Group Theory: Birdtracks, Lie's, and Exceptional Groups | publisher=Princeton University Press | url=http://birdtracks.eu/}}, ур. 9.28 и приложение B.4</ref> Наприклад, розбиття (5,4,1) породжує розмірність відповідного незвідного представлення групи {{math|GL <sub> 7 </sub>}} (обхід клітин по рядках):

: <math > \dim W (\lambda) = \frac {7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 5} {7 \cdot5 \cdot 4 \cdot 3 \cdot 1 \cdot 5 \cdot 3 \cdot 2 \cdot 1 \cdot1} = 66 528.</math>

=== Обмежені представлення === 

Представлення симетричної групи {{math|''S''<sub>''n''</sub>}} на {{mvar|''n''}} елементах є також представленням симетричної групи на {{math|''n''-1}} елементі, {{math|''S''<sub>''n''-1</sub>}}. Однак незвідне представлення {{math|''S''<sub>''n''</sub>}} не обов'язково є незвідним представленням {{math|''S''<sub>''n''-1</sub>}}, а може бути [[пряма сума|прямою сумою]] кількох таких представлень. Ці представлення називаються факторами [[обмежене представлення|обмеженого представлення]]. 

Задача визначення розкладу обмеженого представлення даного незвідного представлення ''S''<sub>''n''</sub>, що відповідає розбиттю {{mvar|''λ''}} числа {{mvar|''n''}}, може бути розв'язаною з використанням діаграм Юнга. Для цього розглядаються всі діаграми Юнга, які можна отримати з діаграми форми {{mvar|''λ''}} видаленням однієї клітини (яка повинна знаходитися в кінці свого рядка і свого стовпця). Обмежене представлення тоді розкладається в пряму суму незвідних представлень {{math|''S''<sub>''n''-1</sub>}}, що відповідають діаграмам, отриманим при цьому, і до того ж кожне з них у сумі зустрічається рівно один раз.

== Примітки ==
{{reflist}}

== Посилання ==
* {{книга|автор=Yong, Alexander. |заголовок=What is...a Young Tableau?|посилання=http://www.ams.org/notices/200702/whatis-yong.pdf|видання='' Notices of the American Mathematical Society'', 2007, '''54''' (2)|pages=240—241}}

== Література ==
* {{книга|автор=Буфетов А. И., Житлухин М. М., Н. Е. Козин Н. Е. |заголовок=Диаграммы Юнга|посилання=http://www.mccme.ru/dubna/2010/notes/bufetov/workbook.pdf|місто=М.|видавництво=Изд-во МЦНМО|рік=2013|страниц=|isbn=978-5-4439-0077-3}}
* Пилипів В.&nbsp;М. [https://web.archive.org/web/20160305022327/http://www.mif.pu.if.ua/attachments/article/24-02-11/Pos_Teor_predst_grup_Pylypiv.pdf Теорія представлень груп та її застосування(навчальний посібник)].&nbsp;— Івано-Франківськ: ВДВ ЦІТ Прикарпатського національного університету імені Василя Стефаника, 2008.&nbsp;— 156&nbsp;с.
* {{книга|автор=Смирнов Е. Ю. |заголовок=Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы|посилання=http://www.mccme.ru/~smirnoff/papers/dubna14.pdf|місто=М.|видавництво=Изд-во МЦНМО|рік=2014|страниц=|isbn=978-5-4439-0137-4}}
* {{книга|автор=Cvitanovic, Predrag. |заголовок=Group Theory: Birdtracks, Lie’s, and Exceptional Groups|місто=Princeton|видавництво=Princeton University Press|рік=2008|allpages=|isbn=}}
*{{Citation | title=Young Tableaux | year=1997 | last1=Fulton | first1=William | series=London Mathematical Society Student Texts | volume=35| publisher=[[Cambridge University Press]] | isbn=978-0-521-56144-0 | mr = 1464693 }}.
* {{книга|автор=Fulton, William; Harris, Joe. |заголовок=Representation theory. A first course|місто=New York|видавництво=Springer-Verlag|рік=1991|allpages=|серия=Graduate Texts in Mathematics. Readings in Mathematics, vol. 129|isbn=978-0-387-97495-8}} (Lecture 4)
* {{книга|автор=Macdonald I. G. |заголовок=Symmetric functions and Hall polynomials|місто=Oxford|видавництво=The Clarendon Press, Oxford University Press|рік=1979|серия=Oxford Mathematical Monographs|allpages=viii + 180|isbn=0-19-853530-9|ref=Macdonald}} {{MathSciNet|id=84g:05003}}
* {{книга|автор=Manivel, Laurent. |заголовок=Symmetric Functions, Schubert Polynomials, and Degeneracy Loci|місто=|видавництво=American Mathematical Society|рік=|allpages=|isbn=}}
* {{книга|автор=Novelli, Jean-Christophe; Pak, Igor; Stoyanovkii, Alexander V. |заголовок=A direct bijective proof of the Hook-length formula|посилання=http://www.liafa.jussieu.fr/web9/rapportrech/description_en.php?idrapportrech=151|видання=''Discrete Mathematics and Theoretical Computer Science'', 1997, '''1'''|pages=53—67}}
* {{книга|автор=Sagan, Bruce E. |заголовок=The Symmetric Group|місто=|видавництво=Springer|рік=2001|allpages=|isbn=0-387-95067-2}}
* {{книга|автор=Vinberg E. B. |часть=Young tableau|посилання часть=https://www.encyclopediaofmath.org/index.php/Young_tableau|заголовок=''Hazewinkel, Michiel.'' Encyclopedia of Mathematics|місто=|видавництво=Springer|рік=2001|allpages=|isbn=978-1-55608-010-4}}

[[Категорія:Комбінаторика]]
[[Категорія:Теорія представлень]]