Исследование свойств классов эквивалентности перестановок с помощью обратного преобразования Робинсона - Шенстеда - Кнута
Ключевые слова:
алгоритм RSK, соответствие RSK, классы эквивалентности перестановок, эквивалентность по Кнуту, двойственная эквивалентность по Кнуту, преобразование Шютценберже, процесс Планшереля, диаграммы Юнга, таблицы Юнга, кривая Вершика — Керова, диаграмма Браттели — Вершика, численные эксперименты, асимптотическая комбинаторикаАннотация
Введение: вся информация о перестановке, т. е. об элементе симметрической группы S(n), содержится в паре таблиц Юнга, сопоставляемых ей преобразованием RSK. Если же вместо перестановки рассматривать бесконечную последовательность натуральных или вещественных чисел, то вся информация о ней содержится только в записывающей бесконечной таблице Юнга. В недавней работе Д. Ромика и П. Сняды была получена явная формула, выражающая первый элемент бесконечной последовательности равномерно распределенных случайных величин через предельный угол наклона нерва нумерующей таблицы. Однако до сих пор не было произведено массовых численных экспериментов, посвященных восстановлению начала такой последовательности по началу записывающей таблицы Юнга. При этом очень важна точность такого восстановления, потому что значение даже первого элемента последовательности может быть определено только по бесконечной таблице. Цель: разработка программного пакета для операций над диаграммами и таблицами Юнга и его применение для компьютерных экспериментов с большими таблицами Юнга. Изучение свойств классов эквивалентности по Кнуту и двойственной эквивалентности по Кнуту на множестве перестановок посредством численных экспериментов с использованием прямого и обратного преобразования RSK. Результаты: разработан программный пакет на языке C++, включающий в себя функции для работы с диаграммами и таблицами Юнга. С помощью массовых численных экспериментов изучена зависимость значений первого элемента перестановки, получаемой обратным преобразованием RSK, от координат конца нерва нумерующей таблицы. Вычислены среднеквадратические отклонения этих значений для перестановок различной длины. Определялись возможные положения единицы в перестановках, принадлежащих одному и тому же классу эквивалентности по Кнуту. Выявлено, что количество этих положений не превышает количества угловых клеток соответствующей диаграммы Юнга. Экспериментально установлено, что при фиксированной записывающей таблице значение первого элемента перестановки зависит только от координат конца нерва нумерующей таблицы.
