Перейти к содержанию

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

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

Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном[англ.] в 1938, который устанавливает биективное соответствие между элементами симметрической группы [math]\displaystyle{ S_n }[/math] и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества

[math]\displaystyle{ \sum_{\lambda\vdash n} (f^\lambda)^2= n! }[/math]

где [math]\displaystyle{ \lambda\vdash n }[/math] означает, что [math]\displaystyle{ \lambda }[/math] пробегает все разбиения [math]\displaystyle{ n }[/math] и [math]\displaystyle{ f^\lambda }[/math] — количество стандартных диаграмм Юнга формы [math]\displaystyle{ \lambda }[/math]. Это достигается путём построения отображения из пар [math]\displaystyle{ \lambda }[/math]-таблиц [math]\displaystyle{ (P,Q) }[/math] в перестановки [math]\displaystyle{ \sigma }[/math].

Алгоритм

Алгоритм Робинсона — Шенстеда начинает работу с перестановки [math]\displaystyle{ \sigma }[/math], записанной в лексикографическом порядке:

[math]\displaystyle{ \begin{pmatrix}1 & 2 & 3 & \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \cdots & \sigma_n \end{pmatrix} }[/math]

где [math]\displaystyle{ \sigma(i)=\sigma_i }[/math], и продолжает, создавая последовательность упорядоченных пар таблиц Юнга той же формы:

[math]\displaystyle{ (P_0,Q_0), (P_1,Q_1),(P_2,Q_2),\ldots,(P_n,Q_n), }[/math]

где [math]\displaystyle{ P_0 = Q_0 = \varnothing }[/math] — пустые таблицы. На выходе получаются таблицы [math]\displaystyle{ P=P_n }[/math] и [math]\displaystyle{ Q=Q_n }[/math].

На основе построенной [math]\displaystyle{ P_{i-1} }[/math] формируется [math]\displaystyle{ P_{i} }[/math] путём вставки Шенстеда (см. ниже) [math]\displaystyle{ \sigma(i) }[/math] в [math]\displaystyle{ P_{i-1} }[/math]. К [math]\displaystyle{ Q_{i} }[/math] добавляется [math]\displaystyle{ i }[/math] в квадрат, добавленный к форме при вставке, чтобы формы для [math]\displaystyle{ P_{i} }[/math] и [math]\displaystyle{ Q_{i} }[/math] были одинаковы для каждого [math]\displaystyle{ i }[/math]. Таким образом, стандартная таблица [math]\displaystyle{ P }[/math] записывает перестановку, а [math]\displaystyle{ Q }[/math] — регистрирует «рост» диаграммы Юнга[1].

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

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

Для вставки строки [math]\displaystyle{ x }[/math] в таблицу [math]\displaystyle{ T }[/math]:

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

Вариации и обобщения

Примечания

  1. Ольшанский Г. Асимптотическая теория представлений II. Записки лекций. Архивная копия от 22 декабря 2015 на Wayback Machine Запись Л. Петрова, 2010

Литература