Eine Bijektion zwischen Untergruppen freier Gruppen und Systemen konnexer Permutationen

Dissertation zur Erlangung des Doktorgrades der Fakultät für Mathematik der Universität Bielefeld

vorgelegt von Torsten Sillke

Nil sine magno labore vita dedit mortalibus. (Horaz)

Den folgenden Personen möchte ich danken: Walter A. Deuber für seine Hilfe bei der Umschiffung einiger Klippen. Andreas W. M. Dress für seine Mitwirkung, ohne die die vorliegende Arbeit nie in dieser Form entstanden wäre. Heidemarie L. E. Dreß für die Schaffung der nötigen Rahmenbedingungen. Olaf Delgado Friedrichs für TEX-nische Hilfen, und der Kritik beim Lesen der Diplomarbeit, der Grundlage dieser Arbeit. Klaus-Uwe Koschnick für seinen Tip, einen axiomatischen Ansatz zu machen. Christian Siebeneicher für seinen nicht zu bremsenden Einsatz, ohne den die Vorläuferarbeit [Sil90] nicht entstanden wäre. Dem Graduiertenkolleg bin ich für seine finanzielle Unterstützung zu Dank verpflichtet.

Inhaltsverzeichnis

1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Zykel–Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4 Foata–Schützenberger . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5 transitiv entspricht konnex . . . . . . . . . . . . . . . . . . . . . . . . 15 6 von Θ_{1} nach Ξ_{1} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7 Fortsetzungslemma und Existenz . . . . . . . . . . . . . . . . . . . . 19 8 Eindeutigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9 Satz und Korollare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1 Einleitung

Wir betrachten die hypergeometrische Reihe ^{1} und deren logarithmische Ableitung ^{2}

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}, (n ≥ 0).

Die Koeffizienten^{3} C_{n}(1, 1) zählen für n ≥ 1

• 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, Example 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 Exercise 14] [GoJ83, [2.4.19]].

Eine Bijektion zwischen diesen beiden Mengen haben A. W. M. Dress und R. Franz in [DrF85] angegeben. Sie studieren dabei die Operation der beiden Erzeugenden τ_{0} und τ_{1} der freien Gruppe auf der Menge F_{2}/U der Nebenklassen der freien Gruppe modulo einer Untergruppe U. Für n = 0 stimmen die Anzahlen nicht überein, da es keine Untergruppe vom Index 0 aber eine konnexe Permutation auf {1} gibt.

Der Koeffizient von α^{k}β^{l} des Polynomes C_{n}(α, β) zählt für n ≥ 1 • zum einen die Anzahl derjenigen Untergruppen U vom Index n in der freien

1Siehe hierzu W. N. Bailey in [Bai35] oder H. Exton in [Ext83].

2Kombinatorische Interpretationen siehe R. P. Stanley in [Sta78, Cha. VI] [Sta78’], D. Foata und M. P. Schützenberger in [FoS70, Cha. III] sowie E. A. Bender und J. R. Goldman in [BeG71, §3]. Weitere Referenzen sind bei D. Foata in [Foa78, §2] enthalten. Einen kategoriellen Ansatz machen A. W. M. Dress und T. Müller in [DrM91], der auf zerlegbare Funktoren führt, die einer Pullbackbedingung genügen. A. Nijenhuis und H. S. Wilf gewinnen in [NiW75, 10.Postscript] aus dieser Beziehung speichereffiziente Algorithmen, um zufällige Partitionen (Integer Partitions), ebene Partitionen (Plane Partitions) oder ungelabelte Wurzelbäume (Unlabeled Rooted Trees) zu erzeugen.

3Über das asymptotische Verhalten siehe L. Comtet in [Com74, p294 Exercise 16] sowie E. A. Bender in [Ben74, Example 5.1].

von τ_{0} und τ_{1} erzeugten Gruppe F_{2}, bei denen die Nebenklassen F_{2}/U unter der Operation von τ_{0} in k Zyklen und unter der Operation τ_{1} in l Zyklen zerfallen,

• zum anderen die Anzahl der konnexen Permutationen σ auf [n + 1] mit genau k ”Rekorden“ von σ^{−1} und genau l ”Rekorden“ von σ. Dabei heißt i ∈ [n + 1] Rekord einer Permutation σ von [n + 1], wenn für alle j ∈ {1, …, i − 1} die Ungleichung σ(j) < σ(i) gilt. (cf. D. Dumont und G. Kreweras in [DuK86]^{4} ).

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. In [Sil90] habe ich eine Bijektion angegeben, die auch mit der durch die Parameter definierten feineren Statistik verträglich ist. Einen axiomatischen Beweis habe ich in der Diplomarbeit [Sil91] vorgestellt.

A. W. M. Dress und R. Franz verallgemeinern in [DrF87] ihre Bijektion aus [DrF85] zu einer Bijektion zwischen Untergruppen der der freien Gruppe F_{k} vom Index n und Systemen konnexer Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) auf der Menge [n + 1], für die μ_{1}(1) ≠ μ_{2}(1) = μ_{3}(1) = … = μ_{k−1}(1) = 1 gilt. Ein System (μ_{1}, μ_{2}, …, μ_{k−1}) heiße dabei konnex, wenn für alle i ∈ [n] ein ϵ ∈ [k − 1] existiert, so daß μ_{ϵ}({1, …, i}) ≠ {1, …, i} gilt. In anderen Worten, wenn für alle i ∈ [n] die Ungleichung ⟨μ_{1}, μ_{2}, …, μ_{k−1}⟩({1, …, i}) ≠ {1, …, i} gilt.

In der vorliegenden Arbeit wird eine gemeinsame Verallgemeinerung von [DrF87] und [Sil91] vorgestellt, die eine Bijektion auf einer größeren Menge liefert. Es wird eine Bijektion zwischen:

• den Untergruppen U vom Index n + 1 der in der freien von x_{0}, x_{1}, …, x_{k−1} erzeugten Gruppe F_{k} mit der Relation x_{0}x_{1} … x_{k−1} ∈ U,

• und den konnexen Systemen von Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) auf [n + 1]

konstruiert. Wählt man stattdessen konnexe Systeme von Permutationen (ν_{0}, ν_{1}, …, ν_{k−1}) auf [n + 1] mit der Bedingung ν_{0}ν_{1} … ν_{k−1} = Id, so kann man zusätzlich #Rekorde(ν_{ϵ}) = #⟨x_{ϵ}⟩\F_{k}/U erreichen.

4Der Beweis von D. Dumont und G. Kreweras in [DuK86] sowie der Beweis des q–Analogon von J. Zeng in [Zen87] sind indirekt. Aus der Differentialgleichung für F und der Beziehung F C = xF′ läßt sich Rekursion C_{n+1}(α, β) := (n + α + β)C_{n}(α, β) + ∑_{i=1}^{n−1} C_{i}(α, β)C_{n−i}(α, β)

mit Startwert C_{1}(α, β) = αβ ableiten. Eine kombinatorische Interpretation dieser Rekursion ist im Bild der Cayley–Nebenklassen–Diagramme altbekannt. Eine Interpretation für β = 1 ist leicht zu finden. Eine komplizierte Konstruktion für das q–Analogon, die auch die Inversionen richtig interpretiert, habe ich 1987 entwickelt. Daß zur gleichen Zeit auch Dumont, Kreweras und Zeng an Abzählformeln für konnexe Permutationen gearbeitet haben, erfuhr ich erst Ende 1988 aus der European Journal of Combinatorics Fassung von [DuK86].

Es ergibt sich außerdem eine Bijektion zwischen Untergruppen U mit nicht endlichem Index der freien Gruppe F_{k} (die Menge der Nebenklassen ist dann abzählbar), die die Endlichkeitsbedingung: #{x_{ϵ}^{i}V | i ∈ ℤ} < ∞ für jedes Erzeugende x_{ϵ} und jede Nebenklasse V ∈ {gU | g ∈ F_{k}} erfüllen, und konnexen Systemen von Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) auf ℕ.

Für die Kombinatorik verwende ich als Darstellung der Untergruppen der freien Gruppe F_{k} deren Cayley Nebenklassen Diagramme, wie dies auch in [DrF85] und [DrF87] geschieht. Statt dann gleich mit den Isomorphieklassen dieser punktierten Systeme zu arbeiten, wird eine Bijektion zwischen solchen Diagrammen mit fester Vertexmenge und entsprechend konnexen Systemen von Bijektionen auf diese Vertexmenge konstruiert, die sich aber als verträglich mit der Isomorphieklassenbildung erweist.

2 Definitionen

Um dieses Resultat präziser formulieren zu können, benötigen wir einige Definitionen. In dieser Arbeit sei mit k im folgenden immer eine natürliche Zahl größer als oder gleich zwei gemeint. Alle im Folgenden auftretenden Indices werden als Indices modulo k aufgefaßt werden. Alle vorkommenden Mengen sind höchstens abzählbar.

Definition 2.1 Für eine höchstens abzählbar unendliche Menge F setzen wir

