Robinson-Schensted-Knuth-Korrespondenz

In der Mathematik und insbesondere in der algebraischen Kombinatorik ist die Robinson-Schensted-Knuth-Korrespondenz , auch RSK-Korrespondenz oder RSK-Algorithmus genannt , eine Bijektion zwischen Matrizen mit natürlichen ganzen Zahlen und Paaren von halbstandardisierten Young-Arrays derselben Form Größe ist gleich der Summe der Einträge in der Matrix . Diese Korrespondenz verallgemeinert die Robinson-Schensted Entsprechung , in dem Sinne , dass , wenn eine Permutationsmatrix ist, dann ist das Paar das Paar von Standard - Arrays ist mit der Permutation zugeordnet ist von der Robinson - Schensted Korrespondenz . $BEIM$ $BEIM$ $BEIM$ $(P, Q)$

Die Robinson-Schensted-Knuth-Korrespondenz erweitert viele der bemerkenswerten Eigenschaften der Robinson-Schensted-Korrespondenz und insbesondere die Symmetrieeigenschaft: Die Transposition der Matrix entspricht dem Austausch von Arrays und . $BEIM$ $P.$ $Q.$

Die Robinson-Schensted-Knuth-Korrespondenz

Einführung

Die Robinson-Schensted-Korrespondenz ist eine Bijektion zwischen Permutationen und Paaren von Standard- Young-Arrays derselben Form. Diese Bijektion kann unter Verwendung eines Algorithmus konstruiert werden, der als Schensted-Insertion bezeichnet wird . Dieser Algorithmus beginnt mit einer leeren Tabelle und fügt nacheinander die Werte der Permutation mit Daten in funktionaler Form ein: $P.$ ${\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}$ $\ sigma$ $\ sigma$

{\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & \ ldots & n \\\ sigma _ {1} & \ sigma _ {2} & \ ldots & \ sigma _ {n} \ end {pmatrix} }}

Das resultierende Array ist das erste des Paares, das entspricht ; Die zweite Standardtabelle, die notiert ist , zeichnet die aufeinanderfolgenden Formen auf, die während des Aufbaus von durchlaufen wurden . $P.$ $\ sigma$ $Q.$ $P.$

Schensteds Konstruktion kann tatsächlich allgemeinere Zahlenfolgen berücksichtigen als solche, die durch Permutationen erhalten werden (insbesondere Wiederholungen können genehmigt werden); In diesem Fall erzeugt die Konstruktion ein Semi-Standard-Array anstelle eines Standard-Arrays, bleibt jedoch ein Standard-Array. Die RSK-Zuordnung stellt die Symmetrie zwischen Arrays wieder her, indem auch für diese ein Semi-Standard-Array erstellt wird. $P.$ $Q.$ $Q.$

Zweizeilige Tabellen

Eine Tabelle mit zwei Zeilen (" zweizeiliges Array " in Englisch) oder einer Bimot- oder verallgemeinerten Permutation , die einer Matrix entspricht, ist wie folgt definiert: Eine Matrix ${\ displaystyle w_ {A}}$ $BEIM$

{\ displaystyle w_ {A} = {\ begin {pmatrix} i_ {1} & i_ {2} & \ cdots & i_ {m} \\ j_ {1} & j_ {2} & \ cdots & j_ {m} \ end {pmatrix}}}

Hiermit werden die folgenden Eigenschaften überprüft:

Die Spalten sind in lexikografischer Reihenfolge angeordnet , was bedeutet, dass
1. ${\ displaystyle i_ {1} \ leq i_ {2} \ leq i_ {3} \ leq \ cdots \ leq i_ {m}}$ , und
2. wenn und dann . ${\ displaystyle i_ {r} = i_ {s}}$ ${\ displaystyle r \ leq s}$ ${\ displaystyle j_ {r} \ leq j_ {s}}$
Für jedes Indexpaar in der Matrix gibt es Spalten gleich . $(i, j)$ $BEIM$ $A_ {i, j}$ ${\ displaystyle {\ tbinom {i} {j}}}$

