В математике соответствие Робинсона – Шенстеда - это взаимно однозначное соответствие между перестановками и парами стандартных таблиц Юнга одинаковой формы. Он имеет различные описания, все из которых имеют алгоритмическую природу, он обладает множеством замечательных свойств и имеет приложения в комбинаторике и других областях, таких как теория представлений . Переписка была обобщена различными способами, в частности путем Кнутом к тому , что известно как соответствия Робинсона-Шенстед-Кнуту и дальнейшее обобщение на картины по Зелевинскому .
Самым простым описанием соответствия является использование алгоритма Шенстеда (Schensted 1961 ), процедуры, которая создает одну таблицу путем последовательной вставки значений перестановки в соответствии с определенным правилом, в то время как другая таблица записывает эволюцию формы во время построения. Соответствие было описано в несколько иной форме намного раньше Робинсоном ( Robinson 1938 ) в попытке доказать правило Литтлвуда – Ричардсона . Соответствие часто называют алгоритмом Робинсона-Шенстеда , хотя процедура, используемая Робинсоном, радикально отличается от алгоритма Шенстеда и почти полностью забыта. Другие методы определения соответствия включают недетерминированный алгоритм с точки зрения jeu de taquin .
Биективный характер соответствия связывает его с перечислительной идентичностью:
где обозначает множество перегородок из п (или из диаграмм Юнга с п квадратами), и т λ обозначает число стандартных таблиц Юнга формы Х .
Алгоритм Шенстеда
Алгоритм Шенстеда начинается с перестановки σ, записанной в двухстрочной записи
где σ i = σ ( i ) , и продолжается путем последовательного построения последовательности (промежуточных) упорядоченных пар таблиц Юнга одинаковой формы:
где P 0 = Q 0 - пустые таблицы. Выходные таблицы: P = P n и Q = Q n . После построения P i −1 формируют P i , вставляя σ i в P i −1 , а затем Q i , добавляя запись i к Q i −1 в квадрате, добавленном к форме вставкой (так, чтобы P i и Q i имеют одинаковую форму для всех i ). Из-за более пассивной роли таблиц Q i последняя Q n , которая является частью вывода и из которой легко считываются предыдущие Q i , называется таблицей записи ; напротив, таблицы P i называются таблицами вставки .
Вставка
Базовая процедура, используемая для вставки каждого σ i , называется вставкой по Шенстеду или вставкой строки (чтобы отличить ее от вариантной процедуры, называемой вставкой столбца). Его простейшая форма определяется в терминах «неполных стандартных таблиц»: как и в стандартных таблицах, они имеют отдельные записи, образующие увеличивающиеся строки и столбцы, но некоторые значения (которые еще предстоит вставить) могут отсутствовать в качестве записей. Процедура принимает в качестве аргументов такую таблицу T и значение x, отсутствующее в качестве записи T ; он производит в качестве вывода новую таблицу, обозначенную T ← x, и квадрат s, на который ее форма увеличилась. Значение В х появляется в первой строке Т ← х , либо будучи добавлен в конце (если нет записей больше , чем х не присутствовали), или иным образом заменить первый элемент у > х в первой строке Т . В первом случае s - это квадрат, в который добавляется x , и вставка завершена; в последнем случае замененная запись y аналогичным образом вставляется во вторую строку T и так далее, пока на каком-то шаге не будет применен первый случай (что обязательно произойдет, если будет достигнута пустая строка T ).
Более формально, следующий псевдокод описывает строку-вставку нового значения х в Т . [1]
- Установить я = 1 и J на один больше , чем длина первой строки T .
- Пока j > 1 и x < T i , j −1 , уменьшите j на 1. (Теперь ( i , j ) является первым квадратом в строке i, у которого либо запись больше x в T , либо запись вообще отсутствует).
- Если квадрат ( i , j ) пуст в T , завершите работу после добавления x к T в квадрате ( i , j ) и установки s = ( i , j ) .
- Поменяйте местами значения x и T i, j . (Это вставляет старый x в строку i и сохраняет значение, которое он заменяет, для вставки в следующую строку.)
- Увеличьте i на 1 и вернитесь к шагу 2.
Форма T увеличивается ровно на один квадрат, а именно на s .
Правильность
Тот факт, что T ← x имеет увеличивающиеся строки и столбцы, если то же самое верно для T , не очевиден из этой процедуры (записи в одном столбце никогда даже не сравниваются). Однако можно увидеть следующее. В любое время, кроме непосредственно после шага 4, квадрат ( i , j ) либо пуст в T, либо имеет значение больше x ; шаг 5 повторно устанавливает это свойство , потому что ( я , J ) теперь квадрат непосредственно ниже той , которая первоначально содержащегося х в Т . Таким образом, эффект замены на шаге 4 на значение T i, j заключается в его уменьшении; в частности, он не может стать больше, чем его правые или нижние соседи. С другой стороны, новое значение также не меньше, чем его левый сосед (если он присутствует), что подтверждается сравнением, которое только что завершило шаг 2. Наконец, чтобы увидеть, что новое значение больше, чем его верхний сосед T i −1, j, если он присутствует, обратите внимание, что T i −1, j сохраняется после шага 5, и что уменьшение j на шаге 2 только уменьшает соответствующее значение T i - 1, J .
Построение картин
Полный алгоритм Шенстеда, применяемый к перестановке σ, действует следующим образом.
- Установите P и Q в пустую таблицу
- Для увеличения i от 1 до n вычислить P ← σ i и квадрат s с помощью процедуры вставки; затем замените P на P ← σ i и добавьте запись i в таблицу Q в квадрате s .
- Завершите, вернув пару ( P , Q ) .
Алгоритм создает пару стандартных таблиц Юнга.
Обратимость конструкции
Можно видеть, что для любой пары ( P , Q ) стандартных таблиц Юнга одинаковой формы существует обратная процедура, которая производит перестановку, которая приведет к ( P , Q ) с помощью алгоритма Шенстеда. По сути, он состоит из отслеживания шагов алгоритма в обратном направлении, каждый раз используя запись Q, чтобы найти квадрат, в котором должна начаться обратная вставка, перемещая соответствующую запись P в предыдущую строку и продолжая вверх по строкам до входа в заменяется первая строка, которая является значением, вставленным на соответствующем шаге алгоритма построения. Эти два обратных алгоритма определяют взаимно однозначное соответствие между перестановками n с одной стороны и парами стандартных таблиц Юнга одинаковой формы, содержащих n квадратов с другой стороны.
Характеристики
Одним из наиболее фундаментальных свойств, но не очевидным из алгоритмической конструкции, является симметрия:
- Если соответствие Робинсона – Шенстеда связывает таблицы ( P , Q ) с перестановкой σ , то оно связывает ( Q , P ) с обратной перестановкой σ −1 .
Это можно доказать, например, апеллируя к геометрической конструкции Венно .
Дальнейшие свойства, предполагающие, что соответствие связывает таблицы ( P , Q ) с перестановкой σ = ( σ 1 , ..., σ n ) .
- В паре таблиц ( P ′, Q ′), связанных с обратной перестановкой ( σ n , ..., σ 1 ) , таблица P ′ является транспонированной таблицей P , а Q ′ - это таблица, определяемая Q независимо от Р (а именно транспонированной таблицы , полученной из Q по инволюции Шютценбержа ).
- Длина самой длинной возрастающей подпоследовательности из сг 1 , ..., сг п равна длине первого ряда Р (и из Q ).
- Длина самой длинной убывающей подпоследовательности σ 1 , ..., σ n равна длине первого столбца P (и Q ), как следует из двух предыдущих свойств.
- Множество спуска { я : σ я > σ я + 1 } из сг равно множество спуска { я : я +1 в строке строго ниже строки I } из Q .
- Отождествите подпоследовательности π с их наборами индексов. Теорема Грина гласит, что для любого k ≥ 1 размер наибольшего множества, которое можно записать как объединение не более чем k возрастающих подпоследовательностей, равен λ 1 + ... + λ k . В частности, λ 1 равна наибольшей длине возрастающей подпоследовательности π .
- Если σ - инволюция , то количество неподвижных точек σ равно количеству столбцов нечетной длины в λ .
Смотрите также
- Геометрическая конструкция Венно, дающая схематичную интерпретацию соответствия.
- Плактический моноид : процесс вставки может использоваться для определения ассоциативного продукта таблиц Юнга с элементами от 1 до n , который называется пластическим моноидом порядка n .
Заметки
- ^ Адаптировано из DE Кнут (1973), Искусство программирования , 3 , стр. 50-51
Рекомендации
- Фултон, Уильям (1997), Young Tableaux , London Mathematical Society Student Texts, 35 , Cambridge University Press , ISBN 978-0-521-56144-0, MR 1464693.
- Кнут, Дональд (1970), "Перестановка, матрица и обобщен Юнга" , Тихоокеанский журнал математика , 34 : 709-727, DOI : 10,2140 / pjm.1970.34.709 , МР 0272654
- Робинсон, Г. де Б. (1938), "О представлениях симметрической группы", American Journal математики , 60 (3): 745-760, DOI : 10,2307 / 2371609 , JSTOR 2371609 , ZBL 0019,25102.
- Саган, BE (2001), Симметричная группа , Тексты для выпускников по математике, 203 , Нью-Йорк: Springer-Verlag, ISBN 0-387-95067-2.
- Шенстеда, С. (1961), "Серия увеличения и уменьшения подпоследовательности", Canadian Journal математики , 13 : 179-191, DOI : 10,4153 / CJM-1961-015-3 , МР 0121305.
- Стэнли, Ричард П. (1999), Перечислительная комбинаторика, Vol. 2 , Кембриджские исследования в области высшей математики, 62 , Cambridge University Press , ISBN 978-0-521-56069-6, Руководство по ремонту 1676282.
- Зелевинский, А.В. (1981), «Обобщение правила Литтлвуда – Ричардсона и соответствия Робинсона – Шенстеда – Кнута», Journal of Algebra , 69 (1): 82–94, DOI : 10.1016 / 0021-8693 (81) 90128 -9 , Руководство по ремонту 0613858.
дальнейшее чтение
- Грин, Джеймс А. (2007). Полиномиальные представления GL n . Конспект лекций по математике. 830 . С приложением о переписке Шенстеда и путях Литтельмана К. Эрдманна, Дж. А. Грина и М. Шокера (2-е исправленное и дополненное изд.). Берлин: Springer-Verlag . ISBN 3-540-46944-3. Zbl 1108.20044 .
Внешние ссылки
- van Leeuwen, MAA (2001) [1994], "Соответствие Робинсона – Шенстеда" , Энциклопедия математики , EMS Press