Zur Kombinatorik von Permutationen

VON

Torsten SILLKE ^{1}

Abstract. — A bijection between the set of subgroups of index n in the free group on 2 generators F_{2} and the set of connex permutations σ of [n + 1] = {1, 2, ..., n + 1} has been constructed by A.W.M. Dress and R. Franz [DrF85], where σ is connex iff σ[k] ≠ [k] for k ∈ [n]. Dumont and Kreweras introduced the record-antirecord statistics for connex permutations of [n + 1], which are the same as the orbit statistics of the Cayley coset diagram of the subgroups of index n in the free group. J. Zeng [Zen87] asked for a bijection between these sets. As the bijection of Dress and Franz is not applicable, a new one is presented. The construction uses a correspondence between the cycles and the basic components of permutations [FoS70, Ch I.3] [Knu68, 1.3.3], which Goulden and Jackson [GoJ83, [3.3.17]] call the Foata Schützenberger correspondence. Dress and Franz [DrF87] generalised their construction to a bijection between subgroups of finite index in F_{k} and connex systems of k − 1 permutations. The bijection presented in this paper can also be extended to this more general case.

Einleitung

Wir betrachten die hypergeometrische Reihe und deren logarithmische Ableitung

F = _{_{2}F_{0}} [α, β x] := ∑_{n=0}^{∞} \frac{(α)_{n}(β)_{n}}{n!} · x^{n}

C = x · \frac{d}{dx} log F = x · \frac{F′}{F} = ∑_{n=1}^{∞} C_{n}(α, β) · x^{n}.

Die Koeffizienten der hypergeometrischen Reihe sind die aufsteigenden Faktoriellen. Sie sind definiert durch

(α)_{0} := 1, (α)_{n+1} := (α + n)(α)_{n}.

1Universität Bielefeld, Fakultät für Mathematik, Postfach 8640, D 4800 Bielefeld 1. e–mail: UMATF071 @ DBIUNI11 (EARN).

Die Koeffizienten C_{n}(1, 1) zählen

• zum einen die Anzahl der Untergruppen von Index n in der freien, von zwei Elementen erzeugten Gruppe F_{2} [Hal59, Thm 7.2.9] [Sta78, Ex 6.10],

• zum anderen die Anzahl der konnexen Permutationen auf der Menge [n + 1] := {1, 2, …, n + 1}. Hierbei heißt eine Permutation σ auf [n + 1] konnex , wenn kein echtes Teilintervall [k] ⊂ [n + 1] durch die Permutation σ in sich überführt wird [Com74, p261 Ex 14] [GoJ83, [2.4.19]].

Eine Bijektion zwischen diesen beiden Mengen haben A. Dress und R. Franz in [DrF85] angegeben. Sie studieren dabei die Operation der beiden Erzeugenden s und u der freien Gruppe auf der Menge F_{2}/U der Nebenklassen der freien Gruppe modulo der Untergruppe U. Der Koeffizient von α^{k}β^{l} des Polynomes C_{n}(α, β) zählt

• zum einen die Anzahl derjenigen Untergruppen U vom Index n in freien von s und u erzeugeten Gruppe F_{2}, bei denen die Nebenklassen F_{2}/U unter der Operation von s in k Zyklen und unter der Operation u in l Zyklen zerfallen,

• zum anderen die Anzahl der konnexen Permutationen σ auf [n + 1], die genau k links–rechts Maxima und l rechts–links Minima haben (hierbei heißt der Punkt (i, σ(i)) ∈ [n + 1] × [n + 1] ein links–rechts Maximum der Permutation σ, falls für alle j < i gilt: σ(j) < σ(i), und rechts–links Minima sind entsprechend definiert) (cf. Dumont und Kreweras in [DuK86]).

In [Zen87] fragt J. Zeng nach einer Bijektion zwischen den jeweiligen relevanten Mengen. (Un)glücklicherweise leistet die in [DrF85] angegebene Bijektion nicht das Gewünschte.

