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

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

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

\sum_{\lambda\vdash n} (f^\lambda)^2= n!

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

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

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

\begin{pmatrix}1 & 2 & 3 & \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \cdots & \sigma_n \end{pmatrix}

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

(P_0,Q_0), (P_1,Q_1),(P_2,Q_2),\ldots,(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 — регистрирует «рост» диаграммы Юнга[1].

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

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

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

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

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

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

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

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