ℕ_{F} = \{ \begin{matrix}\{1, 2, …, #F \} & falls #F < ∞ \\ ℕ & falls #F = ∞. \end{matrix}

Definition 2.2 Sind E, E′ Mengen, so sei mit σ : E ˜ ⟶ E′ eine Bijektion von E nach E′ bezeichnet.

Definition 2.3 Ist F eine Menge, so wird mit F! die symmetrische Gruppe von F, die Gruppe aller Permutationen von F, bezeichnet.

Definition 2.4 Für eine Menge F, eine Permutation σ ∈ F! von F und ein Element f ∈ F sei ⟨σ⟩f := {σ^{i}f | i ∈ ℤ} der von f erzeugte σ–Orbit.

Definition 2.5 Mit F!_{fin} wird die Teilmenge aller derjenigen Permutationen von F bezeichnet, die nur endliche Orbits besitzen.

Wenn F nicht endlich ist, so ist F!_{fin} natürlich keine Untergruppe von F!. Schon das Produkt zweier Involutionen kann unendlich lange Bahnen haben.

Definition 2.6 Sei M = ℕ oder M = {1, 2, …, n} für ein n ∈ ℕ und sei μ ∈ M! eine Permutation von M. Die Rekorde^{5} von μ sind die Stellen i ∈ M, an denen μ ein Links–Rechts–Maximum besitzt:

Rekorde(μ) := {i ∈ M | μ(i) ≥ μ(j) für alle j ∈ M mit j ≤ i}.

Definition 2.7 Für eine höchstens abzählbare Menge F, eine Permutation σ ∈ F! von F, eine Teilmenge F_{1} ⊆ F von F und eine Abbildung v : F_{1} → ℕ setzen wir

F_{1}(σ, v)^{max} := {f ∈ F_{1} | v(f) ≥ v(f′) für alle f′ ∈ F_{1} ∩ ⟨σ⟩f},
F_{1}(σ, v)^{min} := {f ∈ F_{1} | v(f) ≤ v(f′) für alle f′ ∈ F_{1} ∩ ⟨σ⟩f}.

Bemerkung 2.1 Ist f ∈ F_{1} und ist v zusätzlich injektiv, so besteht ⟨σ⟩f ∩ F_{1}(σ, v)^{min} aus genau einem und ⟨σ⟩f ∩ F_{1}(σ, v)^{max} aus höchstens einem Element. Genauer gilt ⟨σ⟩f ∩ F_{1}(σ, v)^{max} = ∅ genau dann, wenn #(⟨σ⟩f ∩ F_{1}) = ∞ gilt.

Bemerkung 2.2 Ist f ∈ F und v : F → ℕ injektiv, so wird durch Bemerkung 2.1 eine Bijektionen zwischen F (σ, v)^{min} und ⟨σ⟩\F, den Bahnen von σ induziert.

Bemerkung 2.3 Ist F_{1} ⊆ F_{2} ⊆ F, σ ∈ F! und gelten v_{1} : F_{1} → ℕ, v_{2} : F_{2} → ℕ mit v_{2}|_{F_{1}} = v_{1}, so folgen aus σ(F_{1}) = F_{1}:

F_{1}(σ, v_{1})^{min} = F_{2}(σ, v_{2})^{min} ∩ F_{1},
F_{1}(σ, v_{1})^{max} = F_{2}(σ, v_{2})^{max} ∩ F_{1}.

Bemerkung 2.4 Ist F_{1} ⊆ F_{2} ⊆ F, σ ∈ F! und gelten v_{1} : F_{1} → ℕ, v_{2} : F_{2} → ℕ mit v_{2}|_{F_{1}} = v_{1}, so folgt aus v_{1}(F_{1}) ≤ v_{2}(F_{2} \ F_{1}), d. h. für alle f_{1} ∈ F_{1} und f_{2} ∈ F_{2} \ F_{1} gilt v_{1}(f_{1}) ≤ v_{2}(f_{2}):

F_{1}(σ, v_{1})^{min} = F_{2}(σ, v_{2})^{min} ∩ F_{1}.

Und aus v_{1}(F_{1}) ≥ v_{2}(F_{2} \ F_{1}) folgt:

F_{1}(σ, v_{1})^{max} = F_{2}(σ, v_{2})^{max} ∩ F_{1}.

5Es gibt eine ganze Reihe von Bezeichnungen für die Rekorde. L. Comtet nennt sie ”outstanding elements“ in [Com74, p258 Exercise 10 (3)], und bei M. Henle heißen sie ”projecting elements“ in MR 51 # 12542. Bei I. P. Goulden und D. M. Jackson [GoJ83, [3.3.17]] heißen sie ”upper records“ und ”left upper records“ bei L. Carlitz und R. Scoville [CaS74]. Im Französischen findet man bei A. Rényi in [Ren62] sowie bei D. Foata und M. P. Schützenberger in [FoS70] auch den Namen ”éléments saillants“. Für die Werte der Rekorde sind auch die Namen ”left–to–right maximum“ (D. E. Knuth), ”strong element“ (A. Rényi) oder ”ladder variable“ (W. Feller) im Umlauf.

J. P. Imhof gibt in [Imh83] mit Rekorden wahrscheinlichkeitstheoretische Interpretationen von zwei Identitäten von Stirlingzahlen erster Art. In der Statistik sind ”Rekorde“ ein häufig behandeltes Thema. Einen Überblicksartikel hierzu gibt es von N. Glick [Gli78]. Neuere Arbeiten findet man bei C. M. Goldie in [Gol89].

Definition 2.8 Für eine Menge E sei Ξ_{1}(E, k) die Menge aller Paare (τ; e) = (τ_{0}, τ_{1}, …, τ_{k−1}; e_{0}, e_{1}, …, e_{k−1}) von Permutationen τ_{0}, τ_{1}, …, τ_{k−1} ∈ E! und Elementen e_{0}, e_{1}, …, e_{k−1} ∈ E, die den folgenden zwei Bedingungen (Ξ0) und (Ξ1) genügen:

τ_{0}, τ_{1}, …, τ_{k−1} ∈ E!_{fin}; (Ξ0) (Ξ1) Es gilt τ_{ϵ}e_{ϵ+1} = e_{ϵ} für alle ϵ ∈ {0, 1, …, k − 1}.

Mit Ξ_{2}(E, k) bezeichnen wir die Teilmengen aller Paare (τ; e) = (τ_{0}, τ_{1}, …, τ_{k−1}; e_{0}, e_{1}, …, e_{k−1}) in Ξ_{1}(E, k), die zusätzlich der folgenden Bedingung (Ξ2) genügen:

(Ξ2) Die von τ_{0}, τ_{1}, …, τ_{k−1} erzeugte Untergruppe operiert transitiv auf E.

Definition 2.9 Für eine Bijektion σ : E ˜ ⟶ E′ sei die induzierte Bijektion:

(E^{E})^{k} × E^{k} ˜ ⟶ (E′^{E′})^{k} × E′^{k}
(τ; e) ⟶ (στ_{0}σ^{−1}, …, στ_{k−1}σ^{−1}; σe_{0}, …, σe_{k−1})

einfachheitshalber wieder mit σ bezeichnet. Zwei Paare (τ; e) = (τ_{0}, τ_{1}, …, τ_{k−1}; e_{0}, e_{1}, …, e_{k−1}) ∈ (E^{E})^{k} × E^{k} und (τ′; e′) = (τ′_{0}, τ′_{1}, …, τ′_{k−1}; e′_{0}, e′_{1}, …, e′_{k−1}) ∈ (E′^{E′})^{k} × E′^{k} werden als isomorph bezeichnet, wenn für eine Bijektion σ ∈ E ˜ ⟶ E′ die Beziehung σ((τ; e)) = (τ′; e′) gilt, in welchem Falle (τ; e) und (τ′; e′) auch als σ–isomorph bezeichnet werden.

Bemerkung 2.5 Ist σ : E ˜ ⟶ E′ eine Bijektion, so gelten σ(Ξ_{1}(E, k)) = Ξ_{1}(E′, k) und σ(Ξ_{2}(E, k)) = Ξ_{2}(E′, k).

Beachte, daß E höchstens abzählbar unendlich ist, falls eine endlich erzeugte (und damit abzählbare!) Gruppe auf E transitiv operiert. Aus Ξ_{2}(E, k) ≠ ∅ folgt daher, daß E höchstens abzählbar unendlich sein kann.

Definition 2.10 Für eine höchstens abzählbare Menge E sei Θ_{1}(E, k) die Menge aller k-Tupel (w_{0}, w_{1}, …, w_{k−1}) von Bijektionen w_{0}, w_{1}, …, w_{k−1} : E ˜ ⟶ ℕ_{E} und Θ_{2}(E, k) sei die Teilmenge aller k-Tupel (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k), für die es keine nicht–triviale Teilmenge E′ von E gibt mit w_{ϵ}(E′) = ℕ_{E′} für alle ϵ ∈ {0, 1, …, k − 1}. Diese k-Tupel (w_{0}, w_{1}, …, w_{k−1}) nennen wir konnex.

Definition 2.11 Für eine Bijektion σ : E ˜ ⟶ E′ sei die induzierte Bijektion:

(ℕ^{E})^{k} ˜ ⟶ (ℕ^{E′})^{k}
(w_{0}, w_{1}, …, w_{k−1}) ⟶ (w_{0}σ^{−1}, w_{1}σ^{−1}, …, w_{k−1}σ^{−1})

einfachheitshalber wieder mit σ bezeichnet. Zwei k-Tupel (w_{0}, w_{1}, …, w_{k−1}) ∈ (ℕ^{E})^{k} und (w′_{0}, w′_{1}, …, w′_{k−1}) ∈ (ℕ^{E′})^{k} werden als isomorph bezeichnet, wenn für eine Bijektion σ ∈ E ˜ ⟶ E′ die Beziehung σ((w_{0}, w_{1}, …, w_{k−1})) = (w′_{0}, w′_{1}, …, w′_{k−1}) gilt, in welchem Falle (w_{0}, w_{1}, …, w_{k−1}) und (w′_{0}, w′_{1}, …, w′_{k−1}) auch als σ–isomorph bezeichnet werden.

Bemerkung 2.6 Ist σ : E ˜ ⟶ E′ ein Bijektion, so gelten σ(Θ_{1}(E, k)) = Θ_{1}(E′, k) und σ(Θ_{2}(E, k)) = Θ_{2}(E′, k).

Definition 2.12 Für eine höchstens abzählbar unendliche Menge E nennen wir ein Paar (τ; e) = (τ_{0}, τ_{1}, …, τ_{k−1}; e_{0}, e_{1}, …, e_{k−1}) in Ξ_{1}(E, k) mit einem k-Tupel (w_{0}, w_{1}, …, w_{k−1}) in Θ_{1}(E, k) kompatibel, wenn für alle ϵ ∈ {0, 1, …, k − 1}die folgenden vier Bedingungen erfüllt sind:

w_{ϵ}(e_{ϵ}) = 1; (T_{ϵ}0) (T_{ϵ}1) für alle f ∈ E gilt w_{ϵ}(τ_{ϵ}f) ≤ w_{ϵ}(f) + 1; E(τ_{ϵ}, w_{ϵ})^{max} = E(τ_{ϵ}, w_{ϵ+1})^{min}; (T_{ϵ}2) (T_{ϵ}3) f,f′∈E(τ_{ϵ}, w_{ϵ})^{max} und w_{ϵ}(f)<w_{ϵ}(f′) impliziert w_{ϵ+1}(f)<w_{ϵ+1}(f′).

Mit T_{1}(E, k) ⊆ Ξ_{1}(E, k) × Θ_{1}(E, k) bezeichnen wir die zugehörige Relation aller kompatiblen Paare aus Ξ_{1}(E, k) und Θ_{1}(E, k), und mit T_{2}(E, k) bezeichnen wir den Schnitt von T_{1}(E, k) mit Ξ_{2}(E, k) × Θ_{2}(E, k).

Bemerkung 2.7 Beachte, daß für (w_{0}, w_{1}, …, w_{k−1}) in Θ_{1}(E, k) und (τ; e) in Ξ_{1}(E, k) die Aussagen (T_{ϵ}2) und (T_{ϵ}3) die folgende, (T_{ϵ}3) verschärfende Aussage implizieren:

(T_{ϵ}3’)  Aus f ∈ E(τ_{ϵ}, w_{ϵ})^{max}, f′ ∈ E und w_{ϵ}(f) ≤ w_{ϵ}(f′)
folgt w_{ϵ+1}(f) ≤ w_{ϵ+1}(f′).

In der Tat, ist {f′′} := ⟨τ_{ϵ}⟩f′ ∩E(τ_{ϵ}, w_{ϵ})^{max}, so gilt w_{ϵ}(f) ≤ w_{ϵ}(f′) ≤ w_{ϵ}(f′′), wegen (T_{ϵ}3) gilt dann auch w_{ϵ+1}(f) ≤ w_{ϵ+1}(f′′) und wegen (T_{ϵ}2) gilt w_{ϵ+1}(f′′) ≤ w_{ϵ+1}(f′). Zusammen ergibt sich also w_{ϵ+1}(f) ≤ w_{ϵ+1}(f′).

Ziel dieser Arbeit ist es zu zeigen, daß die Relation T_{2}(E, k) eine Bijektion zwischen Ξ_{2}(E, k) und Θ_{2}(E, k) definiert, das heißt, daß zu jedem Paar (τ; e) ∈ Ξ_{2}(E, k) genau ein kompatibles k-Tupel w ∈ Θ_{2}(E, k) existiert mit ((τ; e), w) ∈ T_{2}(E, k), und daß auch umgekehrt zu jedem w ∈ Θ_{2}(E, k) genau ein mit w kompatibles Paar (τ; e) ∈ Ξ_{2}(E, k) existiert. Genauer folgt, wie wir sehen werden, aus der von D. Foata und M. P. Schützenberger in [FoS70] betrachteten ”fundamentalen Bijektion“, daß zu jedem w ∈ Θ_{1}(E, k) genau ein mit w kompatibles Paar ((τ; e), w) ∈ T_{1}(E, k) existiert, T_{1}(E, k) ist also Graph einer Abbildung α_{1} : Θ_{1}(E, k) ⟶ Ξ_{1}(E, k). Wir werden zusätzlich zeigen, daß für ein kompatibles Paar ((τ; e), w) genau dann (τ; e) in Ξ_{2}(E, k) liegt, wenn w in Θ_{2}(E, k) liegt. Die Abbildung α_{1} : Θ_{1}(E, k) ⟶ Ξ_{1}(E, k) definiert also durch Restriktion auch eine Abbildung α_{2} : Θ_{2}(E, k) ⟶ Ξ_{2}(E, k), deren Graph gerade T_{2}(E, k) ist. Um zu zeigen, daß α_{2} eine Bijektion ist, T_{2}(E, k) also auch als Graph einer Abbildung β_{2} : Ξ_{2}(E, k) ⟶ Θ_{2}(E, k) aufgefaßt werden kann, konstruieren wir schließlich zu jedem Paar (τ; e) ∈ Ξ_{2}(E, k) ein mit (τ; e) kompatibles k-Tupel w ∈ Θ_{1}(E, k), welches dann notwendig in Θ_{2}(E, k) liegen muß, und zeigen schließlich, daß es nur ein solches w ∈ Θ_{1}(E, k) geben kann.

3 Zykel–Lemma^{6}

Lemma 3.1 Ist F eine höchstens abzählbare Menge, und sind

w : F ˜ ⟶ ℕ_{F}
σ : F!

mit der Eigenschaft

(∗)  w(σ(f)) ≤ w(f) + 1 für alle f ∈ F

gegeben, so gelten folgende Aussagen:

σ ∈ F!_{fin} (0) F (σ, w)^{max} = {f ∈ F | w(f) ≥ w(σf)} (1) F (σ, w)^{min} = {f ∈ F | w(f) ≤ w(σ^{−1}f)} (2) σ F (σ, w)^{max} = F (σ, w)^{min} (3)

(4) Ist f ∈ F (σ, w)^{min} und i ∈ ℕ_{0}, so ist w(σ^{i}f) = w(f) + i für alle 0 ≤ i < #⟨σ⟩f

w(f) ≤ w(f′) ≤ w(f′′) und (5)

⟨σ⟩f = ⟨σ⟩f′′ impliziert ⟨σ⟩f = ⟨σ⟩f′ = ⟨σ⟩f′′

6Nicht zu verwechseln mit dem Lemma von Raney.

Mit anderen Worten, die Zyklen–Zerlegung der Permutation wσw^{−1} : ℕ_{F} ˜ ⟶ ℕ_{F} hat die Gestalt

(1, 2, …, a_{1})(a_{1} +1, a_{1} +2, …, a_{2}) … (a_{i−1} +1, a_{i−1} +2, …, a_{i}) …

für eine streng monoton wachsende Folge a_{1} < a_{2} < a_{3} < … < a_{i} < … in ℕ_{F} mit sup(a_{i}) = sup(ℕ_{F}) und es ist

F (σ, w)^{max} = {w^{−1}(a_{1}), w^{−1}(a_{2}), …}

und

F (σ, w)^{min} = {w^{−1}(1), w^{−1}(a_{1} + 1), w^{−1}(a_{2} + 1), …}.

Beweis Aus (∗) folgt offensichtlich σf = f oder w(σf) = w(f)+1 oder w(σf) < w(f). Ebenso folgt aus (∗) auch, daß w(σ^{i}f) ≤ w(f) + i für alle i ∈ ℕ_{0}, wobei für ein festes i ∈ ℕ_{0} Gleichheit nur im Falle w(σ^{j}f) = w(f) + j für alle j ∈ {0, 1, 2, …, i} gilt. Sei nun f ∈ F fest gewählt und sei f_{0} ∈ ⟨σ⟩f so, daß w(f_{0}) ≤ w(σ^{i}f) für alle i ∈ ℤ gilt, d. h. f_{0} ist das bezüglich w minimale Element in ⟨σ⟩f, und sei f_{1} := σ^{−1}f. Sei n ∈ ℕ_{0} maximal mit w(σ^{i}f_{0}) < w(f_{1}) für 0 ≤ i ≤ n−1, insbesondere also n = 0 im Falle ⟨σ⟩f = {f} = {f_{0}} = {f_{1}}. Dann folgt

w(f_{1}) − w(f_{0}) ≥ #{w(σ^{i}f) | i ∈ {0, 1, …, n − 1} } = n,

während andererseits w(f_{1}) ≤ w(σ^{n}f_{0}) und deshalb auch

w(f_{1}) − w(f_{0}) ≤ w(σ^{n}f_{0}) − w(f_{0}) ≤ n

gelten muß. Also gilt w(f_{1}) = w(σ^{n}f_{0}) = w(f_{0})+n und deshalb auch f_{1} = σ^{n}f_{0} und w(σ^{i}f_{0}) = w(f_{0}) + i für i ∈ {0, 1, …, n}. Wegen σ^{n+1}f_{0} = σf_{1} = f_{0} folgen daraus alle Behauptungen.

q.e.d.

Unmittelbar einsichtig ist das folgende Korollar.

Korollar 3.1 Mit den Bezeichnungen und unter Voraussetzung von Lemma 3.1 gilt für f ∈ F (σ, w)^{max} stets

w(σf) = min{n ∈ ℕ | f′ ∈ F (σ, w)^{max} und
w(f′) < w(f) impliziert w(f′) < n}

Bemerkung 3.1 Das Lemma gilt auch noch wenn w : F ˜ ⟶ M < ω + ω ist. Wenn w : F ˜ ⟶ ω + ω gilt von Lemma 3.1 nur noch (4) für alle Nachfolger des minimalen Elementes.

Beispiel: Sei F = ω+ω und w = Id. Dann erfüllt die folgende Abbildung σ die Bedingung (∗).

σ = (ω)(…, 3 + ω, 2 + ω, 1 + ω, 0, 1, 2, 3, …)

Insbesondere gilt auch die Aussage von Lemma 3.1(5) nicht mehr.

4 Foata–Schützenberger

Im folgenden sei M = ℕ oder M = {1, 2, ..., n} für ein n ∈ ℕ. Für μ, ϕ ∈ M! betrachten wir die folgenden Aussagen:

ϕ ∈ M!_{fin}; (FS0) (FS1) für alle i ∈ M gilt μ^{−1}(ϕ(i)) ≤ μ^{−1}(i) + 1; (FS2) M(ϕ, μ^{−1})^{max} = M(ϕ, Id)^{min}; (FS3) für alle i, j ∈ M(ϕ, μ^{−1})^{max} mit μ^{−1}(i) < μ^{−1}(j) gilt i < j; M(ϕ, μ^{−1})^{max} = Rekorde(μ^{−1}). (FS4)

Definition 4.1 Die Foata–Schützenberger–Relation F S ist durch (FS1), (FS2) und (FS3) wie folgt definiert:

F S := {(μ, ϕ) ∈ M! × M! | μ und ϕ erfüllen

die Bedingungen (FS1), (FS2) und (FS3)}

Analog definieren wir eine Relation F S′ wie folgt:

F S′ := {(μ, ϕ) ∈ M! × M! | μ und ϕ erfüllen

die Bedingungen (FS1) und (FS4)}

Es gilt das folgende

Lemma 4.1 Die Relationen F S und F S′ stimmen überein. Genauer können wir für (μ, ϕ) ∈ M! × M! zeigen:

1. (F S1) ⇒ (F S0)

2. (F S2) ⇔ (F S2_{⊇}) ⇔ (F S2_{⊆}) und (F S0)

3. (F S2) und (F S3) ⇒ (F S4)

4. (F S4_{⊇}) ⇒ (F S3)

5. (F S1) und (F S4) ⇒ (F S2)

Wobei die Notation (F S2_{⊆}), (F S2_{⊇}) und (F S4_{⊇}) natürlich auf die offensichtliche Weise zu deuten sind.

Beweis Wegen 2. reicht es, bei 5. nur (F S2_{⊇}) zu zeigen.

Zeige: (F S1) ⇒ (F S0)

Dies folgt nach Lemma 3.1(0).

Zeige: (F S2_{⊇}) ⇒ (F S0)

Sei i ∈ M so betrachte ⟨ϕ⟩i. Dieser Orbit hat ein minimales Element i′ und zwar gilt {i′} = ⟨ϕ⟩i ∩ M(ϕ, Id)^{min}. Ein minimales Element muß es geben, da die Ordnung auf M eine Wohlordnung ist. Nach (F S2_{⊇}) ist nun i′ ∈ M(ϕ, μ^{−1})^{max} also ein maximales Element einer Teilmenge der natürlichen Zahlen. Nun hat aber eine unendliche Menge natürlicher Zahlen kein Maximum. Somit muß die Teilmenge endlich sein. Da μ eine Bijektion ist, muß also auch ⟨ϕ⟩i endlich sein.

Zeige: (F S2_{⊇}) ⇒ (F S2_{⊆})

Sei i ∈ M(ϕ, μ^{−1})^{max}. Dann gilt {i′} = ⟨ϕ⟩i ∩ M(ϕ, Id)^{min} für ein i′ ∈ M. Weiter gilt nach (F S2_{⊇}) auch i′ ∈ M(ϕ, μ^{−1})^{max}. So erhalten wir {i} = ⟨ϕ⟩i ∩ M(ϕ, μ^{−1})^{max} = {i′} und damit i ∈ M(ϕ, Id)^{min}.

Zeige: (F S2_{⊆}) und (F S0) ⇒ (F S2_{⊇})

Sei i ∈ M(ϕ, Id)^{min}. Dann gilt {i′} = ⟨ϕ⟩i∩M(ϕ, μ^{−1})^{max} für ein i′ ∈ M, da der ϕ-Orbit nach (F S0) endlich ist. Weiter gilt nach (F S2_{⊆}) auch i′ ∈ M(ϕ, Id)^{min}. So erhalten wir {i} = ⟨ϕ⟩i ∩ M(ϕ, Id)^{min} = {i′} und damit i ∈ M(ϕ, μ^{−1})^{max}.

Zeige: (F S2) und (F S3) ⇒ (F S4_{⊆})

Sei i ∈ M(ϕ, Id)^{min} = M(ϕ, μ^{−1})^{max}. Sei weiter j ∈ M mit μ^{−1}(i) < μ^{−1}(j). Zu zeigen ist i < j. Wegen i ∈ M(ϕ, μ^{−1})^{max} gilt j ∉ ⟨ϕ⟩i. Sei j_{0} ∈ ⟨ϕ⟩j mit j_{0} ∈ M(ϕ, Id)^{min}. Für dieses eindeutig bestimmte Element j_{0} gilt dann auch j_{0} ∈ M(ϕ, μ^{−1})^{max}. Es folgt μ^{−1}(j) ≤ μ^{−1}(j_{0}) und folglich auch μ^{−1}(i) < μ^{−1}(j_{0}). Nach (FS3) folgt i < j_{0}. Andererseits ist j_{0} ∈ M(ϕ, Id)^{min} und somit ist j_{0} ≤ j und mithin i < j; d. h. es gilt i ∈ Rekorde(μ^{−1}), wie behauptet.

Zeige: (F S2) und (F S3) ⇒ (F S4_{⊇})

Sei i ∈ M \ M(ϕ, μ^{−1})^{max} = M \ M(ϕ, Id)^{min} und sei i_{0} ∈ ⟨ϕ⟩i das minimale Element in ⟨ϕ⟩i ⊆ ℕ, also {i_{0}} = ⟨ϕ⟩i ∩ M(ϕ, Id)^{min}. Dann ist i > i_{0}. Andererseits ist i_{0} ∈ M(ϕ, μ^{−1})^{max} nach (FS2) und somit gilt μ^{−1}(i) < μ^{−1}(i_{0}). Folglich ist i ∈ M \ Rekorde(μ^{−1}).

Zeige: (F S4_{⊆}) ⇒ (F S3)

(F S4_{⊆}) lautet als Implikation geschrieben:

i ∈ M(ϕ, μ^{−1})^{max}, i′ ∈ M und μ^{−1}(i) < μ^{−1}(i′) impiziert i < i′.

(F S4_{⊆}) ist somit eine Verschärfung von (F S3).

Zeige: (F S1) und (F S4) ⇒ (F S2_{⊇})

Sei i ∈ M \ M(ϕ, μ^{−1})^{max} gewählt. Da aus (F S1) auch (F S0) folgt, ist ⟨ϕ⟩i endlich. Somit gibt es ein j ∈ ⟨ϕ⟩i, für daß j ∈ M(ϕ, μ^{−1})^{max} gilt. Es gibt jetzt zwei Fälle: entweder gilt i > j, dann ist i ∈ M \M(ϕ, Id)^{min} und wir sind fertig, oder es gilt i < j. Sei nun also i < j. Da i ∈ M \Rekorde(μ^{−1}) nach (F S4) gilt, existiert ein j′ ∈ M mit μ^{−1}(i) < μ^{−1}(j′) und i > j′. Wegen j ∈ Rekorde(μ^{−1}) kann μ^{−1}(j) ≤ μ^{−1}(j′) nicht gelten, weil sonst j ≤ j′ und somit i < j′ folgte; also muß μ^{−1}(i) < μ^{−1}(j′) < μ^{−1}(j) gelten. Nach (F S1) und Lemma 3.1(5) gilt dann aber j′ ∈ ⟨ϕ⟩i und wegen i > j′ auch i ∈ M \ M(ϕ, Id)^{min}.

q.e.d.

Mit anderen Worten, die Permutation μ bestimmt vermöge

a_{1} := μ^{−1}(1),
a_{r+1} := μ^{−1}(min{μ(i) | i ≥ a_{r} + 1}),

für alle r ∈ ℕ mit a_{r} < sup(M), rekursiv eine monoton wachsende Folge a_{1} < a_{2} < … < a_{r} < … mit sup({a_{1}, a_{2}, …}) = sup(M), so daß ein ϕ ∈ M!_{fin} genau dann zu μ in der Relation F S steht, wenn ϕ = (μ(1), …, μ(a_{1}))(μ(a_{1} + 1), …, μ(a_{2})) … gilt. Zu jedem μ ∈ M! gibt es also genau ein ϕ ∈ M!_{fin}, welches zu μ in der Relation F S steht. Und für dieses ϕ gilt insbesondere

(FS∗)  μ(1) = ϕ(μ(a_{1})) = ϕ(1).

Umgekehrt existiert aber auch zu jedem ϕ genau ein solches μ: Man ordne die Zyklen (i, ϕ(i), ϕ^{2}(i), …, ϕ^{r−1}(i)), wobei r = #⟨ϕ⟩(i) ist, von ϕ so, daß erstens in jedem Zyklus das letzte Element das kleinste der in diesem Zyklus auftretenden Zahlen ist und ordne dann die Zyklen entsprechend der (natürlichen) Reihenfolge dieser Elemente und erhält für ϕ eine eindeutig bestimmte Darstellung der Form:

ϕ = (i_{11}, i_{12}, …, i_{1r_{1}})(i_{21}, i_{22}, …, i_{2r_{2}}) …

mit

i_{νr_{ν}} ≤ i_{νρ} für alle ρ = 1, …, r_{ν}

und

i_{1r_{1}} < i_{2r_{2}} < …

insbesondere also i_{1r_{1}} = 1. Dann steht ein μ ∈ M! genau dann zu ϕ in der Relation F S, wenn die Permutation μ jedes p ∈ M gerade auf das p-te Element der Folge i_{11}, i_{12}, …, i_{1r_{1}}, i_{21}, i_{22}, …, i_{2r_{2}}, i_{31}, … abbildet. Damit ergibt sich das folgende Lemma.

Lemma 4.2 Die Foata–Schützenberger–Relation F S ist der Graph einer bijektiven Abbildung M! ˜ ⟶ M!_{fin}.

Bemerkung 4.1 Erfüllt (μ, ϕ) die Foata–Schützenberger–Relation F S, so gibt es nach (F S2), (F S4) und Bemerkung 2.2 eine Bijektion zwischen den Rekorden von μ^{−1} und den Bahnen von ϕ: Rekorde(μ^{−1}) = M(ϕ, Id)^{min} ⟷ ⟨ϕ⟩\M.

Bei M. Lothaire finden wir diese Relation unter dem Namen ”erste fundamentale Transformation“ [Lot83, 10.2]. Eine Verallgemeinerung auf Worte ist in [Lot83, 10.5] beschrieben, die D. Foata (1965) konstruierte. Eine ähnliche Zerlegung von Worten ist die Lyndonwortzerlegung [Lot83, 5.1]. Eine genauere Beschreibung der Historie der Foata–Schützenberger–Relation und deren Verallgemeinerungen finden wir in [Lot83, 10.Notes]. Danach ist diese Bijektion schon implizit bei J. Riordan [Rio58, 8.6]^{7} verwendet worden. Die älteste Quelle, in der diese Bijektion explizit konstruiert wird, ist bei A. Rényi in [Ren62, p 111] zu finden. Interessanterweise ist diese Arbeit von Kombinatorikern^{8} nie zitiert worden. Seine Arbeit wird nur von den Statistikern^{9} hinsichtlich der dort bewiesenen Grenzwertsätze wahrgenommen. Statt Rekorde lassen sich auch allgemeine Mittelwerte verwenden, um die Rekordzerlegung zu definieren. Dies ist von H. D. Brunk in [Bru64]^{10} insbesondere im Zuge einer Verallgemeinerung des Lemmas von Spitzer (1956) gemacht worden.

7J. Riordan drückt sich an dieser Stelle ziemlich unklar aus. Etwas ausführlicher ist die in [Rio58] betrachtete Situation bei I. Kaplansky und J. Riordan in [KaR46] beschrieben. In dieser Arbeit wird aber mit Ein- und Ausschlußargumenten gearbeitet. Eine implizite Verwendung der Foata–Schützenberger–Relation kann ich nicht erkennen. Für eine kombinatorische Interpretation des bei J. Riordan auftretenden Rook–Polynomes von E. A. Bender siehe [Knu73, 5.1.3 Exercise 19]. Alternative Interpretationen gibt es von M. Wachs und D. White in [WaW91].

8Eine Ausnahme ist L. Comtet in [Com74, p 258 Exercise 10 (3)]. Bemerkenswerter Weise zieht aber L. Comtet an dieser Stelle keine Verbindung zu [Com74, 1.18.IV&V], wo er zeigt, wie D. Foata und A. Fuchs in [FoF70] aus der Foata–Schützenberger–Relation und einer Form der Prüfer–Korrespondenz eine Bijektion von M^{M} zu dem Worten auf M der Länge #M konstruieren. Diese Konstruktion liefert in den Spezialfällen gerade die Prüfer– beziehungsweise Foata– Schützenberger–Korrespondenz. Eine andere Bijektion zwischen Bäumen auf M mit zwei ausgezeichneten Punkten und den Abbildungen von M nach M konstruiert G. Labelle in [Lab81]. Mit einer gewichteten Version dieser Bijektion gibt er einen direkten Beweis der Bijektivität, einen bijektiven Beweis der Lagrange–Inversion. Einen breiteren historischen Überblick gibt I. M. Gessel in [Ges87].

9Siehe hierzu den Überblicksartikel von N. Glick über Rekorde [Gli78].

10Insbesondere findet sich in dieser Arbeit auch eine allgemeine Fassung des Lemmas von Raney, das ähnlich auch bei von A. Dvoretzky und T. Motzkin [DvM47] vorkommt. Diese verallgemeinerte Foata–Schützenberger–Korrespondenz ist erst vor kurzem von A. Ehrenfeucht, J. Haemer und D. Haussler in [EHH87] wiederentdeckt, und zu algorithmischen Zwecken ausgeschlachtet worden. Die Autoren beschreiben, wie man zufällige Bäume zu gegebenem Typ erzeugt sowie die konvexe Hülle von n Punkten in der Ebene mit O(n log n) Operationen berechnet.

Verschiedene Anwendungen finden wir bei D. Foata und M. P. Schützenberger in [FoS70, Cha. I]^{11}, bei Ö. Eg̃eciog̃lu in [Ege90]^{12} oder bei D. E. Knuth in [Knu68, 1.3.3]^{13}. Die Benennung dieser Bijektion nach Foata und Schützenberger ist wohl zuerst von I. J. Goulden und D. M. Jackson in [GoJ83, [3.3.17]] vorgenommen worden. In dieser Arbeit ist die Bijektion für Permutationen auf ℕ verallgemeinert worden.

Ist M = ℕ so ist ℕ!_{fin} echt in ℕ! enthalten. Daß diese beiden Mengen trotzdem gleichmächtig sind, ist nicht verwunderlich, da nach W. Sirpiński [Sie57, XVI.2.4] für alle Kardinalzahlen m, n, wobei n nicht endlich ist, mit Hilfe des Auswahlaxioms gilt

m^{n} = 2^{n} für 1 < m ≤ n.

Eine weitere einfache Eigenschaft der Foata–Schützenberger–Korrespondenz F S ist, daß sie konnexen nur konnexe Permutationen zuordnet. Diese Eigenschaft wird im Verlauf der Arbeit aber nicht benötigt.

5 transitiv entspricht konnex

Lemma 5.1 Ist ((τ; e), w) ∈ T_{1}(E) so sind äquivalent:

(1) (τ; e) ∈ Ξ_{2}(E, k)
(2)  w ∈ Θ_{2}(E, k)

Beweis

Zu (1) ⇒ (2)

Annahme: w ∈ Θ_{1}(E, k) \ Θ_{2}(E, k).

Das heißt, es gibt eine nicht–triviale Teilmenge E′ von E (E ≠ E′ ≠ ∅) mit w_{ϵ}(E′) = ℕ_{E′} für alle ϵ ∈ {0, 1, …, k − 1}, und damit w_{ϵ}(E \ E′) = ℕ_{E} \ ℕ_{E′} für alle ϵ ∈ {0, 1, …, k − 1}. Da (τ_{0}, τ_{1}, …, τ_{k−1}) transitiv auf E mit endlichen Orbits operieren, gibt es ein ϵ ∈ {0, 1, …, k − 1}und ein f ∈ E \E′ mit der Eigenschaft τ_{ϵ}(f) ∈ E′. Betrachte nun {f′} := E(τ_{ϵ}, w_{ϵ})^{max}∩⟨τ_{ϵ}⟩(f). Da w_{ϵ}(f′) ≥ w_{ϵ}(f) ist, liegt f′ auch in E \ E′. Nach (T_{ϵ}2) gilt aber f′ ∈ E(τ_{ϵ}, w_{ϵ+1})^{min} und somit w_{ϵ+1}(f′) ≤ w_{ϵ+1}τ_{ϵ}(f). Dies führt auf den Widerspruch f′ ∈ E′.

11Es werden z. B. eine Bijektion zwischen der den Permutationen σ auf {1, 2, …, n} mit k = #{i ∈ ℕ | σ(i) > σ(i + 1), i < n} und den Permutationen σ auf {1, 2, …, n} mit k = #{i ∈ ℕ | σ(i) > i, i ≤ n} und eine Bijektion zwischen den fixpunkfreien Permutationen auf {1, 2, …, n} und den Permutationen σ auf {1, 2, …, n} mit σ(1) ≠ 1 und σ(i) + 1 ≠ σ(i + 1) für alle 1 ≤ i < n konstruiert.

12Die Determinate einer schiefsymmetrischen Matrix ist das Quadrat einer Pfaffschen Form. Der Author gibt einen kombinatorischen Beweis, in dem er eine signumerhaltende Bijektion konstruiert.

Die Vorzeichen der Terme der Pfaffschen From ergeben sich als das Signum der Foata-Schützen-berger Transformierten von fixpunktfreien Involutionen.

13Er berechnet die Komplexität eines Algorithmus zur Bestimmung des Maximums einer Liste.

Zu (2) ⇒ (1) Annahme: τ_{0}, τ_{1}, …, τ_{k−1} operieren nicht transitiv auf E. Dann gibt es eine Teilmenge E′ ⊂ E mit ∅ ≠ E′ ≠ E mit τ_{ϵ}(E′) = E′ für alle ϵ ∈ {0, 1, …, k − 1}und e_{0} ∈ E′. Wegen (Ξ1) τ_{ϵ−1}(e_{ϵ}) = e_{ϵ−1} gilt auch e_{ϵ} ∈ E′ für alle ϵ ∈ {0, 1, …, k − 1}. Sei jetzt

Δ_{ϵ} := {f ∈ E′ | f′ ∈ E und w_{ϵ}(f′) ≤ w_{ϵ}(f) impliziert f′ ∈ E′},

dann gelten für ϵ ∈ {0, 1, …, k − 1}:

1. e_{ϵ} ∈ Δ_{ϵ} ⊆ E′

2. w_{ϵ}(Δ_{ϵ}) = ℕ_{Δ_{ϵ}}

3. Δ_{ϵ} = {f ∈ E′ | für alle f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} mit w_{ϵ}(f′) ≤ w_{ϵ}(f) gilt f′ ∈ E′} Beweis: Die Inklusion ”⊆“ folgt aus der Definition von Δ_{ϵ}. Zum Beweis der Inklusion ”⊇“ sei zu f ∈ E′ mit {f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} | w_{ϵ}(f′) ≤ w_{ϵ}(f)} ⊆ E′ ein f′ ∈ E mit w_{ϵ}(f′) ≤ w_{ϵ}(f) gewählt. Sei {f′′} := E(τ_{ϵ}, w_{ϵ})^{max} ∩ ⟨τ_{ϵ}⟩f′. Gilt w_{ϵ}(f′′) ≤ w_{ϵ}(f), so folgt f′′ ∈ E′ und damit auch f′ ∈ ⟨τ_{ϵ}⟩f′′ ⊆ E′. Andernfalls gilt w_{ϵ}(f′) ≤ w_{ϵ}(f) ≤ w_{ϵ}(f′′) und es folgt nach Lemma 3.1(5) ⟨τ_{ϵ}⟩(f′) = ⟨τ_{ϵ}⟩(f) = ⟨τ_{ϵ}⟩(f′′), also ebenfalls f′ ∈ ⟨τ_{ϵ}⟩f ⊆ E′. Bemerkung: Nur die Inklusion ”⊇“ wird in 4 benötigt.