Im folgenden soll eine Bijektion angegeben werden, die auch mit der durch die Parameter definierten feineren Statistik verträglich ist. Hierfür ist es nützlich, anstelle der Operation der freien Gruppe auf der Menge der Nebenklassen F_{2}/U (bei der die Nebenklasse U ein ausgezeichnetes Element ist), transitive Operationen von F_{2} auf Mengen zu betrachten, bei denen es zwei ausgezeichnete Elemente gibt. Genauer betrachten wir endliche Mengen E zusammen mit zwei Permutationen s und u, die den folgenden Bedingungen genügen:

• E ist eine endliche transitive s–u Menge, d.h. für je zwei Elemente x und y aus E gibt es ein Wort w in s und u, so daß w(x) = y ist.

• Es gibt zwei voneinander verschiedene Punkte ◯ s und ◯ u in E, für die gilt: u(◯ s) = ◯ u und s(◯ u) = ◯ s.

Mengen dieser Art wollen wir doppelt punktierte (transitive) s–u Mengen nennen.

[figure: ◯ s; ◯ u; u; s; u; s; u; s]

Es ist klar, daß man durch Identifikation der beiden ausgezeichnete Punkte zu einem ausgezeichneten Punkt (und Weglassen der beiden sie verbindenden Pfeile) aus einer doppelt punktierten s–u Menge die Menge der Nebenklassen nach einer Untergruppe machen kann (man erhält die Untergruppe als Standuntergruppe des neuen ausgezeichneten Punktes) und daß dieses Verfahren eine Bijektion von der Menge der Untergruppen von endlichem Index in einer freien Gruppe mit zwei Erzeugenden und der Menge der doppelt punktierten s–u Mengen liefert. Wir können und werden deshalb von nun an nur noch doppelt punktierte Mengen betrachten. Es gilt der folgende Satz: Satz: Es gibt eine kanonische Bijektion zwischen der Menge (der Isomorphieklassen) der doppelt punktierten s–u Mengen mit einer n–elementigen Trägermenge E und der Menge der konnexen Permutationen von [n], die verträglich ist mit der durch die Parameter α und β gegebenen feineren Statistik.

Von den Permutationen zu den doppelt punktierten Mengen

Ist σ eine Permutation von [n], dann ist der Graphen Γ(σ) ⊂ [n]×[n] definiert durch: Γ(σ) := {(i, σ(i)) | i ∈ [n]}.

Die Permutation σ definiert dann in naheliegender Weise eine Permutation des Graphen von σ. Sie ist definiert durch (i, σ(i)) ↦ (σ(i), σ(σ(i))) und wird ebenfalls mit σ bezeichnet.

Die Permutation σ ist genau dann konnex, wenn es kein echtes Teilintervall [k] von [n] gibt, so daß σ([k] × [k]) ⊂ [k] × [k] ist,

Jede Permutation w von Γ(σ) induziert in naheliegender Weise zwei Permutationen w_{1} und w_{2} von [n]. Sie sind folgendermaßen definiert^{2}

w_{1}(i) = pr_{1}w(i, σ(i))
w_{2}(j) = pr_{1}w(σ^{−1}(j), j)

Beobachtung: Auf dem Graphen Γ(σ) gibt es genau eine Permutation s (genau eine Permutation u) mit den folgenden Eigenschaften:

• Die Zyklen der Permutationen s_{1} und u_{2} sind Intervalle. Auf jedem dieser Interrvalle operieren s_{1} bzw. u_{2} durch Schieben auf den Nachfolger. Der letzte Punkt des Intervalles, der keinen Nachfolger besitzt, wird auf den ersten geschoben.

2die Projektionen eines Produktes zweier Mengen auf die beiden Faktoren werden mit pr_{1} bzw. pr_{2} bezeichnet

• Die Anfangspunkte der zu s_{1} gehörigen Intervalle sind die ersten Koordinaten der links–rechts Maxima von σ. Die Anfangspunkte der der zu u_{2} gehörigen Intervalle sind die zweiten Koordinaten der rechts–links Minima von σ.

Dies ist nichts anderes als die Foata Schützenberger Korrespondenz^{3}, angewendet auf σ und σ^{−1} [CaF69, Cha IV.5], [FoS70, Cha I.3], [Knu68, 1.3.3], [Knu73, 5.1.2 Thm B]. Beispiel: Wir betrachten die Permutation σ = \binom{1 2 3 4 5 6 7 8 9}{5 2 7 1 6 3 9 8 4}. In den folgen-

