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

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

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

Robinson-Schensted алгоритм начинается от перестановки b написано в Лексикографические две линии нотации

где b(i) = bi, или вообще каких-либо Лексикографически упорядоченную последовательность пар

с a я ≤ a , я + 1 и b я ≤ б , я + 1 при a я = a I + 1 , и доходов, создав последовательность упорядоченных пар молодых прибавились же фигуры:

где  являются null экспортировались. Выходной semistandard прибавились являются P = Pn и Q = Qn. Последовательности строится путем, на каждый шаг построения Pi,вставив bi в Pi − 1 и строительства Qi, размещение (Добавление элемента на указанный угол) ai в Qi − 1.

Учитывая молодой доски T, чтобы Вставить строку x в T,

• Установите R равным первой строке T

Хотя R содержит элемент больше, чем x, делать

* Пусть y быть наименьшим элементом R больше, чем x.

* Заменить y по x в R.

* Установить x = y и R равным следующую строку вниз.

• Место x в конце строки R и стоп.

Таким образом алгоритм Robinson-Schensted действует следующим образом

• Установите 

Для i = 1 для n

* Построить Pi, добавив строку bi в Pi − 1

* Построить Qi, поставив ai в Qi − 1 на том же углу курсор прекращено (так, что Pi и Qi имеют одинаковую форму)

Возвращение (Pn,Qn) Алгоритм обратима и производит пара semistandard молодых прибавились, которые являются стандартной молодых прибавились если ai = i и bi являются перестановка. Кроме того если перестановка b дает пару (Pn,Qn) его обратная permuation b − 1 дает пару (Qn,Pn). В более общем плане если пара a,b дает пару (Pn,Qn) тогда b,a дает пару(Qn,Pn).