ZUR ABZÄHLUNG PERIODISCHER WORTE

VON

Andreas DRESS UND Christian SIEBENEICHER^{1}

Abstract. — We show that the basic bijection Ψ of a diagram which has been introduced in [DS3] (see also [DS2]) to unify the known combinatorial proofs of the so called cyclotomic identity (cf. [DS1, MR1, MR2, VW]) and which provides moreover a setting for bijections concerning primitive necklaces, defined and studied by Viennot [V], de Bruijn and Klarner [dBK], and Gessel [DW], may be viewed as a special instance of a more general bijection defined for arbitrary cyclic sets. Indeed, if this more general bijection is applied to the cyclic set P (A) of periodic functions on the integers with values in the set A, one gets the bijection discussed in [DS2, DS3].

Eine Beobachtung über Bijektionen

Daß zwischen zwei Mengen mit offensichtlich gleicher Kardinalität nicht immer nur eine wohlbestimmte kanonische Bijektion zu existieren braucht, führt das wohlbekannte Beispiel eines affinen Raumes A und des zugehörige Vektorraum T (A) der Translationen auf A deutlich vor Augen. Es gibt keine kanonische Bijektion zwischen T (A) und A. Zwar liefert nach Auswahl eines Basispunktes a ∈ A die Abbildung x ↦ a + x eine Bijektion von T (A) auf A, aber diese Abbildung ist natürlich nicht kanonisch, sondern hängt von der Auswahl von a ab. Oder, anders gesagt, sie ist nur dann kanonisch, wenn a ∈ A ein in irgendeiner Weise ausgezeichneter Punkt ist. Zu einer unabhängig von jeder solchen Auszeichnung stets kanonischen Bijektion kommt man bekanntlich jedoch, sozusagen auf einer höheren Ebene, zwischen den Mengen A × T (A) und A×A unter Benutzung der Operation von T (A) auf A: durch die Bijektion (a, x) ↦ (a, a + x) werden die durch Auswahl eines Nullpunktes definierten unkanonischen Bijektionen T (A) → A in gewisser Weise alle in dem folgenden kommutativen Diagramm kanonisch zusammengefaßt:

[figure: A × T (A); A × A; A; pr_{1}; pr_{1}]

Wir bezeichnen hier und im folgenden die kanonischen Projektionen von dem Produkt zweier Mengen auf den ersten bzw. den zweiten Faktor (und auch deren Einschränkung auf irgendeine Teilmenge des Produktes) mit pr_{1} bzw. mit pr_{2}.

Allgemeiner hat man für jede Gruppe G und jeden Raum X, auf dem G transitiv und treu operiert (also, mit anderen Worten, für jeden prinzipal homogenen Raum X zur Gruppe G) ein analoges kommutatives Diagramm, in welchem die durch die Auswahl eines Elementes x aus X definierten nicht kanonischen Bijektionen g ↦ x · g von G auf X kanonisch zusammengefaßt werden:

1Universität Bielefeld, Fakultät für Mathematik, Postfach 10 01 31, D 33 501 Bielefeld, e–mail: dress@mathematik.uni-bielefeld.de sieben@mathematik.uni-bielefeld.de

[figure: (x, g); X × G; (x, x · g); X × X; X; ; pr_{1}; pr_{1}]

Ist insbesondere E eine Menge und ist E! die Gruppe der Permutationen von E, dann liefert die Operation von E! auf der Menge B(E, F) der Bijektionen von E auf eine mit E gleichmächtige Menge F hierfür ein häufig betrachtetes Beispiel.

Dieses Beispiel kann in der folgenden Weise verallgemeinert werden: Sind E_{1}, E_{2}, …, E_{r} und F gleichmächtige, endliche Mengen, dann ist klar, daß auch die Mengen ∏_{i} B(E_{i}, E_{i+1}) und ∏_{i} B(E_{i}, F) gleichmächtig sind. Eine kanonische Bijektion ist auch hier nicht möglich, jedoch hat man wiederum kanonische Bijektionen auf höherem Niveau, zwischen ∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, E_{i+1}) und ∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, F) (über ∏_{i} B(E_{i}, F)), die durch

