Алгоритм Робинсона — Шенстеда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном (англ.) в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества

где означает, что пробегает все разбиения и  — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки .

Алгоритм[править | править вики-текст]

Алгоритм Робинсона — Шенстеда начинает работу с перестановки , записанной в лексикографическом порядке:

где , и продолжает, создавая последовательность упорядоченных пар таблиц Юнга той же формы:

где  — пустые таблицы. На выходе получаются таблицы и .

На основе построенной формируется путём вставки Шенстеда (см. ниже) в . К добавляется в квадрат, добавленный к форме при вставке, чтобы формы для и были одинаковы для каждого . Таким образом, стандартная таблица записывает перестановку, а  — регистрирует «рост» диаграммы Юнга[1].

Вставка (4):
• (4) заменяет (5) в первой строке
• (5) заменяет (8) во второй строке
• (8) записывается в начало новой строки

Неформальное описание вставки Шенстеда[править | править вики-текст]

Для вставки строки в таблицу :

   1. сделать первую строку T текущей
   2. в текущей строке найти первый элемент, который больше x
   3. если такой элемент найден
        обменять значения x и найденной ячейки
        сделать следующую строку текущей
        перейти на шаг 2.
      иначе:
        добавить x к концу текущей строки
        закончить

Вариации и обобщения[править | править вики-текст]

  • Шенстед независимо обнаружил алгоритм и обобщил его для случая  — любая последовательность из чисел (то есть, возможно, с повторениями). В этом случае является полустандартной.
  • Алгоритм Робинсона — Шенстеда — Кнута был разработан Кнутом и устанавливает биективное соответствие между обобщенными перестановками (двустрочные массивы лексикографически упорядоченных положительных целых чисел) и парами полустандартных таблиц Юнга.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]