Alternierende Permutation

Eine alternierende Permutation (auch Zickzack-Permutation genannt) ist in der Kombinatorik eine Permutation der ersten ${\displaystyle n}$ 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

${\displaystyle {\begin{array}{ccccccccccccccccccc}&&\!\!6\!\!&&&&\!\!7\!\!&&&&\!\!4\!\!&&&&\!\!\\&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!&\\\!\!5\!\!&&&&\!\!3\!\!&&&&\!\!1\!\!&&&&\!\!2\!\!\end{array}}}$ Illustration einer Up-Down-Permutation der Zahlen von 1 bis 7

Ist ${\displaystyle S_{n}}$ die symmetrische Gruppe aller Permutationen der Menge ${\displaystyle \{1,\ldots ,n\}}$, dann heißt eine Permutation ${\displaystyle \pi \in S_{n}}$ alternierend, wenn in ihrer Tupeldarstellung

${\displaystyle \pi =(\pi (1),\pi (2),\ldots ,\pi (n))}$

die Zahlen ${\displaystyle \pi (2),\ldots ,\pi (n)}$ immer abwechselnd größer und kleiner als die jeweils vorangegangene Zahl sind. Es muss also für ${\displaystyle j=2,\ldots ,n-1}$ entweder

${\displaystyle \pi (j-1)<\pi (j)>\pi (j+1)}$

oder

${\displaystyle \pi (j-1)>\pi (j)<\pi (j+1)}$

gelten. Beginnt die Folge der Zahlen mit einem Anstieg, ist also ${\displaystyle \pi (2)>\pi (1)}$, so spricht man von einer Up-Down-Permutation, beginnt sie mit einem Abstieg, gilt also ${\displaystyle \pi (2)<\pi (1)}$, von einer Down-Up-Permutation.[1][2] 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 ${\displaystyle n}$ natürlichen Zahlen beschränken.

Beispiele

${\displaystyle n}$	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

${\displaystyle \pi =(3,5,2,4,1,6)\in S_{6}}$

ist eine Up-Down-Permutation, denn es gilt ${\displaystyle 3<5>2<4>1<6}$. Die Permutation

${\displaystyle \pi =(5,1,4,2,6,3)\in S_{6}}$

ist hingegen eine Down-Up-Permutation, da ${\displaystyle 5>1<4>2<6>3}$ gilt. Die Permutation

${\displaystyle \pi =(4,5,2,3,6,1)\in S_{6}}$

ist keine alternierende Permutation, denn sie enthält mit ${\displaystyle 2<3<6}$ zwei aufeinander folgende Anstiege.

Die nebenstehende Tabelle führt a​lle alternierenden Permutationen d​er symmetrischen Gruppen v​om Grad z​wei bis v​ier auf.

Symmetrien

An- und Abstiege

Bei einer alternierenden Permutation wechseln sich Anstiege mit Abstiegen ab. Bei einer Up-Down-Permutation gilt ${\displaystyle \pi (i+1)>\pi (i)}$ für ungerade ${\displaystyle i}$ und ${\displaystyle \pi (i+1)<\pi (i)}$ für gerade ${\displaystyle i}$, 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

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 ${\displaystyle n}$ ungerade ist und eine Down-Up-Permutation, falls ${\displaystyle n}$ gerade ist. Analog dazu ist die Reverse einer Down-Up-Permutation wieder eine Down-Up-Permutation, wenn ${\displaystyle n}$ ungerade ist, und eine Up-Down-Permutation, wenn ${\displaystyle n}$ gerade ist. Die Abbildung

${\displaystyle (\pi (1),\ldots ,\pi (n))\mapsto (\pi (n),\ldots ,\pi (1))}$

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

Vertikale Symmetrie

Ersetzt man in einer Permutation für ${\displaystyle j=1,\ldots ,n}$ jede Zahl ${\displaystyle \pi (j)}$ durch die Zahl ${\displaystyle n-\pi (j)+1}$, erhält man die entsprechende komplementäre Permutation. Das Komplement einer Up-Down-Permutation ist stets eine Down-Up-Permutation und umgekehrt. Die Abbildung