Insbesondere ist die ganze Zahl gleich der Summe der Koeffizienten der Matrix . $m$ $BEIM$

Beispiel

Die zweizeilige Tabelle, die der Matrix entspricht:

{\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 1 & 1 & 0 \ end {pmatrix}}}

ist:

{\ displaystyle w_ {A} = {\ begin {pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 3 & 2 & 2 & 1 & 2 \ end {pmatrix}}}

Definition der Korrespondenz

Wenn wir den Schensted-Einfügealgorithmus auf die zweite Zeile einer zweizeiligen Tabelle anwenden, erhalten wir ein Paar, das aus einem Semi-Standard- Array und einem bezeichneten Standard-Array besteht . Die Tabelle kann auch in einem bekannten Halbstandardtabelle umgewandelt werden , indem jeder Eintrag ersetzt in dem -te Eintrag in der ersten Reihe der . $P.$ ${\ displaystyle Q_ {0}}$ ${\ displaystyle Q_ {0}}$ $Q.$ $h$ ${\ displaystyle Q_ {0}}$ $h$ ${\ displaystyle w_ {A}}$

Auf diese Weise erhalten wir eine Bijektion der Matrizen auf Paare von halbstandardisierten Young-Tischen derselben Form; Die Koeffizienten von sind die Elemente der zweiten Zeile von und die Koeffizienten von sind die Elemente der ersten Zeile von . Außerdem ist die Anzahl der Koeffizienten gleich gleich gleich der Summe der Koeffizienten der Indexspalte von , und die Anzahl der Koeffizienten gleich in ist gleich der Summe der Koeffizienten der Indexzeile von . $BEIM$ $(P, Q)$ $P.$ ${\ displaystyle w_ {A}}$ $Q.$ ${\ displaystyle w_ {A}}$ $P.$ $j$ $j$ $BEIM$ $ich$ $Q.$ $ich$ $BEIM$

Beispiel

Wenn wir für das obige Beispiel die Schensted-Einfügung auf die Einfügung der Sequenz 1,3,3,2,2,1,2 in ein anfänglich leeres Array anwenden, erhalten wir ein Array und eine Registrierungstabelle der aufeinanderfolgenden Formulare. welche gleich sind: $P.$ ${\ displaystyle Q_ {0}}$

{\ displaystyle P \ quad = \ quad {\ begin {matrix} 1 & 1 & 2 & 2 \\ 2 & 3 \\ 3 \ end {matrix}}, \ qquad Q_ {0} \ quad = \ quad {\ begin {matrix} 1 & 2 & 3 & 7 \\ 4 & 5 \\ 6 \ end {matrix}}}

Nachdem wir die Einträge 1,2,3,4,5,6,7 in durch 1,1,1,2,2,3,3 ersetzt haben, erhalten wir das folgende Paar von Halbstandardtabellen: ${\ displaystyle Q_ {0}}$

{\ 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}}.}

Direkte Definition der RSK-Korrespondenz

Die obige Definition verwendet den Schensted-Algorithmus, der eine Standardaufzeichnungstabelle erzeugt ; Diese Tabelle wird dann geändert, um die erste Zeile der zweizeiligen Tabelle zu berücksichtigen und eine Semi-Standard-Datensatztabelle zu erhalten. Diese Definition zeigt deutlich die Beziehung zur Robinson-Schensted-Korrespondenz . Andererseits ist es natürlich, den Teil der Konstruktion bezüglich der Registrierung des Formulars zu vereinfachen, indem die erste Zeile der zweizeiligen Tabelle direkt berücksichtigt wird. In dieser Form wird üblicherweise der Algorithmus zum Aufbau der RSK-Korrespondenz beschrieben. Dies bedeutet einfach, dass nach jedem Einfügungsschritt von Schensted das Array vergrößert wird, indem als Wert im neuen Quadrat das Element aus der ersten Zeile von hinzugefügt wird , wobei die aktuelle Größe der Arrays ist. Die Tatsache, dass dies immer ein Semi-Standard-Array erzeugt, ist eine Folge der Eigenschaft (zuerst von Knuth beobachtet), dass beim Einfügen des gleichen Werts in die erste Zeile von jedes in der Form hinzugefügte Quadrat in einer Spalte liegt, die streng größer als die vorherige ist einer. ${\ displaystyle Q_ {0}}$ $Q.$ ${\ displaystyle i_ {h}}$ ${\ displaystyle w_ {A}}$ $h$ ${\ displaystyle w_ {A}}$

