В математике , то соответствие Робинсон-Шенстед-Кнут , также упоминаются как RSK переписка или RSK алгоритм , является комбинаторной взаимно однозначным соответствием между матрицами А с неотрицательными целыми записями и паром ( P , Q ) в полустандартных Юнга равной формы, чей размер равен сумме элементов матрицы A . Точнее, вес P задается суммами по столбцам A , а вес Q - суммами по строкам. Это обобщениеСоответствие Робинсона – Шенстеда в том смысле, что если A является матрицей перестановок , пара ( P , Q ) будет парой стандартных таблиц, связанных с перестановкой в соответствии с соответствием Робинсона – Шенстеда.
Соответствие Робинсона-Шенстеда-Кнут расширяет многие из замечательных свойств переписки Робинсона-Шенстеда , в частности ее симметрии: транспонирование матрицы А приводит к перестановке Tableaux P , Q .
Соответствие Робинсона – Шенстеда – Кнута
Вступление
Соответствие Робинсона – Шенстеда - это биективное отображение между перестановками и парами стандартных таблиц Юнга , имеющих одинаковую форму. Эта биекция может быть построена с использованием алгоритма, называемого вставкой Шенстеда , начиная с пустой таблицы и последовательно вставляя значения σ 1 ,…, σ n перестановки σ в числа 1,2,… n ; они образуют вторую строку, если σ дано в двухстрочной записи:
.
Первая стандартная таблица P - результат последовательных вставок; другая стандарт таблица Q записывает последовательные формы промежуточных таблиц при строительстве P .
Вставка Шенстеда легко обобщается на случай, когда σ имеет повторяющиеся записи; в этом случае соответствие будет давать полустандартную таблицу P, а не стандартную таблицу, но Q все равно будет стандартной таблицей. Определение RSK переписка восстанавливающей симметрия между P и Q таблицами, производя полустандартную таблицу для Q , а также.
Двухстрочные массивы
Массив две строки (или обобщенная подстановка ) ш А , соответствующий матрице А определяется [1] , как
в котором для любой пары ( i , j ), которая индексирует запись A i , j из A , есть столбцы A i , j, равные, и все столбцы в лексикографическом порядке, что означает, что
- , а также
- если а также тогда .
Пример
Двухстрочный массив, соответствующий
является
Определение соответствия
Применяя алгоритм вставки Шенстеда к нижней строке этого двухстрочного массива, мы получаем пару, состоящую из полустандартной таблицы P и стандартной таблицы Q 0 , где последнюю можно превратить в полустандартную таблицу Q , заменив каждую запись b из Q 0 с помощью B -го входа в верхней строке ш A . Таким образом, получается биекция из матриц A в упорядоченные пары [2] ( P , Q ) полустандартных таблиц Юнга той же формы, в которых набор элементов P совпадает со второй строкой w A , а множество вхождений Q является то , что в первой строке ш A . Число записей J в Р , следовательно , равен сумме показателей в колонке J из А , а число записей I в Q равна сумме записей в строке я из A .
Пример
В приведенном выше примере результат применения вставки Шенстеда для последовательной вставки 1,3,3,2,2,1,2 в первоначально пустую таблицу приводит к таблице P и дополнительной стандартной таблице Q 0, перекодирующей последовательные формы. , данный
и после последовательной замены элементов 1,2,3,4,5,6,7 в Q 0 на 1,1,1,2,2,3,3 получается пара полустандартных таблиц
Прямое определение корреспонденции RSK
В приведенном выше определении используется алгоритм Шенстеда, который создает стандартную таблицу записи Q 0 и модифицирует ее, чтобы учесть первую строку двухстрочного массива и создать полустандартную таблицу записи; это делает очевидной связь с соответствием Робинсона – Шенстеда . Однако естественно упростить конструкцию, изменив часть алгоритма записи формы, чтобы непосредственно учитывать первую строку двухстрочного массива; именно в такой форме обычно описывается алгоритм соответствия RSK. Это просто означает, что после каждого шага вставки Schensted таблица Q расширяется путем добавления в качестве записи нового квадрата b-й записи i b первой строки таблицы w A , где b - текущий размер таблиц. То, что при этом всегда получается полустандартная таблица, следует из свойства (впервые обнаруженного Кнутом [2] ), что для последовательных вставок с идентичным значением в первой строке w A каждый последующий квадрат, добавленный к фигуре, находится в столбце строго по отношению к справа от предыдущего.
Вот подробный пример такой конструкции обеих полустандартных таблиц. Соответствует матрице
один имеет двухстрочный массив
В следующей таблице показано построение обеих таблиц для этого примера.
Вставленная пара | ||||||||
п | ||||||||
Q |
Комбинаторные свойства RSK-соответствия
Случай перестановочных матриц
Если является матрица перестановок , то RSK выходов стандартных таблиц Юнга (SYT), такой же формы . Наоборот, если SYT имеют одинаковую форму , то соответствующая матрица матрица перестановок. В результате этого свойства, просто сравнивая мощности двух множеств по обе стороны биективного отображения, мы получаем следующее следствие:
Следствие 1 : Для каждого у нас есть где средства изменяется во всех разделах в а также число стандартных таблиц Юнга формы .
Симметрия
Позволять - матрица с неотрицательными элементами. Предположим, что алгоритм RSK отображает к тогда алгоритм RSK отображает к , где это транспонирование . [1]
В частности, в случае матриц перестановок восстанавливается симметрия соответствия Робинсона – Шенстеда: [3]
Теорема 2 : если перестановка соответствует тройке , то обратная перестановка ,, соответствует .
Это приводит к следующему соотношению между количеством инволюций на с количеством таблиц, которые можно составить из ( Инволюция - это перестановка, которая сама себе обратна ): [3]
Следствие 2 : количество таблиц, которые можно составить из равно количеству инволюций на .
Доказательство : если инволюция, соответствующая , тогда соответствует ; следовательно. Наоборот, если любая перестановка, соответствующая , тогда также соответствует ; следовательно. Итак, между инволюциями существует однозначное соответствие. и картины
Количество инволюций на дается повторением:
Где . Решая эту рекурсию, мы можем получить количество инволюций на,
Симметричные матрицы
Позволять и пусть алгоритм RSK отображает матрицу к паре , где SSYT формы . [1] Пусть где а также . Тогда карта устанавливает биекцию между симметричными матрицами со строкой () и SSYT типа .
Заявления о переписке RSK
Личность Коши
Соответствие Робинсона – Шенстеда – Кнута обеспечивает прямое биективное доказательство следующего знаменитого тождества для симметричных функций:
где являются функциями Шура .
Костки номера
Починить перегородки , тогда
где а также обозначим числа Костки и количество матриц , с неотрицательными элементами, с строкой () и столбец () .
Рекомендации
- ^ a b c Стэнли, Ричард П. (1999). Перечислительная комбинаторика . 2 . Нью-Йорк: Издательство Кембриджского университета. С. 316–380. ISBN 0-521-55309-1.
- ^ а б Кнут, Дональд Э. (1970). «Перестановки, матрицы и обобщенные таблицы Юнга» . Тихоокеанский математический журнал . 34 (3): 709–727. DOI : 10,2140 / pjm.1970.34.709 . Руководство по ремонту 0272654 .
- ^ а б Кнут, Дональд Э. (1973). Искусство программирования, Vol. 3: Сортировка и поиск . Лондон: Аддисон – Уэсли. С. 54–58. ISBN 0-201-03803-X.
- Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. 108 . Кембридж: Издательство Кембриджского университета . С. 135–162 . ISBN 0-521-86565-4. Zbl 1106.05001 .