Jeu de Taquin - Jeu de taquin

в математический поле комбинаторика, Jeu de Taquin это конструкция из-за Марсель-Пауль Шютценбергер (1977 ), который определяет отношение эквивалентности на съемках наклонные стандартные таблицы Юнга. А слайд Jeu de Taquin представляет собой преобразование, при котором числа в таблице перемещаются аналогично тому, как фигуры в пятнадцать пазлов двигаться. Две картины эквивалент Jeu de Taquin если одно может быть преобразовано в другое с помощью последовательности таких слайдов.

«Jeu de taquin» (буквально «дразнящая игра») - это Французское название головоломки пятнадцати.

Слайд jeu de taquin: определение

Пример слайда Jeu de Taquin

Учитывая наклонную стандартную таблицу Юнга Т скошенной формы ${ displaystyle lambda / mu}$ , выберите соседнюю пустую ячейку c который можно добавить на диаграмму перекоса ${ displaystyle lambda setminus mu}$ ; это означает, что c должен иметь хотя бы одно ребро с некоторой ячейкой в Т, и ${ Displaystyle {с } чашка лямбда setminus mu}$ также должна быть наклонная диаграмма. Есть два типа слайдов, в зависимости от того, c лежит в верхнем левом углу от Т или в правом нижнем углу. Предположим для начала, что c лежит в верхнем левом углу. Вставьте число из соседней ячейки в c; если c имеет соседей справа и снизу, выберите наименьшее из этих двух чисел. (Это правило разработано таким образом, чтобы свойство таблицы иметь увеличивающиеся строки и столбцы было сохранено.) Если только что очищенная ячейка не имеет соседей справа или ниже, то слайд завершен. В противном случае введите число в эту ячейку в соответствии с тем же правилом, что и раньше, и продолжайте таким образом, пока слайд не будет завершен. После этого преобразования результирующая таблица (с удаленной теперь пустой ячейкой) все еще является наклонной (или, возможно, прямой) стандартной таблицей Юнга.

Другой вид слайда, когда c находится в правом нижнем углу Т, просто идет в противоположном направлении. В этом случае каждый сдвигает числа в пустую ячейку от соседа слева или выше, выбирая большее число всякий раз, когда есть выбор. Два типа слайдов являются взаимно инвертированными: слайд одного типа можно отменить, используя слайд другого типа.

Два описанных выше слайда называются скользит в камеру c. Первый вид слайда (когда c лежит в верхнем левом углу от Т) называется внутрь слайд; второй вид называется скольжение наружу.

Слово «слайд» является синонимом французского слова «glissement», которое иногда также используется в английской литературе.

Тонкости

Слайды Jeu-de-taquin изменяют не только относительный порядок элементов таблицы, но и ее форму. В приведенном выше определении результат слайда jeu-de-taquin представлен в виде наклонной диаграммы вместе с наклонной стандартной таблицей, имеющей его форму. Часто лучше работать со скошенными фигурами, чем со скошенными диаграммами. (Напомним, что каждая перекосная форма ${ displaystyle lambda / mu}$ приводит к перекосу диаграммы ${ displaystyle lambda setminus mu}$ , но это не инъективное соответствие, потому что e. г., отчетливые перекосы ${ Displaystyle (2,1) / (2)}$ и ${ Displaystyle (1,1) / (1)}$ дают такую же диаграмму перекоса.) По этой причине полезно изменить приведенное выше определение слайда jeu-de-taquin таким образом, чтобы при заданной форме перекоса вместе со стандартной таблицей перекоса и добавляемой ячейкой как ввода, это дает четко определенный перекос форма вместе с искаженной стандартной таблицей на выходе. Это делается следующим образом: Внутренний слайд наклонной таблицы. Т скошенной формы ${ displaystyle lambda / mu}$ в камеру c определяется, как указано выше, когда c это угол ${ displaystyle mu}$ (то есть когда ${ Displaystyle му setminus left {c right }}$ - диаграмма Юнга), а результирующая форма перекоса устанавливается равной ${ Displaystyle ( лямбда setminus влево {д вправо }) / ( му setminus влево {с вправо })}$ куда d - пустая ячейка в конце процедуры скольжения. Внешний слайд наклонной таблицы Т скошенной формы ${ displaystyle lambda / mu}$ в камеру c определяется, как указано выше, когда c соучастник ${ displaystyle lambda}$ (то есть когда ${ Displaystyle лямбда чашка влево {с вправо }}$ - диаграмма Юнга), а результирующая форма перекоса устанавливается равной ${ Displaystyle ( лямбда чашка влево {с вправо }) / ( му чашка влево {д вправо })}$ куда d - пустая ячейка в конце процедуры скольжения.