4. Δ_{ϵ+1} ⊆ Δ_{ϵ} Beweis: Sei f ∈ Δ_{ϵ+1}, f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} und w_{ϵ}(f′) ≤ w_{ϵ}(f). Aus (T_{ϵ}3’) folgt w_{ϵ+1}(f′) ≤ w_{ϵ+1}(f) und damit f′ ∈ E′. f′ erfüllt somit die Bedingungen von 3. Also gilt f ∈ Δ_{ϵ}.

5. Δ_{0} = Δ_{1} = … = Δ_{k−1} Dies gilt, da Δ_{0} ⊆ Δ_{k−1} ⊆ … ⊆ Δ_{1} ⊆ Δ_{0} nach 4.

Setze dann E′′ := Δ_{0} so gilt nach 2. und 5. für alle ϵ ∈ {0, 1, …, k − 1}die Beziehung w_{ϵ}(E′′) = ℕ_{E′′}. Da ∅ ≠ E′′ ≠ E liegt w nicht in Θ_{2}(E, k).

q.e.d.

6 von Θ_{1} nach Ξ_{1}

Als nächstes zeigen wir, daß (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k) zu (τ; e) ∈ Ξ_{1}(E, k) genau dann in der Relation T_{1} steht, wenn für alle ϵ ∈ {0, 1, …, k − 1}die Permutation μ = μ_{ϵ} := w_{ϵ+1}w_{ϵ}^{−1} von M := ℕ_{E} zu der Permutation ϕ = ϕ_{ϵ} := w_{ϵ+1}τ_{ϵ}w_{ϵ+1}^{−1} in der Relation F S steht und w_{ϵ}(e_{ϵ}) = 1 gilt. Dies folgt leicht durch Kombination der folgenden Lemmata:

