Robinson-Schensted-Knuth korrespondanse
I matematikk , og spesielt i algebraisk kombinatorikk , er korrespondansen Robinson - Schensted - Knuth , også kalt RSK-korrespondanse eller RSK-algoritmen , en sammenheng mellom matriser med naturlige heltall og par semi-standard Young arrays av samme form. størrelse er lik summen av oppføringene i matrisen . Denne korrespondansen generaliserer
Robinson-Schensted-korrespondansen , i den forstand at hvis det er en permutasjonsmatrise, så er paret paret av standardarrays assosiert med permutasjonen av Robinson - Schensted-korrespondansen .
PÅ{\ displaystyle A}
PÅ{\ displaystyle A}
PÅ{\ displaystyle A}
(P,Spørsmål){\ displaystyle (P, Q)}![(P, Q)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7854fbffaf21cef2fd7219d7b2413ea3961fdf4)
Robinson-Schensted-Knuth korrespondanse utvider mange av de bemerkelsesverdige egenskapene til Robinson-Schensted korrespondanse, og særlig egenskapen til symmetri: transponering av matrisen tilsvarer utveksling av matriser og .
PÅ{\ displaystyle A}
P{\ displaystyle P}
Spørsmål{\ displaystyle Q}![Spørsmål](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
Korrespondansen Robinson-Schensted-Knuth
Introduksjon
Den Robinson-Schensted korrespondanse er et Bijeksjon mellom permutasjoner og par av standard Unge rekker av samme form. Denne sammenhengen kan konstrueres ved hjelp av en algoritme kalt Schensted-innsetting . Denne algoritmen starter med en tom tabell og setter inn verdiene til permutasjonen suksessivt , med data i funksjonell form:
P{\ displaystyle P}
σ1,...,σikke{\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}
σ{\ displaystyle \ sigma}
σ{\ displaystyle \ sigma}![\ sigma](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36)
σ=(12...ikkeσ1σ2...σikke){\ 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)
.
Den resulterende matrisen er den første av paret som tilsvarer ; den andre standardtabellen, bemerket , registrerer de påfølgende formene som er krysset under konstruksjonen av .
P{\ displaystyle P}
σ{\ displaystyle \ sigma}
Spørsmål{\ displaystyle Q}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
Schensteds konstruksjon kan faktisk ta hensyn til mer generelle tallsekvenser enn de som oppnås ved permutasjoner (spesielt repetisjoner kan godkjennes); i dette tilfellet produserer konstruksjonen en semi-standard array i stedet for en standard array, men forblir en standard array. RSK-kartlegging gjenoppretter symmetri mellom matriser ved å produsere en semi-standard matrise for også.
P{\ displaystyle P}
Spørsmål{\ displaystyle Q}
Spørsmål{\ displaystyle Q}![Spørsmål](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
To-rad bord
En tabell med to linjer (" to-linjers array " på engelsk) eller bimot eller generalisert permutasjon tilsvarende en matrise er definert som følger er en matrise
wPÅ{\ displaystyle w_ {A}}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
wPÅ=(Jeg1Jeg2⋯Jegmj1j2⋯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)
som sjekker følgende egenskaper:
- Kolonnene er ordnet i leksikografisk rekkefølge , noe som betyr at
-
Jeg1≤Jeg2≤Jeg3≤⋯≤Jegm{\ displaystyle i_ {1} \ leq i_ {2} \ leq i_ {3} \ leq \ cdots \ leq i_ {m}}
, og
- hvis og , da .Jegr=Jegs{\ 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)
- for hvert par indekser i matrisen er det kolonner lik .(Jeg,j){\ displaystyle (i, j)}
PÅ{\ displaystyle A}
PÅJeg,j{\ displaystyle A_ {i, j}}
(Jegj){\ displaystyle {\ tbinom {i} {j}}}![{\ displaystyle {\ tbinom {i} {j}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e577d8167a5df460cedcf1c467f45d3446f44b)
Spesielt er heltallet lik summen av koeffisientene til matrisen .
m{\ displaystyle m}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Eksempel
To-radstabellen som tilsvarer matrisen:
PÅ=(102020110){\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}![{\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9eaf4733ea4c18abb1583577ea1bdbc775db3fff)
er :
wPÅ=(11122331332212){\ displaystyle w_ {A} = {\ begin {pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 3 & 2 & 2 & 1 & 2 \ end {pmatrix}}}![{\ displaystyle w_ {A} = {\ begin {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)
Definisjon av korrespondanse
Ved å anvende Schensteds innsettingsalgoritme på den andre raden i et to-radstabell, får vi et par bestående av en semi-standard array og en betegnet standard array . Bordet kan også omdannes til et semi-standard er angitt tabell ved å erstatte hver oppføring i den -te inngang i den første raden av .
P{\ displaystyle P}
Spørsmål0{\ displaystyle Q_ {0}}
Spørsmål0{\ displaystyle Q_ {0}}
Spørsmål{\ displaystyle Q}
h{\ displaystyle h}
Spørsmål0{\ displaystyle Q_ {0}}
h{\ displaystyle h}
wPÅ{\ displaystyle w_ {A}}![{\ displaystyle w_ {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2252bb47e2495074d4675cdc00a6b8fb8b6a42)
Vi oppnår dermed en sammenbinding av matriser på par semi-standard Young-bord med samme form; koeffisientene til er elementene i den andre linjen av , og koeffisientene til er elementene i den første linjen av . I tillegg ble antallet av koeffisienter lik er lik summen av koeffisientene i kolonne av indeksen av , og antallet koeffisienter lik i er lik summen av koeffisientene til rekken av indeksen av .
PÅ{\ displaystyle A}
(P,Spørsmål){\ displaystyle (P, Q)}
P{\ displaystyle P}
wPÅ{\ displaystyle w_ {A}}
Spørsmål{\ displaystyle Q}
wPÅ{\ displaystyle w_ {A}}
P{\ displaystyle P}
j{\ displaystyle j}
j{\ displaystyle j}
PÅ{\ displaystyle A}
Jeg{\ displaystyle i}
Spørsmål{\ displaystyle Q}
Jeg{\ displaystyle i}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Eksempel
For det ovennevnte eksemplet, hvis vi bruker Schensted-innsettingen til innsettingen av sekvensen 1,3,3,2,2,1,2 i en opprinnelig tom matrise, får vi en matrise og en registreringstabell over påfølgende former er lik:
P{\ displaystyle P}
Spørsmål0{\ displaystyle Q_ {0}}![{\ displaystyle Q_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41937118a9dc51ed18df28fe84c067c84a34733f)
P=1122233,Spørsmål0=1237456{\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q_ {0} \ quad = \ quad {\ begynn {matrise} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ slutt {matrise}}}![{\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q_ {0} \ quad = \ quad {\ begynn {matrise} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ slutt {matrise}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0becd90c2678b1c9c6326c0a90e8b0bd86dbf73b)
.
Etter å ha erstattet oppføringene henholdsvis 1,2,3,4,5,6,7 med 1,1,1,2,2,3,3, får vi følgende par semi-standard tabeller:
Spørsmål0{\ displaystyle Q_ {0}}![{\ displaystyle Q_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41937118a9dc51ed18df28fe84c067c84a34733f)
P=1122233,Spørsmål=1113223.{\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q \ quad = \ quad {\ begin {matrix } 1 & 1 & 1 & 3 \\ 2 & 2 \\ 3 \ end {matrix}}.}![{\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q \ quad = \ quad {\ begin {matrix } 1 & 1 & 1 & 3 \\ 2 & 2 \\ 3 \ end {matrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbe5a5c33df7567703d01dbe1d2106126e05367b)
Direkte definisjon av RSK-korrespondanse
Ovennevnte definisjon bruker Schensteds algoritme som produserer en standard posttabell ; denne tabellen blir deretter modifisert for å ta hensyn til den første raden i to-rad-tabellen og få en semi-standard platetabell. Denne definisjonen viser tydelig forholdet til korrespondansen mellom Robinson og Schensted . På den annen side er det naturlig å forenkle den delen av konstruksjonen som gjelder registrering av skjemaet ved å ta direkte hensyn til den første raden i to-radstabellen. Det er i denne formen at algoritmen for å konstruere RSK-korrespondansen vanligvis blir beskrevet. Dette betyr ganske enkelt at matrisen etter hvert innsettingstrinn i Schensted økes ved å legge til elementet fra den første raden i , som en verdi i den nye firkanten , hvor den nåværende størrelsen på matriser er. Det faktum at dette alltid produserer en semi-standard matrise er en konsekvens av egenskapen (først observert av Knuth) at når du setter inn den samme verdien i den første raden av , er hvert kvadrat lagt i formen i en kolonne som er strengt større enn den forrige en.
Spørsmål0{\ displaystyle Q_ {0}}
Spørsmål{\ displaystyle Q}
Jegh{\ displaystyle i_ {h}}
wPÅ{\ displaystyle w_ {A}}
h{\ displaystyle h}
wPÅ{\ displaystyle w_ {A}}![{\ displaystyle w_ {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2252bb47e2495074d4675cdc00a6b8fb8b6a42)
Detaljert eksempel
Her er et detaljert eksempel på denne konstruksjonen av de to halvstandardbordene. Vi starter fra matrisen:
PÅ=(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 & 1 \\ 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![{\ 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 & 1 \\ 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](https://wikimedia.org/api/rest_v1/media/math/render/svg/134313396f225185b15ae376c79a01314a2fa934)
,
og vi får følgende to-radstabell:
wPÅ=(2234566846475341).{\ displaystyle w_ {A} = {\ begin {pmatrix} 2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\ 4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 \ end {pmatrix }}.}![{\ displaystyle w_ {A} = {\ begin {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)
Den følgende tabellen viser konstruksjonstrinn for de to tabellene for dette eksemplet.
Par satt inn
|
(24){\ displaystyle {\ tbinom {2} {4}}}
|
(26){\ displaystyle {\ tbinom {2} {6}}}
|
(34){\ displaystyle {\ tbinom {3} {4}}}
|
(47){\ displaystyle {\ tbinom {4} {7}}}
|
(55){\ displaystyle {\ tbinom {5} {5}}}
|
(63){\ displaystyle {\ tbinom {6} {3}}}
|
(64){\ displaystyle {\ tbinom {6} {4}}}
|
(81){\ displaystyle {\ tbinom {8} {1}}}
|
P{\ displaystyle P}
|
4{\ displaystyle {\ begin {matrix} 4 \ end {matrix}}}
|
46{\ displaystyle {\ begin {matrix} 4 og 6 \ end {matrix}}}
|
446{\ displaystyle {\ begin {matrix} 4 og 4 \\ 6 \ end {matrix}}}
|
4476{\ displaystyle {\ begin {matrise} 4 og 4 og 7 \\ 6 \ slutt {matrise}}}
|
44567{\ displaystyle {\ begin {matrix} 4 & 4 & 5 \\ 6 & 7 \ end {matrix}}}
|
345476{\ displaystyle {\ begin {matrix} 3 & 4 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}
|
3444567{\ displaystyle {\ begin {matrix} 3 & 4 & 4 \\ 4 & 5 \\ 6 & 7 \ end {matrix}}}
|
14435476{\ displaystyle {\ begin {matrix} 1 & 4 & 4 \\ 3 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}
|
Spørsmål{\ displaystyle Q}
|
2{\ displaystyle {\ begin {matrix} 2 \ end {matrix}}}
|
22{\ displaystyle {\ begin {matrix} 2 og 2 \ end {matrix}}}
|
223{\ displaystyle {\ begin {matrix} 2 og 2 \\ 3 \ end {matrix}}}
|
2243{\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 \ end {matrix}}}
|
22435{\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \ end {matrix}}}
|
224356{\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 \ end {matrix}}}
|
2243566{\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \ end {matrix}}}
|
22435668{\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \\ 8 \ end {matrix}}}
|
Kombinatoriske egenskaper ved RSK-korrespondanse
Tilfellet med permutasjonsmatriser
Hvis A er en permutasjonsmatrise , produserer RSK-korrespondansen et par standard Youngs arrays av samme form, for eksempel . Omvendt, hvis det er standard Youngs matriser av samme form , er den tilsvarende matrisen en permutasjonsmatrise. Som en konsekvens av denne egenskapen oppnår vi, bare ved å sammenligne kardinaliteten til settene som er satt i sammenheng, følgende egenskaper:
λ{\ displaystyle \ lambda}
P,Spørsmål{\ displaystyle P, Q}
λ{\ displaystyle \ lambda}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Frobenius identitet - For , det har vi
ikke≥1{\ displaystyle n \ geq 1}![n \ geq 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8ce9ce38d06f6bf5a3fe063118c09c2b6202bfe)
∑λ∈Pikkefλ2=ikke!{\ 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)
hvor er settet med partisjoner av , og er antall standard Young arrays of form .
Pikke{\ displaystyle {\ mathcal {P}} _ {n}}
ikke{\ displaystyle n}
fλ{\ displaystyle f _ {\ lambda}}
λ{\ displaystyle \ lambda}![\ lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
Symmetri
La være en matrise med naturlige heltall. Anta at RSK-algoritmen sender videre . Deretter sender RSK-algoritmen den transponerte matrisen videre .
PÅ{\ displaystyle A}
PÅ{\ displaystyle A}
(P,Spørsmål){\ displaystyle (P, Q)}
tPÅ{\ displaystyle ^ {t} A}
(Spørsmål,P){\ displaystyle (Q, P)}![{\ displaystyle (Q, P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db106cefc85a444dd9594d9fe37d5195d9128458)
I det spesielle tilfellet med permutasjonsmatriser finner vi symmetrien til korrespondansen Robinson-Schensted, nemlig:
Teorem - Hvis permutasjonen samsvarer med tripletten , så samsvarer omvendt permutasjon med tripletten .
σ{\ displaystyle \ sigma}
(λ,P,Spørsmål){\ displaystyle (\ lambda, P, Q)}
σ-1{\ displaystyle \ sigma ^ {- 1}}
(λ,Spørsmål,P){\ displaystyle (\ lambda, Q, P)}![{\ displaystyle (\ lambda, Q, P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1edd55be66437cd94dfe49c0f7142cd170d7f8da)
Dette fører til følgende forhold mellom antall involveringer på og antall arrays som kan dannes fra :
{1,2,3,...,ikke}{\ displaystyle \ {1,2,3, \ ldots, n \}}
{1,2,3,...,ikke}{\ displaystyle \ {1,2,3, \ ldots, n \}}![{\ displaystyle \ {1,2,3, \ ldots, n \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd810c6a53156f56190667aebf3c8db25d49d2e4)
Eiendom - Antall standard arrays på tilsvarer antall involveringer på{1,2,3,...,ikke}{\ displaystyle \ {1,2,3, \ ldots, n \}}
{1,2,3,...,ikke}{\ displaystyle \ {1,2,3, \ ldots, n \}}
.
Bevis : La være en involusjon som tilsvarer paret ; da tilsvarer derfor . Omvendt, hvis tilsvarer en permutasjon, tilsvarer den også , og derfor . Dette viser sammenhengen mellom involveringer og tabeller .
π{\ displaystyle \ pi}
(P,Spørsmål){\ displaystyle (P, Q)}
π-1=π{\ displaystyle \ pi ^ {- 1} = \ pi}
(Spørsmål,P){\ displaystyle (Q, P)}
P=Spørsmål{\ 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)
Antall involveringer på , og dermed antall Youngs matrix med elementer, er gitt av gjentakelsesforholdet:
{1,2,3,...,ikke}{\ displaystyle \ {1,2,3, \ ldots, n \}}
ikke{\ displaystyle n}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
på(ikke)=på(ikke-1)+(ikke-1)på(ikke-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)
med . Det er A00085- pakken til OEIS . Hun innrømmer uttrykket:
på(1)=1,på(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)
på(ikke)=∑k=0⌊ikke/2⌋ikke!2kk!(ikke-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)
Symmetriske matriser
La = være en symmetrisk matrise . La være paret av semi-standard Young tabeller innhentet av RSK algoritmen for . Enten den vekt (eller innhold , i henhold til forfatterne) av , definert ved: er det antall ganger det hele tall vises på . Så søknaden
PÅ{\ displaystyle A}
tPÅ{\ displaystyle ^ {t} A}
(P,P){\ displaystyle (P, P)}
PÅ{\ displaystyle A}
α=(α1,α2,...){\ displaystyle \ alpha = (\ alpha _ {1}, \ alpha _ {2}, \ ldots)}
P{\ displaystyle P}
αJeg{\ displaystyle \ alpha _ {i}}
Jeg{\ displaystyle i}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
PÅ⟼P{\ displaystyle A \ longmapsto P}![{\ displaystyle A \ longmapsto P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/773f43e7b010639420d9a6004d7397b03224a55a)
er en sammenheng mellom symmetriske matriser som tilfredsstiller og semi-standard Young arrays of weight . Her er vektoren hvis -th komponent er summen av elementene i -th rad av .
rad(PÅ)=α{\ displaystyle {\ text {row}} (A) = \ alpha}
α{\ displaystyle \ alpha}
rad(PÅ){\ displaystyle {\ text {row}} (A)}
Jeg{\ displaystyle i}
Jeg{\ displaystyle i}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Eksempel
La den symmetriske matrisen være:
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
PÅ=(102011210){\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \ end {pmatrix}}}![{\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/713eca55b5d4e67b20232c05e47432c0ff5eeb39)
En beregning viser det
P=11122333{\ displaystyle P = {\ begin {matrix} 1 & 1 & 1 & 2 \\ 2 & 3 & 3 \\ 3 \ end {matrix}}}![{\ displaystyle P = {\ begin {matrix} 1 & 1 & 1 & 2 \\ 2 & 3 & 3 \\ 3 \ end {matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13120feec25fb23a3b4fd20e398a837d89d04217)
Vekten av er , og vektoren for summen av rader av er .
P{\ displaystyle P}
α=(3,2,3){\ displaystyle \ alpha = (3,2,3)}
PÅ{\ displaystyle A}
rad(PÅ)=(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)
Søknader om RSK-korrespondanse
Identitet av Cauchy
La og være variabler. Identiteten som går tilbake til Cauchy er:
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)
∏Jeg,j(1-xJegyj)-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)
der er Schur-polynomer . Den mest passende definisjonen her av Schur-polynomer er
sλ{\ displaystyle s _ {\ lambda}}![{\ displaystyle s _ {\ lambda}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ad7e5606ce090b9dafd6ab6e28b6fdb85acf05)
sλ(x)=sλ(x1,x2,...,xikke)=∑TxT=∑Tx1t1⋯xikketikke{\ 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)
der summeringen er over alle semi-standard Young arrays of form og der eksponentene gir vekten av , med andre ord, teller antall forekomster av in .
λ{\ displaystyle \ lambda}
t1,...,tikke{\ displaystyle t_ {1}, \ ldots, t_ {n}}
T{\ displaystyle T}
tJeg{\ displaystyle t_ {i}}
Jeg{\ displaystyle i}
T{\ displaystyle T}![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
Kostka-tall
La og være to partisjoner av heltallet . Her og blir sett på som , det vil si som en vektor for ikke nødvendigvis synkende heltall, hvis sum er . Så
μ{\ displaystyle \ mu}
ν{\ displaystyle \ nu}
ikke{\ displaystyle n}
μ{\ displaystyle \ mu}
ν{\ displaystyle \ nu}
soJegds{\ displaystyle vekt)
ikke{\ displaystyle n}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
∑λ∈PikkeKλμKλν=IKKEμν{\ 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)
hvor og betegner Kostka-tallene og er antall matriser med naturlige heltallskoeffisienter, med og . Her er vektoren hvis -th koordinat er summen av elementene i -th kolonne av .
Kλμ{\ displaystyle K _ {\ lambda \ mu}}
Kλν{\ displaystyle K _ {\ lambda \ nu}}
IKKEμν{\ displaystyle N _ {\ mu \ nu}}
PÅ{\ displaystyle A}
rad(PÅ)=μ{\ displaystyle {\ text {row}} (A) = \ mu}
kolonne(PÅ)=ν{\ displaystyle {\ text {column}} (A) = \ nu}
kolonne(PÅ){\ displaystyle {\ text {column}} (A)}
j{\ displaystyle j}
j{\ displaystyle j}
PÅ{\ displaystyle A}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Merknader og referanser
(fr) Denne artikkelen er delvis eller helt hentet fra den
engelske Wikipedia- artikkelen med tittelen
“ Robinson - Schensted - Knuth-korrespondanse ” ( se forfatterliste ) .
Merknader
-
( Lascoux, Leclerc og Thibon 2002 )
-
( Stanley, 1999 , s. 316-380)
-
( Knuth 1970 )
-
( Knuth 2005 ), avsnitt 5.1.4, side 47-72
Bibliografi
- (no) Alain Lascoux , Bernard Leclerc og Jean-Yves Thibon , “The plactic monoid” , i M. Lothaire , Algebraic Combinatorics on Words , CUP , koll. "Encyclopedia of Mathematics og dets Applications" ( N o 90)2002( ISBN 978-0-521-81220-7 , leses online ) , s. 164-196
- (in) William Fulton , Young tableaux , CUP, koll. "London Mathematical Society elevtekster" ( N o 35)1997( ISBN 978-0-521-56144-0 og 978-0-521-56724-4 , matematiske anmeldelser 1464693 )
- (i) Donald E. Knuth , “ Permutasjoner, matriser og generaliserte unge tablåer ” , Pacific Journal of Mathematics , vol. 34,1970, s. 709–727 ( ISSN 0030-8730 , matematiske anmeldelser 0272654 , les online )
- (no) Donald E. Knuth , The Art of Computer Programming , vol. 3: Sortering og søking, andre utgave , Addison-Wesley,2005( ISBN 0-201-89685-0 , online presentasjon )
- (en) Bruce E. Sagan (en) , The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , Springer, coll. " Graduate tekster i Mathematics " ( n o 203)2001, 2 nd ed. , 240 s. ( ISBN 978-0-387-95067-9 , les online )
- (no) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ detalj av utgaver ] ( online presentasjon )
Ekstern lenke
(en) Bruce E. Sagan , "Schur fungerer i algebraisk kombinatorikk" , i Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN 978-1556080104 , les online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">