www.wikidata.de-de.nina.az

Alternierende Permutation Eine alternierende Permutation auch Zickzack Permutation genannt ist in der Kombinatorik eine

Alternierende Permutation

Eine alternierende Permutation (auch Zickzack-Permutation genannt) ist in der Kombinatorik eine Permutation der ersten natürlichen Zahlen, bei der keine Zahl der Größe nach zwischen der vorangehenden und der nachfolgenden Zahl steht. Beginnt die Folge mit einem Anstieg, so spricht man von einer Up-Down-Permutation, beginnt sie mit einem Abstieg von einer Down-Up-Permutation. Alternierende Permutationen weisen eine Reihe von Spiegelsymmetrien auf. Jede alternierende Permutation ungerader Länge entspricht einem vollen partiell geordneten Binärbaum und jede alternierende Permutation gerader Länge einem fast vollen solchen Baum. Die Anzahlen der alternierenden Permutationen fester Länge treten als Koeffizienten in der Maclaurin-Reihe der Sekans- und der Tangensfunktion auf und stehen in engem Zusammenhang mit den Euler- und den Bernoulli-Zahlen.

Grafische Darstellung aller Up-Down-Permutationen der Länge fünf, angefangen mit der Permutation (1,3,2,5,4) (oben links) und endend mit der Permutation (4,5,2,3,1) (unten rechts).

Definition Bearbeiten

Illustration einer Up-Down-Permutation der Zahlen von 1 bis 7

Ist die symmetrische Gruppe aller Permutationen der Menge , dann heißt eine Permutation alternierend, wenn in ihrer Tupeldarstellung

die Zahlen immer abwechselnd größer und kleiner als die jeweils vorangegangene Zahl sind. Es muss also für entweder

oder

gelten. Beginnt die Folge der Zahlen mit einem Anstieg, ist also , so spricht man von einer Up-Down-Permutation, beginnt sie mit einem Abstieg, gilt also , von einer Down-Up-Permutation. Allgemeiner können auch alternierende Permutationen geordneter endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten natürlichen Zahlen beschränken.

Beispiele Bearbeiten

Up-Down-Permutationen Down-Up-Permutationen Anzahl
2 (1,2) (2,1) 2
3 (1,3,2), (2,3,1) (2,1,3), (3,1,2) 4
4 (1,3,2,4), (1,4,2,3),
(2,3,1,4),
(2,4,1,3),
(3,4,1,2)		 (2,1,4,3),
(3,1,4,2),
(3,2,4,1),
(4,1,3,2),
(4,2,3,1)		 10

Die Permutation

ist eine Up-Down-Permutation, denn es gilt . Die Permutation

ist hingegen eine Down-Up-Permutation, da gilt. Die Permutation

ist keine alternierende Permutation, denn sie enthält mit zwei aufeinander folgende Anstiege.

Die nebenstehende Tabelle führt alle alternierenden Permutationen der symmetrischen Gruppen vom Grad zwei bis vier auf.

Symmetrien Bearbeiten

An- und Abstiege Bearbeiten

Bei einer alternierenden Permutation wechseln sich Anstiege mit Abstiegen ab. Bei einer Up-Down-Permutation gilt für ungerade und für gerade , bei Down-Up-Permutationen entsprechend umgekehrt. Eine alternierende Permutation gerader Länge weist demnach ebenso viele An- wie Abstiege auf. Eine Up-Down-Permutation ungerader Länge hat einen Anstieg mehr als Abstiege, eine Down-Up-Permutation ungerader Länge einen Abstieg mehr als Anstiege. Weiterhin weisen alternierende Permutationen die folgenden beiden Arten von Spiegelsymmetrien auf.

Horizontale Symmetrie Bearbeiten

Horizontale (oben) und vertikale (unten) Spiegelsymmetrien zwischen Up-Down-Permutationen (blau) und Down-Up-Permutationen (rot) jeweils ungerader und gerader Länge

Liest man eine Permutation von rechts nach links, erhält man die entsprechende reverse Permutation. Die Reverse einer Up-Down-Permutation ist wieder eine Up-Down-Permutation, falls ungerade ist und eine Down-Up-Permutation, falls gerade ist. Analog dazu ist die Reverse einer Down-Up-Permutation wieder eine Down-Up-Permutation, wenn ungerade ist, und eine Up-Down-Permutation, wenn gerade ist. Die Abbildung