Lemma 6.1 Für (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k), (τ; e) ∈ Ξ_{1}(E, k) und ϵ ∈ {0, 1, …, k − 1}gilt für alle f ∈ E die Ungleichung w_{ϵ}τ_{ϵ}(f) ≤ w_{ϵ}(f) + 1 genau dann, wenn mit μ = μ_{ϵ} und ϕ = ϕ_{ϵ} wie oben für alle i ∈ M := ℕ_{E} die Ungleichung μ^{−1}(ϕ(i)) ≤ μ^{−1}(i) + 1 gilt.

Beweis Für ein f ∈ E und i ∈ M mit w_{ϵ+1}(f) = i gilt w_{ϵ}τ_{ϵ}(f) ≤ w_{ϵ}(f) + 1 genau dann, wenn (w_{ϵ}w_{ϵ+1}^{−1})(w_{ϵ+1}τ_{ϵ}w_{ϵ+1}^{−1})(w_{ϵ+1}(f)) ≤ (w_{ϵ}w_{ϵ+1}^{−1})(w_{ϵ+1}(f))+1, das heißt

μ^{−1}(ϕ(i)) ≤ μ^{−1}(i) + 1 gilt.

q.e.d.

Lemma 6.2 Für (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k) und (τ; e) ∈ Ξ_{1}(E, k), ϵ ∈ {0, 1, …, k − 1}und μ = μ_{ϵ}, ϕ = ϕ_{ϵ} wie oben gilt:

