Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном (англ.) в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества
где означает, что пробегает все разбиения и — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки .
Алгоритм
Алгоритм Робинсона — Шенстеда начинает работу с перестановки, записанной в лексикографическом порядке:
где , и продолжает, создавая последовательность упорядоченных пар таблиц Юнга той же формы:
где — пустые таблицы. На выходе получаются таблицы и .
На основе построенной формируется путём вставки Шенстеда (см. ниже) в . К добавляется в квадрат, добавленный к форме при вставке, чтобы формы для и были одинаковы для каждого . Таким образом, стандартная таблица записывает перестановку, а — регистрирует «рост» диаграммы Юнга[1].
Вставка (4):
• (4) заменяет (5) в первой строке
• (5) заменяет (8) во второй строке
• (8) записывается в начало новой строки
Неформальное описание вставки Шенстеда
Для вставки строки в таблицу :
1. сделать первую строку T текущей
2. в текущей строке найти первый элемент, который больше x
3. если такой элемент найден
обменять значения x и найденной ячейки
сделать следующую строку текущей
перейти на шаг 2.
иначе:
добавить x к концу текущей строки
закончить
Вариации и обобщения
Шенстед независимо обнаружил алгоритм и обобщил его для случая — любая последовательность из чисел (то есть, возможно, с повторениями). В этом случае является полустандартной.
Живые числа.— Сб. статей 1981.— М.: Мир, 1985.— С.105-112.— 128с.
Уильям Фултон.Таблицы юнга и их приложения к теории представлений и геометрии=Young Tableaux With Application to Representation Theory and Geometry.— М: Издательство МЦНМО, 2006.— ISBN 5-94057-165-4.
Zelevinsky, A. V.A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence(англ.)// Journal of Algebra.— 1981.— Vol. 69, no. 1.— P. 82-94.— ISSN0021-8693.— DOI:10.1016/0021-8693(81)90128-9.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.
2019-2025 WikiSort.ru - проект по пересортировке и дополнению контента Википедии