Algoritmul Robinson-Schoenstead

Algoritmul Robinson-Schoenstead este un algoritm combinatoriu , descris pentru prima dată de Robinson în 1938, care stabilește o corespondență bijectivă între elementele unui grup simetric și perechile de tablouri Young standard de aceeași formă. Poate fi privită ca o simplă dovadă constructivă a identității $S_{n}$

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

unde înseamnă că rulează prin toate partițiile și este numărul de diagrame Young standard de forma . Acest lucru se realizează prin construirea unei mapări de la perechi de tabele la permutări . $\lambda \vdash n$ $\lambda$ $n$ $f^{\lambda }$ $\lambda$ $\lambda$ $(P,Q)$ $\sigma$

Algoritm

Algoritmul Robinson-Schoenstead începe cu o permutare scrisă în ordine lexicografică: $\sigma$

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

unde , și continuă, creând o succesiune de perechi ordonate de tablouri Young de aceeași formă: $\sigma (i)=\sigma _{i)$

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

unde sunt mesele goale. Ieșirea sunt tabele și . $P_{0}=Q_{0}=\varnothing$ $P=P_{n}$ $Q=Q_{n}$

Pe baza celui construit , se formează prin inserarea Shenstead (vezi mai jos) în . K se adaugă pătratului adăugat la formă atunci când este lipit, astfel încât formele pentru și să fie aceleași pentru fiecare . Astfel, tabelul standard înregistrează permutarea, iar - înregistrează „creșterea” diagramei Young [1] . $P_{{i-1}}$ $P_{{i}}$ $\sigma (i)$ $P_{{i-1}}$ $Q_{i)$ $i$ $P_{{i}}$ $Q_{i)$ $i$ $P$ $Q$

O descriere informală a inserției Shenstead

Pentru a insera un rând într-un tabel : $X$ $T$

1. faceți curent prima linie T 2. găsiți primul element din linia curentă care este mai mare decât x 3. dacă se găseşte un astfel de element schimbă x și a găsit valorile celulei face următoarea linie curentă treceți la pasul 2. in caz contrar: adăugați x la sfârșitul liniei curente finalizarea

Variații și generalizări

Shenstead a descoperit independent algoritmul și l-a generalizat în cazul oricărei secvențe de numere (adică, eventual cu repetări). În acest caz, este semistandard. $\sigma$ $n$ $P$
Algoritmul Robinson-Schoensted-Knuth a fost dezvoltat deKnuthși stabilește ocorespondență bijectivăîntre permutările generalizate (matrice de două linii deordonate lexicografic) și perechi de tablouri Young semistandard.

Note

↑ Olshansky G. Teoria reprezentării asimptotice II. Note de prelegeri. Arhivat 22 decembrie 2015 la Wayback Machine , înregistrat de L. Petrov, 2010

Literatură

numere vii . - Sat. articole 1981. - M . : Mir, 1985. - S. 105 -112. — 128 p.
William Fulton. Tablouri tinere cu aplicație la teoria reprezentării și geometrie. - M . : Editura MTSNMO, 2006. - ISBN 5-94057-165-4 .
Knuth, Donald E. Permutări, matrici și tablouri Young generalizate (engleză) .
Robinson, G. de B. On the Representations of the Symmetric Group (engleză) // American Journal of Mathematics . - The Johns Hopkins University Press, 1938. - Vol. 60 , nr. 3 . — P. 745–760 . — ISSN 0002-9327 . - doi : 10.2307/2371609 .
Schensted, C. Cele mai lungi subsecvențe crescătoare și descrescătoare // Canadian Journal of Mathematics. - 1961. - Vol. 13 . — P. 179-191 . — ISSN 0008-414X .
Stanley, Richard P. Combinatorică enumerativă. Vol. 2 (engleză) . - Cambridge University Press , 1999. - Vol. 62 .
Zelevinsky, A. V. O generalizare a regulii Littlewood–Richardson și a corespondenței Robinson–Schensted–Knuth // Journal of Algebra. - 1981. - Vol. 69 , nr. 1 . — P. 82-94 . — ISSN 0021-8693 . - doi : 10.1016/0021-8693(81)90128-9 .