Моделирование путей выталкиваний в алгоритме RSK и анализ их приближения к предельной форме
Ключевые слова:
алгоритм RSK, соответствие RSK, таблица Юнга, мера Планшереля, кривая Вершика — Керова, путь выталкиваний, предельная форма, линейно упорядоченное множество, численный эксперимент, асимптотическая комбинаторика.Аннотация
Введение: алгоритм RSK устанавливает эквивалентность последовательностей элементов линейно упорядоченных множеств и пар таблиц Юнга P и Q одинаковой формы. Отдельный интерес представляет исследование асимптотического предела, т. е. предельной формы так называемых путей выталкиваний, образуемых выталкиваемыми алгоритмом клетками таблицы P. Точные формулы для этих предельных форм были ранее получены Д. Ромиком и П. Сняды в 2016. Однако проблема изучения динамики стремления путей выталкиваний к их предельным формам остается недостаточно исследованной. Цель: исследовать динамику отклонения путей выталкиваний от их предельных форм в таблицах Юнга с помощью компьютерных экспериментов. Результаты: в проведенной серии компьютерных экспериментов для таблиц Юнга P размеров до 4·106, заполненных вещественными числами в диапазоне [0, 1] и наборов вставляемых значений α Î [0.1, 0.15, … , 0.85], получено большое количество экспериментальных путей выталкиваний, которые сравнивались в метрике L2 с соответствующими предельными формами. Вычислены средние расстояния и дисперсии их отклонений от предельных кривых. Приведена эмпирическая формула для скорости приближения дискретизированных путей выталкиваний к их предельной форме. Получены экспериментальные параметры нормальных распределений отклонения путей выталкиваний для различных входных значений.
