Диаграммы Юнга: разбиения, таблицы и формула крюков

Диаграмма Юнга превращает разбиение целого числа в рисунок из клеток. Например, число 7 можно представить как сумму и нарисовать три выровненные по левому краю строки соответствующей длины. Такой рисунок помогает сравнивать разбиения, строить таблицы и считать их без перебора всех заполнений. В интерактиве ниже измените длины строк и посмотрите, как меняются числа в клетках и количество стандартных таблиц.
Разбиение числа и форма диаграммы
Разбиение числа - запись в виде суммы положительных целых слагаемых, расположенных по невозрастанию. Порядок слагаемых здесь не создаёт нового разбиения: суммы и задают одну форму. Принято писать , где , а сумма частей равна .
В английской ориентации, которой придерживаемся здесь, первая и самая длинная строка находится сверху. Для рисуем четыре клетки в первой строке, две во второй и одну в третьей; левые края совпадают. Всего клеток столько же, сколько единиц в сумме, то есть семь. В другой распространённой, французской ориентации длиннейшая строка расположена снизу. Математическая форма от выбора ориентации не меняется, но слова «выше» и «ниже» в правилах надо согласовать с рисунком.
На видео после каждого добавления остаётся допустимая диаграмма: нельзя добавить клетку с пропуском или сделать нижнюю строку длиннее верхней. Обратное удаление возможно только из внешнего угла, после которого форма всё ещё соответствует разбиению. Один и тот же итоговый рисунок можно получить разными допустимыми последовательностями добавлений.
Диаграмма фиксирует длины строк, но не порядок слагаемых в произвольной записи. Для сравнения с другими способами подсчёта полезно освежить сочетания и перестановки: там порядок может учитываться иначе в зависимости от постановки задачи.
Как построить сопряжённую диаграмму
Поменяем строки и столбцы местами, отразив рисунок относительно главной диагонали. Длины столбцов исходной формы станут длинами строк новой. Их последовательность называют сопряжённым разбиением .
В форме первый столбец содержит три клетки, второй - две, третий и четвёртый - по одной. Поэтому . В ней по-прежнему семь клеток, но теперь четыре строки. Если сопрячь результат ещё раз, вернётся исходная форма. В общем виде равно числу строк исходной диаграммы, длина которых не меньше .
Это преобразование полезно при вычислении крюков и при изучении симметрии форм. Самосопряжённая диаграмма совпадает со своим отражением; например, обладает таким свойством. Не всякое разбиение с одинаковым числом строк и столбцов самосопряжённо: нужно сравнить все соответствующие длины.
Диаграмма и стандартная таблица
Диаграмма задаёт только форму. Таблица Юнга получается, когда в её клетки помещают числа по определённым правилам. В стандартной таблице формы из клеток используют каждое число от 1 до ровно один раз. В нашей ориентации числа строго возрастают слева направо в строках и сверху вниз в столбцах.
Для формы подходит, например, такое заполнение:
Пустые позиции справа не входят в диаграмму. В первой строке , во второй ; в первом столбце , во втором . Числа от 1 до 7 использованы по одному разу. Например, переставить 2 и 3 в этой таблице можно, а переставить 1 и 7 нельзя: нарушится возрастание.
Стандартная таблица также записывает историю роста диаграммы: клетку с числом добавляют на шаге . Поскольку все клетки слева и сверху имеют меньшие числа, каждый промежуточный набор клеток остаётся диаграммой. И наоборот, пронумеровав клетки в порядке допустимого добавления, получим стандартную таблицу. Это соответствие помогает понять, что именно подсчитывается формулой ниже.
Существуют и полустандартные таблицы: в них обычно разрешают повторения и требуют неубывания строк при строгом возрастании столбцов. Правила заполнения важно указывать явно: формула для стандартных таблиц не считает произвольные заполнения или все полустандартные таблицы.
Крюк клетки и формула подсчёта
Крюк выбранной клетки состоит из неё самой, клеток справа в той же строке и клеток ниже в том же столбце. Длина крюка - число клеток в этом объединении. Клетки слева и сверху не входят в крюк. Для первой клетки формы это сама клетка, три справа и две снизу: длина равна шести.