stellt also eine Involution der Menge der Up-Down- bzw. der Down-Up-Permutationen dar, falls ungerade ist und eine Bijektion zwischen den beiden Mengen, falls gerade ist.

Vertikale Symmetrie Bearbeiten

Ersetzt man in einer Permutation für jede Zahl durch die Zahl , erhält man die entsprechende komplementäre Permutation. Das Komplement einer Up-Down-Permutation ist stets eine Down-Up-Permutation und umgekehrt. Die Abbildung

stellt damit für jedes eine Bijektion zwischen der Menge der Up-Down-Permutationen und der Menge der Down-Up-Permutationen dar.

Anzahl Bearbeiten

Rekursive Darstellung Bearbeiten

Anzahl der Down-Up-Permutationen von n Zahlen, die mit der Zahl k beginnen
1 2 3 4 5 6 7 Summe
2 0 1 1
3 0 1 1 2
4 0 1 2 2 5
5 0 2 4 5 5 16
6 0 5 10 14 16 16 61
7 0 16 32 46 56 61 61 272
Anzahl der Up-Down-Permutationen von n Zahlen, die mit der Zahl k beginnen
1 2 3 4 5 6 7 Summe
2 1 0 1
3 1 1 0 2
4 2 2 1 0 5
5 5 5 4 2 0 16
6 16 16 14 10 5 0 61
7 61 61 56 46 32 16 0 272

Aufgrund der vorstehenden Symmetrie gibt es ebenso viele Up-Down- wie Down-Up-Permutationen. Nachdem diese beiden Mengen für disjunkt sind, kann man sich bei der Zählung auf einen der beiden Typen beschränken. Bezeichnet nun die Anzahl der Down-Up-Permutationen der Länge , sowie die Anzahl der Down-Up-Permutationen der Länge , die mit der Zahl beginnen, dann gilt

Die Zahlen werden für ungerades auch (positive) Eulersche Zahlen genannt, die Zahlen heißen auch Entringer-Zahlen (Folge A008282 in OEIS). Man erhält jede der Down-Up-Permutationen der Länge und Startzahl , indem man bei einer Up-Down-Permutation der Länge , die höchstens mit der Zahl beginnt, alle Zahlen von bis um eins erhöht und die Zahl vorne anfügt. Nachdem jede Up-Down-Permutation durch vertikale Spiegelung einer Down-Up-Permutation entsteht, erhält man so für die Anzahl mit und die Rekurrenz

wobei und für alle gesetzt wird. Diese Rekurrenz lässt sich zu

vereinfachen. Entsprechend gespiegelte Rekurrenzen lassen sich auch für die Anzahl der Up-Down-Permutationen, die mit der Zahl beginnen, herleiten (Folge A010094 in OEIS).

Explizite Darstellung Bearbeiten

Durch Auflösung der Rekurrenzen erreicht man nun für die Anzahl der Up-Down- oder Down-Up-Permutationen ungerader Länge die explizite Summendarstellung

und für die Anzahl der Up-Down- oder Down-Up-Permutationen gerader Länge die entsprechende Darstellung

Insgesamt erhält man so für die Anzahl der Up-Down- oder Down-Up-Permutationen die Folge

und für die Gesamtzahl der alternierenden Permutationen der Länge die Folge

Korrespondenz zu Binärbäumen Bearbeiten

Umwandlung einer Up-Down-Permutation in einen vollen, partiell geordneten Binärbaum

Im Folgenden werden Binärbäume betrachtet, deren Knoten mit den ersten natürlichen Zahlen bezeichnet sind. Ein Binärbaum heißt voll, wenn jeder Knoten entweder zwei oder keine Kindknoten hat. In einem partiell geordneten Binärbaum sind alle Knoten derart markiert, dass die Zahl eines Vaterknotens immer größer, als die Zahlen der Kindknoten sind. Jede Up-Down-Permutation ungerader Länge entspricht nun einem vollen, partiell geordneten Binärbaum mit Knoten. Um diese Korrespondenz zu konstruieren, wählt man die größte Zahl als Wurzelknoten des Baums aus und betrachtet die Teilpermutationen

