Ru.Wikipedia.Org - Алгоритм Робинсона

Меню
Главная
Случайная статья
Настройки

Алгоритм Робинсона — Шенстеда
Материал из https://ru.wikipedia.org

Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный Робинсоном^[англ.] в 1938, который устанавливает биективное соответствие между элементами симметрической группы

S_{n}

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

\sum _{\lambda \vdash n}(f^{\lambda })^{2}=n!

где

\lambda \vdash n

означает, что

\lambda

пробегает все разбиения

n

f^{\lambda }

— количество стандартных диаграмм Юнга формы

\lambda

. Это достигается путём построения отображения из пар

\lambda

-таблиц

(P,Q)

в перестановки

\sigma

.

Содержание

Алгоритм

Алгоритм Робинсона — Шенстеда начинает работу с перестановки

\sigma

, записанной в лексикографическом порядке:

{\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}

где

\sigma (i)=\sigma _{i}

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

(P_{0},Q_{0}),(P_{1},Q_{1}),(P_{2},Q_{2}),\ldots ,(P_{n},Q_{n}),

где

P_{0}=Q_{0}=\varnothing

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

P=P_{n}

Q=Q_{n}

.

На основе построенной

P_{i-1}

формируется

P_{i}

путём вставки Шенстеда (см. ниже)

\sigma (i)

P_{i-1}

. К

Q_{i}

добавляется

i

в квадрат, добавленный к форме при вставке, чтобы формы для

P_{i}

Q_{i}

были одинаковы для каждого

i

. Таким образом, стандартная таблица

P

записывает перестановку, а

Q

— регистрирует «рост» диаграммы Юнга^[1].

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

Для вставки строки

x

в таблицу

T

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

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

Шенстед независимо обнаружил алгоритм и обобщил его для случая $\sigma$ — любая последовательность из $n$ чисел (то есть, возможно, с повторениями). В этом случае $P$ является полустандартной.
Алгоритм Робинсона — Шенстеда — Кнута^[англ.] был разработан Кнутом и устанавливает биективное соответствие между обобщенными перестановками (двустрочные массивы лексикографически упорядоченных положительных целых чисел) и парами полустандартных таблиц Юнга.

Примечания

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

Литература

Живые числа. — Сб. статей 1981. — М.: Мир, 1985. — С. 105-112. — 128 с.
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.