Corespondența Robinson-Schensted

În matematică și în special în combinatorie algebrică , corespondența Robinson-Schensted este o bijecție între permutări și perechi de matrice standard Young de aceeași formă. Această bijecție poate fi descrisă în diferite moduri, toate algoritmice. Are multe proprietăți remarcabile și aplicații în combinatorică și în alte domenii, cum ar fi reprezentarea grupurilor finite . Corespondența a fost generalizată în mai multe moduri, mai ales de Knuth în ceea ce este acum cunoscut sub numele de corespondență Robinson-Schensted-Knuth și, mai general, încă în obiecte numite figuri de Zelevinsky.

Cea mai simplă descriere a corespondenței este realizată de algoritmul lui Schensted ( Schensted, 1961 ), o procedură care construiește un tabel prin inserarea succesivă a valorilor unei permutări conform unei reguli precise și un al doilea tabel care înregistrează forma evoluției în timpul constructie. Corespondența a fost descrisă, într-o formă diferită, mult mai devreme de Gilbert de Beauregard Robinson în (Robinson, 1938) , în încercarea de a demonstra regula Littlewood-Richardson . Corespondența este adesea denumită algoritmul Robinson-Schensted , în timp ce procedura utilizată de Robinson este radical diferită de cea a lui Schensted și este aproape complet uitată. Printre celelalte metode de definire a meciului se află un algoritm nedeterminist bazat pe jocul teaser al lui Schützenberger .

Natura individuală a corespondenței se reflectă în identități combinatorii, cum ar fi:

∑λ(fλ)2=nu!{\ displaystyle \ sum _ {\ lambda} (f ^ {\ lambda}) ^ {2} = n!}

unde suma este peste partițiilor de (sau diagrame Young cu pătrate) și este numărul de matrice standard de Young de formă . nu{\ displaystyle n}nu{\ displaystyle n}fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}

Algoritmul lui Schensted

Algoritmul lui Schensted începe de la o permutare scrisă în formă funcțională: σ{\ displaystyle \ sigma}

σ=(123⋯nuσ1σ2σ3⋯σnu){\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & 3 & \ cdots & n \\\ sigma _ {1} & \ sigma _ {2} & \ sigma _ {3} & \ cdots & \ sigma _ {n} \ end {pmatrix}}},

unde , și se desfășoară prin construcția secvențială a unei secvențe de perechi ordonate de matrice Young de aceeași formă, a notat: σeu=σ(eu){\ displaystyle \ sigma _ {i} = \ sigma (i)}

(P0,Î0),(P1,Î1),(P2,Î2),...,(Pnu,Înu){\ displaystyle (P_ {0}, Q_ {0}), \ quad (P_ {1}, Q_ {1}), \ quad (P_ {2}, Q_ {2}), \ quad \ ldots \ ,, \ quad (P_ {n}, Q_ {n})},

unde este matricea goală. Tablourile căutate sunt și . Din construim prin inserarea în , apoi adăugarea valorii la în piața doar adăugată prin inserarea, astfel încât și să aibă aceeași formă. Deoarece matricile joacă un rol mai secundar, matricea (din care matricile pot fi deduse imediat) se numește „matrice de înregistrări”, în timp ce matricile sunt numite „matrice de inserare”. P0=Î0{\ displaystyle P_ {0} = Q_ {0}}P=Pnu{\ displaystyle P = P_ {n}}Î=Înu{\ displaystyle Q = Q_ {n}}Peu-1{\ displaystyle P_ {i-1}}Peu{\ displaystyle P_ {i}} σeu{\ displaystyle \ sigma _ {i}}Peu-1{\ displaystyle P_ {i-1}}Îeu{\ displaystyle Q_ {i}}eu{\ displaystyle i}Îeu-1{\ displaystyle Q_ {i-1}}Peu{\ displaystyle P_ {i}}Îeu{\ displaystyle Q_ {i}}Îeu{\ displaystyle Q_ {i}}Înu{\ displaystyle Q_ {n}}Îeu{\ displaystyle Q_ {i}}Peu{\ displaystyle P_ {i}}