((φ_{i}); (σ_{i}))_{i mod r} ↦ ((φ_{i}); (φ_{i+1} ^{∘} σ_{i}))_{i mod r}
((φ_{i}); (φ_{i+1}^{−1} ^{∘} τ_{i}))_{i mod r} ←((φ_{i}); (τ_{i}))_{i mod r}

definiert sind

[figure: E_{1}; E_{1}; E_{2}; F; E_{4}; E_{2}; F; E_{4}; E_{3}; E_{3}; σ_{1}; σ_{2}; σ_{3}; σ_{4}; φ_{1}; φ_{2}; φ_{3}; φ_{4}; φ_{1}; τ_{1}; φ_{2}; τ_{2}; φ_{3}; τ_{3}; φ_{4}; τ_{4}]

und die das folgende kommutative Diagramm etablieren:

[figure: ∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, E_{i+1}); ∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, F); ∏_{i} B(E_{i}, F); pr_{1}; pr_{1}]

Hat man eine Familie ausgezeichneter Bijektionen φ_{i} : E_{i} → F, sind beispielsweise sämtliche Mengen linear geordnet, so hat man natürlich auch eine kanonische Bijektion ψ : ∏_{i} B(E_{i}, E_{i+1}) → ∏_{i} B(E_{i}, F). Wir werden später hierauf zurückkommen.

Eine Anwendung auf zyklische Mengen Die kanonische Bijektion

∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, E_{i+1}) → ∏_{i} B(E_{i}, F) × ∏_{i} B(E_{i}, F)

kann in der Sprache der zyklischen Mengen auf folgende einfache, aber überraschend folgenreiche Weise interpretiert werden:

Sei X eine Menge, sei α eine auf X wirkenden Permutation^{2} und sei S(X) := {u : X → N_{0} | ∑_{x∈X} u(x) < ∞} das in [DS1] betrachtete frei von X erzeugte kommutative Monoid, kurz die symmetrische Algebra von X, die aus allen auf X definierten Funktionen mit Werten in N_{0} := {0, 1, 2, … } und endlichem Träger supp(u) := {x ∈ X | u(x) ≠ 0} besteht. Der Shift– Operator von X induziert durch α · u := u^{∘} α^{−1} einen Shift–Operator auf S(X), der auch S(X) zu einer zyklischen Menge macht. Für u ∈ S(X) sei^{3} [u] := {(x, i) | x ∈ X, i ∈ [u(x)]} ⊂ X × N_{0}. Die Menge [u] ist genau dann invariant unter dem naheliegenden Shift–Operator auf X ×N_{0}, wenn u eine shift– invariante Funktion auf X ist. Die Menge der shift–invarianten Elemente von S(X) sei mit s(X) bezeichnet.

Für jede endliche Menge E und jede Abbildung π : E → X ist die Funktion #π : X ⟶ N_{0}, die definiert ist durch x ↦ #π^{−1}(x), ein Element von S(X). Dieses Element ist genau dann invariant unter dem Shift–Operator (und liegt dann in s(X)), wenn über jeder Bahn von X sämtliche Fasern von π gleichviel Elemente haben. Bezeichnet man die Menge derjenigen Abbildungen π von E nach X, für welche ^{#}π shift–invariant ist, mit X^{(E)}, dann liefert die Zuordnung π ↦ ^{#}π eine kanonische Abbildung ^{#} : X^{(E)} → s(X).

Seien nun für festes π : E → X aus X^{(E)} mit

T_{X,π}(E) := {σ ∈ E! | π^{∘} σ = α^{∘} π}

die Menge der mit π verträglichen Shift–Operatoren σ : E →^{∼} E und mit

