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

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

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

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

Вступление

В Переписка Робинсона – Шенстеда это биективный отображение между перестановки и пары стандартных Молодые картины, оба имеют одинаковую форму. Это биекция может быть построена с использованием алгоритма, называемого Вставка Schensted, начиная с пустой таблицы и последовательно вставляя значения σ₁,…,σ_п перестановки σ под номерами 1,2,…п; они образуют вторую строку, когда σ дается в двухстрочной записи:

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

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

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

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

В двухстрочный массив (или же обобщенная перестановка) ш_А соответствующая матрице А определено^[1] в качестве

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

в котором для любой пары (я,j) который индексирует запись А_я,j из А, Существуют А_я,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}}}$

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

Применяя алгоритм вставки Шенстеда к нижней строке этого двухстрочного массива, мы получаем пару, состоящую из полустандартной таблицы п и стандартная таблица Q₀, где последнюю можно превратить в полустандартную таблицу Q заменяя каждую запись б из Q₀ посредством б-я запись верхней строки ш_А. Таким образом, получается биекция из матриц А заказанным парам,^[2] (п,Q) полустандартных таблиц Юнга такой же формы, в которых множество записей п это вторая строка ш_А, а набор записей Q это первая строка ш_А. Количество записей j в п следовательно, равно сумме записей в столбце j из А, а количество записей я в Q равно сумме записей в строке я из А.

Пример

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

${\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 расширяется путем добавления в качестве входа нового квадрата б-я запись я_б первой линии ш_А, куда б - текущий размер таблиц. То, что это всегда дает полустандартную таблицу, следует из свойства (впервые обнаруженного Кнутом^[2]), что для последовательных вставок с одинаковым значением в первой строке ш_А, каждый последующий квадрат, добавленный к фигуре, находится в столбце строго правее предыдущего.

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

${\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&1&0&0\\0&0&1&1&0&0&0\\0&0&0&0&0&0&0\\1&0&0&0&0&0&0\\\end{pmatrix}}}$

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

${\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-соответствия

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

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

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

Симметрия

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

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

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

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

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

Доказательство: Если ${\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 ,n\}}$ дается повторением:

${\displaystyle a(n)=a(n-1)+(n-1)a(n-2)\,}$

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

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

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

Позволять ${\displaystyle A=A^{T}}$ и пусть алгоритм RSK отображает матрицу ${\displaystyle A}$ к паре ${\displaystyle (P,P)}$, куда ${\displaystyle P}$ SSYT формы ${\displaystyle \alpha }$.^[1] Позволять ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\ldots )}$ где ${\displaystyle \alpha _{i}\in N}$ и ${\displaystyle \sum \alpha _{i}<\infty }$. Тогда карта ${\displaystyle A\longmapsto P}$ устанавливает биекцию между симметричными матрицами со строкой (${\displaystyle A}$) ${\displaystyle =\alpha }$ и SSYT типа ${\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 }$.

Рекомендации

1. Стэнли, Ричард П. (1999). Перечислительная комбинаторика. 2. Нью-Йорк: Издательство Кембриджского университета. С. 316–380. ISBN  0-521-55309-1.
2. Кнут, Дональд Э. (1970). «Перестановки, матрицы и обобщенные таблицы Юнга». Тихоокеанский математический журнал. 34 (3): 709–727. Дои:10.2140 / pjm.1970.34.709. МИСТЕР  0272654.
3. Кнут, Дональд Э. (1973). Искусство программирования, Vol. 3. Сортировка и поиск. Лондон: Аддисон – Уэсли. С. 54–58. ISBN  0-201-03803-X.

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