den Diagrammen ist der Graph Γ(σ) der gegebenen Permutation dargestellt. Links sind die Zyklen der Permutation s durch senkrechte Linien voneinander getrennt, rechts die Zyklen der Permutation u durch horizontale Linien.

\begin{aligned}♠ & ♠ & ♠ & ♠ & ♠ & ♠ & ◯ & s & ♠ & ◯ & u & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ & & s_{1} = (12)(3456)(789) \end{aligned}  \begin{aligned}♠ & ♠ & ♠ & ♠ & ♠ & ♠ & ◯ & s & ♠ & ◯ & u & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ & & u_{2} = (12)(3)(456789) \end{aligned}

Lemma: Es gibt genau ein links–rechts Maximum ◯ s ∈ Γ(σ) für das su◯ s = ◯ s ist. Es gibt genau ein rechts–links Minimum ◯ u ∈ Γ(σ) für das us◯ u = ◯ u ist. Darüber hinaus gilt für diese Punkte: s · ◯ u = ◯ s und u · ◯ s = ◯ u.

Die Kombination dieser Beobachtungen etabliert auf der Menge Γ(σ) die Struktur einer doppelt punktierten transitiven s–u Menge. Insgesamt haben wir somit eine Abbildung von der Menge der konnexen Permutationen auf [n] in die Menge der doppelt punktierten transitiven s–u Mengen.

Von den F_{2}–Mengen zu den Permutationen Das Cayley Diagramm Modell

Es soll nun umgekehrt eine Abbildung von der Menge (der Isomorphieklassen) der doppelt punktierten transitiven s–u Mengen mit n Elementen in die Menge der konnexen Permutationen auf [n] konstruiert werden.

3so genannt von Goulden und Jackson [GoJ83, [3.3.17]]

Hierfür geben wir ein Verfahren an, durch das schrittweise jedem Element von E eine Position in der Menge [n] × [n] derart zugeordnet wird, daß die dabei resultierende Teilmenge des Quadrates Q := [n] × [n] der Graph einer konnexen Permutation von [n] ist.

Beispiel:

[figure: ◯; s; ◯; u; G; E; F; C; D; A; B]

Die s–Bahnen von E

[figure: ◯; s; ◯; u; G; E; F; C; D; A; B]

Die u–Bahnen von E.

Wir starten, indem wir die Elemente der s–Bahn des Punktes ◯ s (mit ◯ s startend) horizontal oberhalb des Quadrates Q so hinzeichnen, daß ihr letztes Element (hier das Element ◯ u) oberhalb der rechten oberen Ecke von Q steht, und ebenso tragen wir die Elemente der u–Bahn von ◯ u rechts von dem Quadrat Q vertikal so auf, daß ihr letztes Element (hier das Element ◯ s) rechts von der oberen Ecke von Q steht. Die oberhalb des Quadrates liegenden Punkte von E sind hierdurch schon in ihrer ersten Koordinate festgelegt, die rechts stehenden in ihrer zweiten. In der folgenden Abbildungen ist links diese Konfiguration dargestellt:

◯ s G ◯ u ◯ u C A D G ◯ s  ^{♠ ♠ ♠ ◯ s G ◯ u ◯ u C A D G ◯ s ⇒}

Für diejenigen Punkte von E, die sowohl oben als auch rechts eingetragen sind, sind schon beide Koordinaten bestimmt: sie werden an der durch ihre Koordinaten bestimmten Stelle in das Quadrat Q eingetragen. Beispiele hierfür sind die Punkte ◯ s und ◯ u.

Erhalten bei diesem Verfahren sämtliche Punkte oben und rechts schon zwei Koordinaten, dann ist die s–Bahn von ◯ s gleich der u–Bahn von ◯ u, und es folgt, daß diese Menge sowohl unter der Operation von s als auch unter Operation von u abgeschlossen ist; sie ist daher schon gleich E (denn es wurde ja vorausgesetzt, daß die Menge E eine transitive s–u Menge ist). Alle Punkte von E haben dann schon ihren Platz in [n] × [n] gefunden, und wir sind fertig.