${\displaystyle (\pi (1),\ldots ,\pi (n))\mapsto (n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$

stellt damit für jedes ${\displaystyle n}$ eine Bijektion zwischen der Menge der Up-Down-Permutationen und der Menge der Down-Up-Permutationen dar.[1]

Anzahl

Rekursive Darstellung

Anzahl der Down-Up-Permutationen von n Zahlen, die mit der Zahl k beginnen

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	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

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	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 ${\displaystyle n\geq 2}$ disjunkt sind, kann man sich bei der Zählung auf einen der beiden Typen beschränken. Bezeichnet nun ${\displaystyle A_{n}}$ die Anzahl der Down-Up-Permutationen der Länge ${\displaystyle n}$, sowie ${\displaystyle A_{n,k}}$ die Anzahl der Down-Up-Permutationen der Länge ${\displaystyle n}$, die mit der Zahl ${\displaystyle k}$ beginnen, dann gilt

${\displaystyle A_{n}=\sum _{k=1}^{n}A_{n,k}}$.

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

${\displaystyle A_{n,k}=\sum _{j=1}^{k-1}A_{n-1,n-j}}$,

wobei ${\displaystyle A_{2,2}=1}$ und ${\displaystyle A_{n,1}=0}$ für alle ${\displaystyle n}$ gesetzt wird. Diese Rekurrenz lässt sich zu

${\displaystyle A_{n,k}=A_{n,k-1}+A_{n-1,n-k+1}}$

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

Explizite Darstellung

Durch Auflösung d​er Rekurrenzen erreicht m​an nun für d​ie Anzahl d​er Up-Down- o​der Down-Up-Permutationen ungerader Länge d​ie explizite Summendarstellung[3]

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

und für d​ie Anzahl d​er Up-Down- o​der Down-Up-Permutationen gerader Länge d​ie entsprechende Darstellung

${\displaystyle A_{2n}=\sum _{j=1}^{n}\sum _{k=j}^{n}(-1)^{j+n}{\binom {2k}{k-j}}{\frac {j^{2n}}{2^{k-1}}}}$.

Insgesamt erhält man so für die Anzahl der Up-Down- oder Down-Up-Permutationen ${\displaystyle A_{n}}$ die Folge

${\displaystyle 1,1,2,5,16,61,272,1385,7936,\ldots }$   (Folge A000111 in OEIS)

und für die Gesamtzahl ${\displaystyle 2A_{n}}$ der alternierenden Permutationen der Länge ${\displaystyle n}$ die Folge

${\displaystyle 1,2,4,10,32,122,544,2770,15872,\ldots }$   (Folge A001250 in OEIS).

Korrespondenz zu Binärbäumen

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 ${\displaystyle \pi \in S_{2n+1}}$ entspricht nun einem vollen, partiell geordneten Binärbaum mit ${\displaystyle 2n+1}$ Knoten.[4] Um diese Korrespondenz zu konstruieren, wählt man die größte Zahl ${\displaystyle \pi (j)=2n+1}$ als Wurzelknoten des Baums aus und betrachtet die Teilpermutationen

${\displaystyle (\pi (1),\ldots ,\pi (j-1))}$   und   ${\displaystyle (\pi (j+1),\ldots ,\pi (2n+1))}$

links und rechts dieser Zahl. Die beiden Teilpermutationen sind nun wieder Up-Down-Permutationen jeweils einer Teilmenge der Zahlen ${\displaystyle \{1,\ldots ,2n\}}$. 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 ${\displaystyle j\in \{2,4,\ldots ,2n\}}$ aufweisen, sodass der linke Teilbaum ${\displaystyle j-1}$ Knoten und der rechte Teilbaum ${\displaystyle 2n-j+1}$ Knoten besitzt. Es gibt nun genau ${\displaystyle {\tbinom {2n}{j-1}}}$ Möglichkeiten, die Zahlen des linken Teilbaums auszuwählen, wodurch die übrigen Zahlen im rechten Teilbaum stehen müssen. Setzt man ${\displaystyle i=j/2}$, so folgt daraus für die Anzahl der Up-Down-Permutationen ungerader Länge die Rekurrenz[5]

${\displaystyle A_{2n+1}=\sum _{i=1}^{n}{\binom {2n}{2i-1}}A_{2i-1}A_{2n-2i+1}}$

mit Startwert ${\displaystyle A_{1}=1}$. Jede Up-Down-Permutation gerader Länge ${\displaystyle \pi \in S_{2n}}$ entspricht einem fast vollen, partiell geordneten Binärbaum mit ${\displaystyle 2n}$ 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

${\displaystyle A_{2n}=\sum _{i=1}^{n}{\binom {2n-1}{2i-1}}A_{2i-1}A_{2n-2i}}$

mit Startwert ${\displaystyle A_{0}=1}$. 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 ${\displaystyle n}$ die Rekurrenz[6]

${\displaystyle 2A_{n+1}=\sum _{i=0}^{n}{\binom {n}{i}}A_{i}A_{n-i}}$

und nach Setzen von ${\displaystyle a_{i}=A_{i}/i!}$ die diskrete Faltung[5]

${\displaystyle 2a_{n+1}={\frac {1}{n+1}}\sum _{i=0}^{n}a_{i}a_{n-i}}$.

Erzeugende Funktionen

Differentialgleichung

Die exponentiell erzeugende Funktion der Folge ${\displaystyle A_{n}}$

${\displaystyle f(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}=\sum _{n=0}^{\infty }a_{n}x^{n}}$

erfüllt d​ie gewöhnliche Differentialgleichung

${\displaystyle 2f'(x)=1+(f(x))^{2}}$

mit der Anfangsbedingung ${\displaystyle f(0)=1}$, wie durch Einsetzen der obigen Rekurrenz nachgerechnet werden kann. Durch Separation der Variablen erhält man die Lösung dieses Anfangswertproblems als

${\displaystyle f(x)=\sec x+\tan x=\tan \left({\frac {x}{2}}+{\frac {\pi }{4}}\right)}$.

Dieses klassische Resultat d​er analytischen Kombinatorik a​us dem Jahr 1881 g​eht auf d​en französischen Mathematiker Désiré André zurück.[7]

Maclaurin-Reihen

Die Zahlen ${\displaystyle A_{n}}$ werden für gerades ${\displaystyle n}$ auch Sekantenzahlen genannt und treten in der Maclaurin-Reihe der Sekansfunktion

${\displaystyle \sec x=A_{0}+A_{2}{\frac {x^{2}}{2!}}+A_{4}{\frac {x^{4}}{4!}}+\ldots }$

auf, während die Zahlen für ungerades ${\displaystyle n}$ auch Tangentenzahlen genannt werden und in der Reihenentwicklung der Tangensfunktion

${\displaystyle \tan x=A_{1}x+A_{3}{\frac {x^{3}}{3!}}+A_{5}{\frac {x^{5}}{5!}}+\ldots }$

vorkommen.[6] Die Zahlen ${\displaystyle A_{n}}$ stehen dabei in enger Verwandtschaft zu den Bernoulli-Zahlen ${\displaystyle B_{n}}$.[8]

Asymptotik

Für den Anteil der alternierenden Permutationen in der Menge aller Permutationen gilt für ${\displaystyle n\to \infty }$ asymptotisch

${\displaystyle {\frac {A_{n}}{n!}}\simeq 2\left({\frac {2}{\pi }}\right)^{n+1}}$.

Dieser Anteil entspricht der Wahrscheinlichkeit, dass eine (gleichverteilt) zufällige Permutation der Länge ${\displaystyle n}$ alternierend ist.[8]

Literatur

• 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

• Eric 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

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.