Соответствие Робинсона-Шенстеда-Кнута

Соответствие Робинсона-Шенстеда-Кнута (также известное как алгоритм RSK, от англ. Robinson–Schensted–Knuth correspondence) — это биективное отображение между множеством матриц с неотрицательными целыми элементами (или, в частном случае, перестановок) и парами полустандартных таблиц Юнга одинаковой формы. Это фундаментальный результат комбинаторики и теории представлений, обобщающий классическое соответствие Робинсона-Шенстеда для перестановок. Соответствие устанавливает глубокую связь между комбинаторными объектами, симметрическими функциями и представлениями симметрической группы.

История

Соответствие берёт начало в работах Гилберта де Бомона Робинсона (1938), который описал алгоритм для перестановок, и Крейга Шенстеда (1961), который независимо переоткрыл и формализовал его. В 1970 году Дональд Кнут обобщил конструкцию на случай произвольных матриц с неотрицательными целыми элементами, что позволило применять соответствие к более широкому классу задач, включая теорию симметрических функций и комбинаторную интерпретацию тождеств.

Определение и базовые понятия

Таблицы Юнга

Полустандартная таблица Юнга (ПСТЮ) — это заполнение клеток диаграммы Юнга (конечного множества клеток, выровненных по левому краю, с невозрастающей длиной строк) целыми положительными числами, которое удовлетворяет двум условиям:

• числа строго возрастают вдоль столбцов (сверху вниз);
• числа не убывают вдоль строк (слева направо).

Стандартная таблица Юнга — частный случай ПСТЮ, где каждое число от 1 до n встречается ровно один раз.

Матрицы и перестановки

В простейшем случае соответствие RSK сопоставляет перестановке π (записанной в виде матрицы перестановок) пару стандартных таблиц Юнга одинаковой формы. В обобщённом виде оно работает с матрицами A размера m × n с неотрицательными целыми элементами aᵢⱼ. Каждой такой матрице ставится в соответствие пара ПСТЮ (P, Q) одинаковой формы, где P — таблица вставки, а Q — таблица записи.

Алгоритм

Вставка Шенстеда

Основная операция алгоритма — вставка Шенстеда (или RSK-вставка). Пусть имеется ПСТЮ T и число x. Процедура вставки:

1. Найти первую строку таблицы T. Если x больше или равно всем элементам строки, поместить x в конец строки (создав новую клетку). Процесс завершён.
2. Иначе найти самый левый элемент в строке, который строго больше x (обозначим его y). Заменить y на x.
3. Взять y и повторить шаги 1–2 для следующей строки. Если текущая строка последняя, создать новую строку, содержащую y.

Этот процесс гарантирует, что после вставки таблица остаётся полустандартной.

Построение пары таблиц

Для матрицы A с элементами aᵢⱼ алгоритм RSK выполняется следующим образом:

• Для каждой пары (i, j), где aᵢⱼ > 0, выполнить aᵢⱼ раз вставку числа j в таблицу P. При этом каждый раз в таблицу Q вставляется число i в позицию, соответствующую новой клетке, созданной в P в результате вставки. Если i и j упорядочены лексикографически (по i, затем по j), то результат однозначен.
• Начальные таблицы P и Q пусты.

В результате получается пара ПСТЮ (P, Q) одинаковой формы. Для перестановок (когда aᵢⱼ = 1 для i = π(j) и 0 иначе) таблицы P и Q являются стандартными.

Свойства

Биективность

Соответствие RSK является биекцией между множеством матриц с неотрицательными целыми элементами и множеством пар ПСТЮ одинаковой формы. Это означает, что каждой матрице соответствует единственная пара таблиц, и наоборот, по любой паре таблиц можно восстановить исходную матрицу.

Симметрия

Одно из ключевых свойств: если матрице A соответствует пара (P, Q), то транспонированной матрице Aᵀ соответствует пара (Q, P). Это свойство отражает дуальность между строками и столбцами.

