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

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

$\sum _{\lambda ⊢n}(f^{\lambda }{)}^2=n!$

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

Алгоритм

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

$\left(\begin{array}{ccccc}1& 2& 3& \cdots & n\\ {\sigma }_1& {\sigma }_2& {\sigma }_3& \cdots & {\sigma }_n\end{array}\right)$

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

$(P_0,Q_0),(P_1,Q_1),(P_2,Q_2),\dots ,(P_n,Q_n),$

где $P_0=Q_0=\varnothing$ — пустые таблицы. На выходе получаются таблицы $P=P_n$ и $Q=Q_n$.

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья