Robinson-Schoenstead algoritme

Robinson-Schoenstead- algoritmen er en kombinatorisk algoritme, først beskrevet af Robinson i 1938, som etablerer en bijektiv overensstemmelse mellem elementer i en symmetrisk gruppe og par af standard Young-tableauer af samme form. Det kan betragtes som et simpelt konstruktivt bevis på identiteten $S_{n}$

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

hvor betyder, at det løber gennem alle partitioner og er antallet af standard Young-diagrammer i formen . Dette opnås ved at konstruere en mapping fra par af -tabeller til permutationer . $\lambda \vdash n$ $\lambda$ $n$ $f^{\lambda}$ $\lambda$ $\lambda$ $(P,Q)$ $\sigma$

Algoritme

Robinson-Schoenstead-algoritmen starter med en permutation skrevet i leksikografisk rækkefølge: $\sigma$

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

hvor , og fortsætter med at skabe en sekvens af ordnede par unge tableauer af samme form: ${\displaystyle \sigma (i)=\sigma _{i))$

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

hvor er tomme borde. Outputtet er tabeller og . $P_{0}=Q_{0}=\varnothing$ $P=P_{n}$ $Q=Q_{n}$

Baseret på den konstruerede dannes den ved at indsætte Shenstead (se nedenfor) i . K'et føjes til den firkant, der tilføjes til formen, når den indsættes, så formerne for og er de samme for hver . Således registrerer standardtabellen permutationen og - registrerer "væksten" af Young-diagrammet [1] . $P_{{i-1}}$ $P_{{i}}$ $\sigma (i)$ $P_{{i-1}}$ ${\displaystyle Q_{i))$ $jeg$ $P_{{i}}$ ${\displaystyle Q_{i))$ $jeg$ $P$ $Q$

En uformel beskrivelse af Shenstead-indsættelsen

Sådan indsætter du en række i en tabel : $x$ $T$

1. gør den første linje T strøm 2. find det første element i den aktuelle linje, der er større end x 3. hvis et sådant element er fundet udveksle x og fundne celleværdier gør næste linje aktuel gå til trin 2. Ellers: tilføje x til slutningen af den aktuelle linje Afslut

Variationer og generaliseringer

Shenstead opdagede uafhængigt algoritmen og generaliserede den til tilfældet med enhver sekvens af tal (det vil sige muligvis med gentagelser). I dette tilfælde er semistandard. $\sigma$ $n$ $P$
Robinson-Schoensted-Knuth-algoritmen blev udviklet afKnuthog etablerer enbijektiv overensstemmelsemellem generaliserede permutationer (to-line arrays afleksikografisk ordnedepositive heltal) og par af semistandard Young tableauer.

Noter

↑ Olshansky G. Asymptotisk repræsentationsteori II. Noter af forelæsninger. Arkiveret 22. december 2015 på Wayback Machine Optaget af L. Petrov, 2010

Litteratur

levende tal . - Lør. artikler 1981. - M . : Mir, 1985. - S. 105 -112. — 128 s.
William Fulton. Unge Tableaux med Anvendelse til Repræsentationsteori og Geometri. - M . : MTSNMO Publishing House, 2006. - ISBN 5-94057-165-4 .
Knuth, Donald E. Permutationer, matricer og generaliserede unge tableauer (engelsk) .
Robinson, G. de B. Om repræsentationerne af den symmetriske gruppe (engelsk) // American Journal of Mathematics . - The Johns Hopkins University Press, 1938. - Vol. 60 , nr. 3 . — S. 745–760 . — ISSN 0002-9327 . - doi : 10.2307/2371609 .
Schensted, C. Længst stigende og faldende delsekvenser // Canadian Journal of Mathematics. - 1961. - Bd. 13 . — S. 179-191 . — ISSN 0008-414X .
Stanley, Richard P. Enumerativ kombinatorik. Vol. 2 (engelsk) . - Cambridge University Press , 1999. - Vol. 62 .
Zelevinsky, A. V. En generalisering af Littlewood-Richardson-reglen og Robinson-Schensted-Knuth-korrespondancen // Journal of Algebra. - 1981. - Bd. 69 , nr. 1 . — S. 82-94 . — ISSN 0021-8693 . - doi : 10.1016/0021-8693(81)90128-9 .