Длина наибольшей возрастающей подпоследовательности

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

Применение

Комбинаторика

Соответствие RSK используется для доказательства комбинаторных тождеств, таких как тождество Коши для симметрических функций: ∑_{λ} s_λ(x) s_λ(y) = ∏_{i,j} (1 - x_i y_j)^{-1}, где s_λ — функция Шура, а сумма берётся по всем разбиениям λ. RSK даёт биективное доказательство этого тождества, интерпретируя произведение как сумму по матрицам, а пары таблиц — как разбиения.

Теория представлений

В теории представлений симметрической группы S_n соответствие RSK связывает перестановки с парами стандартных таблиц Юнга, что лежит в основе построения неприводимых представлений. Каждой перестановке сопоставляется её форма (разбиение), которая определяет неприводимое представление, в котором она действует.

Алгебраическая комбинаторика

RSK применяется в изучении алгебр Гекке, квантовых групп и в теории игр (например, в задаче о «русском кресте» и в анализе алгоритмов сортировки). Оно также используется для вычисления статистик на перестановках, таких как число инверсий и длина наибольшей возрастающей подпоследовательности.

Пример

Рассмотрим перестановку π = (3, 1, 4, 2). Запишем её в виде последовательности пар: (1,3), (2,1), (3,4), (4,2). Выполним вставки:

1. Вставить 3 в пустую P: P = [3]. В Q вставить 1: Q = [1].
2. Вставить 1: в первой строке 3 > 1, заменяем 3 на 1, вытесненное 3 вставляем во вторую строку: P = [[1], [3]]. В Q вставить 2 в позицию новой клетки: Q = [[1], [2]].
3. Вставить 4: в первой строке 4 > 1, добавляем в конец: P = [[1, 4], [3]]. В Q вставить 3 в позицию новой клетки: Q = [[1, 3], [2]].
4. Вставить 2: в первой строке 2 > 1, но 4 > 2, заменяем 4 на 2, вытесненное 4 вставляем во вторую строку: во второй строке 3 < 4, добавляем в конец: P = [[1, 2], [3, 4]]. В Q вставить 4 в позицию новой клетки: Q = [[1, 3], [2, 4]].

Итоговая пара: P = [[1, 2], [3, 4]], Q = [[1, 3], [2, 4]]. Обе таблицы стандартные, форма — разбиение (2,2).

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

Соответствие Бёрджесса

Для перестановок существует также соответствие Бёрджесса (или алгоритм Бёрджесса), которое даёт другую биекцию между перестановками и парами стандартных таблиц, но с иным правилом вставки. RSK и Бёрджесс связаны через обратную перестановку.

RSK для слов

Соответствие может быть адаптировано для слов (последовательностей символов), где таблица P строится по вставке символов, а Q — по их позициям. Это используется в анализе алгоритмов и в комбинаторике слов.

Квантовое RSK

В квантовой комбинаторике существует обобщение RSK, связанное с квантовыми группами и кристаллами, где таблицы заменяются на кристаллы, а вставка — на комбинацию кристаллических операций.

Критика и ограничения

Хотя RSK является мощным инструментом, его применение ограничено размером таблиц: для больших перестановок (например, n > 10⁵) прямое построение таблиц становится ресурсоёмким. Кроме того, соответствие не даёт простого способа восстановления матрицы по таблицам без обратного алгоритма, который также требует времени O(n²) в худшем случае. В некоторых задачах, таких как анализ случайных перестановок, RSK используется в сочетании с вероятностными методами, но его детерминированная природа может быть избыточной.

Источники

• Knuth, D. E. (1970). "Permutations, matrices, and generalized Young tableaux". Pacific Journal of Mathematics, 34(3), 709–727.
• Stanley, R. P. (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press.
• Fulton, W. (1997). Young Tableaux: With Applications to Representation Theory and Geometry. Cambridge University Press.
• Sagan, B. E. (2001). The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions (2nd ed.). Springer.