Robinson-Schensted-Knuth levelezés
A matematika , és különösen a algebrai kombinatorika , a Robinson - Schensted - Knuth levelezés , más néven a RSK levelezés vagy a RSK algoritmus , egy bijekciót közötti mátrixok természetes egész szám, és pár félig szabványos Young tömbök az azonos formában., amelynek mérete megegyezik a mátrix bejegyzéseinek összegével . Ez levelezés általánosítja a
Robinson-Schensted levelezés , abban az értelemben, hogy ha egy permutációs mátrix, akkor a pár a pár szabványos tömbök kapcsolódó permutációs a Robinson - Schensted levelezés .
NÁL NÉL{\ displaystyle A}
NÁL NÉL{\ displaystyle A}
NÁL NÉL{\ displaystyle A}
(P,Q){\ displaystyle (P, Q)}![(P, Q)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4)
A Robinson-Schensted-Knuth levelezés kiterjeszti a Robinson-Schensted levelezés számos figyelemre méltó tulajdonságát, nevezetesen a szimmetria tulajdonságát: a mátrix átültetése tömbök és .
NÁL NÉL{\ displaystyle A}
P{\ displaystyle P}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
A Robinson-Schensted-Knuth levelezés
Bevezetés
A Robinson-Schensted-megfeleltetés a permutációk és az azonos formájú standard Young tömbpárok közötti bijekció . Ez a bijekció a Schensted-beillesztés nevű algoritmus segítségével szerkeszthető . Ez az algoritmus kezdődik egy üres asztal , és egymás után beilleszti az értékeket a permutáció , az adatokat a funkcionális formában:
P{\ displaystyle P}
σ1,...,σnem{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}
σ{\ displaystyle \ sigma}
σ{\ displaystyle \ sigma}![\ sigma](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36)
σ=(12...nemσ1σ2...σnem){\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & \ ldots & n \\\ sigma _ {1} & \ sigma _ {2} & \ ldots & \ sigma _ {n} \ end {pmatrix} }}![{\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & \ ldots & n \\\ sigma _ {1} & \ sigma _ {2} & \ ldots & \ sigma _ {n} \ end {pmatrix} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62d6fbb36a1dd87fd316c01cb34ed429a86b77ce)
.
Az eredményül kapott tömb az első a megfelelő párnak ; a második szabványtábla, amely megjegyzi , rögzíti az egymás után következő alakzatokat, amelyek áthaladtak a .
P{\ displaystyle P}
σ{\ displaystyle \ sigma}
Q{\ displaystyle Q}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
Schensted felépítése valójában általánosabb számszekvenciákat vehet figyelembe, mint a permutációkkal kapott számok (különösen az ismétlések engedélyezhetők); ebben az esetben a konstrukció egy standard tömb helyett félig szabványos tömböt állít elő , de továbbra is szabványos tömb marad. Az RSK leképezés helyreállítja a tömbök közötti szimmetriát azáltal, hogy félig standard tömböt is létrehoz.
P{\ displaystyle P}
Q{\ displaystyle Q}
Q{\ displaystyle Q}![Q](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
Kétsoros asztalok
A két sorból álló táblázatot (angolul " two-line array ") vagy egy mátrixnak megfelelő bimot vagy általánosított permutációt a következőképpen definiáljuk:
wNÁL NÉL{\ displaystyle w_ {A}}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
wNÁL NÉL=(én1én2⋯énmj1j2⋯jm){\ displaystyle w_ {A} = {\ begin {pmatrix} i_ {1} & i_ {2} & \ cdots & i_ {m} \\ j_ {1} & j_ {2} & \ cdots & j_ {m} \ end {pmatrix}}}![{\ displaystyle w_ {A} = {\ begin {pmatrix} i_ {1} & i_ {2} & \ cdots & i_ {m} \\ j_ {1} & j_ {2} & \ cdots & j_ {m} \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da5ec7a1a953f7e13e13fbcf3b169725560087b8)
amely a következő tulajdonságokat ellenőrzi:
- Az oszlopok lexikográfiai sorrendben vannak , ami azt jelenti
-
én1≤én2≤én3≤⋯≤énm{\ displaystyle i_ {1} \ leq i_ {2} \ leq i_ {3} \ leq \ cdots \ leq i_ {m}}
, és
- ha és akkor .énr=éns{\ displaystyle i_ {r} = i_ {s}}
r≤s{\ displaystyle r \ leq s}
jr≤js{\ displaystyle j_ {r} \ leq j_ {s}}![{\ displaystyle j_ {r} \ leq j_ {s}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2f0bd9eb3ad8e317532c8580485cfd9b1529ad9)
- minden egyes pár indexek a mátrixban vannak oszlopok egyenlő a .(én,j){\ displaystyle (i, j)}
NÁL NÉL{\ displaystyle A}
NÁL NÉLén,j{\ displaystyle A_ {i, j}}
(énj){\ displaystyle {\ tbinom {i} {j}}}![{\ displaystyle {\ tbinom {i} {j}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e577d8167a5df460cedcf1c467f45d3446f44b)
Különösen az egész szám egyenlő a mátrix együtthatóinak összegével .
m{\ displaystyle m}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Példa
A mátrixnak megfelelő kétsoros táblázat:
NÁL NÉL=(102020110){\ displaystyle A = {\ kezdés {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}![{\ displaystyle A = {\ kezdés {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9eaf4733ea4c18abb1583577ea1bdbc775db3fff)
az:
wNÁL NÉL=(11122331332212){\ displaystyle w_ {A} = {\ elején {pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 3 & 2 & 2 & 1 & 2 \ end {pmatrix}}}![{\ displaystyle w_ {A} = {\ elején {pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 3 & 2 & 2 & 1 & 2 \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf2535951d47105665a19902253f94818f68d7b)
A levelezés meghatározása
A Schensted beillesztési algoritmust a kétsoros tábla második sorára alkalmazva kapunk egy párot, amely egy félig standard tömbből és egy jelzett szabványos tömbből áll . A táblázat is átalakítható egy jegyezni félig standard táblázat helyettesítve minden egyes bejegyzés az a -edik bejegyzés első sorában .
P{\ displaystyle P}
Q0{\ displaystyle Q_ {0}}
Q0{\ displaystyle Q_ {0}}
Q{\ displaystyle Q}
h{\ displaystyle h}
Q0{\ displaystyle Q_ {0}}
h{\ displaystyle h}
wNÁL NÉL{\ displaystyle w_ {A}}![{\ displaystyle w_ {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2252bb47e2495074d4675cdc00a6b8fb8b6a42)
Mi így szerezzen bijekciót a mátrixok a pár félig-szabványos Young táblázatok az azonos alakú; az együtthatók a második sor elemei , az együtthatók pedig az első sor elemei . Ezen túlmenően, az együtthatók számát az egyenlő egyenlő az összege együtthatók az oszlop index a , és az együtthatók számát egyenlő a a egyenlő az összege együtthatók a sor index az .
NÁL NÉL{\ displaystyle A}
(P,Q){\ displaystyle (P, Q)}
P{\ displaystyle P}
wNÁL NÉL{\ displaystyle w_ {A}}
Q{\ displaystyle Q}
wNÁL NÉL{\ displaystyle w_ {A}}
P{\ displaystyle P}
j{\ displaystyle j}
j{\ displaystyle j}
NÁL NÉL{\ displaystyle A}
én{\ displaystyle i}
Q{\ displaystyle Q}
én{\ displaystyle i}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Példa
A fenti példához, ha a Schensted-beillesztést alkalmazzuk az 1,3,3,2,2,1,2 szekvencia beillesztésére egy kezdetben üres tömbbe, akkor egy tömböt és egy egymást követő formák regisztrációs táblázatát kapjuk , amely egyenlő:
P{\ displaystyle P}
Q0{\ displaystyle Q_ {0}}![{\ displaystyle Q_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41937118a9dc51ed18df28fe84c067c84a34733f)
P=1122233,Q0=123745.6.{\ displaystyle P \ quad = \ quad {\ begin {mátrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {mátrix}}, \ qquad Q_ {0} \ quad = \ quad {\ kezdete {mátrix} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ vége {mátrix}}}![{\ displaystyle P \ quad = \ quad {\ begin {mátrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {mátrix}}, \ qquad Q_ {0} \ quad = \ quad {\ kezdete {mátrix} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ vége {mátrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0becd90c2678b1c9c6326c0a90e8b0bd86dbf73b)
.
Miután az 1,2,3,4,5,6,7 bejegyzéseket lecseréltük 1,1,1,2,2,3,3-ra, megkapjuk a következő félig standard táblák párját:
Q0{\ displaystyle Q_ {0}}![{\ displaystyle Q_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41937118a9dc51ed18df28fe84c067c84a34733f)
P=1122233,Q=1113223.{\ displaystyle P \ quad = \ quad {\ begin {mátrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {mátrix}}, \ qquad Q \ quad = \ quad {\ begin {mátrix } 1 & 1 & 1 & 3 \\ 2 & 2 \\ 3 \ end {mátrix}}.}![{\ displaystyle P \ quad = \ quad {\ begin {mátrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {mátrix}}, \ qquad Q \ quad = \ quad {\ begin {mátrix } 1 & 1 & 1 & 3 \\ 2 & 2 \\ 3 \ end {mátrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbe5a5c33df7567703d01dbe1d2106126e05367b)
Az RSK levelezés közvetlen meghatározása
A fenti definíció Schensted algoritmusát használja, amely szabványos rekordtáblát állít elő ; ezt a táblázatot ezután módosítják, hogy figyelembe vegyék a kétsoros táblázat első sorát, és egy félig szabványos rekordtáblát kapjanak. Ez a meghatározás egyértelműen megmutatja a kapcsolatot a Robinson-Schensted-levelezéssel . Másrészt természetes, hogy egyszerűsíteni kell a konstrukció azon részét, amely a nyomtatvány regisztrálását illeti, a kétsoros táblázat első sorának közvetlen figyelembevételével. Ebben a formában szokták leírni az RSK-levelezés összeállításának algoritmusát. Ez egyszerűen azt jelenti, hogy a Schensted minden beszúrási lépése után a tömb megnövekszik azáltal, hogy az új négyzet értékeként hozzáadjuk az elem első sorának elemét , ahol a tömbök aktuális mérete van. Az a tény, hogy ez mindig félig szabványos tömböt eredményez, annak a tulajdonságnak a következménye (először Knuth figyelte meg), hogy amikor ugyanazt az értéket beszúrja az első sorba , az alakzatba felvett minden négyzet szigorúan nagyobb oszlopban van, mint az előző egy.
Q0{\ displaystyle Q_ {0}}
Q{\ displaystyle Q}
énh{\ displaystyle i_ {h}}
wNÁL NÉL{\ displaystyle w_ {A}}
h{\ displaystyle h}
wNÁL NÉL{\ displaystyle w_ {A}}![{\ displaystyle w_ {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2252bb47e2495074d4675cdc00a6b8fb8b6a42)
Részletes példa
Íme egy részletes példa a két félig szabványos táblázat felépítésére. A mátrixból indulunk ki:
NÁL NÉL=(00000000001010000100000000010000100001100000000001000000){\ displaystyle A = {\ begin {pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0![{\ displaystyle A = {\ begin {pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/134313396f225185b15ae376c79a01314a2fa934)
,
és megkapjuk a következő kétsoros táblázatot:
wNÁL NÉL=(22345.6.6.8.46.475.341).{\ displaystyle w_ {A} = {\ kezdete {pmatrix} 2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\ 4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 \ end {pmatrix }}.}![{\ displaystyle w_ {A} = {\ kezdete {pmatrix} 2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\ 4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 \ end {pmatrix }}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3792d09e49f5785e61c49b9de2e806b7548d8448)
Az alábbi táblázat bemutatja a példa két táblázatának felépítési lépéseit.
Pár beillesztve
|
(24){\ displaystyle {\ tbinom {2} {4}}}
|
(26.){\ displaystyle {\ tbinom {2} {6}}}
|
(34){\ displaystyle {\ tbinom {3} {4}}}
|
(47){\ displaystyle {\ tbinom {4} {7}}}
|
(5.5.){\ displaystyle {\ tbinom {5} {5}}}
|
(6.3){\ displaystyle {\ tbinom {6} {3}}}
|
(6.4){\ displaystyle {\ tbinom {6} {4}}}
|
(8.1){\ displaystyle {\ tbinom {8} {1}}}
|
P{\ displaystyle P}
|
4{\ displaystyle {\ begin {mátrix} 4 \ end {mátrix}}}
|
46.{\ displaystyle {\ begin {matrix} 4 és 6 \ end {matrix}}}
|
446.{\ displaystyle {\ begin {mátrix} 4 & 4 \\ 6 \ end {mátrix}}}
|
4476.{\ displaystyle {\ begin {mátrix} 4 & 4 & 7 \\ 6 \ end {mátrix}}}
|
445.6.7{\ displaystyle {\ begin {mátrix} 4 & 4 & 5 \\ 6 & 7 \ end {mátrix}}}
|
345.476.{\ displaystyle {\ begin {mátrix} 3 & 4 & 5 \\ 4 & 7 \\ 6 \ end {mátrix}}}
|
34445.6.7{\ displaystyle {\ begin {mátrix} 3 & 4 & 4 \\ 4 & 5 \\ 6 & 7 \ end {mátrix}}}
|
14435.476.{\ displaystyle {\ begin {mátrix} 1 & 4 & 4 \\ 3 & 5 \\ 4 & 7 \\ 6 \ end {mátrix}}}
|
Q{\ displaystyle Q}
|
2{\ displaystyle {\ elején {mátrix} 2 \ vége {mátrix}}}
|
22{\ displaystyle {\ elején {mátrix} 2 és 2 \ vége {mátrix}}}
|
223{\ displaystyle {\ begin {mátrix} 2 & 2 \\ 3 \ end {mátrix}}}
|
2243{\ displaystyle {\ begin {mátrix} 2 & 2 & 4 \\ 3 \ end {mátrix}}}
|
22435.{\ displaystyle {\ begin {mátrix} 2 & 2 & 4 \\ 3 & 5 \ end {mátrix}}}
|
22435.6.{\ displaystyle {\ begin {mátrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 \ end {mátrix}}}
|
22435.6.6.{\ displaystyle {\ begin {mátrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \ end {mátrix}}}
|
22435.6.6.8.{\ displaystyle {\ begin {mátrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \\ 8 \ end {mátrix}}}
|
Az RSK levelezés kombinatorikus tulajdonságai
A permutációs mátrixok esete
Ha A permutációs mátrix , akkor az RSK levelezés egy pár standard Young tömböt hoz létre, mondjuk . Ezzel szemben, ha standard Young tömbjei azonos alakúak , akkor a megfelelő mátrix egy permutációs mátrix. Ennek a tulajdonságnak a következményeként egyszerűen azáltal, hogy összehasonlítjuk az így bijectionbe helyezett halmazok számosságát, a következő tulajdonságot kapjuk:
λ{\ displaystyle \ lambda}
P,Q{\ displaystyle P, Q}
λ{\ displaystyle \ lambda}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Frobenius kiléte - Mert megvan
nem≥1{\ displaystyle n \ geq 1}![n \ geq 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8ce9ce38d06f6bf5a3fe063118c09c2b6202bfe)
∑λ∈Pnemfλ2=nem!{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} f _ {\ lambda} ^ {2} = n!}![{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} f _ {\ lambda} ^ {2} = n!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23db162613420909e4196eeb2ea6e7d90b87671e)
hol van a partíciók halmaza , és a standard Young tömbök formáinak száma .
Pnem{\ displaystyle {\ mathcal {P}} _ {n}}
nem{\ displaystyle n}
fλ{\ displaystyle f _ {\ lambda}}
λ{\ displaystyle \ lambda}![\ lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
Szimmetria
Legyen egy mátrix természetes egész számokkal. Tegyük fel, hogy az RSK algoritmus küld a . Ezután a RSK algoritmus küldi a ültették mátrix on .
NÁL NÉL{\ displaystyle A}
NÁL NÉL{\ displaystyle A}
(P,Q){\ displaystyle (P, Q)}
tNÁL NÉL{\ displaystyle ^ {t} A}
(Q,P){\ displaystyle (Q, P)}![{\ displaystyle (Q, P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db106cefc85a444dd9594d9fe37d5195d9128458)
A permutációs mátrixok esetében a Robinson-Schensted-megfelelés szimmetriáját találjuk meg, nevezetesen:
Tétel - Ha a permutáció megegyezik a triplettel , akkor a fordított permutáció megegyezik a triplettel .
σ{\ displaystyle \ sigma}
(λ,P,Q){\ displaystyle (\ lambda, P, Q)}
σ-1{\ displaystyle \ sigma ^ {- 1}}
(λ,Q,P){\ displaystyle (\ lambda, Q, P)}![{\ displaystyle (\ lambda, Q, P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1edd55be66437cd94dfe49c0f7142cd170d7f8da)
Ez vezet a következő összefüggés száma involutions a száma és a tömbök képezhetők :
{1,2,3,...,nem}{\ displaystyle \ {1,2,3, \ ldots, n \}}
{1,2,3,...,nem}{\ displaystyle \ {1,2,3, \ ldots, n \}}![{\ displaystyle \ {1,2,3, \ ldots, n \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd810c6a53156f56190667aebf3c8db25d49d2e4)
Tulajdonság - A standard tömbök száma megegyezik a bekapcsolások számával{1,2,3,...,nem}{\ displaystyle \ {1,2,3, \ ldots, n \}}
{1,2,3,...,nem}{\ displaystyle \ {1,2,3, \ ldots, n \}}
.
Bizonyítás : Legyen a párnak megfelelő involúció ; akkor megfelel tehát . Fordítva, ha egy permutáció megfelel , akkor ennek is megfelel , és ezért . Ez mutatja az invenciók és a táblázatok közötti bizonytalanságot .
π{\ displaystyle \ pi}
(P,Q){\ displaystyle (P, Q)}
π-1=π{\ displaystyle \ pi ^ {- 1} = \ pi}
(Q,P){\ displaystyle (Q, P)}
P=Q{\ displaystyle P = Q}
π{\ displaystyle \ pi}
(P,P){\ displaystyle (P, P)}
π-1{\ displaystyle \ pi ^ {- 1}}
(P,P){\ displaystyle (P, P)}
π-1=π{\ displaystyle \ pi ^ {- 1} = \ pi}
π{\ displaystyle \ pi}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
A bekapcsolódások számát , tehát Young standard elemeivel rendelkező tömbjének számát a megismétlődés reláció adja:
{1,2,3,...,nem}{\ displaystyle \ {1,2,3, \ ldots, n \}}
nem{\ displaystyle n}![nem](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
nál nél(nem)=nál nél(nem-1)+(nem-1)nál nél(nem-2){\ displaystyle a (n) = a (n-1) + (n-1) a (n-2) \,}![{\ displaystyle a (n) = a (n-1) + (n-1) a (n-2) \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/945a49069c542345437a0901409496721dce7ab5)
a . Ez az OEIS A00085 csomagja . Elismeri a kifejezést:
nál nél(1)=1,nál nél(2)=2{\ displaystyle a (1) = 1, a (2) = 2}![{\ displaystyle a (1) = 1, a (2) = 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68cce09497e87ae23fb07e04a6ce63ac027739a9)
nál nél(nem)=∑k=0⌊nem/2⌋nem!2kk!(nem-2k)!{\ displaystyle a (n) = \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {n!} {2 ^ {k} k! (n-2k)!}}}![{\ displaystyle a (n) = \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {n!} {2 ^ {k} k! (n-2k)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83e2f494e3b47253de8c757cb6c0d509f9ad85a2)
Szimmetrikus mátrixok
Legyen = lehet egy szimmetrikus mátrix . Legyen az a félig standard Young tábla, amelyet az RSK algoritmus kapott . Vagy a tömege (vagy a tartalmat , a szerzők szerint) a , által meghatározott: az a szám, ahányszor a egész szám jelenik meg . Tehát az alkalmazás
NÁL NÉL{\ displaystyle A}
tNÁL NÉL{\ displaystyle ^ {t} A}
(P,P){\ displaystyle (P, P)}
NÁL NÉL{\ displaystyle A}
α=(α1,α2,...){\ displaystyle \ alpha = (\ alpha _ {1}, \ alpha _ {2}, \ ldots)}
P{\ displaystyle P}
αén{\ displaystyle \ alpha _ {i}}
én{\ displaystyle i}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
NÁL NÉL⟼P{\ displaystyle A \ longmapsto P}![{\ displaystyle A \ longmapsto P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/773f43e7b010639420d9a6004d7397b03224a55a)
a szimmetrikus mátrixok kielégítő és félig standard fiatal tömegtömbök közötti bijekció . Itt van az a vektor, amelynek -edik összetevője a -edik sorának elemeinek összege .
sor(NÁL NÉL)=α{\ displaystyle {\ text {row}} (A) = \ alpha}
α{\ displaystyle \ alpha}
sor(NÁL NÉL){\ displaystyle {\ text {row}} (A)}
én{\ displaystyle i}
én{\ displaystyle i}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Példa
Legyen a szimmetrikus mátrix:
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
NÁL NÉL=(102011210){\ displaystyle A = {\ kezdés {pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \ end {pmatrix}}}![{\ displaystyle A = {\ kezdés {pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/713eca55b5d4e67b20232c05e47432c0ff5eeb39)
Egy számítás azt mutatja
P=11122333{\ displaystyle P = {\ kezdet {mátrix} 1 & 1 & 1 & 2 \\ 2 & 3 & 3 \\ 3 \ end {mátrix}}}![{\ displaystyle P = {\ kezdet {mátrix} 1 & 1 & 1 & 2 \\ 2 & 3 & 3 \\ 3 \ end {mátrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13120feec25fb23a3b4fd20e398a837d89d04217)
A súlya IS , és a vektor az összegek sorainak IS .
P{\ displaystyle P}
α=(3,2,3){\ displaystyle \ alpha = (3,2,3)}
NÁL NÉL{\ displaystyle A}
sor(NÁL NÉL)=(3,2,3){\ displaystyle {\ text {row}} (A) = (3,2,3)}![{\ displaystyle {\ text {row}} (A) = (3,2,3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b7ab75a0bc441aaefd3d3124621625039868846)
RSK levelezés alkalmazásai
Cauchy személyazonossága
Legyen és legyen változó. A Cauchy-ra visszanyúló identitás:
x1,x2,...{\ displaystyle x_ {1}, x_ {2}, \ ldots}
y1,y2,...{\ displaystyle y_ {1}, y_ {2}, \ ldots}![{\ displaystyle y_ {1}, y_ {2}, \ ldots}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4b6f607df13cd938f354080b5bf91612964ca49)
∏én,j(1-xényj)-1=∑λsλ(x)sλ(y){\ displaystyle \ prod _ {i, j} (1-x_ {i} y_ {j}) ^ {- 1} = \ sum _ {\ lambda} s _ {\ lambda} (x) s _ {\ lambda } (y)}![{\ displaystyle \ prod _ {i, j} (1-x_ {i} y_ {j}) ^ {- 1} = \ sum _ {\ lambda} s _ {\ lambda} (x) s _ {\ lambda } (y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46196a15621c250b241d0379ae9dc99edbfb74df)
ahol az a Schur-polinomok . A Schur-polinomok itt a legmegfelelőbb meghatározás
sλ{\ displaystyle s _ {\ lambda}}![{\ displaystyle s _ {\ lambda}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ad7e5606ce090b9dafd6ab6e28b6fdb85acf05)
sλ(x)=sλ(x1,x2,...,xnem)=∑TxT=∑Tx1t1⋯xnemtnem{\ displaystyle s _ {\ lambda} (x) = s _ {\ lambda} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = \ sum _ {T} x ^ {T} = \ sum _ {T} x_ {1} ^ {t_ {1}} \ cdots x_ {n} ^ {t_ {n}}}![{\ displaystyle s _ {\ lambda} (x) = s _ {\ lambda} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = \ sum _ {T} x ^ {T} = \ sum _ {T} x_ {1} ^ {t_ {1}} \ cdots x_ {n} ^ {t_ {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8d7ee08ba7dc721c512c689005cc4de2960406c)
ahol az összesítés meghaladja az összes félig standard Young tömböt, és az exponensek megadják a súlyát , más szóval megszámolják az in előfordulásainak számát .
λ{\ displaystyle \ lambda}
t1,...,tnem{\ displaystyle t_ {1}, \ ldots, t_ {n}}
T{\ displaystyle T}
tén{\ displaystyle t_ {i}}
én{\ displaystyle i}
T{\ displaystyle T}![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
Kostka számok
Legyen és legyen az egész két partíciója . Itt és tekintik , vagyis a vektor nem szükségképpen csökkenő számok, amelyek összege . Így
μ{\ displaystyle \ mu}
v{\ displaystyle \ nu}
nem{\ displaystyle n}
μ{\ displaystyle \ mu}
v{\ displaystyle \ nu}
ooénds{\ displaystyle weight}
nem{\ displaystyle n}![nem](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
∑λ∈PnemKλμKλv=NEMμv{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} K _ {\ lambda \ mu} K _ {\ lambda \ nu} = N _ {\ mu \ nu}}![{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} K _ {\ lambda \ mu} K _ {\ lambda \ nu} = N _ {\ mu \ nu}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/293b45c471207d9e98625f3e54a7b544d8c42c24)
ahol és jelöljük a Kostka-számokat, és a természetes egész együtthatóval rendelkező mátrixok száma , és . Itt van az a vektor, amelynek -edik koordinátája a -edik oszlopának elemeinek összege .
Kλμ{\ displaystyle K _ {\ lambda \ mu}}
Kλv{\ displaystyle K _ {\ lambda \ nu}}
NEMμv{\ displaystyle N _ {\ mu \ nu}}
NÁL NÉL{\ displaystyle A}
sor(NÁL NÉL)=μ{\ displaystyle {\ text {row}} (A) = \ mu}
oszlop(NÁL NÉL)=v{\ displaystyle {\ text {oszlop}} (A) = \ nu}
oszlop(NÁL NÉL){\ displaystyle {\ text {oszlop}} (A)}
j{\ displaystyle j}
j{\ displaystyle j}
NÁL NÉL{\ displaystyle A}![NÁL NÉL](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Megjegyzések és hivatkozások
(fr) Ez a cikk részben vagy egészben az
angol Wikipedia
„ Robinson - Schensted - Knuth-levelezés ” című
cikkéből származik ( lásd a szerzők felsorolását ) .
Megjegyzések
-
( Lascoux, Leclerc és Thibon 2002 )
-
( Stanley, 1999 , 316-380 . O.)
-
( Knuth 1970 )
-
( Knuth 2005 ), 5.1.4. Szakasz, 47–72. Oldal
Bibliográfia
- (en) Alain Lascoux , Bernard Leclerc és Jean-Yves Thibon , „A plaktikus monoid” , M. Lothaire , Algebraic Combinatorics on Words , CUP , coll. "Encyclopedia of matematika és alkalmazásai" ( n o 90)2002( ISBN 978-0-521-81220-7 , online olvasás ) , p. 164-196
- (in) William Fulton , Young tableaux , CUP, koll. "London Mathematical Society Student szövegek" ( n o 35)1997( ISBN 978-0-521-56144-0 és 978-0-521-56724-4 , Math Reviews 1464693 )
- (in) Donald E. Knuth , „ Permutációk, mátrixok és általánosított fiatal táblák ” , Pacific Journal of Mathematics , vol. 34,1970, P. 709–727 ( ISSN 0030-8730 , Math Reviews 0272654 , olvassa el online )
- (en) Donald E. Knuth , A számítógépes programozás művészete , vol. 3: Rendezés és keresés, 2. kiadás , Addison-Wesley,2005( ISBN 0-201-89685-0 , online előadás )
- (en) Bruce E. Sagan (en) , A szimmetrikus csoport: ábrázolások, kombinatorikus algoritmusok és szimmetrikus függvények , Springer, koll. " Diplomaszövegek a matematikából " ( n o 203)2001, 2 nd ed. , 240 p. ( ISBN 978-0-387-95067-9 , online olvasás )
- (en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ a kiadások részlete ] ( online bemutató )
Külső hivatkozás
(en) Bruce E. Sagan , „Schur funkciók az algebrai kombinatorikában” , Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN 978-1556080104 , online olvasás )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">