Detailliertes Beispiel

Hier ist ein detailliertes Beispiel für diesen Aufbau der beiden Semi-Standard-Tabellen. Wir gehen von der Matrix aus:

{\ 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 & 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

und wir erhalten die folgende zweizeilige Tabelle:

{\ displaystyle w_ {A} = {\ begin {pmatrix} 2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\ 4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 \ end {pmatrix }}.}

Die folgende Tabelle zeigt die Konstruktionsschritte für die beiden Tabellen für dieses Beispiel.

Paar eingefügt	${\ displaystyle {\ tbinom {2} {4}}}$	${\ displaystyle {\ tbinom {2} {6}}}$	${\ displaystyle {\ tbinom {3} {4}}}$	${\ displaystyle {\ tbinom {4} {7}}}$	${\ displaystyle {\ tbinom {5} {5}}}$	${\ displaystyle {\ tbinom {6} {3}}}$	${\ displaystyle {\ tbinom {6} {4}}}$	${\ displaystyle {\ tbinom {8} {1}}}$
$P.$	${\ displaystyle {\ begin {matrix} 4 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 & 7 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 4 & 4 & 5 \\ 6 & 7 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 3 & 4 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 3 & 4 & 4 \\ 4 & 5 \\ 6 & 7 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 1 & 4 & 4 \\ 3 & 5 \\ 4 & 7 \\ 6 \ end {matrix}}}$
$Q.$	${\ displaystyle {\ begin {matrix} 2 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 \\ 3 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \ end {matrix}}}$	${\ displaystyle {\ begin {matrix} 2 & 2 & 4 \\ 3 & 5 \\ 6 & 6 \\ 8 \ end {matrix}}}$

Kombinatorische Eigenschaften der RSK-Korrespondenz

Der Fall von Permutationsmatrizen

Wenn A eine Permutationsmatrix ist , erzeugt die RSK-Entsprechung beispielsweise ein Paar von Standard-Young-Arrays derselben Form . Umgekehrt ist die entsprechende Matrix eine Permutationsmatrix , wenn Standard-Young-Arrays dieselbe Form haben . Als Konsequenz dieser Eigenschaft erhalten wir einfach durch Vergleichen der Kardinalität der so bijektierten Mengen die folgende Eigenschaft: $\ lambda$ $P, Q.$ $\ lambda$ $BEIM$

Identität von Frobenius - Denn wir haben $n \ geq 1$

{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} f _ {\ lambda} ^ {2} = n!}

Wo ist die Menge der Partitionen von und ist die Anzahl der Standard-Young-Arrays der Form . ${\ displaystyle {\ mathcal {P}} _ {n}}$ $nicht$ ${\ displaystyle f _ {\ lambda}}$ $\ lambda$

Symmetrie

Sei eine Matrix mit natürlichen ganzen Zahlen. Angenommen, der RSK-Algorithmus sendet weiter . Dann sendet der RSK-Algorithmus die transponierte Matrix weiter . $BEIM$ $BEIM$ $(P, Q)$ ${\ displaystyle ^ {t} A}$ ${\ displaystyle (Q, P)}$

Im speziellen Fall von Permutationsmatrizen finden wir die Symmetrie der Robinson-Schensted-Korrespondenz, nämlich:

Satz - Wenn die Permutation mit dem Triplett übereinstimmt , stimmt die umgekehrte Permutation mit dem Triplett überein . $\ sigma$ ${\ displaystyle (\ lambda, P, Q)}$ ${\ displaystyle \ sigma ^ {- 1}}$ ${\ displaystyle (\ lambda, Q, P)}$

