Введение

В математике соответствие Робинсона — Шенстеда — это биективное соответствие между перестановками и парами стандартных таблиц Янга одинаковой формы. Оно имеет различные описания, все из которых носят алгоритмический характер, обладает множеством замечательных свойств и находит применение в комбинаторике и других областях, таких как теория представлений. Соответствие было обобщено многими способами, в частности, Кнутом, что привело к известному соответствию Робинсона — Шенстеда — Кнута, а также к дальнейшему обобщению Зелевинским на случай диаграмм. Наиболее простое описание соответствия использует алгоритм Шенстеда — процедуру, которая последовательно вставляет значения перестановки в одну таблицу согласно определённому правилу, а другая таблица фиксирует изменение формы в процессе построения. Ранее, в несколько иной форме, соответствие было описано Робинсоном в попытке доказать правило Литтлвуда — Ричардсона. Часто соответствие называют алгоритмом Робинсона — Шенстеда, хотя процедура, использованная Робинсоном, радикально отличается от алгоритма Шенстеда и практически забыта. Другие способы определения соответствия включают недетерминированный алгоритм, основанный на игре «jeu de taquin». Биективный характер соответствия связывает его с перечислительной тождеством

где обозначает множество разбиений числа n (или диаграмм Янга с n клетками), а tλ — количество стандартных таблиц Янга формы λ.

Вставка

Основная процедура, используемая для вставки каждого σi, называется вставкой Шенстеда или вставкой по строкам (чтобы отличать её от вариантной процедуры, называемой вставкой по столбцам). Её простейшая форма определяется в терминах "неполных стандартных таблиц": как и стандартные таблицы, они имеют различные записи, образующие возрастающие строки и столбцы, но некоторые значения (которые ещё предстоит вставить) могут отсутствовать в качестве элементов. Процедура принимает в качестве аргументов такую таблицу T и значение x, отсутствующее в таблице T; она выдаёт новую таблицу, обозначаемую T ← x, и квадрат s, на который увеличилась её форма. Значение x появляется в первой строке T ← x, либо будучи добавленным в конец (если в таблице нет элементов, больших x), либо заменяя первый элемент y > x в первой строке T. В первом случае s – это квадрат, в который добавляется x, и вставка завершена; во втором случае заменённый элемент y аналогично вставляется во вторую строку T, и так далее, пока не будет применён первый случай (что обязательно произойдёт, если будет достигнута пустая строка T). Более формально, следующий псевдокод описывает вставку нового значения x в таблицу T по строкам.
Установите i и j равными единице больше, чем длина первой строки T.
Пока j > 1 и x < Ti, j−1, уменьшите j на 1. (Теперь (i, j) – это первый квадрат в строке i, содержащий либо элемент, больший x, в таблице T, либо вообще не содержащий элемента.) Если квадрат (i, j) пуст в T, завершите процесс после добавления x в T в квадрат (i, j) и установки s. Поменяйте местами значения x и Ti, j. (Это вставляет исходное x в строку i и сохраняет значение, которое оно заменило, для вставки в следующую строку.) Увеличьте i на 1 и вернитесь к шагу 2. Форма T увеличивается ровно на один квадрат, а именно s.

Правильность

Тот факт, что матрица T ← x имеет неубывающие строки и столбцы, если то же самое верно для T, не очевиден из данной процедуры (элементы в одном и том же столбце никогда даже не сравниваются). Однако это можно показать следующим образом. В любой момент времени, кроме непосредственно после шага 4, элемент (i, j) в матрице T либо пуст, либо содержит значение, большее чем x; шаг 5 восстанавливает это свойство, поскольку (i, j) теперь является элементом непосредственно под тем, который первоначально содержал x в T. Таким образом, эффект замены на шаге 4 на значение Ti, j заключается в его уменьшении; в частности, оно не может стать больше, чем его правый или нижний соседи. С другой стороны, новое значение также не меньше, чем его левый сосед (если он существует), что обеспечивается сравнением, которое только что завершило шаг 2. Наконец, чтобы показать, что новое значение больше, чем его верхний сосед Ti−1, j (если он существует), заметим, что Ti−1, j сохраняется после шага 5, и что уменьшение j на шаге 2 только уменьшает соответствующее значение Ti−1, j.

Необратимость конструкции

Можно увидеть, что для любой пары (P, Q) стандартных таблиц Янга одинаковой формы существует обратная процедура, которая порождает перестановку, приводящую к (P, Q) посредством алгоритма Шенстеда. Она по сути заключается в прослеживании шагов алгоритма в обратном порядке, при этом каждый раз элемент из Q используется для определения ячейки, с которой следует начать обратную вставку, соответствующий элемент из P перемещается в предыдущую строку, и этот процесс продолжается вверх по строкам, пока не будет заменен элемент первой строки, который и является значением, вставленным на соответствующем шаге алгоритма построения. Эти два обратных алгоритма устанавливают биективное соответствие между перестановками из n элементов с одной стороны и парами стандартных таблиц Янга одинаковой формы, содержащими n ячеек, с другой стороны.

Применение теоремы Эрдоша-Шекереса

Соответствие Робинсона-Шенстеда можно использовать для простого доказательства теоремы Эрдеша — Секереша.