links und rechts dieser Zahl. Die beiden Teilpermutationen sind nun wieder Up-Down-Permutationen jeweils einer Teilmenge der Zahlen . Von diesen Teilpermutationen kann nun wieder jeweils das größte Element ausgewählt werden und auf diese Weise rekursiv ein voller, partiell geordneter Binärbaum aufgebaut werden (siehe Abbildung). Die rekursive Struktur der Binärbäume kann man sich nun zunutze machen, um weitere Rekurrenzen herzuleiten. Der Wurzelknoten muss einen geraden Index aufweisen, sodass der linke Teilbaum Knoten und der rechte Teilbaum Knoten besitzt. Es gibt nun genau Möglichkeiten, die Zahlen des linken Teilbaums auszuwählen, wodurch die übrigen Zahlen im rechten Teilbaum stehen müssen. Setzt man , so folgt daraus für die Anzahl der Up-Down-Permutationen ungerader Länge die Rekurrenz

mit Startwert . Jede Up-Down-Permutation gerader Länge entspricht einem fast vollen, partiell geordneten Binärbaum mit Knoten, bei dem nur das am weitesten rechts stehende Blatt des Baums fehlt. Für die Anzahl der Up-Down-Permutationen gerader Länge erhält man die entsprechende Rekurrenz

mit Startwert . Analog zu diesen beiden Fällen entspricht jede Down-Up-Permutation einem bezüglich der umgedrehten Ordnung partiell geordneten Binärbaum, der bei ungerader Länge voll und bei gerader Länge fast voll ist. Aufgrund der Spiegelsymmetrie erhält man so für die Gesamtzahl der alternierenden Permutationen der Länge die Rekurrenz

und nach Setzen von die diskrete Faltung

Erzeugende Funktionen Bearbeiten

Differentialgleichung Bearbeiten

Die exponentiell erzeugende Funktion der Folge

erfüllt die gewöhnliche Differentialgleichung

mit der Anfangsbedingung , wie durch Einsetzen der obigen Rekurrenz nachgerechnet werden kann. Durch Separation der Variablen erhält man die Lösung dieses Anfangswertproblems als

Dieses klassische Resultat der analytischen Kombinatorik aus dem Jahr 1881 geht auf den französischen Mathematiker Désiré André zurück.

Maclaurin-Reihen Bearbeiten

Die Zahlen werden für gerades auch Sekantenzahlen genannt und treten in der Maclaurin-Reihe der Sekansfunktion

auf, während die Zahlen für ungerades auch Tangentenzahlen genannt werden und in der Reihenentwicklung der Tangensfunktion

vorkommen. Die Zahlen stehen dabei in enger Verwandtschaft zu den Bernoulli-Zahlen .

Asymptotik Bearbeiten

Für den Anteil der alternierenden Permutationen in der Menge aller Permutationen gilt für asymptotisch

Dieser Anteil entspricht der Wahrscheinlichkeit, dass eine (gleichverteilt) zufällige Permutation der Länge alternierend ist.

