Переписка Робинсона – Шенстеда – Кнута - Robinson–Schensted–Knuth correspondence

В математике , то соответствие Робинсон-Шенстед-Кнут , также упоминаются как RSK переписка или RSK алгоритм , является комбинаторной взаимно однозначным соответствием между матрицами А с неотрицательными целыми записями и паром ( P , Q ) в полустандартных Юнга равной формы, чей размер равен сумме элементов матрицы A . Точнее, вес P задается суммами по столбцам A , а вес Q - суммами по строкам. Это обобщение соответствия Робинсона – Шенстеда в том смысле, что если A быть матрицей перестановок , пара ( P , Q ) будет парой стандартных таблиц, связанных с перестановкой в ​​соответствии с соответствием Робинсона – Шенстеда.

Соответствие Робинсона-Шенстеда-Кнут расширяет многие из замечательных свойств переписки Робинсона-Шенстеда , в частности ее симметрии: транспонирование матрицы А приводит к перестановке Tableaux P , Q .

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

Введение

Соответствие Робинсона – Шенстеда - это биективное отображение между перестановками и парами стандартных таблиц Юнга , имеющих одинаковую форму. Эта биекция может быть построена с использованием алгоритма, называемого вставкой Шенстеда , начиная с пустой таблицы и последовательно вставляя значения σ ₁ ,…, σ _n перестановки σ в числа 1,2,… n ; они образуют вторую строку, если σ дано в двухстрочной записи:

${\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & \ ldots & n \\\ sigma _ {1} & \ sigma _ {2} & \ ldots & \ sigma _ {n} \ end {pmatrix}}}$.

Первая стандартная таблица P - результат последовательных вставок; другая стандарт таблица Q записывает последовательные формы промежуточных таблиц при строительстве P .

Вставка Шенстеда легко обобщается на случай, когда σ имеет повторяющиеся записи; в этом случае соответствие будет давать полустандартную таблицу P, а не стандартную таблицу, но Q все равно будет стандартной таблицей. Определение RSK переписка восстанавливающей симметрия между P и Q таблицами, производя полустандартную таблицу для Q , а также.

Двухстрочные массивы

Массив две строки (или обобщенная подстановка ) ш _А , соответствующий матрице А определяется как

${\ displaystyle w_ {A} = {\ begin {pmatrix} i_ {1} & i_ {2} & \ ldots & i_ {m} \\ j_ {1} & j_ {2} & \ ldots & j_ {m} \ end {pmatrix }}}$

в котором для любой пары ( i , j ), которая индексирует запись A _{i , j} из A , имеется A _{i , j} столбцов, равных , и все столбцы находятся в лексикографическом порядке, что означает, что ${\ displaystyle {\ tbinom {i} {j}}}$

1. ${\ Displaystyle i_ {1} \ leq i_ {2} \ leq i_ {3} \ cdots \ leq i_ {m}}$, и
2. если а потом .${\ displaystyle i_ {r} = i_ {s} \,}$${\ displaystyle r \ leq s}$${\ displaystyle j_ {r} \ leq j_ {s}}$

пример

Двухстрочный массив, соответствующий

${\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}$

является