Inserare

Procedura de bază, care introduce o valoare , se numește „inserare Schensted” sau „inserare rând” (pentru a o distinge de o variantă numită inserare coloană). Procedura funcționează pe „tabele standard incomplete”: sunt tabele care cresc în rând și în coloană, dar care nu conțin în mod necesar numerele întregi consecutive de la 1 la dimensiunea tabelului. σeu{\ displaystyle \ sigma _ {i}}

Dat fiind un tablou (incomplet) și o valoare care nu se află , inserarea lui Schensted construiește un tablou și un pătrat care conține coordonatele noii celule. T{\ displaystyle T}X{\ displaystyle x}T{\ displaystyle T}T←X{\ displaystyle T \ leftarrow x}s{\ displaystyle s}

Valoarea apare în prima linie a , fie pentru că a fost adăugată la sfârșit (acesta este cazul când toate valorile prezente sunt mai mici decât ), fie pentru că a înlocuit cea mai mică valoare din prima linie a . În primul caz, este pătratul unde a fost adăugat și procedura se oprește. În al doilea caz, procedura continuă, dar de data aceasta construim , unde este matricea privată a primului său rând, prin inserarea în al doilea rând al și așa mai departe până când se aplică primul caz, ceea ce este cu siguranță cazul când vine vorba la o linie goală. Caseta este pătratul care a fost adăugat la formă. 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 y}T{\ displaystyle T}s{\ displaystyle s}

O descriere formală a algoritmului de inserție în este dată de Knuth. Aici este ușor adaptat: X{\ displaystyle x}T{\ displaystyle T}

1. Este eu=1{\ displaystyle i = 1}
2. Fie cel mai mic indice astfel încât , sau, în caz contrar, lungimea liniei plus 1.j{\ displaystyle j}X<Teu,j{\ displaystyle x <T_ {i, j}}j{\ displaystyle j}
3. Dacă celula este goală , întrebați și și terminați.(eu,j){\ displaystyle (i, j)}T{\ displaystyle T}Teu,j=X{\ displaystyle T_ {i, j} = x}s=(eu,j){\ displaystyle s = (i, j)}
4. În caz contrar, schimbați valorile și creșteți cu 1 și continuați cu pasul 2.X{\ displaystyle x}Teu,j{\ displaystyle T_ {i, j}}eu{\ displaystyle i}

Corecţie