Обобщение на косые полустандартные таблицы

Слайды Jeu de taquin обобщаются для искажения полустандартных (в отличие от искаженных стандартных) таблиц и сохраняют большую часть своих свойств в этой общности. Единственное изменение, которое необходимо внести в определение внутреннего слайда, чтобы оно было обобщенным, - это правило о том, как действовать, когда (временно) пустая ячейка имеет соседей снизу и справа, и эти соседи заполнены с равными числами. В этой ситуации сосед ниже (не тот, что справа) нужно вставить в пустую ячейку. Аналогичное изменение необходимо в определении сдвига наружу (где нужно выбрать соседа выше). Эти изменения могут показаться произвольными, но на самом деле они делают «единственно разумный выбор» - то есть единственные варианты, при которых столбцы таблицы (без учета пустой ячейки) строго увеличиваются (в отличие от простого незначительного увеличения).

Исправление

Дана скошенная стандартная или скошенная полустандартная таблица Т, можно итеративно применять внутренние слайды к Т пока таблица не станет прямой (что означает невозможность скольжения внутрь). Обычно это можно сделать множеством разных способов (можно свободно выбирать, в какую ячейку перемещаться первой), но, как известно, полученная в результате таблица прямой формы будет одинаковой для всех возможных вариантов. Эта таблица называется исправление из Т.

Jeu-de-taquin эквивалентность

Две косые полустандартные таблицы Т и S как говорят эквивалент jeu-de-taquin если можно преобразовать один из них в другой, используя последовательность (возможно, пустую) слайдов (разрешены как внутренние, так и внешние слайды). Эквивалентно две косые полустандартные таблицы Т и S являются jeu-de-taquin эквивалентными тогда и только тогда, когда они имеют одинаковую ректификацию.

Чтение слов и эквивалентность Кнута

Существуют различные способы связать слово (в смысле комбинаторики, т. Е. Конечную последовательность элементов алфавита - здесь множество положительных целых чисел) с каждой таблицей Юнга. Мы выбираем, по-видимому, самую популярную: мы ассоциируем каждую картину Юнга. Т слово, полученное объединением строк Т от нижнего ряда к верхнему. (Каждый ряд Т рассматривается как слово, просто читая его записи слева направо, и мы рисуем таблицы Юнга в английской нотации так, чтобы самая длинная строка таблицы прямой формы появлялась вверху.) Это слово будет называться чтение слова, или кратко как слово, из Т.

Тогда можно показать, что две косые полустандартные таблицы Т и S jeu-de-taquin эквивалентны тогда и только тогда, когда слова чтения Т и S находятся Эквивалент Кнута. Как следствие, исправление косой полустандартной таблицы Т также может быть получена как таблица вставки слова чтения Т под Переписка Робинсона-Шенстеда.

Инволюция Шютценбергера

Jeu de taquin можно использовать для определения операции на стандартном Молодые картины любой заданной формы, которая оказывается инволюция, хотя из определения это не очевидно. Первый начинается с очистки квадрата в верхнем левом углу, превращая таблицу в скошенную, на один квадрат меньше. Теперь примените слайд jeu de taquin, чтобы превратить эту наклонную таблицу в прямую, которая освободит один квадрат на внешней границе. Затем заполните этот квадрат отрицанием значения, которое изначально было удалено в верхнем левом углу; это инвертированное значение считается частью новой таблицы, а не исходной таблицы, и его положение не изменится в дальнейшем. Теперь, пока в исходной таблице осталось несколько записей, повторите операцию удаления записи. Икс верхнего левого угла, выполняя слайд jeu de taquin на том, что осталось от исходной таблицы, и помещая значение -Икс на площадь так освобождена. Когда все записи исходной таблицы обработаны, их отрицательные значения упорядочиваются таким образом, что строки и столбцы увеличиваются. Наконец, можно добавить соответствующую константу ко всем записям, чтобы получить таблицу Юнга с положительными элементами.

Приложения

Jeu de taquin тесно связан с такими темами, как Переписка Робинсона – Шенстеда – Кнута, то Правило Литтлвуда – Ричардсона, и Эквивалентность Кнута.