Robinson-Schenstedova korespondence
V matematiky , a zejména v algebraických kombinatorika je Robinson-Schensted korespondence je bijection mezi permutace a páry standardních mladých polí o stejné formě. Tuto bijekci lze popsat různými způsoby, všemi algoritmickými. Má mnoho pozoruhodných vlastností a aplikací v kombinatorice a v jiných oblastech, jako je reprezentace konečných skupin . Korespondence byla zobecněna několika způsoby, zejména Knuthem v tom, co je nyní známé jako korespondence Robinson-Schensted-Knuth , a ještě obecněji v objektech zvaných postavy od Zelevinského.
Nejjednodušší popis korespondence je podle Schenstedova algoritmu ( Schensted, 1961 ), postupu, který vytváří tabulku postupným vkládáním hodnot permutace podle přesného pravidla a druhou tabulku, která zaznamenává vývojový tvar během konstrukce. Korespondence byla popsána v jiné podobě, mnohem dříve Gilbert de Beauregard Robinson v (Robinson, 1938) , ve snaze dokázat pravidlo Littlewood-Richardson . Korespondence se často označuje jako Robinson-Schenstedův algoritmus , zatímco postup, který Robinson používá, se radikálně liší od Schenstedova postupu a je téměř úplně zapomenut. Mezi další metody pro definování shody patří nedeterministický algoritmus založený na hlavolamské hře Schützenbergera .
Individuální povaha korespondence se odráží v kombinatorických identitách, jako jsou:
∑λ(Fλ)2=ne!{\ displaystyle \ sum _ {\ lambda} (f ^ {\ lambda}) ^ {2} = n!}![{\ displaystyle \ sum _ {\ lambda} (f ^ {\ lambda}) ^ {2} = n!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f562ad8bdbf4edf29b2b39fc245973d37edca581)
kde součet je přes příčky z (nebo diagramů Young s čtverečky), a je počet polí standardní Young z formy .
ne{\ displaystyle n}
ne{\ displaystyle n}
Fλ{\ displaystyle f ^ {\ lambda}}
λ{\ displaystyle \ lambda}![\ lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
Schenstedův algoritmus
Schenstedův algoritmus začíná permutací napsanou ve funkční formě:
σ{\ displaystyle \ sigma}![\ sigma](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36)
σ=(123⋯neσ1σ2σ3⋯σne){\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & 3 & \ cdots & n \\\ sigma _ {1} & \ sigma _ {2} & \ sigma _ {3} & \ cdots & \ sigma _ {n} \ end {pmatrix}}}![{\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & 3 & \ cdots & n \\\ sigma _ {1} & \ sigma _ {2} & \ sigma _ {3} & \ cdots & \ sigma _ {n} \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b0ab5f563659bdc8c8d0e6e0b1d83a8f47969aa)
,
kde , a postupuje postupnou konstrukcí posloupnosti uspořádaných párů Youngových polí stejné formy, je uvedeno:
σi=σ(i){\ displaystyle \ sigma _ {i} = \ sigma (i)}![{\ displaystyle \ sigma _ {i} = \ sigma (i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1164f58804d5136f46c68fc3e4bf5fd3df63cb86)
(P0,Q0),(P1,Q1),(P2,Q2),...,(Pne,Qne){\ displaystyle (P_ {0}, Q_ {0}), \ quad (P_ {1}, Q_ {1}), \ quad (P_ {2}, Q_ {2}), \ quad \ ldots \ ,, \ quad (P_ {n}, Q_ {n})}![{\ displaystyle (P_ {0}, Q_ {0}), \ quad (P_ {1}, Q_ {1}), \ quad (P_ {2}, Q_ {2}), \ quad \ ldots \ ,, \ quad (P_ {n}, Q_ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7a3097ca99eaf0941cbc32bbd3e0023b115998b)
,
kde je prázdné pole. Hledaná pole jsou a . From we build by inserting in , then adding the value to in the square just added by inserting, so that and have the same shape. Vzhledem k tomu, že pole hrají sekundárnější roli, pole (ze kterého lze pole okamžitě odvodit) se nazývá „záznamové pole“, zatímco pole se nazývá „vkládací pole“.
P0=Q0{\ displaystyle P_ {0} = Q_ {0}}
P=Pne{\ displaystyle P = P_ {n}}
Q=Qne{\ displaystyle Q = Q_ {n}}
Pi-1{\ displaystyle P_ {i-1}}
Pi{\ displaystyle P_ {i}}
σi{\ displaystyle \ sigma _ {i}}
Pi-1{\ displaystyle P_ {i-1}}
Qi{\ displaystyle Q_ {i}}
i{\ displaystyle i}
Qi-1{\ displaystyle Q_ {i-1}}
Pi{\ displaystyle P_ {i}}
Qi{\ displaystyle Q_ {i}}
Qi{\ displaystyle Q_ {i}}
Qne{\ displaystyle Q_ {n}}
Qi{\ displaystyle Q_ {i}}
Pi{\ displaystyle P_ {i}}![P_i](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3)
Vložení
Základní postup, který vloží hodnotu , se nazývá „Schenstedova vložka“ nebo „řádková vložka“ (aby se odlišila od varianty zvané vložení sloupce). Procedura funguje na „neúplných standardních tabulkách“: jedná se o tabulky zvětšující se v řádcích a ve sloupcích, které však nemusí nutně obsahovat po sobě jdoucí celá čísla od 1 do velikosti tabulky.
σi{\ displaystyle \ sigma _ {i}}![\ sigma _ {i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ab3208a7d0c634ef720e03ff5a9949e8310edc4)
Vzhledem k (neúplnému) poli a hodnotě, která není v , vložením Schensted vytvoří pole a čtverec, který obsahuje souřadnice nové buňky.
T{\ displaystyle T}
X{\ displaystyle x}
T{\ displaystyle T}
T←X{\ displaystyle T \ leftarrow x}
s{\ displaystyle s}![s](https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632)
Hodnota se objeví v prvním řádku , buď proto, že byla přidána na konec (to je případ, kdy jsou všechny přítomné hodnoty menší než ), nebo proto, že nahradila nejmenší hodnotu v prvním řádku . V prvním případě je čtverec, kde byl přidán, a postup se zastaví. V druhém případě postup pokračuje, ale tentokrát stavíme , kde je soukromé pole jeho první řady, vložením do druhé řady atd., Dokud se nepoužije první případ, což je jistě případ, když přijde na prázdný řádek. Krabice je čtverec, který byl přidán do tvaru.
X{\ displaystyle x}
T←X{\ displaystyle T \ leftarrow x}
X{\ displaystyle x}
y>X{\ displaystyle y> x}
T{\ displaystyle T}
s{\ displaystyle s}
X{\ displaystyle x}
T′←y{\ displaystyle T '\ leftarrow y}
T′{\ displaystyle T '}
y{\ displaystyle}
T{\ displaystyle T}
s{\ displaystyle s}![s](https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632)
Formální popis vkládání algoritmu inu je dán Knuth. Zde je mírně upraven:
X{\ displaystyle x}
T{\ displaystyle T}![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- Je i=1{\ displaystyle i = 1}
- Buď nejmenší takový index, nebo jinak délka řádku plus 1.j{\ displaystyle j}
X<Ti,j{\ displaystyle x <T_ {i, j}}
j{\ displaystyle j}![j](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0)
- V případě, že buňka je prázdná , zeptejte se a a povrchová úprava.(i,j){\ displaystyle (i, j)}
T{\ displaystyle T}
Ti,j=X{\ displaystyle T_ {i, j} = x}
s=(i,j){\ displaystyle s = (i, j)}![{\ displaystyle s = (i, j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe079d4db6e04aa45e78ecb434416d44549e533d)
- Jinak zaměňte hodnoty a zvyšte o 1 a pokračujte krokem 2.X{\ displaystyle x}
Ti,j{\ displaystyle T_ {i, j}}
i{\ displaystyle i}![i](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
Oprava
Skutečnost, že tabulka má rostoucí čáry, je zřejmá z konstrukce. Na druhou stranu to, že se jeho sloupce také zvyšují, vyžaduje reflexi, zejména proto, že sloupce se během algoritmu nikdy neporovnávají. Když nahradí hodnotu v buňce , máme . Nová hodnota je proto menší než stará, a proto menší než hodnota, pokud buňka není prázdná. Pojďme zkontrolovat, zda vkládání listů zvyšuje počet sloupců. Jak máme , vložení lze provést pouze mezi klady . Když je jedna z těchto hodnot nahrazena , máme tedy novou hodnotu buňky menší než , což ukazuje, že tabulka narůstá ve sloupci.
T←X{\ displaystyle T \ leftarrow x}
X{\ displaystyle x}
y=Ti,j{\ displaystyle y = T_ {i, j}}
(i,j){\ displaystyle (i, j)}
y>X{\ displaystyle y> x}
Ti+1,j{\ displaystyle T_ {i + 1, j}}
(i+1,j){\ displaystyle (i + 1, j)}
y{\ displaystyle}
y<Ti+1,j{\ displaystyle y <T_ {i + 1, j}}
y{\ displaystyle}
Ti+1,j′{\ displaystyle T_ {i + 1, j '}}
j′≤j{\ displaystyle j '\ leq j}
y{\ displaystyle}
Ti+1,j′{\ displaystyle T_ {i + 1, j '}}
Ti,j′<X<y{\ displaystyle T_ {i, j '} <x <y}
y{\ displaystyle}
Ti+1,j′{\ displaystyle T_ {i + 1, j '}}
Ti,j′{\ displaystyle T_ {i, j '}}![{\ displaystyle T_ {i, j '}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b63bf9b39809298e8f202acff07605d0b57e342b)
Právě jsme viděli, že indexy sloupců se snižují během vkládání do po sobě jdoucích řádků (v příkladu jsou sloupce postupně 3, 2, 1). To ukazuje, že celkový počet buněk, které se mají zkoumat při sestavování tabulky, se maximálně rovná počtu řádků plus počtu sloupců v tabulce.
T←X{\ displaystyle T \ leftarrow x}![{\ displaystyle T \ leftarrow x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6db879a2a0f7d150f74ce0f9f171ee8c22947e4)
Kompletní stavba
Kompletní Schenstedův algoritmus aplikovaný na permutaci probíhá následovně:
σ{\ displaystyle \ sigma}![\ sigma](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36)
- inicializovat a do prázdného pole;P{\ displaystyle P}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
- pro měnící se od 1 do , výpočet tabulky a buňka vložením Schensted, nahradí se a přidejte položku do tabulky buňky ;i{\ displaystyle i}
ne{\ displaystyle n}
P←X{\ displaystyle P \ leftarrow x}
s{\ displaystyle s}
P{\ displaystyle P}
P←X{\ displaystyle P \ leftarrow x}
i{\ displaystyle i}
s{\ displaystyle s}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
- dokončit a vrátit pár .(P,Q){\ displaystyle (P, Q)}
![(P, Q)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4)
Algoritmus vytváří dvojici standardních Youngových tabulek; jeho časová složitost je nanejvýš .
Ó(ne2){\ displaystyle O (n ^ {2})}![O (n ^ 2)](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392)
Obrácení konstrukce
Vidíme, že každá dvojice standardních Youngových polí stejného tvaru pochází z permutace, která umožňuje jejich konstrukci. Načrtneme inverzi konstrukce. Abychom našli tuto permutaci, pracujeme tak, že se vrátíme opačným směrem, což jsou kroky, které dvojici mohly dát . Je to pole Q, které dává buňce místo, kde skončilo poslední vložení. Poté přejdeme po řádcích nahoru, abychom našli buňky obsahující nahrazené hodnoty; dorazil na první řádek, získáme hodnotu permutace.
(P,Q){\ displaystyle (P, Q)}
(P,Q){\ displaystyle (P, Q)}
σne{\ displaystyle \ sigma _ {n}}![{\ displaystyle \ sigma _ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e4aeaa7d544d1f21afc8c8993cf5e5625ed8f95)
Procedura a její právě načrtnutá inverze tedy poskytuje účinnou bijekci mezi permutacemi a dvojicemi standardních Youngových polí stejné formy: jedná se o korespondenci Robinson-Schensted.
Geometrická konstrukce Viennotu
Geometrickou konstrukci Robinson-Schenstedovy korespondence mezi permutacemi a dvojicemi standardních Youngových stolů stejné formy dal Viennot.
Vlastnosti
Jednou ze základních vlastností, která však není zjevným důsledkem konstrukce, je symetrie:
- Pokud korespondence Robinson-Schensted spojuje pole s permutací , spojuje pár s permutací .(P,Q){\ displaystyle (P, Q)}
σ{\ displaystyle \ sigma}
(Q,P){\ displaystyle (Q, P)}
σ-1{\ displaystyle \ sigma ^ {- 1}}![{\ displaystyle \ sigma ^ {- 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a27db551f348581a5fb0ecb539255c55a8fa53)
Tuto vlastnost lze prokázat například pomocí
geometrické konstrukce Viennotu .
Zde jsou další vlastnosti. Nechť je dvojice spojená s permutací :
(P,Q){\ displaystyle (P, Q)}
σ=(σ1,...,σne){\ displaystyle \ sigma = (\ sigma _ {1}, \ ldots, \ sigma _ {n})}![{\ displaystyle \ sigma = (\ sigma _ {1}, \ ldots, \ sigma _ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af19bb077ed84804db1e13d913fbfa7484e1af28)
- Dovolit být dvojice polí spojených s vrácenou permutací . V tabulce je transpozice v tabulce , a v tabulce je určen pouze : to je transpozice tabulky získaného, z , z involuce Schützenberger .(P′,Q′){\ displaystyle (P ', Q')}
(σne,...,σ1){\ displaystyle (\ sigma _ {n}, \ ldots, \ sigma _ {1})}
P′{\ displaystyle P '}
P{\ displaystyle P}
Q′{\ displaystyle Q '}
Q{\ displaystyle Q}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
- Délka nejdelší rostoucí posloupnosti je délka prvního řádku (nebo ).σ1,...,σne{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}
P{\ displaystyle P}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
- Délka nejdelší klesající subsekvence je délka prvního sloupce (nebo ), jak vyplývá z předchozích dvou vlastností.σ1,...,σne{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}
P{\ displaystyle P}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
A konečně, bijekce mezi dvojicemi standardních polí a permutací poskytuje důkaz kombinatorické identity již oznámené výše:
∑λ∈Pne(Fλ)2=ne!{\ displaystyle \ sum _ {\ lambda \ v {\ mathcal {P}} _ {n}} (f ^ {\ lambda}) ^ {2} = n!}![{\ displaystyle \ sum _ {\ lambda \ v {\ mathcal {P}} _ {n}} (f ^ {\ lambda}) ^ {2} = n!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95a3ab14ad5acb03c1152e186fff1c52fa6c737f)
kde je soubor přepážek z (nebo diagramů Young s čtverečky), a je počet standardních mladých polí formuláře . Další důkaz lze získat pomocí Youngovy mřížky .
Pne{\ displaystyle {\ mathcal {P}} _ {n}}
ne{\ displaystyle n}
ne{\ displaystyle n}
Fλ{\ displaystyle f ^ {\ lambda}}
λ{\ displaystyle \ lambda}![\ lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
Dodatky
Reference
-
( Knuth, 2005 ), strany 49-50
(fr) Tento článek je částečně nebo zcela převzat z článku
anglické Wikipedie s názvem
„ Robinson - Schensted korespondence “ ( viz seznam autorů ) .
Bibliografie
- William Fulton , Young tableaux , Cambridge University Press, kol. "Londýn matematická společnost Student texty" ( n o 35)1997( ISBN 978-0-521-56144-0 a 978-0-521-56724-4 , Math Reviews 1464693 )
- Donald E. Knuth , „ Permutace, matice a generalizovaná Youngova pole, “ Pacific Journal of Mathematics , sv. 34,1970, str. 709–727 ( ISSN 0030-8730 , Math Reviews 0272654 , číst online )
- Donald E. Knuth, The Art of Computer Programming , sv. 3: Třídění a vyhledávání, druhé vydání , Addison-Wesley,2005( ISBN 0-201-89685-0 , online prezentace )
-
Gilbert de Beauregard Robinson , „ O zastoupeních symetrické skupiny “, American Journal of Mathematics , sv. 60, n o 3,1938, str. 745–760 ( ISSN 0002-9327 , DOI 10.2307 / 2371609 , JSTOR 2371609 ) Zentralblatt 0019.25102
- (en) Bruce E. Sagan , The Symetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , New York / Berlin / Heidelberg etc., Springer, coll. "Graduate texty matematiky" ( n o 203)2001, 2 nd ed. , 238 s. ( ISBN 0-387-95067-2 , číst online )
-
(en) Richard P. Stanley , Enumerative Combinatorics , sv. 2 [ detail vydání ] ( online prezentace )Odkaz na matematické recenze
- Craige Schensted , „ Nejdelší rostoucí a klesající subsekvence “, Canadian Journal of Mathematics , sv. 13,1961, str. 179–191 ( ISSN 0008-414X , DOI 10.4153 / CJM-1961-015-3 , matematické recenze 0121305 , číst online )
- Andrei V. Zelevinsky, „ Zobecnění pravidla Littlewood - Richardson a korespondence Robinson - Schensted - Knuth, “ Journal of Algebra , sv. 69, n o 1,devatenáct osmdesát jedna, str. 82–94 ( ISSN 0021-8693 , DOI 10.1016 / 0021-8693 (81) 90128-9 , matematické recenze 613858 )
Související články
Externí odkaz
(en) Mark AA van Leeuwen , „korespondence Robinson - Schensted“ , Michiel Hazewinkel , Encyklopedie matematiky , Springer ,2002( ISBN 978-1556080104 , číst online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">