Dies führt zu der folgenden Beziehung zwischen der Anzahl der Involutionen auf und der Anzahl von Arrays , die aus gebildet werden können : ${\ displaystyle \ {1,2,3, \ ldots, n \}}$ ${\ displaystyle \ {1,2,3, \ ldots, n \}}$

Eigenschaft - Die Anzahl der Standard-Arrays auf entspricht der Anzahl der Involutionen auf ${\ displaystyle \ {1,2,3, \ ldots, n \}}$ ${\ displaystyle \ {1,2,3, \ ldots, n \}}$

Beweis : Sei eine dem Paar entsprechende Involution ; dann entspricht also also . Umgekehrt, wenn eine Permutation entspricht , dann entspricht auch und daher . Dies zeigt die Bijektion zwischen Involutionen und Tabellen . $\ pi$ $(P, Q)$ ${\ displaystyle \ pi ^ {- 1} = \ pi}$ ${\ displaystyle (Q, P)}$ $P = Q.$ $\ pi$ ${\ displaystyle (P, P)}$ ${\ displaystyle \ pi ^ {- 1}}$ ${\ displaystyle (P, P)}$ ${\ displaystyle \ pi ^ {- 1} = \ pi}$ $\ pi$ $P.$

Die Anzahl der Involutionen und damit die Anzahl der Standard-Young-Arrays mit Elementen ergibt sich aus der Wiederholungsrelation: ${\ displaystyle \ {1,2,3, \ ldots, n \}}$ $nicht$

{\ Anzeigestil a (n) = a (n-1) + (n-1) a (n-2) \,}

mit . Es ist die A00085- Suite des OEIS . Sie gibt den Ausdruck zu: ${\ displaystyle a (1) = 1, a (2) = 2}$

{\ displaystyle a (n) = \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {n!} {2 ^ {k} k! (n-2k)!}}}

Symmetrische Matrizen

Sei = eine symmetrische Matrix . Sei das Paar von Standard-Young-Tabellen, die vom RSK-Algorithmus für erhalten wurden . Entweder das Gewicht (oder der Inhalt , laut den Autoren) von , definiert durch: ist die Häufigkeit, mit der die Ganzzahl erscheint . Also die Anwendung $BEIM$ ${\ displaystyle ^ {t} A}$ ${\ displaystyle (P, P)}$ $BEIM$ ${\ displaystyle \ alpha = (\ alpha _ {1}, \ alpha _ {2}, \ ldots)}$ $P.$ $\ alpha_i$ $ich$ $P.$

{\ displaystyle A \ longmapsto P}

ist eine Bijektion zwischen symmetrischen Matrizen, die zufriedenstellen, und halbstandardmäßigen Young-Gewichtsarrays . Hier ist der Vektor, dessen -te Komponente die Summe der Elemente der -ten Zeile von ist . ${\ displaystyle {\ text {row}} (A) = \ alpha}$ $\Alpha$ ${\ displaystyle {\ text {row}} (A)}$ $ich$ $ich$ $BEIM$

Beispiel

Lassen Sie die symmetrische Matrix sein: $BEIM$

{\ displaystyle A = {\ begin {pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \ end {pmatrix}}}

Eine Berechnung zeigt das

{\ displaystyle P = {\ begin {matrix} 1 & 1 & 1 & 2 \\ 2 & 3 & 3 \\ 3 \ end {matrix}}}

Das Gewicht von ist und der Vektor der Summen von Reihen von ist . $P.$ ${\ displaystyle \ alpha = (3,2,3)}$ $BEIM$ ${\ displaystyle {\ text {row}} (A) = (3,2,3)}$

Anwendungen der RSK-Korrespondenz

Identität von Cauchy

Lass und sei Variablen. Die Identität, die auf Cauchy zurückgeht, ist: ${\ displaystyle x_ {1}, x_ {2}, \ ldots}$ ${\ displaystyle y_ {1}, y_ {2}, \ ldots}$

{\ displaystyle \ prod _ {i, j} (1-x_ {i} y_ {j}) ^ {- 1} = \ sum _ {\ lambda} s _ {\ lambda} (x) s _ {\ lambda } (y)}

wo sind die Schur-Polynome . Die am besten geeignete Definition von Schur-Polynomen ist hier ${\ displaystyle s _ {\ lambda}}$

{\ 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}}}