Faptul că tabelul are linii în creștere este evident prin construcție. Pe de altă parte, faptul că coloanele sale sunt, de asemenea, în creștere necesită o reflecție, în special deoarece coloanele nu sunt niciodată comparate în timpul algoritmului. Când înlocuim valoarea din celulă , avem . Prin urmare, noua valoare este mai mică decât cea veche și, prin urmare, mai mică decât valoarea dacă celula nu este goală. Să verificăm dacă inserția coloanelor crește. Așa cum am făcut , inserarea lui se poate face numai printre profesioniști . Atunci când una dintre aceste valori este înlocuită , avem , prin urmare, noua valoare a celulei este mai mică decât , ceea ce arată că tabelul crește în coloană. T←X{\ displaystyle T \ leftarrow x}X{\ displaystyle x}y=Teu,j{\ displaystyle y = T_ {i, j}}(eu,j){\ displaystyle (i, j)}y>X{\ displaystyle y> x}Teu+1,j{\ displaystyle T_ {i + 1, j}}(eu+1,j){\ displaystyle (i + 1, j)}y{\ displaystyle y}y<Teu+1,j{\ displaystyle y <T_ {i + 1, j}}y{\ displaystyle y}Teu+1,j′{\ displaystyle T_ {i + 1, j '}}j′≤j{\ displaystyle j '\ leq j}y{\ displaystyle y}Teu+1,j′{\ displaystyle T_ {i + 1, j '}}Teu,j′<X<y{\ displaystyle T_ {i, j '} <x <y}y{\ displaystyle y}Teu+1,j′{\ displaystyle T_ {i + 1, j '}}Teu,j′{\ displaystyle T_ {i, j '}}

Tocmai am văzut că indicii coloanei scad în timpul inserțiilor în rânduri succesive (în exemplu, coloanele sunt succesiv 3, 2, 1). Acest lucru arată că numărul total de celule de examinat la construirea unui tabel este cel mult egal cu numărul de rânduri plus numărul de coloane din tabel. T←X{\ displaystyle T \ leftarrow x}

Construcția completă

Algoritmul Schensted complet, aplicat unei permutări , se desfășoară după cum urmează: σ{\ displaystyle \ sigma}

1. inițializați și la matricea goală;P{\ displaystyle P}Î{\ displaystyle Q}
2. pentru a varia de la 1 la , calculați tabelul și celula inserând Schensted, înlocuiți cu și adăugați intrarea în celula tabelului ;eu{\ displaystyle i}nu{\ displaystyle n}P←X{\ displaystyle P \ leftarrow x}s{\ displaystyle s}P{\ displaystyle P}P←X{\ displaystyle P \ leftarrow x}eu{\ displaystyle i}s{\ displaystyle s}Î{\ displaystyle Q}
3. terminați și returnați perechea .(P,Î){\ displaystyle (P, Q)}

Algoritmul produce o pereche de tabele standard ale lui Young; complexitatea sa de timp este cel mult . O(nu2){\ displaystyle O (n ^ {2})}

Inversarea construcției

Putem vedea că fiecare pereche de matrice standard Young de aceeași formă provine dintr-o permutare care permite construirea ei. Să schițăm inversiunea construcției. Pentru a găsi această permutare, operăm retrăgând în direcția opusă, pașii care ar fi putut da perechea . Este matricea Q care oferă celula unde s-a încheiat ultima inserție. Apoi, urcăm liniile pentru a găsi celulele care conțin valorile înlocuite; ajuns la prima linie, obținem valoarea permutării. (P,Î){\ displaystyle (P, Q)}(P,Î){\ displaystyle (P, Q)}σnu{\ displaystyle \ sigma _ {n}}

Astfel, procedura și inversul său doar schițat oferă o bijecție eficientă între permutări și perechi de matrice standard Young de aceeași formă: aceasta este corespondența Robinson-Schensted.

Construcția geometrică a Viennotului

Viennot a dat o construcție geometrică a corespondenței Robinson-Schensted între permutații și perechi de tabele standard Young de aceeași formă.

Proprietăți

Una dintre proprietățile fundamentale, dar care nu este o consecință evidentă a construcției, este simetria:

• Dacă corespondența Robinson-Schensted asociază matricele cu permutația , aceasta asociază perechea cu permutația .(P,Î){\ displaystyle (P, Q)}σ{\ displaystyle \ sigma}(Î,P){\ displaystyle (Q, P)}σ-1{\ displaystyle \ sigma ^ {- 1}}

Această proprietate poate fi dovedită, de exemplu, utilizând construcția geometrică a Viennot .

Iată alte proprietăți. Fie perechea asociată cu permutația  : (P,Î){\ displaystyle (P, Q)}σ=(σ1,...,σnu){\ displaystyle \ sigma = (\ sigma _ {1}, \ ldots, \ sigma _ {n})}

• Fie perechea de tablouri asociate cu permutarea returnată . Tabelul este transpunerea tabelului , iar tabelul este determinat numai de  : este transpunerea tabelului obținut, de la , prin implicarea lui Schützenberger .(P′,Î′){\ displaystyle (P ', Q')}(σnu,...,σ1){\ displaystyle (\ sigma _ {n}, \ ldots, \ sigma _ {1})}P′{\ displaystyle P '}P{\ displaystyle P}Î′{\ displaystyle Q '}Î{\ displaystyle Q}Î{\ displaystyle Q}
• Lungimea celei mai lungi subsecvențe în creștere a este lungimea primei linii a (sau a ).σ1,...,σnu{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}P{\ displaystyle P}Î{\ displaystyle Q}
• Lungimea celei mai lungi subsecvențe descrescătoare este lungimea primei coloane a (sau a ), după cum urmează din cele două proprietăți anterioare.σ1,...,σnu{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}P{\ displaystyle P}Î{\ displaystyle Q}

În cele din urmă, bijecția dintre perechile de matrice standard și permutări oferă dovada identității combinatorii deja anunțată mai sus:

∑λ∈Pnu(fλ)2=nu!{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} (f ^ {\ lambda}) ^ {2} = n!}

