В математике плактический моноид — это моноид всех слов в алфавите положительных целых чисел по модулю эквивалентности Кнута . Его элементы можно отождествить с полустандартными таблицами Юнга . Он был открыт Дональдом Кнутом (1970) (который назвал его алгеброй таблиц ), используя операцию, данную Крейгом Шенстедом (1961) в его исследовании самой длинной возрастающей подпоследовательности перестановки.
Он был назван " monoïde plaxique " Ласку и Шютценбергером (1981), которые допускали любой полностью упорядоченный алфавит в определении. Этимология слова " plaxique " неясна; оно может относиться к тектонике плит ("tectonique des plates" на французском), поскольку элементарные отношения, которые порождают эквивалентность, допускают условную коммутацию символов генератора: они иногда могут скользить друг по другу (по очевидной аналогии с тектоническими плитами), но не свободно.
Пластический моноид над некоторым полностью упорядоченным алфавитом (часто положительными целыми числами) — это моноид со следующим представлением :
Два слова называются эквивалентными по Кнуту, если они представляют один и тот же элемент пластического моноида или, другими словами, если одно из них может быть получено из другого с помощью последовательности элементарных преобразований Кнута.
Эквивалентность Кнута сохраняет несколько свойств.
Каждое слово эквивалентно Кнуту слову уникальной полустандартной таблицы Юнга (это означает, что каждая строка не убывает, а каждый столбец строго возрастает) над тем же упорядоченным алфавитом, где таблица может читаться по строкам или по столбцам. Таким образом, элементы пластического моноида можно отождествить с полустандартными таблицами Юнга, которые, следовательно, также образуют моноид.
Умножение слова полустандартной таблицы Юнга слева на генератор эквивалентно вставке Шенстеда в таблицу Юнга. В порядке строк слово таблицы эквивалентно произведению все более длинных неубывающих последовательностей генераторов. Новый генератор может быть вставлен на свое место либо путем его добавления, если он больше, либо путем многократного применения пластических отношений для перемещения элемента, выходящего из последовательности, в следующую строку. В последнем случае элемент, выходящий из порядка, заменяет самую левую запись, большую, чем он, в каждой строке, а затем смещенный элемент вставляется в следующую строку.
Поскольку вставка Шенстеда сохраняет таблицы Юнга, это дает индуктивное доказательство того, что элементы пластического моноида могут быть записаны в стандартной форме, соответствующей таблице Юнга, а конструкция определяет естественное произведение полустандартных таблиц.
Две перекошенные таблицы Юнга эквивалентны по методу Же де такен , если и только если их словесные прочтения эквивалентны по Кнуту, т. е. соответствуют эквивалентным элементам пластической группы. Это дает альтернативное определение произведения пластической группы непосредственно в терминах таблиц Юнга. Две таблицы можно умножить, нарисовав их обе вокруг пустого прямоугольника, чтобы сформировать перекошенную таблицу, и используя слайды Же де такен, чтобы исправить ее.
Кольцо таблиц является моноидным кольцом пластического моноида, поэтому оно имеет Z -базис, состоящий из элементов пластического моноида, с тем же произведением, что и в пластическом моноиде.
Существует гомоморфизм из пластического кольца на алфавите в кольцо многочленов (с переменными, индексированными алфавитом), переводящий любую таблицу в произведение переменных ее элементов, что соответствует абелианизации пластической полугруппы.
Производящая функция пластического моноида на алфавите размера n равна
показывая, что существует полиномиальный рост размерности .
{{citation}}: Отсутствует или пусто |title=( помощь )