Satz von Baik-Deift-Johansson
mathematisches Resultat aus der Kombinatorik / aus Wikipedia, der freien encyclopedia
Der Satz von Baik-Deift-Johansson ist ein mathematisches Resultat aus der Kombinatorik. Er beschäftigt sich mit den Teilfolgen einer zufällig gezogenen Permutation aus der Menge . Zufällig heißt, alle Permutationen besitzen dieselbe Wahrscheinlichkeit gezogen zu werden. Das Theorem macht eine Aussage über die Verteilung der Länge der längsten, aufsteigenden Teilfolge im Grenzwert.
Angenommen, man zieht aus der Menge die Permutation , dann sind die längsten, aufsteigenden Teilfolgen und . Sei die Länge von und die Länge der längsten, aufsteigenden Teilfolge. Betrachtet man allgemein , dann charakterisiert das Baik-Deift-Johansson-Theorem die Verteilung von wenn nach Unendlich strebt.[1]
Das Theorem wurde von Jinho Baik, Percy Deift und Kurt Johansson gezeigt.