wobei die Summierung über allen semi-standardmäßigen Young-Arrays der Form liegt und die Exponenten das Gewicht von angeben , mit anderen Worten, die Anzahl der Vorkommen von in zählen . $\ lambda$ ${\ displaystyle t_ {1}, \ ldots, t_ {n}}$ $T.$ $t_i$ $ich$ $T.$

Kostka Zahlen

Sei und sei zwei Partitionen der ganzen Zahl . Hier und werden als , das heißt als ein Vektor von nicht notwendigerweise abnehmenden ganzen Zahlen gesehen, deren Summe ist . So $\ mu$ $\nackt$ $nicht$ $\ mu$ $\nackt$ ${\ displaystyle weight}$ $nicht$

{\ displaystyle \ sum _ {\ lambda \ in {\ mathcal {P}} _ {n}} K _ {\ lambda \ mu} K _ {\ lambda \ nu} = N _ {\ mu \ nu}}

wo und bezeichnen die Kostka-Zahlen und ist die Anzahl der Matrizen mit natürlichen ganzzahligen Koeffizienten, mit und . Hier ist der Vektor, dessen -te Koordinate die Summe der Elemente der -ten Spalte von ist . ${\ displaystyle K _ {\ lambda \ mu}}$ ${\ displaystyle K _ {\ lambda \ nu}}$ ${\ displaystyle N _ {\ mu \ nu}}$ $BEIM$ ${\ displaystyle {\ text {row}} (A) = \ mu}$ ${\ displaystyle {\ text {column}} (A) = \ nu}$ ${\ displaystyle {\ text {column}} (A)}$ $j$ $j$ $BEIM$

Anmerkungen und Referenzen

(fr) Dieser Artikel stammt teilweise oder vollständig aus dem englischen Wikipedia- Artikel „ Robinson-Schensted-Knuth-Korrespondenz “ ( siehe Autorenliste ) .

Anmerkungen

( Lascoux, Leclerc und Thibon 2002 )
( Stanley, 1999 , S. 316-380)
( Knuth 1970 )
( Knuth 2005 ), Abschnitt 5.1.4, Seiten 47-72

Literaturverzeichnis

(en) Alain Lascoux , Bernard Leclerc und Jean-Yves Thibon , „Das plaktische Monoid“ , in M. Lothaire , Algebraische Kombinatorik der Wörter , CUP , Slg. "Encyclopedia of Mathematics and its Applications" ( n o 90)2002( ISBN 978-0-521-81220-7 , online lesen ) , p. 164-196
(in) William Fulton , Junge Tableaus , CUP, Slg. "London Mathematical Society Schülertexte" ( n o 35)1997( ISBN 978-0-521-56144-0 und 978-0-521-56724-4 , Math Reviews 1464693 )
(in) Donald E. Knuth , " Permutationen, Matrizen und verallgemeinerte junge Tableaus " , Pacific Journal of Mathematics , vol. 34,1970, p. 709–727 ( ISSN 0030-8730 , Math Reviews 0272654 , online lesen )
(en) Donald E. Knuth , Die Kunst der Computerprogrammierung , vol. 3: Sortieren und Suchen, 2. Auflage , Addison-Wesley,2005( ISBN 0-201-89685-0 , Online-Präsentation )
(en) Bruce E. Sagan (en) , Die symmetrische Gruppe: Darstellungen, kombinatorische Algorithmen und symmetrische Funktionen , Springer, Slg. " Graduate Texts in Mathematics " ( n o 203)2001, 2 nd ed. 240 p. ( ISBN 978-0-387-95067-9 , online lesen )
(en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ Detail der Ausgaben ] ( Online-Präsentation )

Externer Link

(en) Bruce E. Sagan , „Schur-Funktionen in der algebraischen Kombinatorik“ , in Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN 978-1556080104 , online lesen )