w_{ϵ+1}(E(τ_{ϵ}, w_{ϵ+1})^{min}) = M(ϕ, Id)^{min}

und

w_{ϵ+1}(E(τ_{ϵ}, w_{ϵ})^{max}) = M(ϕ, μ^{−1})^{max}.

Beweis Für i ∈ M und f = w_{ϵ+1}^{−1}(i) ∈ E gilt i ≤ j beziehungsweise μ^{−1}(i) ≥ μ^{−1}(j) für alle j ∈ ⟨ϕ⟩i = ⟨w_{ϵ+1}τ_{ϵ}w_{ϵ+1}^{−1}⟩i = w_{ϵ+1}(⟨τ_{ϵ}⟩f) offenbar genau dann, wenn für alle f′ ∈ ⟨τ_{ϵ}⟩f die Ungleichung w_{ϵ+1}(f) ≤ w_{ϵ+1}(f′), beziehungsweise w_{ϵ}(f) =

μ^{−1}(i) ≥ μ^{−1}(w_{ϵ+1}^{−1}(f′)) = w_{ϵ}(f′) gilt.

q.e.d.

Lemma 6.3 Mit (w_{0}, w_{1}, …, w_{k−1}), (τ; e), μ und ϕ wie oben gilt w_{ϵ+1}(f) < w_{ϵ+1}(f′) für alle f, f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} mit w_{ϵ}(f) < w_{ϵ}(f′) genau dann, wenn für alle i, i′ ∈ M(ϕ, μ^{−1})^{max} mit μ^{−1}(i) < μ^{−1}(i′) die Ungleichung i < i′ gilt.

Beweis Für i, i′ ∈ M mit f = w_{ϵ+1}^{−1}(i) ∈ E und f′ = w_{ϵ+1}^{−1}(i′) ∈ E gilt nach Lemma 6.2 i, i′ ∈ M(ϕ, μ^{−1})^{max} genau dann, wenn f, f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} gilt. Damit gilt die Implikation μ^{−1}(i) < μ^{−1}(i′) ⇒ i < i′ genau dann, wenn die Implikation w_{ϵ}w_{ϵ+1}^{−1}w_{ϵ+1}(f) < w_{ϵ}w_{ϵ+1}^{−1}w_{ϵ+1}(f′) ⇒ w_{ϵ+1}(f) < w_{ϵ+1}(f′), also

w_{ϵ}(f) < w_{ϵ}(f′) ⇒ w_{ϵ+1}(f) < w_{ϵ+1}(f′) gilt.

q.e.d.

Zusammen mit Lemma 4.2, der Foata–Schützenberger–Korrespondenz, folgt aus diesen Beobachtungen, daß es zu (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k) stets genau ein (τ; e) ∈ Ξ_{1}(E, k) gibt, welches zu (w_{0}, w_{1}, …, w_{k−1}) in der Relation T_{1} steht und durch e_{ϵ} := w_{ϵ}^{−1}(1) und τ_{ϵ} := w_{ϵ+1}^{−1}ϕ_{ϵ}w_{ϵ+1} (ϵ ∈ {0, 1, …, k − 1}) definiert ist, wobei ϕ_{ϵ} gerade die zu μ_{ϵ} = w_{ϵ+1}w_{ϵ}^{−1} in der Relation F S stehende Permutation aus E!_{fin} ist. Es ist klar, daß es für jedes ϵ ∈ {0, 1, …, k − 1}keine andere Wahl geben kann und die Lemmata 6.1, 6.2 und 6.3 zeigen, daß es auch für τ_{ϵ} für alle ϵ ∈ {0, 1, …, k − 1}keine andere Wahl gibt und daß das Paar ((τ; e), w) bei dieser Wahl auch (T_{ϵ}0), (T_{ϵ}1), (T_{ϵ}2) und (T_{ϵ}3) erfüllt. Schließlich gilt auch τ_{ϵ}(e_{ϵ+1}) = e_{ϵ} für ϵ ∈ {0, 1, …, k − 1}, da ja τ_{ϵ}(e_{ϵ+1}) = (w_{ϵ+1}^{−1}ϕ_{ϵ}w_{ϵ+1})(w_{ϵ+1}^{−1}(1)) = w_{ϵ+1}^{−1}ϕ_{ϵ}(1) sowie w_{ϵ+1}(e_{ϵ}) = w_{ϵ+1}w_{ϵ}^{−1}(1) = μ_{ϵ}(1) und wegen (F S∗) auch μ_{ϵ}(1) = ϕ_{ϵ}(1) gilt, das heißt, das Paar (τ; e) steht nicht nur in der Relation T_{1} zu w, sondern liegt auch in Ξ_{1}(E, k). Somit ergibt sich mit Bemerkung 4.1 das folgende Lemma.

Lemma 6.4 Mit obiger Bezeichnung gilt ((τ; e), w) ∈ T_{1}(E) genau dann, wenn ((μ_{0}, ϕ_{0}), (μ_{1}, ϕ_{1}), …, (μ_{k−1}, ϕ_{k−1})) ∈ (F S)^{k} ist. Dies induziert die folgenden Bijektionen Rekorde(μ_{ϵ}^{−1}) ⟷ ⟨τ_{ϵ}⟩\E für alle ϵ ∈ {0, 1, …, k − 1}.

Lemma 6.5 Sind ((τ; e), w) ∈ Ξ_{1}(E, k) × Θ_{1}(E, k) und ((τ′; e′), w′) ∈ Ξ_{1}(E′, k) × Θ_{1}(E′, k), so sind mit obiger Notation die folgenden beiden Aussagen äquivalent:

(1) Es gibt σ : E ˜ ⟶ E′, so daß für alle ϵ ∈ {0, 1, …, k − 1} :

τ′_{ϵ} = στ_{ϵ}σ^{−1}, e′_{ϵ} = σ(e_{ϵ}), w′_{ϵ} = w_{ϵ}σ^{−1},

(μ_{ϵ}, ϕ_{ϵ}) = (μ′_{ϵ}, ϕ′_{ϵ}), w_{ϵ}(e_{ϵ}) = w′_{ϵ}(e′_{ϵ}) für ϵ ∈ {0, 1, …, k − 1}. (2)

Beweis Aus (1) folgt (2), da μ′_{ϵ} = w′_{ϵ+1}w′_{ϵ}^{−1} = (w_{ϵ+1}σ^{−1})(σw_{ϵ}^{−1}) = w_{ϵ+1}w_{ϵ}^{−1} = μ_{ϵ}, ϕ′_{ϵ} = w′_{ϵ+1}τ′_{ϵ}w′_{ϵ+1}^{−1} = (w_{ϵ+1}σ^{−1})(στ_{ϵ}σ^{−1})(σw_{ϵ+1}^{−1}) = w_{ϵ+1}τ_{ϵ}w_{ϵ+1}^{−1} = ϕ_{ϵ} und w′_{ϵ}(e′_{ϵ}) = w_{ϵ}σ^{−1}σ(e_{ϵ}) = w_{ϵ}(e_{ϵ}) für ϵ ∈ {0, 1, …, k − 1} gilt. Umgekehrt gilt, aus (2) folgt (1). Denn aus μ_{ϵ} = μ′_{ϵ} folgt w′_{ϵ}^{−1}w_{ϵ} = w′_{ϵ+1}^{−1}w_{ϵ+1}. Setze jetzt σ = w′_{ϵ}^{−1}w_{ϵ}, welches nicht von ϵ abhängt, so folgen τ′_{ϵ} = w′_{ϵ+1}^{−1}ϕ′_{ϵ}w′_{ϵ+1} = w′_{ϵ+1}^{−1}ϕ_{ϵ}w′_{ϵ+1} = w′_{ϵ+1}^{−1}w_{ϵ+1}τ_{ϵ}w_{ϵ+1}^{−1}w′_{ϵ+1} = στ_{ϵ}σ^{−1}, w′_{ϵ} = w_{ϵ}w_{ϵ}^{−1}w′_{ϵ} = w_{ϵ}σ^{−1} und e′_{ϵ} = w′_{ϵ}^{−1}w′_{ϵ}(e′_{ϵ}) = w′_{ϵ}^{−1}w_{ϵ}(e_{ϵ}) = σ(w_{ϵ}) für alle ϵ ∈ {0, 1, …, k − 1}. q.e.d.

7 Fortsetzungslemma und Existenz

Für (τ; e)  ∈  Ξ_{1}(E, k) sei W (τ; e) die Menge der Systeme

(E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) bestehend aus Teilmengen E_{0}, E_{1}, …, E_{k−1} von E und Bijektionen w_{ϵ} : E_{ϵ} ˜ ⟶ ℕ_{E_{ϵ}} für alle ϵ ∈ {0, 1, …, k − 1}, welche den folgenden Bedingungen für alle ϵ ∈ {0, 1, …, k − 1}genügen:

e_{ϵ} ∈ E_{ϵ}; w_{ϵ}(e_{ϵ}) = 1; (TP_{ϵ}1) τ_{ϵ}(E_{ϵ}) = E_{ϵ}; (TP_{ϵ}2) (TP_{ϵ}3) w_{ϵ}(τ_{ϵ}(e)) ≤ w_{ϵ}(e) + 1 für alle e ∈ E_{ϵ}; (TP_{ϵ}4) E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} ⊆ E_{ϵ+1}(τ_{ϵ}, w_{ϵ+1})^{min}; (TP_{ϵ}5) Ist f ∈ E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} so gilt:

f′ ∈ E_{ϵ+1} & w_{ϵ+1}(f′) < w_{ϵ+1}(f) ⇒ f′ ∈ E_{ϵ} & w_{ϵ}(f′) < w_{ϵ}(f).

Bemerkung 7.1 Ist f ∈ E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max}, so ist f ∈ E_{ϵ+1} nach (TP_{ϵ}4), somit ist (TP_{ϵ}5) immer wohldefiniert.

Bemerkung 7.2 Ist (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e), so sind die Mengen E_{0}, E_{1}, …, E_{k−1} nicht leer. Dies ist klar nach (TP_{ϵ}1).

Bemerkung 7.3 Ist (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e), so sind entweder alle E_{0}, E_{1}, …, E_{k−1} unendlich oder alle endlich. Denn ist E_{ϵ} unendlich, so ist auch E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} unendlich, was aus τ_{ϵ} ∈ E!_{fin} und Bemerkung 2.1 folgt. Nach (TP_{ϵ}4) ist dann auch insbesondere auch E_{ϵ+1} unendlich. Durch Iteration dieses Argumentes zeigt man, daß E_{ϵ} unendlich ist für alle ϵ ∈ {0, 1, …, k − 1}.

Lemma 7.1 Ist (τ; e) ∈ Ξ_{1}(E, k) so gilt: W (τ; e) ≠ ∅