Literatur Bearbeiten

  • Folkmar Bornemann: Konkrete Analysis: für Studierende der Informatik. Springer, 2008, ISBN 978-3-540-70854-4.
  • Vladimir A. Dobrushkin: Methods in Algorithmic Analysis. CRC Press, 2011, ISBN 978-1-4200-6830-6 (englisch).
  • Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, ISBN 978-0-511-80165-5, doi:10.1017/CBO9780511801655 (englisch).
  • Richard P. Stanley: A Survey of Alternating Permutations. 2009, arxiv:0912.4240 (englisch).
  • Richard P. Stanley: Enumerative Combinatorics. Cambridge University Press, 2011, ISBN 978-1-107-01542-5 (englisch).

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Stanley: Enumerative Combinatorics. 2011, S. 32.
  2. Dobrushkin: Methods in Algorithmic Analysis. 2011, S. 430–431.
  3. Louis Comtet: Advanced Combinatorics. Reidel, Dordrecht 1974, ISBN 90-277-0380-9, S. 259.
  4. Bornemann: Konkrete Analysis: für Studierende der Informatik. 2008, S. 139.
  5. ↑ Bornemann: Konkrete Analysis: für Studierende der Informatik. 2008, S. 140.
  6. ↑ Stanley: Enumerative Combinatorics. 2011, S. 47.
  7. Flajolet, Sedgewick: Analytic Combinatorics. 2009, S. 2.
  8. ↑ Bornemann: Konkrete Analysis: für Studierende der Informatik. 2008, S. 141–142.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine alternierende Permutation auch Zickzack Permutation genannt ist in der Kombinatorik eine Permutation der ersten n displaystyle n naturlichen Zahlen bei der keine Zahl der Grosse nach zwischen der vorangehenden und der nachfolgenden Zahl steht Beginnt die Folge mit einem Anstieg so spricht man von einer Up Down Permutation beginnt sie mit einem Abstieg von einer Down Up Permutation Alternierende Permutationen weisen eine Reihe von Spiegelsymmetrien auf Jede alternierende Permutation ungerader Lange entspricht einem vollen partiell geordneten Binarbaum und jede alternierende Permutation gerader Lange einem fast vollen solchen Baum Die Anzahlen der alternierenden Permutationen fester Lange treten als Koeffizienten in der Maclaurin Reihe der Sekans und der Tangensfunktion auf und stehen in engem Zusammenhang mit den Euler und den Bernoulli Zahlen Grafische Darstellung aller Up Down Permutationen der Lange funf angefangen mit der Permutation 1 3 2 5 4 oben links und endend mit der Permutation 4 5 2 3 1 unten rechts Inhaltsverzeichnis 1 Definition 2 Beispiele 3 Symmetrien 3 1 An und Abstiege 3 2 Horizontale Symmetrie 3 3 Vertikale Symmetrie 4 Anzahl 4 1 Rekursive Darstellung 4 2 Explizite Darstellung 5 Korrespondenz zu Binarbaumen 6 Erzeugende Funktionen 6 1 Differentialgleichung 6 2 Maclaurin Reihen 6 3 Asymptotik 7 Literatur 8 Weblinks 9 EinzelnachweiseDefinition Bearbeiten6 7 4 5 3 1 2 displaystyle begin array ccccccccccccccccccc amp amp 6 amp amp amp amp 7 amp amp amp amp 4 amp amp amp amp amp diagup amp amp diagdown amp amp diagup amp amp diagdown amp amp diagup amp amp diagdown amp amp amp 5 amp amp amp amp 3 amp amp amp amp 1 amp amp amp amp 2 end array nbsp Illustration einer Up Down Permutation der Zahlen von 1 bis 7 Ist S n displaystyle S n nbsp die symmetrische Gruppe aller Permutationen der Menge 1 n displaystyle 1 ldots n nbsp dann heisst eine Permutation p S n displaystyle pi in S n nbsp alternierend wenn in ihrer Tupeldarstellung p p 1 p 2 p n displaystyle pi pi 1 pi 2 ldots pi n nbsp die Zahlen p 2 p n displaystyle pi 2 ldots pi n nbsp immer abwechselnd grosser und kleiner als die jeweils vorangegangene Zahl sind Es muss also fur j 2 n 1 displaystyle j 2 ldots n 1 nbsp entweder p j 1 lt p j gt p j 1 displaystyle pi j 1 lt pi j gt pi j 1 nbsp oder p j 1 gt p j lt p j 1 displaystyle pi j 1 gt pi j lt pi j 1 nbsp gelten Beginnt die Folge der Zahlen mit einem Anstieg ist also p 2 gt p 1 displaystyle pi 2 gt pi 1 nbsp so spricht man von einer Up Down Permutation beginnt sie mit einem Abstieg gilt also p 2 lt p 1 displaystyle pi 2 lt pi 1 nbsp von einer Down Up Permutation 1 2 Allgemeiner konnen auch alternierende Permutationen geordneter endlicher Mengen beispielsweise Alphabete betrachtet werden zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten n displaystyle n nbsp naturlichen Zahlen beschranken Beispiele Bearbeitenn displaystyle n nbsp Up Down Permutationen Down Up Permutationen Anzahl2 1 2 2 1 23 1 3 2 2 3 1 2 1 3 3 1 2 44 1 3 2 4 1 4 2 3 2 3 1 4 2 4 1 3 3 4 1 2 2 1 4 3 3 1 4 2 3 2 4 1 4 1 3 2 4 2 3 1 10Die Permutation p 3 5 2 4 1 6 S 6 displaystyle pi 3 5 2 4 1 6 in S 6 nbsp ist eine Up Down Permutation denn es gilt 3 lt 5 gt 2 lt 4 gt 1 lt 6 displaystyle 3 lt 5 gt 2 lt 4 gt 1 lt 6 nbsp Die Permutation p 5 1 4 2 6 3 S 6 displaystyle pi 5 1 4 2 6 3 in S 6 nbsp ist hingegen eine Down Up Permutation da 5 gt 1 lt 4 gt 2 lt 6 gt 3 displaystyle 5 gt 1 lt 4 gt 2 lt 6 gt 3 nbsp gilt Die Permutation p 4 5 2 3 6 1 S 6 displaystyle pi 4 5 2 3 6 1 in S 6 nbsp ist keine alternierende Permutation denn sie enthalt mit 2 lt 3 lt 6 displaystyle 2 lt 3 lt 6 nbsp zwei aufeinander folgende Anstiege Die nebenstehende Tabelle fuhrt alle alternierenden Permutationen der symmetrischen Gruppen vom Grad zwei bis vier auf Symmetrien BearbeitenAn und Abstiege Bearbeiten Bei einer alternierenden Permutation wechseln sich Anstiege mit Abstiegen ab Bei einer Up Down Permutation gilt p i 1 gt p i displaystyle pi i 1 gt pi i nbsp fur ungerade i displaystyle i nbsp und p i 1 lt p i displaystyle pi i 1 lt pi i nbsp fur gerade i displaystyle i nbsp bei Down Up Permutationen entsprechend umgekehrt Eine alternierende Permutation gerader Lange weist demnach ebenso viele An wie Abstiege auf Eine Up Down Permutation ungerader Lange hat einen Anstieg mehr als Abstiege eine Down Up Permutation ungerader Lange einen Abstieg mehr als Anstiege Weiterhin weisen alternierende Permutationen die folgenden beiden Arten von Spiegelsymmetrien auf Horizontale Symmetrie Bearbeiten nbsp Horizontale oben und vertikale unten Spiegelsymmetrien zwischen Up Down Permutationen blau und Down Up Permutationen rot jeweils ungerader und gerader LangeLiest man eine Permutation von rechts nach links erhalt man die entsprechende reverse Permutation Die Reverse einer Up Down Permutation ist wieder eine Up Down Permutation falls n displaystyle n nbsp ungerade ist und eine Down Up Permutation falls n displaystyle n nbsp gerade ist Analog dazu ist die Reverse einer Down Up Permutation wieder eine Down Up Permutation wenn n displaystyle n nbsp ungerade ist und eine Up Down Permutation wenn n displaystyle n nbsp gerade ist Die Abbildung p 1 p n p n p 1 displaystyle pi 1 ldots pi n mapsto pi n ldots pi 1 nbsp stellt also eine Involution der Menge der Up Down bzw der Down Up Permutationen dar falls n displaystyle n nbsp ungerade ist und eine Bijektion zwischen den beiden Mengen falls n displaystyle n nbsp gerade ist Vertikale Symmetrie Bearbeiten Ersetzt man in einer Permutation fur j 1 n displaystyle j 1 ldots n nbsp jede Zahl p j displaystyle pi j nbsp durch die Zahl n p j 1 displaystyle n pi j 1 nbsp erhalt man die entsprechende komplementare Permutation Das Komplement einer Up Down Permutation ist stets eine Down Up Permutation und umgekehrt Die Abbildung p 1 p n n p 1 1 n p n 1 displaystyle pi 1 ldots pi n mapsto n pi 1 1 ldots n pi n 1 nbsp stellt damit fur jedes n displaystyle n nbsp eine Bijektion zwischen der Menge der Up Down Permutationen und der Menge der Down Up Permutationen dar 1 Anzahl BearbeitenRekursive Darstellung Bearbeiten Anzahl der Down Up Permutationen von n Zahlen die mit der Zahl k beginnen n k displaystyle n diagdown k nbsp 1 2 3 4 5 6 7 Summe2 0 1 13 0 1 1 24 0 1 2 2 55 0 2 4 5 5 166 0 5 10 14 16 16 617 0 16 32 46 56 61 61 272Anzahl der Up Down Permutationen von n Zahlen die mit der Zahl k beginnen n k displaystyle n diagdown k nbsp 1 2 3 4 5 6 7 Summe2 1 0 13 1 1 0 24 2 2 1 0 55 5 5 4 2 0 166 16 16 14 10 5 0 617 61 61 56 46 32 16 0 272Aufgrund der vorstehenden Symmetrie gibt es ebenso viele Up Down wie Down Up Permutationen Nachdem diese beiden Mengen fur n 2 displaystyle n geq 2 nbsp disjunkt sind kann man sich bei der Zahlung auf einen der beiden Typen beschranken Bezeichnet nun A n displaystyle A n nbsp die Anzahl der Down Up Permutationen der Lange n displaystyle n nbsp sowie A n k displaystyle A n k nbsp die Anzahl der Down Up Permutationen der Lange n displaystyle n nbsp die mit der Zahl k displaystyle k nbsp beginnen dann gilt A n k 1 n A n k displaystyle A n sum k 1 n A n k nbsp Die Zahlen A n displaystyle A n nbsp werden fur ungerades n displaystyle n nbsp auch positive Eulersche Zahlen genannt die Zahlen A n k displaystyle A n k nbsp heissen auch Entringer Zahlen Folge A008282 in OEIS Man erhalt jede der Down Up Permutationen der Lange n displaystyle n nbsp und Startzahl k displaystyle k nbsp indem man bei einer Up Down Permutation der Lange n 1 displaystyle n 1 nbsp die hochstens mit der Zahl k 1 displaystyle k 1 nbsp beginnt alle Zahlen von k displaystyle k nbsp bis n 1 displaystyle n 1 nbsp um eins erhoht und die Zahl k displaystyle k nbsp vorne anfugt Nachdem jede Up Down Permutation durch vertikale Spiegelung einer Down Up Permutation entsteht erhalt man so fur die Anzahl A n k displaystyle A n k nbsp mit n 3 displaystyle n geq 3 nbsp und k 2 n displaystyle k 2 ldots n nbsp die Rekurrenz A n k j 1 k 1 A n 1 n j displaystyle A n k sum j 1 k 1 A n 1 n j nbsp wobei A 2 2 1 displaystyle A 2 2 1 nbsp und A n 1 0 displaystyle A n 1 0 nbsp fur alle n displaystyle n nbsp gesetzt wird Diese Rekurrenz lasst sich zu A n k A n k 1 A n 1 n k 1 displaystyle A n k A n k 1 A n 1 n k 1 nbsp vereinfachen Entsprechend gespiegelte Rekurrenzen lassen sich auch fur die Anzahl der Up Down Permutationen die mit der Zahl k displaystyle k nbsp beginnen herleiten Folge A010094 in OEIS Explizite Darstellung Bearbeiten Durch Auflosung der Rekurrenzen erreicht man nun fur die Anzahl der Up Down oder Down Up Permutationen ungerader Lange die explizite Summendarstellung 3 A 2 n 1 j 1 n k j n 1 j n 2 k k j k 1 j 2 n 2 k 1 displaystyle A 2n 1 sum j 1 n sum k j n 1 j n binom 2k k j k 1 frac j 2n 2 k 1 nbsp und fur die Anzahl der Up Down oder Down Up Permutationen gerader Lange die entsprechende Darstellung A 2 n j 1 n k j n 1 j n 2 k k j j 2 n 2 k 1 displaystyle A 2n sum j 1 n sum k j n 1 j n binom 2k k j frac j 2n 2 k 1 nbsp Insgesamt erhalt man so fur die Anzahl der Up Down oder Down Up Permutationen A n displaystyle A n nbsp die Folge 1 1 2 5 16 61 272 1385 7936 displaystyle 1 1 2 5 16 61 272 1385 7936 ldots nbsp Folge A000111 in OEIS und fur die Gesamtzahl 2 A n displaystyle 2A n nbsp der alternierenden Permutationen der Lange n displaystyle n nbsp die Folge 1 2 4 10 32 122 544 2770 15872 displaystyle 1 2 4 10 32 122 544 2770 15872 ldots nbsp Folge A001250 in OEIS Korrespondenz zu Binarbaumen Bearbeiten nbsp Umwandlung einer Up Down Permutation in einen vollen partiell geordneten BinarbaumIm Folgenden werden Binarbaume betrachtet deren Knoten mit den ersten naturlichen Zahlen bezeichnet sind Ein Binarbaum heisst voll wenn jeder Knoten entweder zwei oder keine Kindknoten hat In einem partiell geordneten Binarbaum sind alle Knoten derart markiert dass die Zahl eines Vaterknotens immer grosser als die Zahlen der Kindknoten sind Jede Up Down Permutation ungerader Lange p S 2 n 1 displaystyle pi in S 2n 1 nbsp entspricht nun einem vollen partiell geordneten Binarbaum mit 2 n 1 displaystyle 2n 1 nbsp Knoten 4 Um diese Korrespondenz zu konstruieren wahlt man die grosste Zahl p j 2 n 1 displaystyle pi j 2n 1 nbsp als Wurzelknoten des Baums aus und betrachtet die Teilpermutationen p 1 p j 1 displaystyle pi 1 ldots pi j 1 nbsp und p j 1 p 2 n 1 displaystyle pi j 1 ldots pi 2n 1 nbsp links und rechts dieser Zahl Die beiden Teilpermutationen sind nun wieder Up Down Permutationen jeweils einer Teilmenge der Zahlen 1 2 n displaystyle 1 ldots 2n nbsp Von diesen Teilpermutationen kann nun wieder jeweils das grosste Element ausgewahlt werden und auf diese Weise rekursiv ein voller partiell geordneter Binarbaum aufgebaut werden siehe Abbildung Die rekursive Struktur der Binarbaume kann man sich nun zunutze machen um weitere Rekurrenzen herzuleiten Der Wurzelknoten muss einen geraden Index j 2 4 2 n displaystyle j in 2 4 ldots 2n nbsp aufweisen sodass der linke Teilbaum j 1 displaystyle j 1 nbsp Knoten und der rechte Teilbaum 2 n j 1 displaystyle 2n j 1 nbsp Knoten besitzt Es gibt nun genau 2 n j 1 displaystyle tbinom 2n j 1 nbsp Moglichkeiten die Zahlen des linken Teilbaums auszuwahlen wodurch die ubrigen Zahlen im rechten Teilbaum stehen mussen Setzt man i j 2 displaystyle i j 2 nbsp so folgt daraus fur die Anzahl der Up Down Permutationen ungerader Lange die Rekurrenz 5 A 2 n 1 i 1 n 2 n 2 i 1 A 2 i 1 A 2 n 2 i 1 displaystyle A 2n 1 sum i 1 n binom 2n 2i 1 A 2i 1 A 2n 2i 1 nbsp mit Startwert A 1 1 displaystyle A 1 1 nbsp Jede Up Down Permutation gerader Lange p S 2 n displaystyle pi in S 2n nbsp entspricht einem fast vollen partiell geordneten Binarbaum mit 2 n displaystyle 2n nbsp Knoten bei dem nur das am weitesten rechts stehende Blatt des Baums fehlt Fur die Anzahl der Up Down Permutationen gerader Lange erhalt man die entsprechende Rekurrenz A 2 n i 1 n 2 n 1 2 i 1 A 2 i 1 A 2 n 2 i displaystyle A 2n sum i 1 n binom 2n 1 2i 1 A 2i 1 A 2n 2i nbsp mit Startwert A 0 1 displaystyle A 0 1 nbsp Analog zu diesen beiden Fallen entspricht jede Down Up Permutation einem bezuglich der umgedrehten Ordnung partiell geordneten Binarbaum der bei ungerader Lange voll und bei gerader Lange fast voll ist Aufgrund der Spiegelsymmetrie erhalt man so fur die Gesamtzahl der alternierenden Permutationen der Lange n displaystyle n nbsp die Rekurrenz 6 2 A n 1 i 0 n n i A i A n i displaystyle 2A n 1 sum i 0 n binom n i A i A n i nbsp und nach Setzen von a i A i i displaystyle a i A i i nbsp die diskrete Faltung 5 2 a n 1 1 n 1 i 0 n a i a n i displaystyle 2a n 1 frac 1 n 1 sum i 0 n a i a n i nbsp Erzeugende Funktionen BearbeitenDifferentialgleichung Bearbeiten Die exponentiell erzeugende Funktion der Folge A n displaystyle A n nbsp f x n 0 A n x n n n 0 a n x n displaystyle f x sum n 0 infty A n frac x n n sum n 0 infty a n x n nbsp erfullt die gewohnliche Differentialgleichung 2 f x 1 f x 2 displaystyle 2f x 1 f x 2 nbsp mit der Anfangsbedingung f 0 1 displaystyle f 0 1 nbsp wie durch Einsetzen der obigen Rekurrenz nachgerechnet werden kann Durch Separation der Variablen erhalt man die Losung dieses Anfangswertproblems als f x sec x tan x tan x 2 p 4 displaystyle f x sec x tan x tan left frac x 2 frac pi 4 right nbsp Dieses klassische Resultat der analytischen Kombinatorik aus dem Jahr 1881 geht auf den franzosischen Mathematiker Desire Andre zuruck 7 Maclaurin Reihen Bearbeiten Die Zahlen A n displaystyle A n nbsp werden fur gerades n displaystyle n nbsp auch Sekantenzahlen genannt und treten in der Maclaurin Reihe der Sekansfunktion sec x A 0 A 2 x 2 2 A 4 x 4 4 displaystyle sec x A 0 A 2 frac x 2 2 A 4 frac x 4 4 ldots nbsp auf wahrend die Zahlen fur ungerades n displaystyle n nbsp auch Tangentenzahlen genannt werden und in der Reihenentwicklung der Tangensfunktion tan x A 1 x A 3 x 3 3 A 5 x 5 5 displaystyle tan x A 1 x A 3 frac x 3 3 A 5 frac x 5 5 ldots nbsp vorkommen 6 Die Zahlen A n displaystyle A n nbsp stehen dabei in enger Verwandtschaft zu den Bernoulli Zahlen B n displaystyle B n nbsp 8 Asymptotik Bearbeiten Fur den Anteil der alternierenden Permutationen in der Menge aller Permutationen gilt fur n displaystyle n to infty nbsp asymptotisch A n n 2 2 p n 1 displaystyle frac A n n simeq 2 left frac 2 pi right n 1 nbsp Dieser Anteil entspricht der Wahrscheinlichkeit dass eine gleichverteilt zufallige Permutation der Lange n displaystyle n nbsp alternierend ist 8 Literatur BearbeitenFolkmar Bornemann Konkrete Analysis fur Studierende der Informatik Springer 2008 ISBN 978 3 540 70854 4 Vladimir A Dobrushkin Methods in Algorithmic Analysis CRC Press 2011 ISBN 978 1 4200 6830 6 englisch Philippe Flajolet Robert Sedgewick Analytic Combinatorics Cambridge University Press 2009 ISBN 978 0 511 80165 5 doi 10 1017 CBO9780511801655 englisch Richard P Stanley A Survey of Alternating Permutations 2009 arxiv 0912 4240 englisch Richard P Stanley Enumerative Combinatorics Cambridge University Press 2011 ISBN 978 1 107 01542 5 englisch Weblinks BearbeitenEric W Weisstein Alternating Permutation In MathWorld englisch Eric W Weisstein Euler Zigzag Number In MathWorld englisch Eric W Weisstein Entringer Number In MathWorld englisch Einzelnachweise Bearbeiten a b Stanley Enumerative Combinatorics 2011 S 32 Dobrushkin Methods in Algorithmic Analysis 2011 S 430 431 Louis Comtet Advanced Combinatorics Reidel Dordrecht 1974 ISBN 90 277 0380 9 S 259 Bornemann Konkrete Analysis fur Studierende der Informatik 2008 S 139 a b Bornemann Konkrete Analysis fur Studierende der Informatik 2008 S 140 a b Stanley Enumerative Combinatorics 2011 S 47 Flajolet Sedgewick Analytic Combinatorics 2009 S 2 a b Bornemann Konkrete Analysis fur Studierende der Informatik 2008 S 141 142 Abgerufen von https de wikipedia org w index php title Alternierende Permutation amp oldid 228466920