Mengen aus Tupeln
Definition (Tupel und ihre Einträge)
Seien A eine beliebige Menge und k ∈ ℕ. Die Elemente von Ak nennen wir k-Tupel in A. Ist (a1, …, ak) ∈ Ak und 1 ≤ i ≤ k, so heißt ai der i-te Eintrag oder der Eintrag an der Stelle i des Tupels.
Im Spezialfall k = 0 gibt es nur das leere Tupel () in A. Es gilt also A0 = { () }, sodass A0 genau ein Element besitzt, in Übereinstimmung mit der Anzahlformel |A0| = |A|0 = 00 = 1.
Ist A = { a1, …, an } mit paarweise verschiedenen Elementen ai, so können wir Tupel in A mit Tupeln in { 1, …, n } identifizieren, indem wir ein Element ai mit seinem Index i gleichsetzen. Dies motiviert, warum wir uns im Folgenden auf Tupel in Mengen der Form { 1, …, n } konzentrieren. Für die Einträge dieser Tupel steht uns zudem ein „kleiner“ und „größer“ zur Verfügung. Wir definieren vier spezielle Tupelmengen:
Definition (die Tupelmengen T1, …, T4)
Seien n, k ∈ ℕ. Wir setzen:
T1 = T1(n, k) = { 1, …, n }k,
T2 = T2(n, k) = { (a1, …, ak) ∈ T1 | ai ≠ aj für alle i ≠ j },
T3 = T3(n, k) = { (a1, …, ak) ∈ T1 | ai < aj für alle i < j },
T4 = T4(n, k) = { (a1, …, ak) ∈ T1 | ai ≤ aj für alle i ≤ j }.
Etwas anschaulicher formuliert gilt:
T1 = „Menge aller k-Tupel in { 1, …, n }“,
T2 = „Menge aller injektiven (wiederholungsfreien) k-Tupel in { 1, …, n }“,
T3 = „Menge aller streng monoton steigenden k-Tupel in { 1, …, n }“,
T4 = „Menge aller monoton steigenden Tupel in { 1, …, n }“.
Es gelten die Inklusionen
T3 ⊆ T2 ⊆ T1 und T3 ⊆ T4 ⊆ T1.
Ist k > n, so gibt es nach dem Schubfachprinzip kein injektives k-Tupel in der Menge { 1, …, n }. Damit sind in diesem Fall T2 und folglich auch T3 ⊆ T2 leer. Dagegen ist für jedes k und i ∈ { 1, …, n } das konstante k-Tupel (i, …, i) stets ein Element von T4. Für k ≥ 1 gilt also n ≤ |T4| ≤ |T1|. Im Fall k = 0 sind alle Ti gleich { () }. Im Fall n = 0, k > 0 sind alle Tupelmengen leer.
Tupel können wir funktional darstellen:
Mit n = 8 und k = 6: (1, 4, 3, 8, 7, 3) ∈ T1 (links) und (1, 2, 8, 6, 5, 4) ∈ T2 (rechts)
Mit n = 8 und k = 6: (1, 3, 4, 5, 6, 8) ∈ T3 (links) und (2, 2, 4, 5, 7, 7) ∈ T4 (rechts)
Die Mächtigkeiten der vier Tupelmengen lassen sich mit Hilfe des folgendes Satzes berechnen:
Satz (Anzahlformeln für T1, …, T4)
Für alle n, k ∈ ℕ gilt:
| |T1| | = nk, |
| |T2| | = n!(n − k)!, | falls k ≤ n, |
| |T3| | = |T2|k! = , | falls k ≤ n, |
| |T4| | = . |
Die Formel für T2 liefert im Spezialfall k = n die Mächtigkeit |Sn| = n! der Permutationen Sn auf { 1, …, n }. Denn eine solche Permutation können wir mit einem injektiven (und damit bijektiven) n-Tupel in { 1, …, n } identifizieren.
Beweis
zu T1: Für alle n, k gilt |T1(n, k)| = |{ 1, …, n }k| = nk.
zu T2: Sei n ∈ ℕ. Wir zeigen die Behauptung durch Induktion nach k ≤ n.
Induktionsanfang k = 0: Es gilt |T2(n, 0)| = 1 = n!/(n − 0)!
Induktionsschritt von k nach k + 1 mit k + 1 ≤ n: Jedes injektive Tupel (a1, …, ak) in { 1, …, n } können wir in genau n − k Arten zu einem injektiven Tupel (a1, …, ak, a) in { 1, …, n } erweitern, und alle injektiven (k + 1)-Tupel in { 1, …, n } werden so erreicht. Also gilt
|T2(n, k + 1)| = |T2(n, k)| (n − k) =I.V. n!(n − k)!(n − k) = n!(n − (k + 1))!.
zu T3: Seien n, k ∈ ℕ mit k ≤ n, und sei T3 = T3(n, k). Für alle (a1, …, ak), (b1, …, bk) ∈ T2 = T2(n, k) setzen wir
(a1, …, ak) ≡ (b1, …, bk) falls { a1, …, ak } = { b1, …, bk }.
Dann ist ≡ eine Äquivalenz auf T2, deren Klassen alle die gleiche Mächtigkeit k! haben. Denn für jedes injektive Tupel (a1, …, ak) besteht die Klasse des Tupels aus allen Permutationen (aπ(1), …, aπ(k)) mit π ∈ Sk, und davon gibt es genau k! viele. In jeder Klasse gibt es zudem genau einen Repräsentanten in T3. Damit ist |T2| = k! |T3|.
zu T4: Seien n, k ∈ ℕ. Wir betrachten
T = T3(n + k − 1, k) = { (b1, …, bk) | 1 ≤ b1 < … < bk ≤ n + k + 1 }.
Nach der Formel für streng monotone k-Tupel gilt |T| = . Es genügt also, eine Bijektion F : T4 → T zu konstruieren. Eine solche wird definiert durch
F(a1, …, ak) = (a1, a2 + 1, a3 + 2, …, ak + k − 1) für alle (a1, …, ak) ∈ T4.
Die Beweise für T2 und T3 lassen sich verkürzen, wenn wir den üblichen kombinatorischen Jargon zulassen: Beim Aufbau eines injektiven Tupels (a1, …, ak) in T2 haben wir für die ersten Eintrag n Möglichkeiten, für den zweiten noch n − 1 Möglichkeiten, …, für den k-ten noch n − k + 1 Möglichkeiten. Damit ist
|T2| = n (n − 1) … (n − k + 1) = n!(n − k)!.
Die injektiven k-Tupel in T2 können wir nun streng monoton anordnen. Dabei führen genau k! viele Tupel zum gleichen Ergebnis, sodass
|T3| = |T2|k! = n!k! (n − k)! = .
Alle drei Fakultäten des Binomialkoeffizienten haben eine anschauliche Bedeutung: n! ist die Anzahl aller injektiven n-Tupel in { 1, …, n }. Die Division durch (n − k)! beschreibt die Reduktion auf k-Tupel. Und die Division durch k! bedeutet, dass wir von der Reihenfolge der Tupelelemente absehen.
Für T4 bleibt das schöne Argument des Beweises bestehen, streng monotone Tupel auf einem größeren Auswahlvorrat zu betrachten. Eine monotone Folge wird durch Addition von (0, 1, …, k − 1) zu einer streng monotonen Folge geliftet. Dies erklärt das Auftreten von n + k − 1.
Übergang von (2, 2, 4, 5, 7, 7) ∈ T4(8, 6) zu (2, 3, 6, 8, 11, 12) ∈ T3(13, 6)
Aus der Formel für T3 erhalten wir eine wichtige Interpretation der Binomialkoeffizienten. Hierzu definieren wir:
Definition (Teilmengen einer bestimmten Größe)
Sei A eine Menge. Dann setzen wir für alle k ∈ ℕ:
℘k(A) = [ A ]k = { B ⊆ A | |B| = k }.
Hat A weniger als k Elemente, so gilt ℘k(A) = ∅. Für endliche Mengen gilt:
Korollar (Mächtigkeit der k-elementigen Teilmengen)
Sei A eine endliche Menge, und sei n = |A|. Dann gilt für alle 0 ≤ k ≤ n:
|℘k(A)| = .
Beweis
Ohne Einschränkung sei A = { 1, …, n }. Sei k ≤ n beliebig. Wir definieren F : T3 → ℘k(A) durch
F(a1, …, ak) = { a1, …, ak } für alle (a1, …, ak) ∈ T3.
Da die Tupel in T3 injektiv sind, liegt jeder Funktionswert in ℘k(A). Da die Tupel in T3 streng monoton steigend sind, ist F injektiv. Schließlich ist jede k-elementige Teilmenge von A von der Form { a1, …, ak } mit a1 < … < ak, sodass F auch surjektiv ist. Damit ist |℘k(A)| = |T3| = .