♠ ♠ ♠ D F A B ◯ s G ◯ u ◯ u C A D G ◯ s  ^{♠ ♠ ♠ ♠ ♠ D F A B ◯ s G ◯ u ⇑  ◯ u C A D G ◯ s ⇒}

Diejenigen Elemnte von E, für die erst eine Koordinate festliegt, werden durch einen Rahmen hervorgehoben. Man betrachte hierzu den rechte Teil der vorangehenden Abbildung. Wir wählen dann unter den oben liegenden Punkten denjenigen, der möglichst weit rechts liegt, bzw. falls es einen solchen Punkt nicht gibt, den möglichst weit oben liegenden Punkt unter den rechts liegenden. Dieser Punkt ist in dem rechten Teil der Abbildungen durch den Pfeil ⇒ markiert. Im ersten Fall betrachten wir die u–Bahn des Punktes und tragen sie auf der rechten Seite des Quadrates so ein, daß ihr letzter Punkt sich an den ersten Punkt der schon eingetragenen u–Bahn anschließt. Im anderen Fall verfährt man entsprechend und trägt die s–Bahn des Punktes oberhalb des Quadrates und anschließend an die schon eingetragene s–Bahn ein. Es ist inzwischen sicherlich klar geworden, daß im linken Teil unserer Abbildungen immer der Zustand wiedergegeben ist, in dem neue Zyklen angefügt wurden und rechts der, nach dem Eintragen der Punkte.

♠ ♠ ♠ ♠ ♠ C E D F A B ◯ s G ◯ u B ◯ u C A D G ◯ s  ^{♠ ♠ ♠ ♠ ♠ ♠ ♠ C E D F A B ◯ s G ◯ u ⇑  B ◯ u C A D G ◯ s}

In der sich dann neu ergebenden Situation gibt man wiederum diejenigen Punkten, die sowohl oben als auch rechts eingetragen wurden den ihren Koordinaten entsprechenden Platz im Quadrat Q. Da dies zumindest für den Startpunkt der neu hinzugekommenen Bahn geschieht, nimmt nach diesem Schritt die Anzahl der Elemente von E, die noch nicht eingeordnet sind, um mindestens 1 ab.

♠ ♠ ♠ ♠ ♠ ♠ ♠ C E D F A B ◯ s G ◯ u F E B ◯ u C A D G ◯ s  ^{♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ C E D F A B ◯ s G ◯ u F E B ◯ u C A D G ◯ s}

Nach endlich vielen Schritten dieser Art kommt man deshalb in einen Zustand, bei dem alle bis dahin eingetragenen Punkte von E schon ihren Platz im Quadrat gefunden haben. Das bedeutet aber, daß die Menge dieser Punkte sowohl unter der Operation von s als auch der Operation von u abgeschlossen und daher gleich E ist; wir sind dann fertig. Aufgrund der Konstruktion ist es klar, daß in jeder Zeile und in jeder Spalte von Q genau ein Element von E seinen Platz gefunden hat, die enstandene Teilmenge von Q ist daher der Graph einer Permutation von [n]. Diese Permutation ist konnex, denn wäre sie es nicht, dann wäre man bei der Konstruktion schon in einen unter s und u stabilen Zustand gekommen, ohne dabei alle Elemente aus E ausgeschöpft zu haben. Weil E eine transitive s–u Menge ist, geht dies natürlich nicht.

Wir haben hiermit also eine Abbildung angegeben, die jeder doppelt punktierten transitiven s–u Menge eine konnexe Permutation von [n] zuordnet. Diese Konstruktion ist invers zu der im ersten Teil gegebenen Konstruktion und beide zusammen liefern die angekündigte Bijektion.

Anmerkungen: Betrachtet man für eine konnexe Permutation zusätzlich noch die Statistik der Inversionen, dann erhält man ein q–Analogon [Zen87] für die erzeugende Funktion. Hierfür gibt es noch keine Interpretation im Rahmen der Cayley Diagramme. Das Untergruppen-Modell läßt sich auf mehrere Generatoren verallgemeinern [DrF87], wo eine Bijektion zu einem verallgemeinerten Modell von konnexen Permutationen konstruiert wird. Rekorde (links–rechts Maxima) sind auch früher schon betrachtet [Cha52],

