Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества
где означает, что пробегает все разбиения и — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки .
Алгоритм Алгоритм Робинсона — Шенстеда начинает работу с перестановки , записанной в лексикографическом порядке:
где , и продолжает, создавая последовательность упорядоченных пар таблиц Юнга той же формы:
где — пустые таблицы. На выходе получаются таблицы и .
На основе построенной формируется путём вставки Шенстеда (см. ниже) в . К добавляется в квадрат, добавленный к форме при вставке, чтобы формы для и были одинаковы для каждого . Таким образом, стандартная таблица записывает перестановку, а — регистрирует «рост» диаграммы ЮнгаОльшанский Г. Асимптотическая теория представлений II. Записки лекций. Запись Л. Петрова, 2010.
Неформальное описание вставки Шенстеда Для вставки строки в таблицу :
1. сделать первую строку T текущей 2. в текущей строке найти первый элемент, который больше x 3. если такой элемент найден обменять значения x и найденной ячейки сделать следующую строку текущей перейти на шаг 2. иначе: добавить x к концу текущей строки закончить
Вариации и обобщения Шенстед независимо обнаружил алгоритм и обобщил его для случая — любая последовательность из чисел (то есть, возможно, с повторениями). В этом случае является полустандартной. был разработан Кнутом и устанавливает биективное соответствие между обобщенными перестановками (двустрочные массивы лексикографически упорядоченных положительных целых чисел) и парами полустандартных таблиц Юнга.
Примечания
Литература
Категория:Комбинаторика Категория:Комбинаторные алгоритмы Категория:Теория представлений конечных групп