Beweis Setze E_{ϵ} = ⟨τ_{ϵ}⟩(e_{ϵ}) und w_{ϵ}(τ_{ϵ}^{i}e_{ϵ}) = 1 + i für i ∈ {0, 1, …, #E_{ϵ} − 1} für alle ϵ ∈ {0, 1, …, k − 1}. Dann sind sicherlich für ϵ ∈ {0, 1, …, k − 1}die Bedingungen (TP_{ϵ}1), (TP_{ϵ}2) und (TP_{ϵ}3) erfüllt. Da E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} = {τ_{ϵ}^{−1}e_{ϵ}} = {e_{ϵ+1}} = E_{ϵ+1}(τ_{ϵ}, w_{ϵ+1})^{min} aus (Ξ1) und w_{ϵ+1}(e_{ϵ+1}) = 1 folgt, ist auch (TP_{ϵ}4) erfüllt. Insbesondere folgt aus f ∈ E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} die Aussage w_{ϵ+1}(f) = 1. Sei jetzt f′ ∈ E_{ϵ+1} dann kann w_{ϵ+1}(f′) < w_{ϵ+1}(f) nie gelten. Bedingung (TP_{ϵ}5) ist also leer und gilt damit trivialerweise.

q.e.d.

Lemma 7.2 Sei (τ; e) ∈ Ξ_{1}(E, k) und sei (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e) mit endlichen Mengen E_{0}, E_{1}, …, E_{k−1}, für die nicht alle E_{0}, E_{1}, …, E_{k−1} gleich sind, also E_{ϵ+1} ⊈ E_{ϵ} für ein ϵ ∈ {0, 1, …, k − 1}gilt. Es existiert dann ein (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e), so daß mit diesem ϵ gelten: E′_{ϵ} ⊃ E_{ϵ}, w′_{ϵ}|_{E_{ϵ}} = w_{ϵ} und E′_{ϵ} enthält genau einen τ_{ϵ}-Orbit mehr als E_{ϵ}. Zu jedem ϵ′ ≠ ϵ mit ϵ′ ∈ {0, 1, …, k − 1}sind E′_{ϵ′} = E_{ϵ′}, w′_{ϵ′} = w_{ϵ′}. Ferner gilt die echte Inklusion E′_{ϵ+1} \ E′_{ϵ} ⊂ E_{ϵ+1} \ E_{ϵ}.

Beweis Es wird zuerst eine Fortsetzung konstruiert, von der dann gezeigt wird, daß sie in W (τ; e) liegt.

Konstruktion einer Fortsetzung Sei ein ϵ, für das E_{ϵ+1} ⊈ E_{ϵ} gilt, fest gewählt. Sei dann f_{0} das bezüglich w_{ϵ+1} kleinste Element in E_{ϵ+1} \ E_{ϵ}. Dann ist ⟨τ_{ϵ}⟩(f_{0}) ∩ E_{ϵ} = ∅ nach (TP_{ϵ}2). Setze E′_{ϵ} := E_{ϵ} ∪ ⟨τ_{ϵ}⟩(f_{0}) und definiere w′_{ϵ} auf ⟨τ_{ϵ}⟩(f_{0}) durch w′_{ϵ}(τ_{ϵ}^{i}(f_{0})) = i + #E_{ϵ} für i ∈ {1, …, #⟨τ_{ϵ}⟩(f_{0})}.

Beweis von (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e)

Nach Konstruktion bekommt f_{0} den größten Wert. Da f_{0} ∉ E′_{ϵ+1} \ E′_{ϵ} aber f_{0} ∈ E_{ϵ+1} \ E_{ϵ} gilt, folgt die echte Inklusion E′_{ϵ+1} \ E′_{ϵ} ⊂ E_{ϵ+1} \ E_{ϵ}. Es ist jetzt zu zeigen, daß für das so definierte (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) die Eigenschaften (TP_{ϵ′}1), (TP_{ϵ′}2), …, (TP_{ϵ′}5) für alle ϵ′ ∈ {0, 1, …, k − 1}gelten. Die Eigenschaften (TP_{ϵ′}1), (TP_{ϵ′}2) und (TP_{ϵ′}3) gelten offensichtlich. (TP_{ϵ′}4) und (TP_{ϵ′}5) ist nur für ϵ′ ∈ {ϵ, ϵ − 1} zu zeigen, da nur in diesen Fällen E′_{ϵ} oder w′_{ϵ} auftreten.

Zeige (TP_{ϵ}4)

Nach Konstruktion ist f_{0} ∈ E_{ϵ+1}(τ_{ϵ}, w_{ϵ+1})^{min}. Somit ist E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} = {f_{0}} ∪ E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} ⊆ E_{ϵ+1}(τ_{ϵ}, w_{ϵ+1})^{min} = E′_{ϵ}(τ_{ϵ}, w′_{ϵ+1})^{min}.

Zeige (TP_{ϵ−1}4)

Dies folgt aus der Inklusionskette E′_{ϵ−1}(τ_{ϵ−1}, w′_{ϵ−1})^{max} = E_{ϵ−1}(τ_{ϵ−1}, w_{ϵ−1})^{max} ⊆ E_{ϵ}(τ_{ϵ−1}, w_{ϵ})^{min} ⊆ E′_{ϵ}(τ_{ϵ−1}, w′_{ϵ})^{min}. Die letzte Inklusion folgt hierbei aus Bemerkung 2.4.

Zeige (TP_{ϵ}5)

Sei f ∈ E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} = {f_{0}}∪E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} und f′ ∈ E′_{ϵ−1} = E_{ϵ−1}. Ist f ≠ f_{0} so folgt (TP_{ϵ}5) wegen (TP_{ϵ}5) für (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}). Ist f = f_{0} so ist w_{ϵ}(f) = #E′_{ϵ}, und damit ist zum Nachweis von (TP_{ϵ}5) nur f′ ∈ E′_{ϵ} zu zeigen. Da aber f_{0} ∈ E_{ϵ−1} \ E_{ϵ} minimal bezüglich w_{ϵ−1} gewählt ist, folgt aus f′ ∈ E_{ϵ−1} und w_{ϵ−1}(f′) < w_{ϵ−1}(f) sogar f′ ∈ E_{ϵ}.

Zeige (TP_{ϵ−1}5)

Sei f ∈ E′_{ϵ−1}(τ_{ϵ−1}, w′_{ϵ−1})^{max} = E_{ϵ−1}(τ_{ϵ−1}, w_{ϵ−1})^{max}, f′ ∈ E′_{ϵ} und w′_{ϵ}(f′) < w′_{ϵ}(f). Wegen E_{ϵ−1}(τ_{ϵ−1}, w_{ϵ−1})^{max} ⊆ E_{ϵ} folgt f′ ∈ E_{ϵ} und damit folgt auch w_{ϵ−1}(f′) < w_{ϵ−1}(f), da (TP_{ϵ−1}5) für (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) vorausgesetzt wurde.

q.e.d.

Eine Fortsetzung für nicht endliche Mengen E_{0}, E_{1}, …, E_{k−1} kann es nicht geben. Dies folgt schon daraus, daß w_{0}, w_{1}, …, w_{k−1} Bijektionen nach ℕ sind. Somit sind alle (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e) mit nicht endlichen E_{0}, E_{1}, …, E_{k−1} maximale Elemente bezüglich Fortsetzung. Daß sogar alle E_{0}, E_{1}, …, E_{k−1} gleich sind, zeigt das folgende Lemma.

Lemma 7.3 Sei (τ; e) ∈ Ξ_{1}(E, k) und sei (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e) mit nicht endlichen Mengen E_{0}, E_{1}, …, E_{k−1}, so gilt E_{0} = E_{1} = … = E_{k−1}.

Beweis Nehmen wir an, es gäbe ein ϵ ∈ {0, 1, …, k − 1}mit E_{ϵ+1} \ E_{ϵ} ≠ ∅. Sei dann f′ das bezüglich w_{ϵ+1} kleinste Element ^{14} in E_{ϵ+1} \ E_{ϵ}. Nach (Ξ0) gilt τ_{ϵ} ∈ E!_{fin}. Daher ist auch die Menge E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} nicht endlich. Da w_{ϵ+1} eingeschränkt auf E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} injektiv ist, gibt es ein f ∈ E_{ϵ}(τ_{ϵ}, w_{ϵ})^{max} ⊆ E_{ϵ+1}, für das w_{ϵ+1}(f′) < w_{ϵ+1}(f) gilt. Die Bedingung (TP_{ϵ}5) fordert nun, daß insbesondere f′ ∈ E_{ϵ} gilt, was ein Widerspruch zur Wahl von f′ ist. Wir haben somit gezeigt, daß E_{0} = E_{1} = … = E_{k−1}.

q.e.d.

Lemma 7.4 Für (w_{0}, w_{1}, …, w_{k−1}) ∈ Θ_{1}(E, k) und (τ; e) ∈ Ξ_{1}(E, k) läßt sich jedes (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e), wobei die E_{0}, E_{1}, …, E_{k−1} nicht alle gleich sind, fortsetzen zu einem (E′, E′, …, E′; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e), d. h. es gelten: E_{0} ∪ E_{1} ∪ … ∪ E_{k−1} ⊆ E′ sowie w′_{ϵ}|_{E_{ϵ}} = w_{ϵ} für alle ϵ ∈ {0, 1, …, k − 1}.

Beweis Sei (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e) gegeben, wobei die E_{0}, E_{1}, …, E_{k−1} nicht alle gleich sind. Folglich sind die Mengen E_{0}, E_{1}, …, E_{k−1} endlich, was aus dem vorigen Lemma 7.3 und der Bemerkung 7.3 folgt. Endweder landen wir bei dem gewünschten (E′, E′, …, E′; w′_{0}, w′_{1}, …, w′_{k−1}) nach einer endlichen Anzahl von Fortsetzungen nach Lemma 7.2, in welchem Fall E′ eine endliche Menge ist, oder wir erhalten eine unendliche Folge von Fortsetzungen (E_{0}^{i}, E_{1}^{i}, …, E_{k−1}^{i}; w_{0}^{i}, w_{1}^{i}, …, w_{k−1}^{i})_{i∈ℕ} mit (E_{0}^{1}, E_{1}^{1}, …, E_{k−1}^{1}; w_{0}^{1}, w_{1}^{1}, …, w_{k−1}^{1}) = (E_{0}, E_{1}, …, E_{k−1}; w_{0}, w_{1}, …, w_{k−1}), E_{ϵ}^{i} endlich, E_{ϵ}^{i} ⊆ E_{ϵ}^{j} und w_{ϵ}^{j}|_{E_{ϵ}^{i}} = w_{ϵ}^{i} für i ≤ j und ϵ ∈ {0, 1, …, k − 1}. Bilde (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) als induktiven Limes dieser Folge, d. h. setze für ϵ ∈ {0, 1, …, k − 1}

14Dies ist die kanonische Auswahlfunktion. Jedes andere Element tut es genauso.

E′_{ϵ} := ⋃_{i∈ℕ} E_{ϵ}^{i},
w′_{ϵ} := lim_{⟶} w_{ϵ}^{i} : E_{ϵ}^{i} ˜ ⟶ ℕ_{E_{ϵ}^{i}}.

Wir werden jetzt (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e) zeigen. Als erstes folgt aus Bemerkung 2.3, daß ⋃_{i∈ℕ} E_{ϵ}^{i}(τ_{ϵ}, w_{ϵ}^{i})^{max} = ⋃_{i∈ℕ}(E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} ∩ E_{ϵ}^{i}) = E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} gilt. Analog folgt für die Minima mit Bemerkung 2.4 die Gleichung ⋃_{i∈ℕ} E_{ϵ+1}^{i}(τ_{ϵ}, w_{ϵ+1}^{i})^{min} = ⋃_{i∈ℕ}(E′_{ϵ+1}(τ_{ϵ}, w′_{ϵ+1})^{min} ∩ E_{ϵ+1}^{i}) = E′_{ϵ+1}(τ_{ϵ}, w′_{ϵ+1})^{min}. Jetzt können wir leicht die Bedingungen (TP_{ϵ}1) bis (TP_{ϵ}5) für (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) verifizieren. Aus e_{ϵ} ∈ E_{ϵ} ⊆ E′_{ϵ} und w′_{ϵ}(e_{ϵ}) = w_{ϵ}(e_{ϵ}) = 1 folgt (TP_{ϵ}1). Aus τ_{ϵ}(E′_{ϵ}) := τ_{ϵ}(⋃_{i∈ℕ} E_{ϵ}^{i}) = ⋃_{i∈ℕ} τ_{ϵ}(E_{ϵ}^{i}) = ⋃_{i∈ℕ} E_{ϵ}^{i} =: E′_{ϵ} folgt (TP_{ϵ}2). Ist f ∈ E′_{ϵ} so ist f ∈ E_{ϵ}^{i} und damit τ_{ϵ}(f) ∈ E_{ϵ}^{i} für ein i ∈ ℕ. Damit gilt w′_{ϵ}(τ_{ϵ}(f)) = w_{ϵ}^{i}(τ_{ϵ}(f)) ≤ w_{ϵ}^{i}(f) + 1 = w′_{ϵ}(f) + 1 und somit (TP_{ϵ}3). Aus E_{ϵ}^{i}(τ_{ϵ}, w_{ϵ}^{i})^{max} ⊆ E_{ϵ+1}^{i}(τ_{ϵ}, w_{ϵ+1}^{i})^{min} für alle i ∈ ℕ folgt nun E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} = ⋃_{i∈ℕ} E_{ϵ}^{i}(τ_{ϵ}, w_{ϵ}^{i})^{max} ⊆ ⋃_{i∈ℕ} E_{ϵ+1}^{i}(τ_{ϵ}, w_{ϵ+1}^{i})^{min} = E′_{ϵ+1}(τ_{ϵ}, w′_{ϵ+1})^{min} und somit (TP_{ϵ}4). Sind schließlich f ∈ E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} und f′ ∈ E′_{ϵ+1} so existieren i, j ∈ ℕ mit f ∈ E_{ϵ}^{i} ⊆ E_{ϵ}^{p}, f′ ∈ E_{ϵ+1}^{j} ⊆ E_{ϵ+1}^{p} und p = max(i, j). Somit gilt f ∈ E_{ϵ}^{p}(τ_{ϵ}, w_{ϵ}^{p})^{max} = E′_{ϵ}(τ_{ϵ}, w′_{ϵ})^{max} ∩ E_{ϵ}^{p} nach Bemerkung 2.3. Gilt jetzt w′_{ϵ+1}(f′) < w′_{ϵ+1}(f), so folgt w_{ϵ+1}^{p}(f′) = w′_{ϵ+1}(f′) < w′_{ϵ+1}(f) = w_{ϵ+1}^{p}(f). Damit ist die Voraussetzung von (TP_{ϵ}5) für (E_{0}^{p}, E_{1}^{p}, …, E_{k−1}^{p}; w_{0}^{p}, w_{1}^{p}, …, w_{k−1}^{p})) erfüllt. Es folgen also f′ ∈ E_{ϵ}^{p} ⊆ E′_{ϵ} und w′_{ϵ}(f′) = w_{ϵ}^{p}(f′) < w_{ϵ}^{p}(f) = w′_{ϵ}(f). Damit sind die Implikationen von (TP_{ϵ}5) für (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) gezeigt. Hiermit ist also (E′_{0}, E′_{1}, …, E′_{k−1}; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e) gezeigt. Da nach dem Schubfachprinzip nicht alle E′_{0}, E′_{1}, …, E′_{k−1} endliche Mengen sein können, folgt nach Bemerkung 7.3, daß alle E′_{0}, E′_{1}, …, E′_{k−1} nicht endliche Mengen sind. Nach Lemma 7.3 folgt dann E′_{0} = E′_{1} = … = E′_{k−1}.