[FoS54] und wiederentdeckt [Imh83] worden. Eine alternative Darstellung für Permutationen ist ein Paar transitiver gerichteter Graphen, die die Inversionen und nicht-Inversionen darstellen, deren Vereinigung den vollständigen gerichteten kreisfreien Graphen ergibt [Knu73, 5.1.1 Ex 11]. Die Konnexität entspricht in dieser Darstellung dem Zusammenhang des Inversionsgraphen, die r–l Minima und l–r Maxima entsprechen den Quellen und Senken des Inversionsgraphen. Die Symmetrieoperationen des Quadrates werden überführt in das Umdrehen der gerichteten Kanten oder Austauschen des Graphenpaares. Eine Verbindung zu Robinson-Schensted [Vie82] ist nicht zu erkennen, obwohl die Bilder bei Viennot ähnlich aussehen. In der Sprache von Viennot sind die links–rechts Maxima die nord–westlich beleuchteten Elemente und die rechts–links Minima die süd–östlich beleuchteten Elemente.

Literatur

[CaF69] Cartier (P.) et Foata (D.) — Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics 85, Springer (1969).

[Cha52] Chandler (K.N.) — The Distribution and Frequency of Record Values, Journal of the Royal Statistical Society B 14 (1952) 220–228.

[Com74] Comtet (L.) — Advanced Combinatorics, Dordrecht (1974).

[DrF85] Dress (A.W.M.) und Franz (R.) — Parametrizing the subgroups of finite index in a free group and related topics, Bayreuther Mathematische Schriften 20 (1985) 1–8.

[DrF87] Dress (A.W.M.) und Franz (R.) — Zur Parametrisierung von Untergruppen freier Gruppen, Beiträge zur Algebra und Geometrie 24 (1987) 125–134.

[DuK86] Dumont (D.) et Kreweras (G.) — Sur le développement d’une fraction continue liée à la série hypérgeométrique et son interprétation en termes de records et anti-records dans les permutations, Séminaire Lotharingien de Combinatoire, 14^{e} session, Publ. I.R.M.A. Strasbourg, (1986), 67–74; siehe auch: European Journal of Combinatorics 9 (1988) 27–32.

[FoS70] Foata (D.) et Schützenberger (M.P.) — Théorie Géométrique des Polynômies Eulériens, Lecture Notes in Mathematics 138, Springer (1970).

[FoS54] Foster (F.G.) and Stuart (A.) — Distribution Free Tests in Time-Series Based on the Breaking of Records (together with the subsequent discussion), Journal of the Royal Statistical Society B 16 (1954) 1–22.

[GoJ83] Goulden (I.P.) and Jackson (D.M.) — Combinatorial Enumeration, John Wiley, New York (1983).

[Hal59] Hall (M.) — The Theory of Groups, Macmillan, New York (1959).

[Imh83] Imhof (J.P.) — Stirling Numbers and Records, Journal of Combinatorial Theory A 34 (1983) 252–254.

[Knu68] Knuth (D.E.) — The Art of Computer Programming I (Fundamental Algorithms), Addison-Wesley, Reading (1968, 2nd Edition 1973).

[Knu73] Knuth (D.E.) — The Art of Computer Programming III (Sorting and Searching), Addison-Wesley, Reading (1973).

[Sta78] Stanley (R.P.) — Generating Functions, in: Studies in Combinatorics (G.C. Rota, editor), MAA Studies in Mathematics 17 (1978).

[Vie82] Viennot (G.) — Chain and Antichain Families Grids and Young Tableaux, in: M. Pouzet, D. Riachard; Orders: Descriptions and Rules, Conference on Ordered Sets and their Applications (1982, l’Arbresle), Annals of Discrete Mathematics 23 (1984) 409–464.

[Zen87] Zeng (J.) — Records, Antirecords et Permutations Discordantes Séminaire Lotharingien de Combinatoire, 15^{e} session, Publ. I.R.M.A. Strasbourg, (1987), 121– 128. siehe auch: European Journal of Combinatorics 10 (1989) 103–110.