Диаграммы Юнга

Двумерная диаграмма Юнга — это конечный набор клеток, выровненных по левому и нижнему краям, в котором длины столбцов образуют невозрастающую последовательность. На рис. 1 представлены 4 диаграммы Юнга.

Диаграмма Юнга называется строгой, если высоты ее столбцов строго убывают, иначе диаграмма называется стандартной. На рис. 1 диаграммы а) и б) являются строгими, в) и г) — стандартными.

Существуют также n-мерные обобщения диаграмм Юнга. В частности, трехмерные диаграммы Юнга, также известные как плоские разбиения, состоят из последовательно вложенных друг в друга двумерных диаграмм. На рис. 2 изображены примеры трехмерных диаграмм Юнга.

Способ представления диаграмм Юнга, при котором клетки выравниваются по нижнему и левому краям, называется французской нотацией. Существуют и другие нотации, в том числе английская нотация и нотация Вершика-Керова, которую также называют русской нотацией. В английской нотации клетки выравниваются по верхнему и левому краям; нотация Вершика-Керова получается путем поворота диаграммы во французской нотации на 45 градусов против часовой стрелки. При этом вместо системы координат (x, y) используется система координат (u, v). Одна и та же диаграмма Юнга из 500 клеток представлена в трех различных нотациях на рис. 3.

Разбиение натурального числа n — набор натуральных чисел, сумма которых равна n.
Диаграмма Юнга взаимно однозначно соответствует разбиению натурального числа, т.е. его разложению на сумму положительных целых чисел n=l_1+l_2+…+l_n, l_1>=l_2>=…>=l_n, где n — число клеток диаграммы, т.е. ее размер, а значения l_i соответствуют высотам столбцов диаграммы. Например, разбиения 3+2+1 и 2+3+1 считаются идентичными, для определенности слагаемые упорядочиваются по убыванию.

На рис. 4 приведены примеры некоторых диаграмм Юнга размера 7 и соответствующих им разбиений.

Существуют различные способы вычисления числа разбиений:

• По формуле Эйлера:
  Производящая функция для числа разбиений p(n), т.е. числа диаграмм Юнга размера n (формула Эйлера):

\sum_{n=0}^{\infty}p(n)x^n=\prod_{k=1}^{\infty}\frac{1}{1-x^k}

• С помощью рекуррентной формулы:

p(n)=\sum_{m=1}^{\infty}(-1)^{m+1}\left(p\left(n-\frac{m(3m-1)}{2}\right)+p\left(n-\frac{m(3m+1)}{2}\right)\right)

Некоторые значения p(n):

n	p(n)
1	1
10	42
50	204226
100	190569292
500	2300165032574323995027
1000	24061467864032622473692149727991
2000	4720819175619413888601432406799959512200344166

Внутренняя и внешняя угловые клетки диаграммы — это клетки, которые можно удалить или добавить к диаграмме соответственно без нарушения ее структуры. На рис. 5 а) внутренние угловые клетки диаграммы Юнга выделены серым цветом, на рис. 5 б) внешние угловые клетки изображены пунктиром. Диаграмма Юнга может быть однозначно представлена с помощью набора внешних или внутренних угловых клеток.

Каждая угловая клетка может быть представлена в виде монома.  На рис. 6 в угловых клетках диаграммы Юнга подписаны соответствующие им мономы. Степени переменных x и y равны номерам строк и столбцов угловой клетки.

Перестановка — упорядоченный набор чисел от 1 до n, в котором числу i\in [1,n] ставится в соответствие i-й элемент из набора.

Элементы перестановки разбиваются на циклы: i_1\mapsto i_2 \mapsto … \mapsto i_{k-1} \mapsto i_k \mapsto i_1. Такой цикл записывается как (i_1 i_2 … i_{k-1} i_k), но можно также начинать запись с любого другого элемента из цикла: (i_t i_{t+1} …). Любую перестановку можно разложить в произведение циклов, элементы которых не пересекаются.

Например, на рис. 7 приведена перестановка и циклы, на которые она раскладывается. Длины циклов, т.е. количество элементов, из которых состоит цикл, подписаны красным цветом.

Каждая диаграмма Юнга взаимно-однозначно соответствует длинам циклов некоторой перестановки. На рис. 8 изображена диаграмма Юнга, соответствующая перестановке, изображенной на рис. 7.