На рисунке длины крюков по строкам равны ; ; . Их произведение равно . По формуле крюков число стандартных таблиц формы с клетками равно
Здесь произведение берётся по всем клеткам диаграммы, а - произведение целых чисел от 1 до . Для нашего примера , следовательно, . У формы одна и та же сетка, но ей соответствуют 35 различных стандартных заполнений. Формулировку и примеры формулы можно сверить с учебником Ричарда Стэнли по алгебраической комбинаторике.
Интерактив считает тот же результат для трёх непустых строк длиной до пяти клеток. Если уменьшить верхнюю строку, нижние при необходимости тоже сократятся: это сохраняет условие разбиения. Инструмент показывает длины всех крюков, а не сами заполненные таблицы; их число вычисляется по формуле. Для принципа умножения отдельных множителей см. также правила суммы и произведения в комбинаторике.
Как проверить результат вручную
Для небольшой формы удобно дополнить формулу независимым рассуждением через последние клетки. Самое большое число стандартной таблицы обязано стоять во внешнем углу: если бы справа или снизу оставалась клетка, её число должно было бы быть ещё больше. У формы есть три таких угла, расположенных в концах первой, второй и третьей строк. Удалив один из них вместе с числом 7, получаем допустимую таблицу на шести клетках.
Отсюда следует практический способ проверки: отдельно посчитать таблицы каждой из трёх оставшихся форм и сложить результаты. Группы не пересекаются, поскольку положение числа 7 различается. Далее тот же приём можно повторять для каждой меньшей формы, пока не останется пустая диаграмма. Ей соответствует одна пустая таблица: это начальное значение подсчёта. Такой рекурсивный метод объясняет логику перебора, хотя для больших форм формула крюков обычно удобнее.
Можно проверить и крайние случаи. У одной строки все числа вынуждены идти по возрастанию, поэтому стандартная таблица единственная. То же верно для одного столбца. Если расчёт для этих форм дал другое число, ошибка находится в выделении клеток крюка или в произведении длин.
Зачем эти формы в математике и алгоритмах
Диаграмма позволяет хранить разбиение как короткий список длин строк. Проверка формы сводится к сравнению соседних чисел, а сопряжённое разбиение можно построить подсчётом строк, доходящих до каждого столбца. Такие операции удобны в алгоритмах перечисления разбиений и таблиц: вместо перебора произвольных наборов клеток алгоритм добавляет только допустимые внешние углы.
Таблицы появляются и в соответствии Робинсона - Шенстеда: перестановке ставится в соответствие пара стандартных таблиц одинаковой формы. Это связь между порядком элементов и геометрией заполнений; сама форма отражает свойства возрастающих и убывающих подпоследовательностей. При решении задачи важно различать перестановку, пару таблиц и одну таблицу: их количества не обязаны совпадать. Основы подсчёта упорядочиваний разобраны в статье о перестановках с повторениями.
Есть связь и с теорией представлений: разбиения индексируют неприводимые комплексные представления симметрической группы , а число равно размерности соответствующего представления. Это более глубокий результат, чем формула крюков сама по себе. Общее значение слова «представление» в алгебре поясняется в статье о фундаментальном представлении группы.
Частые ошибки
- Рисуют строки в произвольном порядке. Для выбранной английской ориентации каждая строка должна быть не длиннее предыдущей и начинаться у одного левого края.
- Считают в крюке всю строку и весь столбец. Берут только клетки справа и снизу вместе с выбранной клеткой, причём её считают один раз.
- Путают форму и заполнение. Одной диаграмме может соответствовать несколько стандартных таблиц; для их 35.
- Применяют формулу к другой задаче. Формула выше считает именно стандартные таблицы обычной формы, а не произвольные заполнения.
FAQ
Диаграмма Юнга связана с психологией Карла Юнга?
Нет. Название связано с математиком Альфредом Юнгом; задача относится к комбинаторике и теории представлений.
Можно ли использовать разбиение с нулями?
При записи разбиения обычно перечисляют только положительные части. Нули в конце иногда добавляют для удобства вычислений, но они не создают новых строк клеток и не меняют диаграмму.
Всегда ли число таблиц целое?
Да. Формула крюков даёт количество стандартных таблиц, поэтому для любой корректной формы результат - целое число. Если получилась дробь, стоит перепроверить длины крюков и факториал.
Коротко
Диаграмма Юнга изображает разбиение числа строками клеток, а стандартная таблица добавляет числа с возрастанием по строкам и столбцам. Сопряжение меняет строки и столбцы местами. Формула крюков позволяет посчитать стандартные заполнения: для формы это .
Читайте также

Числа Белла: разбиения множества и формула
Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

Комбинаторика: размещения и формулы подсчёта
Размещения в комбинаторике: как учитывать порядок и повторения, вывести формулу, решить задачи с ограничениями и проверить ответ на конкретных примерах с разбором.

Метод шаров и перегородок: формулы и примеры
Метод шаров и перегородок помогает считать распределения одинаковых предметов и решения целочисленных уравнений. Разбираем формулы, ограничения и примеры.

Мультимножество: кратности, операции и примеры
Мультимножество простыми словами: как считать кратности, отличать сумму от объединения, находить пересечение и разность, работать с повторами в Python и решать задачи.

Мультиномиальный коэффициент: формула и примеры
Мультиномиальный коэффициент показывает число способов получить одночлен при раскрытии степени суммы. Разбираем формулу, пример, связь с вероятностью и расчёт без переполнения.

Разбиение числа на слагаемые: подсчёт и алгоритм
Разбиение числа на слагаемые без учёта порядка: примеры, отличие от упорядоченных сумм, рекуррентная формула и алгоритм динамического программирования.