q.e.d.

Statt der obigen induktiven Definition können wir auch mit dem Zornschen Lemma schließen [Lev79, Cha. V]. Dies ist möglich, da nach Lemma 7.2 und Lemma 7.3 maximale Elemente bezüglich Fortsetzung nur von der Form E_{0} = E_{1} = … = E_{k−1} sein können.

Nach Lemma 7.1 und 7.4 gibt es zu (τ; e) ∈ Ξ_{1}(E, k) ein (E′, E′, …, E′; w′_{0}, w′_{1}, …, w′_{k−1}) ∈ W (τ; e). Ist nun (τ; e) ∈ Ξ_{2}(E, k), so folgt aus (TP_{ϵ}2) und Bemerkung 7.2, τ_{0}(E′) = τ_{1}(E′) = … = τ_{k−1}(E′) = E′ ≠ ∅, sogar E′ = E, also existieren w_{0}, w_{1}, …, w_{k−1} : E ˜ ⟶ ℕ_{E} mit (E, E, …, E; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e).

Lemma 7.5 Für w  ∈  Θ_{1}(E, k) und (τ; e)  ∈  Ξ_{1}(E, k) gilt

(E, E, …, E; w_{0}, w_{1}, …, w_{k−1}) ∈ W (τ; e) genau dann, wenn w zu (τ; e) in der Relation T_{1} steht.

Beweis Es ist also zu zeigen, daß für E_{0} = E_{1} = … = E_{k−1} = E die Bedingungen (T_{ϵ}0), (T_{ϵ}1), (T_{ϵ}2) und (T_{ϵ}3) zu den Bedingungen (TP_{ϵ}1), …, (TP_{ϵ}5) äquivalent sind. Für (T_{ϵ}0) und (T_{ϵ}1) ist dies klar. Zu zeigen bleiben (T_{ϵ}2) und (T_{ϵ}3).

Zu (T_{ϵ}2)

Es ist zu zeigen, daß aus der Inklusion E(τ_{ϵ}, w_{ϵ})^{max} ⊆ E(τ_{ϵ}, w_{ϵ+1})^{min} die Gleichheit E(τ_{ϵ}, w_{ϵ})^{max} = E(τ_{ϵ}, w_{ϵ+1})^{min} folgt. Dies gilt, da für f ∈ E(τ_{ϵ}, w_{ϵ+1})^{min} und {f′} := ⟨τ_{ϵ}⟩f ∩ E(τ_{ϵ}, w_{ϵ})^{max} aus f′ ∈ E(τ_{ϵ}, w_{ϵ+1})^{min} ∩ ⟨τ_{ϵ}⟩f = {f} sofort f = f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} folgt. Dabei ist (Ξ0) wesentlich.

Zu (T_{ϵ}3)

(TP_{ϵ}5) ist offensichtlich zu (T_{ϵ}3’) äquivalent. Da (T_{ϵ}3’) eine Verschärfung von (T_{ϵ}3) war, impliziert (TP_{ϵ}5) auch (T_{ϵ}3). Nach Bemerkung 2.7 folgen aus (T_{ϵ}2) und (T_{ϵ}3) aber (T_{ϵ}3’) und damit (TP_{ϵ}5).

q.e.d.

Damit ist das folgende Lemma gezeigt:

Lemma 7.6 Ist (τ; e) ∈ Ξ_{2}(E, k) gegeben, so existiert ein w ∈ Θ_{1}(E, k), welches zu (τ; e) in der Relation T_{1} stehen.

8 Eindeutigkeit

Lemma 8.1 Ist (τ; e) ∈ Ξ_{2}(E, k) und sind (w_{0}, w_{1}, …, w_{k−1}), (w′_{0}, w′_{1}, …, w′_{k−1}) ∈ Θ_{1}(E, k), so daß sowohl (τ; e) und w als auch (τ; e) und w′ in der Relation T_{1} stehen, so folgt w = w′.

Beweis Für alle ϵ ∈ {0, 1, …, k − 1}definiere nur n_{ϵ} := min{i ∈ ℕ_{E} | w_{ϵ}^{−1}(i) ≠ w_{ϵ}^{′−1}(i)} und Δ_{ϵ} := {f ∈ E | w_{ϵ}(f) < n_{ϵ}} = {f ∈ E | w′_{ϵ}(f) < n_{ϵ}} also Δ_{ϵ} = {f ∈ E | w_{ϵ}(f′) = w′_{ϵ}(f′) für alle f′ ∈ E mit w_{ϵ}(f′) ≤ w_{ϵ}(f)}. Ist w_{ϵ} = w′_{ϵ} so kann n_{ϵ} := ω definiert werden. Im folgenden wird aber n_{ϵ} nur verwendet, wenn w_{ϵ} ≠ w′_{ϵ} gilt. Wir zeigen jetzt einige Eigenschaften von Δ_{ϵ}:

1. e_{ϵ} ∈ Δ_{ϵ} und n_{ϵ} > 1, da w_{ϵ}(e_{ϵ}) = w′_{ϵ}(e_{ϵ}) = 1, und

2. τ_{ϵ}(Δ_{ϵ}) ⊆ Δ_{ϵ}, da aus f ∈ Δ_{ϵ} und τ_{ϵ}f ∉ Δ_{ϵ} die Ungleichungen n_{ϵ} ≤ w_{ϵ}(τ_{ϵ}f) ≤ w_{ϵ}(f) + 1 ≤ n_{ϵ} und n_{ϵ} ≤ w′_{ϵ}(τ_{ϵ}f) ≤ w′_{ϵ}(f) + 1 ≤ n_{ϵ} folgten und damit w_{ϵ}(τ_{ϵ}f) = w′_{ϵ}(τ_{ϵ}f) = n_{ϵ} im Widerspruch zur Definiton von n_{ϵ}. Wegen (Ξ0) gilt sogar τ_{ϵ}(Δ_{ϵ}) = Δ_{ϵ}. Schließlich gilt auch

3. Δ_{ϵ+1} ⊆ Δ_{ϵ}.

Sei nämlich andernfalls f ∈ Δ_{ϵ+1} \ Δ_{ϵ} bezüglich w_{ϵ+1} minimal gewählt. Dann gilt ⟨τ_{ϵ}⟩f ∩ Δ_{ϵ} = ∅ wegen (2) und folglich gilt f ∈ E(τ_{ϵ}, w_{ϵ+1})^{min} ∩ E(τ_{ϵ}, w′_{ϵ+1})^{min} = E(τ_{ϵ}, w_{ϵ})^{max}∩E(τ_{ϵ}, w′_{ϵ})^{max}, da für f′ ∈ ⟨τ_{ϵ}⟩f ⊆ E\Δ_{ϵ} im Falle f′ ∉ Δ_{ϵ+1} ohnehin w_{ϵ+1}(f′), w′_{ϵ+1}(f′) ≥ n_{ϵ+1} > w_{ϵ+1}(f) = w′_{ϵ+1}(f) gilt, während im Falle f′ ∈ Δ_{ϵ+1} die Ungleichung w_{ϵ+1}(f) = w′_{ϵ+1}(f) ≤ w_{ϵ+1}(f′) = w′_{ϵ+1}(f′) aufgrund der speziellen Wahl von f gelten muß. Aus dem Korollar zu Lemma 3.1 folgt nun wegen {f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} | w_{ϵ}(f′) < w_{ϵ}(f)} ⊆ {f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} | w_{ϵ+1}(f′) < w_{ϵ+1}(f)} ⊆ {f′ ∈ Δ_{ϵ+1} | w_{ϵ+1}(f′) < w_{ϵ+1}(f)} ⊆ Δ_{ϵ} und wegen τ_{ϵ}f ∉ Δ_{ϵ} die Beziehung n_{ϵ} ≤ w_{ϵ}(τ_{ϵ}f) = min{n ∈ ℕ | f′ ∈ E(τ_{ϵ}, w_{ϵ})^{max} und w_{ϵ}(f′) < w_{ϵ}(f) impiziert w_{ϵ}(f′) < n} ≤ min{n ∈ ℕ | f′ ∈ Δ_{ϵ} impliziert w_{ϵ}(f′) < n} = n_{ϵ}, also n_{ϵ} = w_{ϵ}(τ_{ϵ}f) und ebenso n_{ϵ} = w′_{ϵ}(τ_{ϵ}f) im Widerspruch zur Definition von n_{ϵ}.

Nun folgt ∅ ≠ Δ_{0} = Δ_{1} = … = Δ_{k−1} = τ_{0}(Δ_{0}) = τ_{1}(Δ_{1}) = … = τ_{k−1}(Δ_{k−1} und wegen der Transitivität von τ_{0}, τ_{1}, …, τ_{k−1} folgt Δ_{0} = Δ_{1} = … = Δ_{k−1} = E. Somit ist w_{ϵ} = w′_{ϵ} für alle ϵ ∈ {0, 1, …, k − 1}.

q.e.d.

9 Satz und Korollare

Aus den vorangegangenen Abschnitten folgt jetzt der Satz:

Satz 9.1 Die Relation T_{2}(E) ⊆ Ξ_{2}(E, k) × Θ_{2}(E, k) ist der Graph einer Bijektion.

Daraus wollen wir jetzt einige Folgerungen ziehen. Die erste wichtige Beobachtung, die wir machen, ist, daß E! auf den vier Mengen Ξ_{2}(E, k) ⊆ Ξ_{1}(E, k) und Θ_{2}(E, k) ⊆ Θ_{1}(E, k) verträglich mit der Relation T_{2}(E) ⊆ Ξ_{2}(E, k) × Θ_{2}(E, k) operiert, da die definierenden Bedingungen (T_{ϵ}0), (T_{ϵ}1), (T_{ϵ}2) und (T_{ϵ}3) invariant unter E!–Operationen sind, wie auch die Eigenschaften der Transitivität und Konnexität. Die Gruppenoperationen sehen dabei wie folgt aus: τ_{ϵ} → στ_{ϵ}σ^{−1}, e_{ϵ} → σe_{ϵ} und w_{ϵ} → w_{ϵ}σ^{−1} für σ ∈ E!. Beachte, daß die E!–Orbits von Θ_{1}(E, k) gerade k − 1 Permutationen von M := ℕ_{E} vermöge {(w_{0}u^{−1}, w_{1}u^{−1}, …, w_{k−1}u^{−1}) | u ∈ E!} ⟷ {(w_{0}(f), w_{1}(f), …, w_{k−1}(f)) | f ∈ E} ⟷ (w_{1}w_{0}^{−1}, w_{2}w_{0}^{−1}, …, w_{k−1}w_{0}^{−1}) entsprechen, wobei die E!–Orbits von Θ_{2}(E, k) gerade den konnexen Systemen k − 1 Permutationen von M entsprechen, das heißt den Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) ∈ (M!)^{k−1}, für welche für alle 0 < i < sup(M) ein ϵ ∈ {1, 2, …, k − 1} existiert, so daß μ_{ϵ}({1, …, i}) ≠ {1, …, i} gilt. Nach dieser Definition ist natürlich (w_{0}, w_{1}, …, w_{k−1}) genau dann konnex, wenn (w_{1}w_{0}^{−1}, w_{2}w_{0}^{−1}, …, w_{k−1}w_{0}^{−1}) konnex ist.

