Алгоритм Робинсона — Шенстеда (Glikjnmb JkQnuvkug — Oyuvmy;g)

Перейти к навигации Перейти к поиску

Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном[англ.] в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества

где означает, что пробегает все разбиения и  — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки .

Алгоритм Робинсона — Шенстеда начинает работу с перестановки , записанной в лексикографическом порядке:

где , и продолжает, создавая последовательность упорядоченных пар таблиц Юнга той же формы:

где  — пустые таблицы. На выходе получаются таблицы и .

На основе построенной формируется путём вставки Шенстеда (см. ниже) в . К добавляется в квадрат, добавленный к форме при вставке, чтобы формы для и были одинаковы для каждого . Таким образом, стандартная таблица записывает перестановку, а  — регистрирует «рост» диаграммы Юнга[1].

Вставка (4):
• (4) заменяет (5) в первой строке
• (5) заменяет (8) во второй строке
• (8) записывается в начало новой строки

Неформальное описание вставки Шенстеда

[править | править код]

Для вставки строки в таблицу :

   1. сделать первую строку T текущей
   2. в текущей строке найти первый элемент, который больше x
   3. если такой элемент найден
        обменять значения x и найденной ячейки
        сделать следующую строку текущей
        перейти на шаг 2.
      иначе:
        добавить x к концу текущей строки
        закончить

Вариации и обобщения

[править | править код]

Примечания

[править | править код]
  1. Ольшанский Г. Асимптотическая теория представлений II. Записки лекций. Архивная копия от 22 декабря 2015 на Wayback Machine Запись Л. Петрова, 2010

Литература

[править | править код]
  • Живые числа. — Сб. статей 1981. — М.: Мир, 1985. — С. 105-112. — 128 с.
  • Уильям Фултон. Таблицы юнга и их приложения к теории представлений и геометрии = Young Tableaux With Application to Representation Theory and Geometry. — М.: Издательство МЦНМО, 2006. — ISBN 5-94057-165-4.
  • Knuth, Donald E. Permutations, matrices, and generalized Young tableaux (англ.).
  • Robinson, G. de B. On the Representations of the Symmetric Group (англ.) // American Journal of Mathematics. — The Johns Hopkins University Press, 1938. — Vol. 60, no. 3. — P. 745–760. — ISSN 0002-9327. — doi:10.2307/2371609.
  • Schensted, C. Longest increasing and decreasing subsequences (англ.) // Canadian Journal of Mathematics. — 1961. — Vol. 13. — P. 179-191. — ISSN 0008-414X.
  • Stanley, Richard P. Enumerative combinatorics. Vol. 2 (англ.). — Cambridge University Press, 1999. — Vol. 62.
  • Zelevinsky, A. V. A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence (англ.) // Journal of Algebra. — 1981. — Vol. 69, no. 1. — P. 82-94. — ISSN 0021-8693. — doi:10.1016/0021-8693(81)90128-9.