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

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

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

Алгоритм

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

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}}$

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

${\displaystyle (P_{0},Q_{0}),(P_{1},Q_{1}),(P_{2},Q_{2}),\ldots ,(P_{n},Q_{n}),}$

где ${\displaystyle P_{0}=Q_{0}=\varnothing }$ — пустые таблицы. На выходе получаются таблицы ${\displaystyle P=P_{n}}$ и ${\displaystyle Q=Q_{n}}$ .

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

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

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

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

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

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

Примечания

Литература

• . — Сб. статей 1981. — М. : Мир, 1985. — С. -112. — 128 с.
• Уильям Фултон. Таблицы юнга и их приложения к теории представлений и геометрии = Young Tableaux With Application to Representation Theory and Geometry. — М. : Издательство МЦНМО, 2006. — ISBN 5-94057-165-4 .
• Knuth, Donald E. (англ.) .
• Robinson, G. de B. (англ.) // American Journal of Mathematics . — The Johns Hopkins University Press, 1938. — Vol. 60 , no. 3 . — P. 745–760 . — ISSN . — doi : .
• Schensted, C. (англ.) // Canadian Journal of Mathematics. — 1961. — Vol. 13 . — P. 179-191 . — ISSN .
• Stanley, Richard P. (англ.) . — Cambridge University Press , 1999. — Vol. 62 .
• 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 . — ISSN . — doi : .