Robinson-Schoenstead-algoritmi

Robinson-Schoenstead- algoritmi on kombinatorinen algoritmi, jonka Robinson kuvasi ensimmäisen kerran vuonna 1938, ja joka luo bijektiivisen vastaavuuden symmetrisen ryhmän elementtien ja samanmuotoisten Youngin standarditaulukoiden parien välille. Sitä voidaan pitää yksinkertaisena rakentavana todisteena henkilöllisyydestä $S_{n}$

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

jossa tarkoittaa joka kulkee kaikkien osioiden läpi ja on muodon vakiomuotoisten Young-kaavioiden lukumäärä . Tämä saavutetaan rakentamalla kartoitus -taulukkopareista permutaatioihin . $\lambda \vdash n$ $\lambda$ $n$ $f^{\lambda }$ $\lambda$ $\lambda$ $(P,Q)$ $\sigma$

Algoritmi

Robinson-Schoenstead-algoritmi alkaa permutaatiolla , joka on kirjoitettu leksikografisessa järjestyksessä: $\sigma$

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

jossa , ja jatkuu, luomalla sarjan järjestettyjä samanmuotoisia Young-taulukuvia: ${\displaystyle \sigma (i)=\sigma _{i))$

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

missä on tyhjät pöydät. Tulos on taulukot ja . $P_{0}=Q_{0}=\varnothing$ $P=P_{n}$ $Q=Q_{n}$

Konstruoidun perusteella se muodostetaan lisäämällä Shenstead (katso alla) kohtaan . K lisätään muotoon lisättyyn neliöön liitettynä siten, että muodot ja ovat samat jokaiselle . Näin ollen standarditaulukko tallentaa permutaatiot ja - rekisteröi Youngin diagrammin "kasvun" [1] . $P_{{i-1}}$ $P_{{i}}$ $\sigma (i)$ $P_{{i-1}}$ ${\displaystyle Q_{i))$ $i$ $P_{{i}}$ ${\displaystyle Q_{i))$ $i$ $P$ $K$

Epävirallinen kuvaus Shenstead-lisäyksestä

Rivin lisääminen taulukkoon : $x$ $T$

1. Tee ensimmäinen rivi T virta 2. etsi nykyisen rivin ensimmäinen alkio, joka on suurempi kuin x 3. jos sellainen elementti löytyy vaihtaa x ja löydetyt soluarvot tehdä seuraavasta rivistä ajan tasalla siirry vaiheeseen 2. muuten: lisää x nykyisen rivin loppuun suorittaa loppuun

Muunnelmia ja yleistyksiä

Shenstead löysi itsenäisesti algoritmin ja yleisti sen minkä tahansa numerosarjan tapaukselle (eli mahdollisesti toistoille). Tässä tapauksessa se on puolistandardi. $\sigma$ $n$ $P$
Knuthin kehittämä Robinson-Schoensted-Knuth-algoritmi [ muodostaabijektiivisen vastaavuudenyleistettyjen permutaatioiden (leksikografisesti järjestetynpositiivisten kokonaislukujen kaksiriviset taulukot) ja puolistandardien Young-taulukkoparien välille.

Muistiinpanot

↑ Olshansky G. Asymptoottinen esitysteoria II. Luentojen muistiinpanot. Arkistoitu 22. joulukuuta 2015 Wayback Machinessa Äänittäjä L. Petrov, 2010

Kirjallisuus

elävät numerot . - la. artikkelit 1981. - M. : Mir, 1985. - S. 105 -112. — 128 s.
William Fulton. Nuoret taulut, jotka soveltuvat esitysteoriaan ja geometriaan. - M . : MTSNMO Publishing House, 2006. - ISBN 5-94057-165-4 .
Knuth, Donald E. Permutaatiot, matriisit ja yleistetyt Young-taulukot (englanniksi) .
Robinson, G. de B. Symmetrinen ryhmän esityksistä (englanniksi) // American Journal of Mathematics . - The Johns Hopkins University Press, 1938. - Voi. 60 , ei. 3 . — s. 745–760 . — ISSN 0002-9327 . - doi : 10.2307/2371609 .
Schensted, C. Pisin kasvavat ja laskevat osasekvenssit // Canadian Journal of Mathematics. - 1961. - Voi. 13 . - s. 179-191 . — ISSN 0008-414X .
Stanley, Richard P. Enumeratiivinen kombinatoriikka. Voi. 2 (englanniksi) . - Cambridge University Press , 1999. - Voi. 62 .
Zelevinsky, A. V. Littlewood-Richardson-säännön yleistys ja Robinson-Schensted-Knuthin kirjeenvaihto // Journal of Algebra. - 1981. - Voi. 69 , ei. 1 . — s. 82-94 . — ISSN 0021-8693 . - doi : 10.1016/0021-8693(81)90128-9 .