unde este setul de partiții ale (sau diagramele lui Young cu pătrate) și este numărul de matrice standard de formă Young . O altă dovadă poate fi obținută folosind rețeaua lui Young . Pnu{\ displaystyle {\ mathcal {P}} _ {n}}nu{\ displaystyle n}nu{\ displaystyle n}fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}

Anexe

Referințe

1. ( Knuth, 2005 ), paginile 49-50

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia în engleză intitulat „  Corespondență Robinson - Schensted  ” ( vezi lista autorilor ) .

Bibliografie

• William Fulton , Young tableaux , Cambridge University Press, col.  „London Mathematical Society Texts Student” ( nr .  35)1997( ISBN  978-0-521-56144-0 și 978-0-521-56724-4 , Recenzii matematice  1464693 )
• Donald E. Knuth , „  Permutări, matrici și matrice tinere generalizate  ” , Pacific Journal of Mathematics , vol.  34,1970, p.  709–727 ( ISSN  0030-8730 , Math Reviews  0272654 , citiți online )
• Donald E. Knuth, The Art of Computer Programming , vol.  3: Sortare și căutare, Ediția a doua , Addison-Wesley,2005( ISBN  0-201-89685-0 , prezentare online )
• Gilbert de Beauregard Robinson , „  Despre reprezentările grupului simetric  ”, American Journal of Mathematics , vol.  60, n o  3,1938, p.  745–760 ( ISSN  0002-9327 , DOI  10.2307 / 2371609 , JSTOR  2371609 ) Zentralblatt 0019.25102
• (ro) Bruce E. Sagan , The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , New York / Berlin / Heidelberg etc., Springer, col.  „Textele absolvenților în matematică” ( nr .  203)2001, A 2 -a  ed. , 238  p. ( ISBN  0-387-95067-2 , citit online )
• (ro) Richard P. Stanley , Enumerative Combinatorics , vol.  2 [ detaliu ediții ] ( prezentare online )Link  Recenzii matematice
• Craige Schensted , „  Cele mai lungi subsecvențe crescătoare și descrescătoare  ”, Canadian Journal of Mathematics , vol.  13,1961, p.  179–191 ( ISSN  0008-414X , DOI  10.4153 / CJM-1961-015-3 , Math Reviews  0121305 , citiți online )
• Andrei V. Zelevinsky, „  O generalizare a regulii Littlewood - Richardson și a corespondenței Robinson - Schensted - Knuth  ” , Journal of Algebra , vol.  69, n o  1,nouăsprezece optzeci și unu, p.  82–94 ( ISSN  0021-8693 , DOI  10.1016 / 0021-8693 (81) 90128-9 , Recenzii matematice  613858 )

Articole similare

• Construcție Viennot geometrică  : oferă o interpretare prin diagrame a corespondenței.
• Rețeaua lui Young

Link extern

(ro) Mark AA van Leeuwen , „Corespondență Robinson - Schensted” , în Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN  978-1556080104 , citit online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">