Der Fall k = 2 verdient besonderer Beachtung. In der Sprache von G. Viennot in [Vie82] entsprechen die Rekorde von w_{0}w_{1}^{−1} den süd–östlich beleuchteten Elementen von (w_{0}, w_{1}), und die Rekorde von w_{1}w_{0}^{−1} entsprechen den nord– westlich beleuchteten Elementen. Betrachtet man auf E die Inversionsordnung von (w_{0}, w_{1}), die definiert ist als ”e ≤ e′ ⇔ w_{0}(e) ≥ w_{0}(e′) & w_{1}(e) ≤ w_{1}(e′)“ nach D. E. Knuth in [Knu73, 5.1.1 Ex 11], so entsprechen die minimalen Elemente dieser Ordnung den Rekorden von w_{0}w_{1}^{−1} und die maximalen Elemente den Rekorden von w_{1}w_{0}^{−1}. Die oben etablierte Bijektion induziert also insbesondere im Falle n = #E < ∞ für α, β ∈ ℕ nach Lemma 6.4 und Lemma 6.5 eine Bijektion zwischen den konnexen Permutationen μ von M = {1, …, n} mit #Rekorde(μ^{−1}) = α und #Rekorde(μ) = β und den Isomorphie–Klassen von Paare (τ; e) aus Ξ_{2}(E, 2) mit #⟨τ_{0}⟩\E = α und #⟨τ_{1}⟩\E = β, wobei selbstverständlich zwei Paare (τ; e) ∈ Ξ_{2}(E, 2) und (τ′; e′) ∈ Ξ_{2}(E′, 2) als isomorph bezeichnet werden, wenn es eine Bijektion σ : E ˜ ⟶ E′ mit τ′_{0} = στ_{0}σ^{−1}, τ′_{1} = στ_{1}σ^{−1}, e′_{0} = σ(e_{0}) und e′_{1} = σ(e_{1}) gibt.

Es folgt, daß es für jeden Abschnitt M = {0, 1, …, i, …} von ℕ – endlich oder unendlich – eine kanonische Bijektion zwischen den konnexen Systemen von Permutationen (μ_{1}, μ_{2}, … μ_{k−1}) von M und den Untergruppen U vom Index #M in der von k Elementen x_{0}, x_{1}, …, x_{k−1} erzeugten Gruppe F_{k} mit x_{0}x_{1} … x_{k−1} ∈ U gibt. Da x_{0}x_{1} … x_{k−1} ∈ U als ein beliebiges Element aus einem freien Erzeugendensystem von F_{k} angesehen werden kann, bedeutet dies, daß es ebenso eine kanonische Bijektion zwischen den konnexen Systemen von Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) von M und den Untergruppen U vom Index #M von F_{k} mit, sagen wir , x_{k−1} ∈ U gibt. Im Falle k = 2 sind diese Untergruppen ihrerseits mittels einer in [DrF85] beschriebenen, einfachen Konstruktion den Untergruppen von F_{k} vom Index #M − 1 umkehrbar eindeutig zugeordnet. Wir erhalten also als Spezialfall das in [DrF85] und [Sil91] beschriebene Resultat. Im allgemeinen korreliert die obige Bijektion für eine Äquivalenzrelation π auf {0, 1, …, k − 1} konnexe Systeme von Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) von M mit der Eigenschaft i ∼^{π} j ⇔ μ_{i}^{−1}(1) = μ_{j}^{−1}(1) (wobei μ_{0} := Id gesetzt ist) genau mit denjeniegen Untergruppen U vom Index #M in F_{k}, für welche

i ∼^{π} j ⇔ x_{i}^{−1}x_{i−1}^{−1} … x_{0}^{−1}U = x_{j}^{−1}x_{j−1}^{−1} … x_{0}^{−1}U

gilt, wobei die Indices modulo k zu verstehen sind, d. h. es muß insbesondere we-

gen k ≡ 0 ∼^{π} 0 auch x_{k}^{−1}x_{k−1}^{−1} … x_{0}^{−1}U = x_{0}^{−1}U, also x_{k−1}^{−1} … x_{0}^{−1}U = U und d. h.

x_{0}x_{1} … x_{k−1} ∈ U gelten und umgekehrt impliziert diese Beziehung auch, daß die Nebenklassen x_{i}^{−1}x_{i−1}^{−1} … x_{0}^{−1}U nur von der Kongruenzklasse von i modulo k abhängt.

Geht man zum freien Erzeugendensystem

y_{0} := x_{0}^{−1}, y_{1} := x_{1}^{−1}x_{0}^{−1}, …, y_{k−1} := x_{k−1}^{−1} … x_{0}^{−1}

von F_{k} über, so lassen sich diese Untergruppen U von F_{k} auch durch die Bedingung (F_{k} : U) = #M, y_{k−1} ∈ U und i ∼^{π} j ⇔ y_{i}U = y_{j}U kennzeichnen. Außer im Trivialfall #M = 1 muß π die Menge {0, 1, …, k−1} in mindestens zwei Äquivalenzklassen zerlegen. Ist die Anzahl der π-Äquivalenzklassen genau gleich zwei – und das umfaßt den in [DrF87] betrachteten Fall μ_{1}(1) ≠ μ_{2}(1) = μ_{3}(1) = … = μ_{k−1}(1) = 1 sowie den ebenso interessanten Fall μ_{1}^{−1}(1) = μ_{2}^{−1}(1) = … = μ_{k−1}^{−1}(1) ≠ 1, so läßt sich in Verallgemeinerung der in [DrF87] gegebenen Konstruktion leicht zeigen, daß die Untergruppen U vom Index #M in F_{k} mit y_{k−1} ∈ U und i ∼^{π} j ⇔ y_{i}U = y_{j}U in umkehrbar eindeutiger Beziehung zu den Untergruppen V von F_{k} vom Index #M − 1 stehen: Ist U gegeben und ist x ∈ F_{k} \ U so gewählt, daß {y_{i}U | i = 0, …, k − 1} = {U, xU}, so definiere man eine Aktion von F_{k} auf den X := (F_{k}/U) \ {U} vermöge

y_{i} zU := \{ \begin{matrix}y_{i} zU falls & y_{i} zU ⊈ U ∪ xU \\ xU falls & y_{i} zU ⊆ U ∪ xU \end{matrix}

(zU ∈ X, d. h. z ∈ F_{k} \ U) und wähle V = V_{U} als den Stabilisator von xU ∈ X bezüglich dieser Aktion. Es ist klar, daß F_{k} transitiv auf X operiert, d. h., daß V den Index #M − 1 in F_{k} hat. Ist umgekehrt V eine Untergruppe von F_{k} vom Index #M − 1 und ist π eine Äquivalenzrelation auf {0, 1, …, k − 1} mit genau zwei Äquivalenzklassen, so läßt sich eine zu V korrespondierende Untergruppe U = U_{V}^{π} von F_{k} vom Index #M mit #{y_{i}U | i = 0, 1, …, k − 1} = 2 und y_{k−1}U = U wie folgt konstruieren: man betrachte die Menge Y := F_{k}/V ˙∪ {⋆}, definiere eine F_{k}-Aktion auf Y vermöge

y_{i} ⋆ := \{ \begin{matrix}⋆ & falls i ∼^{π} k − 1 \\ V & sonst \end{matrix}

und

y_{i} zV := \{ \begin{matrix}⋆ & falls i ≁^{π} k − 1 und y_{i} zV = V \\ y_{i} zV & sonst \end{matrix}

und wähle für U = U_{V}^{π} den Stabilisator von ⋆ ∈ Y bezüglich dieser Aktion. Man verifiziert mit wenig Rechnung, daß zu gegebener Äquivalenzrelation π auf {0, 1, …, k − 1} mit genau zwei Äquivalenzklassen für Untergruppen U von F_{k} vom Index #M mit #{y_{i}U | i = 0, 1, …, k − 1} = 2 und y_{k−1}U = U und Untergruppen V von F_{k} vom Index #M − 1 stets U_{(V_{U})}^{π} = U und V_{(U_{V}^{π})} = V gilt. Insbesondere erhält man also auf diese Weise eine Bijektion der in [DrF87] betrachteten Art zwischen den konnexen Systemen von Permutationen (μ_{1}, μ_{2}, …, μ_{k−1}) von M mit μ_{1}(1) ≠ 1 = μ_{2}(1) = … = μ_{k−1}(1) (oder auch mit 1 ≠ μ_{1}^{−1}(1) = … μ_{k−1}^{−1}(1)) und den Untergruppen von F_{k} vom Index #M − 1.

Literaturverzeichnis

[And87] Andrews (G. E.) — Catalan Numbers, q–Catalan Numbers and Hypergeometric Series, Journal of Combinatorial Theory A 44 (1987) 267–273.

[Bai35] Bailey (W. N.) — Generalized Hypergeometric Series, Cambridge Mathematical Tract No. 32, Cambridge Univ. Press, Cambridge (1935).

[Ben74] Bender (E. A.) — Asymptotic Methods in Enumeration, SIAM Review 16 (1974) 485– 515.

[BeG71] Bender (E. A.) and Goldman (J. R.) — Enumerative uses of generating functions, Indiana University Mathematics Journal 20 (1971) 753–765.

[Bru64] Brunk (H. D.) — A Generalization of Spitzer’s Combinatorial Lemma, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1964) 395–405.

[CaS74] Carlitz (L.) et Scoville (R.) — Generalized Eulerian numbers: combinatorial applications, Journal für die reine und angewandte Mathematik 265 (1974) 110-137.

[Com74] Comtet (L.) — Advanced Combinatorics, D. Reidel, 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.

[DrM91] Dress (A. W. M.) und Müller (T.) — Logarithm of generating functions and combinatorial decomposition of functors, in Vorbereitung.

[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.

[DvM47] Dvoretzky (A.) and Motzkin (T.) — A problem of arrangements, Duke Mathematical Journal 14 (1947) 305–313.

[Ege90] Eg̃eciog̃lu (Ö.) — Skew-symmetric matrices and the Pfaffian, Ars Combinatoria 29 (1990) 107–116.

[EHH87] Ehrenfeucht (A.), Haemer (J.) and Haussler (D.) — Quasi–Monotonic Sequences: Theory, Algorithms and Applications, SIAM Journal of Algebraic and Discrete Methods 8 (1987) 410–429.

[Ext83] Exton (H.) — q–Hypergeometric Functions and Applications, Ellis Horwood Ltd., Chichester (1983).

[Foa78] Foata (D.) — A Combinatorial Proof of the Mehler Formula, Journal of Combinatorial Theory, Series A, 24 (1983) 367–376.

[FoF70] Foata (D.) et Fuchs (A.) — Réarrangements of dénumbrements, Journal of Combinatorial Theory, 8 (1970) 361–375.

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

[FüH85] Fürlinger (J.) and Hofbauer (J.) — q–Catalan Numbers, Journal of Combinatorial

Theory A 40 (1985) 248–264.

[Ges82] Gessel (I. M.) — A q–Analog of the Exponential Formula, Discrete Mathematics 40 (1982) 69–80.

[Ges87] Gessel (I. M.) — A Combinatorial Proof of the Multivariable Lagrange Inversion Formula, Journal of Combinatorial Theory A 45 (1987) 178–195.

[Gli78] Glick (N.) — Breaking records and breaking boards, American Mathematical Monthly 85 (1978) 2–26.

[Gol89] Goldie (C. M.) — Records, permutations and greatest convex minorants, Mathematical Proceedings of the Cambridge Philosophical Society 106 (1989) 169–178.

[Gou61] Gould (H. W.) — q–Stirling numbers, Duke Mathematical Journal 28 (1961) 281–289.

[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.

[KaR46] Kaplansky (I.) and Riordan (J.) — The problem of the rooks and its applications, Duke Mathematical Journal, 13 (1946) 259–268.

[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).

[Lab81] Labelle (G.) — Une nouvelle démonstration combinatoire des formules d’inversion Lagrange, Advances in Mathematics, 42 (1981) 217–247.

[Lev79] Levy (A.) — Basic Set Theory, (Ω Perspectives in Mathematical Logic), Springer, Berlin (1979).

[Lot83] Lothaire (M.) — Combinatorics on Words, (Encyclopedia of Math. and its Appl., 17), Addison–Wesley, Reading (1983).

[NiW75] Nijenhuis (A.) and Wilf (H. S.) — Combinatorial Algorithms, Academic Press, New York (1975, 2nd Edition 1978).

[Ren62] Rényi (A.) — Théorie des éléments sailants d’une suite d’observations, Colloquium on Combinatorial Methods in Probability Theory, Aarhus (1962) 104–117.

[Rio58] Riordan (J.) — An Introduction to Combinatorial Analysis, John Wiley, New York (1958).

[Sie57] Sierpiński (W.) — Cardinal and Ordinal Numbers, Polish Scientific Publishers, Warszawa (1957, 2nd Edition 1965).

[Sil90] Sillke (T.) — Zur Kombinatorik von Permutationen, Séminaire Lotharingien de Combinatoire, 21^{e} session, Publ. I.R.M.A. Strasbourg (1990), 111–119.

[Sil91] Sillke (T.) — Ljk Gwdhirurokbb atn Degoeeoathzre, Diplomarbeit, Bielefeld, 1991.

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

[Sta78’] Stanley (R. P.) — Exponential structures, Studies in Applied Mathematics 59 (1978) 73–82.

[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.

[WaW91] Wachs (M.) and White (D.) — p, q–Stirling Numbers and Set Partition Statistics, Journal of Combinatorial Theory A 56 (1991) 27–46.

[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.

Studenten, Handwerksburschen und Soldaten greifen nur ungern zur Feder, ehe nicht der Wechsel oder die Hose oder die Butter zu Ende ist.

Wilhelm Busch