s_{X,π}(E) := {Φ ∈ B(E, [^{#}π]) | pr_{1} ^{∘} Φ = π}.

die Menge der Bijektionen zwischen E und [^{#}π] über X bezeichnet.

Besteht π(E) = supp(^{#}π) aus einer einzigen Bahn des Shift–Operators α, wählt man ein beliebiges Element x ∈ π(E), bezeichnet man die Fasern von π über der Bahn x, α · x, …, α^{r−1} · x von x mit E_{1}, E_{2}, …, E_{r} und setzt man F = [^{#}π(x)], so definiert

\begin{matrix}T_{X,π}(E) →^{∼} ∏_{i=1}^{r} B(E_{i}, E_{i+1}) \\ σ ↦ (σ|_{E_{1}}, σ|_{E_{2}}, …, σ|_{E_{r}}) \end{matrix}

(was wegen σ(E_{i}) = σ(π^{−1}(α^{i−1} · x)) = π^{−1}(α^{i} · x) = E_{i+1} wohldefiniert ist!) und

\begin{matrix}s_{X,π}(E) →^{∼} ∏_{i=1}^{r} B(E_{i}, F) \\ Φ ↦ (pr_{2} ^{∘} Φ|_{E_{1}}, pr_{2} ^{∘} Φ|_{E_{2}}, …, pr_{2} ^{∘} Φ|_{E_{r}}) \end{matrix}

kanonische Bijektionen, die folglich eine kanonische Bijektion

2Wir wollen dann X eine zyklische Menge mit Shift–Operator α nennen.

3Für jede natürliche Zahl n setzen wir [n] := {1, …, n}.

[figure: s_{X,π}(E) × T_{X,π}(E); s_{X,π}(E) × s_{X,π}(E); s_{X,π}(E); pr_{1}; pr_{1}]

über den jeweiligen Projektionen auf den ersten Faktor induzieren.

Diese Bijektion läßt sich sogar für ganz beliebiges π auch ohne Bezug auf die obige einführende Diskussion direkt durch Betrachten der umkehrbar eindeutigen Korrespondenz

(Φ, σ) ↔ (Φ, Φ′) ⟺ Φ′|_{π^{−1}(x)} = Φ|_{π^{−1}(αx)} ^{∘} σ|_{π^{−1}(x)}
für alle x ∈ X

etablieren.

Durch Einachränkung dieser Korrespondenz auf die Fasern (jeweils bezüglich der Abbildung pr_{1}) über einem beliebigen Element Φ ∈ s_{X,π}(E) erhält man folglich auch (von der Auswahl von Φ abhängige) Bijektionen ψ_{Φ} : T_{X,π}(E) → s_{X,π}(E). Für den Fall, daß E linear geordnet ist (insbesondere also im Falle E = [n]), gibt es in s_{X,π} genau ein Element Φ_{π} : E →^{∼} [^{#}π], dessen Einschränkung auf jede der Fasern von π monoton wächst. In dieser Situation hat man deshalb sogar eine kanonische Bijektion ψ_{π} : T_{X,π}(E) → s_{X,π}(E).

Definiert man schließlich für jede endliche Menge E die Mengen

T_{X}(E) := {(σ, π) | σ ∈ E!, π ∈ X^{E}, π^{∘} σ = α^{∘} π} ⊂ E! × X^{(E)}

bzw.

s_{X}(E) := {(u, Φ) | u ∈ s(X), Φ ∈ B(E, [u])},

dann sind die Mengen T_{X,π}(E) bzw. s_{X,π}(E) gerade die Fasern der Projektions– Abbildung pr_{2} : T_{X}(E) → X^{(E)} bzw. der Abbildung t : s_{X}(E) → X^{(E)}, die definiert ist durch (u, Φ) ↦ pr_{1} ^{∘} Φ und deren Komposition mit der Abbildung # : X^{(E)} → s(X) gleich der Projektion pr_{1} : s_{X}(E) → s(X) ist. Die obige Korrespondenz liefert also eine kanonische und über der jeweiligen Projektion auf den ersten Faktor fasertreue Bijektion der Faserprodukte

[figure: s_{X}(E) × T_{X}(E); X^{(E)}; s_{X}(E) × s_{X}(E); X^{(E)}; s_{X}(E); pr_{1}; pr_{1}]

Sie induziert durch Einschränkung auf das Bild eines (beliebigen) Schnittes ρ : X^{(E)} → s_{X}(E) für die Abbildung t : s_{X}(E) → X^{(E)} eine (von ρ abhängige) Bijektion ψ_{ρ} : T_{X}(E) → s_{X}(E). Falls die Menge E linear geordnet ist, existiert wiederum ein kanonischer Schnitt

ρ_{X}^{E} : X^{(E)} → s_{X}(E) π ↦ (^{#}π, Φ_{π})

so daß in diesem Falle auch eine kanonische Bijektion

ψ_{X}^{E} : T_{X}(E) →^{∼} s_{X}(E)

existiert.

Bemerkung Für den Fall, daß die Menge E linear geordnet ist, liefert die Komposition des Schnittes ρ_{X}^{E} : X^{(E)} → s_{X}(E) mit dem Inversen der kanonischen Bijektion ψ_{X}^{E} : T_{X}(E) → s_{X}(E) einen kanonischen Schnitt für die Abbildung pr_{2} : T_{X}(E) → X^{(E)}. In dem Bild (σ_{π}, π) von π unter diesem Schnitt, ist σ_{π} diejenige der Gleichung π^{∘} σ = α^{∘} π genügende Permutation von E, die auf den Fasern von π monoton wächst.

Der Spezialfall der Menge der periodischen Funktionen

Ist speziell X = P (A), gleich der zyklischen Menge der auf Z definierten periodischen Funktionen^{4} mit Werten in der Menge A (cf. [DS3]), dann hat man zusätzlich zu den vielen von der Auswahl eines Schnittes ρ : X^{(E)} → s_{X}(E) abhängigen (unkanonischen) Bijektionen T_{P (A)}(E) → s_{P (A)}(E) noch eine kanonische Bijektion ω : E! × A^{E} ⟶ T_{P (A)}(E). Sie ist wie folgt definiert: für jedes Element (σ, f) ∈ E! × A^{E} und jedes ϵ ∈ E wird durch die Zuordnung i ↦ f(σ^{i}(ϵ)) eine periodische Punktion f_{σ}^{ϵ} : Z → A definiert. Die Zuordnung ϵ ↦ f_{σ}^{ϵ} ist mit σ und dem Shift–Operator α verträglich (d.h., es ist f_{σ}^{ϵ} ^{∘} σ = α^{∘} f_{σ}^{ϵ}), und sie definiert daher eine äquivariante Abbildung π_{σ,f} : (E, σ) ⟶ (P (A), α). Durch die Zuordnung

(σ, f) ↦ (σ, π_{σ,f})

wird daher eine natürliche Abbildung

ω : E! × A^{E} ⟶ T_{P (A)}(E)

definiert, die leicht als Bijektion zu erkennen ist: ihre Umkehrabbildung ist durch

(σ, π) ↦ (σ, ev^{∘} π)

gegeben, wobei ev : P (A) → A durch die Zuordnung g ↦ g(0) definiert ist. Abstrakt gesehen resultieren diese Bijektionen aus der Tatsache, daß der Funktor A ↦ P (A) von der Kategorie der Mengen in die Kategorie der zyklischen Mengen links–adjungiert zum Vergißfunktor ist, wobei die Evaluationsabbildung ev eine der beiden Adjunktionsabbildungen ist und die Zuordnung f ↦ π_{σ,f} die andere Adjunktionsabbildung definiert.

Auf der Menge E! × A^{E} hat man eine Reihe weiterer kanonisch definierter Abbildungen.

• Die Projektion pr_{2} : E! × A^{E} → A^{E}

• Die Abbildung r : E! × A^{E} → P (A)^{(E)} (σ, f) ↦ π_{σ,f}.

Für sie gilt r = pr_{2} ^{∘} ω.

• Die Abbildung q : E! × A^{E} → s(P (A)) (σ, f) ↦ u_{σ,f},

wobei (cf. [DS2, DS3]) u_{σ,f}(g) := #{ϵ ∈ E | f_{σ}^{ϵ} = g} = ^{#}π_{σ,f}(g)

ist. Für diese Abbildung gilt daher q = ^{#} ^{∘} r.

Darüber hinaus induziert die Komposition mit der Evaluation ev : P (A) → A eine kanonische Abbildung ev^{∗} : P (A)^{(E)} → A^{E}. Für die Komposition von ev^{∗} mit der Abbildung t : s_{P (A)}(E) → P (A)^{(E)} gilt:

ev^{∗} ^{∘} t (u, Φ) = ev^{∗}(pr_{1} ^{∘} Φ) = ev^{∘} pr_{1} ^{∘} Φ.

Die Komposition ev^{∗} ^{∘} t ist daher gleich der in [DS2, DS3] definierten Abbildung^{5} p : s_{P (A)}(E) → A^{E}. Ferner sieht man unmittelbar, daß die zu dem Element (σ, f) ∈ E! × A^{E} gehörige Abbildung ev^{∗} ^{∘} r(σ, f) = ev^{∗}(π_{σ,f}) : E → A in folgender Weise wirkt: ϵ ↦ f_{σ}^{ϵ}(0) = f(ϵ), und dies bedeutet, daß ev^{∗} ^{∘} r = pr_{2} ist.

4Der Shift–Operator α : P (A) → P (A) ist definiert durch (α · g)(i) := g(i + 1) für alle g ∈ P (A)

5Man beachte, daß dort die Menge s_{P (A)}(E) mit S^{A}(E) bezeichnet wurde.

Schließlich hat man noch eine natürliche Abbildung (cf. [DS3])

δ : s(P (A)) → S(A) δ(u)(a) = ∑_{g(0)=a} u(g),

und eine analog zur Abbildung ^{#} : P (A)^{(E)} → s(P (A)) definierte Abbildung # : A^{E} → S(A). Es ist klar, daß für jedes Element π ∈ P (A)^{(E)} gilt: δ(^{#}π) = #(ev^{∘} π). Dies bedeutet aber, daß die Kompositionen δ^{∘} pr_{1} : P (A)^{(E)} → S(A) und ^{#} ^{∘} p : P (A)^{(E)} → S(A) übereinstimmen.

Wir fassen nun alle diese Daten in dem folgenden kommutativen Diagramm zusammen. In ihm sind, bis auf die von der Auswahl eines t–Schnittes ρ : X^{(E)} → s_{X}(E) abhängende Bijektion ψ_{ρ} : T_{P (A)}(E) → s_{P (A)}(E), sämtliche Abbildungen kanonisch:

[figure: E! × A^{E}; A^{E}; P (A)^{(E)}; T_{P (A)}(E); P (A)^{(E)}; s(P (A)); s_{P (A)}(E); S(A); pr_{2}; r; r; q; ω; ev^{∗}; pr_{2}; pr_{2}; #; p; t; t; pr_{1}; ψ_{ρ}; #; δ]

Ist E = [n], dann hat man, wie wir gesehen haben, einen kanonischen t–Schnitt ρ_{A}^{n} := ρ_{P (A)}^{[n]} : P (A)^{[n]} → s_{P (A)}([n]) und folglich auch eine kanonische Bijektion

ψ_{A}^{n} := ψ_{P (A)}^{[n]} : T_{P (A)}(E) → s_{P (A)}(E). Setzt man nun

s^{n}(P (A)) := {u ∈ s(P (A)) | |u| := ∑_{g∈P (A)} u(g) = n},

und entsprechend S^{n}(A) := {v ∈ S(A) | |v| := ∑_{a∈A} v(a) = n}, dann geht unser Diagramm in das folgende Diagramm über, in welchem nunmehr sämtliche Pfeile kanonisch und surjektiv und die senkrechten Pfeile Bijektionen sind:

[figure: [n]! × A^{n}; A^{n}; P (A)^{([n])}; T_{P (A)}([n]); P (A)^{([n])}; s^{n}(P (A)); s_{P (A)}([n]); S(A); pr_{2}; r; r; q; ω; ev^{∗}; pr_{2}; pr_{2}; #; p; t; t; pr_{1}; ψ_{A}^{n}; #; δ]

In diesem Diagramm erkennt man in dem dicker ausgezogenen Rhombus das in [DS2, DS3] etablierte Viereck, und aus einem Vergleich mit der dort gegebenen Definition für die Abbildung Ψ geht unmittelbar hervor, daß diese mit der Komposition ψ_{A}^{n} ^{∘} ω übereinstimmt. Ferner lassen sich die dort gezogenen Folgerungen aus dem vervollständigten Diagramm besonders bequem ablesen:

1. Hat die Menge A die Kardinalität q, dann gilt:

n! · q^{n} = #[n]! × A^{[n]} = #T_{P (A)}([n]) = #s_{P (A)}([n])
= ∑_{u∈s^{n}(P (A))} #pr_{1}^{−1}(u)
= ∑_{u∈s^{n}(P (A))} n!
= n! · #s^{n}(P (A))

und es folgt

q^{n} = #s^{n}(P (A))

2. Ist v ∈ S^{n}(A), dann ist die Anzahl der Elemente f ∈ A^{n}, für die ^{#}f = v ist, bekanntlich gleich dem (in [DS2, DS3] mit ((v)) bezeichneten) Multinomialkoeffizienten \binom{n}{v} := \frac{n!}{v!} := \frac{n!}{∏_{a∈A} v(a)!}. Folglich ist die Anzahl der (u, Φ) ∈ s_{P (A)}([n]),

die durch die Komposition ^{#} ^{∘} p auf v abgebildet werden, gleich der Anzahl der (σ, π) ∈ T_{P (A)}([n]), die durch ^{#} ^{∘} ev^{∗} ^{∘} pr_{2} auf v abgebildet werden, also gleich n! · \binom{n}{v}. Andererseits ist diese Anzahl wegen der Kommutativität des unteren Vierecks in unserem Diagramm aber auch die Anzahl der Urbilder von v unter δ^{∘} pr_{1}, und da alle Fasern der Projektion pr_{1} : s_{P (A)}([n]) → s^{n}(P (A)) die gleiche Kardinalität n! haben, folgt, daß die Menge δ^{−1}(v) genau \binom{n}{v} Elemente hat. Für diese Menge gilt aber

δ^{−1}(v) = {u ∈ s^{n}(P (A)) | δ(u) = v}
= {u ∈ s^{n}(P (A)) | ∑_{g(0)=a} u(g) = v(a) für alle a ∈ A}

Definiert man also für jede Bahn T (unter dem Shift–Operator α) in P (A) und jedes a ∈ A die Zahlen

Δ(a, T) := #{g ∈ T | g(0) = a}
= ∑_{\begin{matrix}g∈T \\ g(0)=a \end{matrix}} 1

und setzt u(T) gleich dem gemeinsamen Wert von u auf allen Elementen der Bahn T ⊂ P (A), dann erhält man

δ^{−1}(v) = {u ∈ s^{n}(P (A)) | ∑_{T ⊂P (A)} Δ(a, T) · u(T) = v(a) für alle a ∈ A}
= {u ∈ s^{n}(P (A)) | Δ · u = v}.

Wegen #δ^{−1}(v) = \binom{n}{v} ergibt sich hieraus also unmittelbar die Aussage von Theorem 1 aus [DS2], daß die Anzahl der ganzzahligen, nicht negativen Lösungen der linearen diophantischen Gleichung Δ · u = v gerade gleich \binom{n}{v} ist.

3. Ist die Menge A linear geordnet, beispielsweise A = N = {1, 2, … }, dann tragen auch die Mengen A^{n} und P (A) kanonische lineare Ordnungen. Auf der Menge A^{n} ist es die lexikographische Ordnung, auf der Menge P (A) ist es die folgendermaßen definierte lineare Ordnung: Es gilt g < g′ genau dann, wenn es ein k ∈ N_{0} gibt, so daß

ev(α^{k} · g) < ev(α^{k} · g′)
ev(α^{k−1} · g) = ev(α^{k−1} · g′)
⋮ = ⋮
ev(α · g) = ev(α · g′)
ev(g) = ev(g′)

gilt.

Betrachtet man P (A) mit dieser Ordnung, dann gibt es zu jedem u ∈ s^{n}(P (A)) genau eine monotone Abbildung π_{u} : [n] → P (A), für die ^{#}π_{u} = u ist. Die Zuordnung u ↦ π_{u} definiert also einen kanonischen Schnitt λ : s^{n}(P (A)) → P (A)^{([n])} für die Abbildung ^{#} : P (A)^{([n])} → s^{n}(P (A)). Die Komposition ρ_{A}^{n} ^{∘} λ : s^{n}(P (A)) → s_{P (A)}([n]) von λ mit dem am Ende des letzten Paragraphen definierten t–Schnitt ρ_{A}^{n} : P (A)^{([n])} → s_{P (A)}([n]) liefert daher einen Schnitt für die Komposition^{#} ^{∘} t. Komponiert mit dem Inversen von ψ_{A}^{n} definiert dieser eine kanonische, eineindeutige Korrespondenz zwischen den Elementen von s^{n}(P (A)) und der Menge derjenigen Elemente (σ, π) ∈ T_{P (A)}([n]), für die die Abbildung π : [n] → P (A) monoton wächst und die Permutation σ auf den Konstanz– Intervallen von π (d.h. den Fasern von π) ebenfalls monoton wächst. Da die Evaluationsabbildung ev : P (A) → A gleichfalls monoton wächst, ist die Komposition f := ev^{∘} π für jedes Element (σ, π) der beschriebenen Menge, ebenso wie die Funktion π monoton wachsend. Es zeigt sich, daß die Permutation σ sogar auf den Fasern der Funktion f monoton wächst. Sind nämlich ϵ und ϵ′ Elemente von [n] mit ϵ < ϵ′ , f(ϵ) = f(ϵ′) aber π(ϵ) < π(ϵ′), dann gilt aufgrund der Definition der Ordnung in P (A) auch α · π(ϵ) < α · π(ϵ′). Weil π äquivariant ist, folgt hieraus π(σ(ϵ)) < π(σ(ϵ′)), und da π monoton wächst, folgt hieraus σ(ϵ) < σ(ϵ′). Insgesamt erhält man damit die folgende Aussage (cf. [DW]): Gessel’s Lemma Ist die Menge A linear geordnet, dann definiert der q–Schnitt

(ψ_{A}^{n} ^{∘} ω)^{−1} ^{∘} λ : s^{n}(P (A)) → [n]! × A^{([n])}

eine Bijektion von s^{n}(P (A)) auf die Menge derjenigen Elemente (σ, f) ∈ [n]! × A^{([n])}, für die die Funktion f monoton wächst und die Permutation σ auf den Fasern von f ebenfalls.

Genauso einfach läßt sich im Falle eines linear geordneten A die von de Bruijn und Klarner definierte Bijektion A^{n} →^{∼} s^{n}P (A) (cf. [dBK]) durch die Konstruktion geeigneter Schnitte in dem obigen Diagramm herleiten (cf. [DS3]).

Zyklische Mengen und Funktoren

Aus unserer Diskussion folgt weiterhin, daß die Kardinalitäten der Werte der Funktoren

E ↦ T_{X}(E)

und

E ↦ s_{X}(E),

die auf der Kategorie der enlichen Mengen (mit den Bijektionen als Morphismen) definiert sind, übereinstimmen, d.h. daß für jede endliche Menge E

#T_{X}(E) = #s_{X}(E)

gilt. Als unmittelbare Konsequenz der Definitionen ergeben sich darüber hinaus die folgenden funktoriellen Bijektionen:

T_{X⊔Y} (E) ≅ ∐_{F ⊂E} T_{X}(F) × T_{Y} (E \ F)

und

s_{X⊔Y} (E) ≅ ∐_{F ⊂E} s_{X}(F) × s_{Y} (E \ F).

Mit der von Joyal vorgeschlagenen Definition des Produktes solcher Funktoren (cf. [J]) hat man also

T_{X⊔Y} ≅ T_{X} · T_{Y} und s_{X⊔Y} ≅ s_{X} · s_{Y} .

Ist daher X ≅ ∐ a_{k}C(k) die kanonische Zerlegeung der zyklischen Menge X in Bahnen, wobei C(k) den Zyklus der Länge k bezeichnet und a_{k} die Vielfachheit angibt, mit der dieser in der Zyklenzerlegung von X vorkommt, dann hat man die kanonischen Zerlegungen

T_{X}(E) ≅ ∏(T_{C(k)}(E))^{a_{k}}

und

s_{X}(E) ≅ ∏(s_{C(k)}(E))^{a_{k}}.

Für die Kardinalitäten der Werte des Funktor s_{C(k)} ergibt sich unmittelbar aus der Definition (siehe auch [DS1]):

#s_{C(k)}(E) = \{ \begin{matrix}(#E)! & falls & k ein Teiler von #E ist \\ 0 & sonst \end{matrix}

Man erhält somit für die von Joyal in [J] für Funktoren F der obigen Art definierte Kardinalität

#F := ∑_{n=0}^{∞} #F ([n]) · \frac{t^{n}}{n!}

im Falle F = T_{C(k)} und F = s_{C(k)} die Reihe

#T_{C(k)} = #s_{C(k)} = ∑_{i=0}^{∞}(k · i)!\frac{t^{k·i}}{(k · i)!} = \frac{1}{1 − t^{k}} .

Für die Kardinalität der zu einer beliebigen zyklischen Menge gehörigen Funktoren ergibt sich dann wegen der leicht zu verifizierenden Formel #(F_{1} · F_{2}) = #F_{1} · #F_{2} die folgende Identität von Potenzreihen:

#T_{X} = #s_{X} = ∏_{j=1}^{∞} (\frac{1}{1 − t^{j}} )^{a_{j}} .

Ist insbesondere X = P (A) und enthält die Menge A gerade q Elemente, dann liefert die kanonische Zyklenzerlegung

P (A) = ∑_{j=1}^{∞} M(q, j)C(j)

von P (A), in welcher die Koeffizienten M(q, j) gerade die durch Möbius Inversion berechenbaren und im Kontext der zyklotomischen Identität diskutierten (cf. [MR1, MR2, DS1]) Größen

M(q, j) = \frac{1}{j} ∑_{d|j} μ(j)q^{j/d}

bezeichnen, zusammen mit der aus unserem Diagramm folgenden Tatsache, daß #s^{n}(P (A)) = q^{n} ist, die folgende Identität von Potenzreihen

\frac{1}{1 − qt} = ∏_{j=1}^{∞} (\frac{1}{1 − t^{j}} )^{M(q,j)} ,

also gerade die zyklotomische Identität.

Literatur

[dBK] de Bruijn (N.G.) and Klarner (D.A.) — Multisets of aperiodic cycles, SIAM J. Alg. Disc. Meth., vol. 3 (1982), 359–368.

[DS1] Dress (A.W.M.) and Siebeneicher (Ch.) — The Burnside Ring of the Infinite Cyclic Group and its Relations to The Necklace Algebra, λ–Rings and The Universal Ring of Witt Vectors (1987); to appear in: Advances in Mathematics.

[DS2] Dress (A.W.M.) und Siebeneicher (Ch.) — Ein Lemma über Perlenketten, Séminaire Lotharingien de Combinatoire, 20^{e} session, Publ. I.R.M.A. Strasbourg, (1988), 47–55.

[DS3] Dress (A.W.M.) and Siebeneicher (Ch.) — On the Number of Solutions of Certain Linear Diophantine Equations to appear in: Hokkaido Mathematical Journal.

[DW] Désarménien (J.) et Wachs (M.) — Descentes des dérangement et mots crculaires, Séminaire Lotharingien de Combinatoire, 19^{e} session, Publ. I.R.M.A. Strasbourg, (1988), 13–21.

[J] Joyal (A.) — Une Théorie combinatoire des séries formelles, Advances in Mathematics, vol. 42 (1981), 1–82.

[MR1] Metropolis (N.) and Rota (G.-C.) — Witt Vectors and the Algebra of Necklaces, Advances in Mathematics, vol. 50 (1983), 95–125.

[MR2] Metropolis (N.) and Rota (G.-C.) — The cyclotomic Identity, Contemporary Mathematics, vol. 34 Amer. Math. Soc. (1984), 19–24.

[V] Viennot (G.) — Algébre de Lie Libres et Monoides Libres, Lecture Notes in Mathematics 691, Springer (1978).

[VW] Varadarajan (K.) and Wehrhahn (K.), Aperiodic Rings, Necklace Rings and Witt Vectors, preprint (1988).