${\ displaystyle w_ {A} = {\ begin {pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 3 & 2 & 2 & 1 & 2 \ end {pmatrix}}}$

Определение соответствия

Применяя алгоритм вставки Шенстеда к нижней строке этого двухстрочного массива, мы получаем пару, состоящую из полустандартной таблицы P и стандартной таблицы Q ₀ , где последнюю можно превратить в полустандартную таблицу Q , заменив каждую запись b из Q ₀ с помощью B -го входа в верхней строке ш _A . Таким образом получают в биекция из матриц A для упорядоченных пар, ( P , Q ) полустандартных Юнга той же формы, в которых множество записей P является то , что второй линии ж _А , и набор записей Вопрос в том , что в первой строке ш _A . Число записей J в Р , следовательно , равен сумме показателей в колонке J из А , а число записей I в Q равна сумме записей в строке я из A .

пример

В приведенном выше примере результат применения вставки Шенстеда для последовательной вставки 1,3,3,2,2,1,2 в первоначально пустую таблицу приводит к таблице P и дополнительной стандартной таблице Q _0, перекодирующей последовательные формы , данный

${\ Displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q_ {0} \ quad = \ quad {\ begin {matrix} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ end {matrix}},}$

и после последовательной замены элементов 1,2,3,4,5,6,7 в Q ₀ на 1,1,1,2,2,3,3 получается пара полустандартных таблиц

${\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q \ quad = \ quad {\ begin {matrix} 1 & 1 & 1 & 3 \\ 2 & 2 \\ 3 \ end {matrix}}.}$

Прямое определение корреспонденции RSK

В приведенном выше определении используется алгоритм Шенстеда, который создает стандартную таблицу записи Q ₀ и модифицирует ее, чтобы учесть первую строку двухстрочного массива и создать полустандартную таблицу записи; это делает очевидной связь с соответствием Робинсона – Шенстеда . Однако естественно упростить конструкцию, изменив часть алгоритма записи формы, чтобы непосредственно учитывать первую строку двухстрочного массива; именно в такой форме обычно описывается алгоритм RSK-соответствия. Это просто означает, что после каждого шага вставки Schensted таблица Q расширяется путем добавления в качестве записи нового квадрата b-й записи i _b первой строки таблицы w _A , где b - текущий размер таблиц. То, что при этом всегда получается полустандартная таблица, следует из свойства (впервые обнаруженного Кнутом), что для последовательных вставок с одинаковым значением в первую строку w _A каждый последующий квадрат, добавленный к фигуре, находится в столбце строго справа от Предыдущая.

Вот подробный пример такой конструкции обеих полустандартных таблиц. Соответствует матрице

${\ Displaystyle A = {\ begin {pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0&} \\ 0 & 0 & 1 & 0\} \\ 0 & 0 & 1 & 0\}$

один имеет двухстрочный массив

${\ displaystyle w_ {A} = {\ begin {pmatrix} 2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\ 4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 \ end {pmatrix}}.}$

В следующей таблице показано построение обеих таблиц для этого примера.

Вставленная пара	${\ displaystyle {\ tbinom {2} {4}}}$	${\ displaystyle {\ tbinom {2} {6}}}$	${\ displaystyle {\ tbinom {3} {4}}}$	${\ displaystyle {\ tbinom {4} {7}}}$	${\ displaystyle {\ tbinom {5} {5}}}$	${\ displaystyle {\ tbinom {6} {3}}}$	${\ displaystyle {\ tbinom {6} {4}}}$	${\ displaystyle {\ tbinom {8} {1}}}$
п	${\ displaystyle {\ begin {matrix} 4 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 & 7 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 & 5 \\ 6 & 7 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 3 & 4 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 3 & 4 & 4 \\ 4 & 5 \\ 6 & 7 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 1 & 4 & 4 \\ 3 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}$
Q	${\ displaystyle {\ begin {matrix} 2 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 \\ 3 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \\ 8 \ end {matrix}}}$

Комбинаторные свойства RSK-соответствия

Случай перестановочных матриц

Если это матрица перестановок, то RSK выводит стандартные таблицы Юнга (SYT) той же формы . И наоборот, если SYT имеет ту же форму , то соответствующая матрица является матрицей перестановок. В результате этого свойства, просто сравнивая мощности двух множеств по обе стороны биективного отображения, мы получаем следующее следствие: ${\ displaystyle A}$${\ displaystyle P, Q}$${\ displaystyle \ lambda}$${\ displaystyle P, Q}$${\ displaystyle \ lambda}$${\ displaystyle A}$

Следствие 1 : Для каждого у нас есть где средства изменяется во всех разделах в и это число стандартных таблиц Юнга формы . ${\ Displaystyle п \ geq 1}$${\ Displaystyle \ сумма _ {\ лямбда \ vdash п} (т _ {\ лямбда}) ^ {2} = п!}$${\ displaystyle \ lambda \ vdash n}$${\ displaystyle \ lambda}$${\ displaystyle n}$${\ displaystyle t _ {\ lambda}}$${\ displaystyle \ lambda}$

Симметрия

Позвольте быть матрица с неотрицательными элементами. Предположим , что алгоритм RSK карты в то алгоритм RSK сопоставляет к , где есть транспонирование . ${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle (P, Q)}$${\ displaystyle A ^ {T}}$${\ displaystyle (Q, P)}$${\ displaystyle A ^ {T}}$${\ displaystyle A}$

В частности, в случае матриц перестановок восстанавливается симметрия соответствия Робинсона – Шенстеда:

Теорема 2 : если перестановка соответствует тройной , то обратной перестановке , соответствует . ${\ displaystyle \ sigma}$${\ displaystyle (\ lambda, P, Q)}$${\ displaystyle \ sigma ^ {- 1}}$${\ displaystyle (\ lambda, Q, P)}$

Это приводит к следующему соотношению между количеством инволюций и количеством таблиц, из которых можно составить ( инволюция - это перестановка, которая сама себе обратна ): ${\ displaystyle S_ {n}}$${\ displaystyle S_ {n}}$

Следствие 2 : количество таблиц, из которых можно составить , равно количеству инволюций на . ${\ Displaystyle \ {1,2,3, \ ldots, п \}}$${\ Displaystyle \ {1,2,3, \ ldots, п \}}$

Доказательство : если - инволюция, соответствующая , то соответствует ; следовательно . И наоборот, если любая перестановка соответствует , то также соответствует ; следовательно . Таким образом, между инволюциями и таблицами существует однозначное соответствие. ${\ displaystyle \ pi}$${\ displaystyle (P, Q)}$${\ displaystyle \ pi = \ pi ^ {-}}$${\ displaystyle (Q, P)}$${\ Displaystyle P = Q}$${\ displaystyle \ pi}$${\ Displaystyle (P, P)}$${\ displaystyle \ pi ^ {-}}$${\ Displaystyle (P, P)}$${\ displaystyle \ pi = \ pi ^ {-}}$${\ displaystyle \ pi}$${\ displaystyle P}$

Число инволюций на дается повторением: ${\ Displaystyle \ {1,2,3, \ ldots, п \}}$

${\ Displaystyle а (п) = а (п-1) + (п-1) а (п-2) \,}$

Где . Решая эту рекурсию, мы можем получить количество инволюций на , ${\ Displaystyle а (1) = 1, а (2) = 2}$${\ Displaystyle \ {1,2,3, \ ldots, п \}}$

${\ displaystyle I (n) = n! \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {1} {2 ^ {k} k! (n-2k)!}} }$

Симметричные матрицы

Пусть алгоритм RSK отображает матрицу в пару , где - SSYT формы . Пусть где то и . Затем карта устанавливает биекцию между симметричными матрицами с типом row ( ) и SSYT . ${\ displaystyle A = A ^ {T}}$${\ displaystyle A}$${\ Displaystyle (P, P)}$${\ displaystyle P}$${\ displaystyle \ alpha}$${\ Displaystyle \ альфа = (\ альфа _ {1}, \ альфа _ {2}, \ ldots)}$${\ displaystyle \ alpha _ {i} \ in N}$${\ Displaystyle \ сумма \ альфа _ {я} <\ infty}$${\ Displaystyle A \ longmapsto P}$${\ displaystyle A}$${\ displaystyle = \ alpha}$${\ displaystyle \ alpha}$

Заявления о переписке RSK

Личность Коши

Соответствие Робинсона – Шенстеда – Кнута обеспечивает прямое биективное доказательство следующего знаменитого тождества для симметричных функций:

${\ displaystyle \ prod _ {i, j} (1-x_ {i} y_ {j}) ^ {- 1} = \ sum _ {\ lambda} s _ {\ lambda} (x) s _ {\ lambda} ( y)}$

где - функции Шура . ${\ displaystyle s _ {\ lambda}}$

Костки номера

Починить перегородки , затем ${\ displaystyle \ mu, \ nu \ vdash n}$

${\ displaystyle \ sum _ {\ lambda \ vdash n} K _ {\ lambda \ mu} K _ {\ lambda \ nu} = N _ {\ mu \ nu}}$

где и обозначают числа Костки, а - количество матриц с неотрицательными элементами, строками ( ) и столбцами ( ) . ${\ displaystyle K _ {\ lambda \ mu}}$${\ displaystyle K _ {\ lambda \ nu}}$${\ Displaystyle N _ {\ mu \ nu}}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle = \ mu}$${\ displaystyle A}$${\ displaystyle = \ nu}$

Ссылки

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. 108 . Кембридж: Издательство Кембриджского университета . С.  135–162 . ISBN 0-521-86565-4. Zbl  1106.05001 .