close

Вход

Забыли?

вход по аккаунту

?

3951.Kombinatorik 001 .pdf

код для вставкиСкачать
Ausgewählte Kapitel der Kombinatorik
2st. Vorlesung im SS 2001
Jens Schwaiger
Inhaltsverzeichnis
1 Grundlegendes über endliche Mengen
1.1 Begriffsbestimmungen und Rechenregeln . . . . .
1.2 Binomialkoeffizienten . . . . . . . . . . . . . . . .
1.3 Die Siebformel und Anwendungen . . . . . . . . .
1.4 Auswahlen mit Berücksichtigung der Anordnung .
1.5 Operationen von Gruppen auf Mengen . . . . . .
1.6 Auswahlen ohne Berücksichtigung der Anordnung
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Konstruktive Aspekte der Kombinatorik
2.1 Die lexikographische und andere Ordnungen . . . . . . . .
2.2 Produkt- und Potenzmengen . . . . . . . . . . . . . . . . .
2.3 Monotone Funktionen und n-elementige Teilmengen . . . .
2.4 Permutationen mit und ohne Wiederholung, surjektive und
bildungen . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Der
3.1
3.2
3.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . .
. . . . . . . .
. . . . . . . .
injektive Ab. . . . . . . .
Heiratssatz
Das Resultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ein algorithmischer Beweis . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
7
9
11
12
13
15
15
17
19
23
26
26
29
31
Kombinatorik ist (grobgesprochen) die Beschäftigung mit endlichen Mengen. Typische Fragestellungen entstammen z.B. den folgenden Bereichen:
1. Abzählprobleme: beispielsweise die Frage nach der Anzahl aller Teilmengen, aller
k-elementigen Teilmengen einer endlichen Menge; oder nach der Anzahl aller (injektiven, surjektiven, bijektiven) Abbildungen einer endlichen Menge in eine zweite.
2. Konstruktionsaufgaben: Angabe von Methoden und Algorithmen, um alle Objekte
mit bestimmten Eigenschaften zu bestimmen; auch Algorithmen zur zufälligen Auswahl derartiger Objekte. (Beispielsweise Konstruktion aller k-elementigen Teilmengen einer n-elementigen Menge; zufällige Auswahl solcher Mengen, so daß jede
Auswahl gleich wahrscheinlich ist [Lotto]).
3. Existenzprobleme: z.B. der Themenkreis des Heiratssatzes: Gegeben ist dabei eine
endliche Menge F von Frauen und eine Abbildung ϕ : F → P(M ) (M eine endliche
1
Menge von Männern, P(M ) die Menge aller Teilmengen von M , ϕ(x) die Menge der
Männer aus M , die der Frau x sympathisch sind). Frage: Unter welchen Voraussetzungen an ϕ existiert eine injektive Abbildung h : F → M (simultane Heirat),
so daß h(x) ∈ ϕ(x) für alle x ∈ F ?
4. Optimierungsaufgaben: z.B. Rucksackproblem.
1
Grundlegendes über endliche Mengen
1.1
Begriffsbestimmungen und Rechenregeln
Es sei N die Menge der natürlichen Zahlen (ohne 0), es sei N0 = N ∪ {0}. Für n ∈ N0 sei
n := {1, 2, . . . , n}. Ferner sei für n, m ∈ N (oder auch in Z) das Intervall hn, mi erklärt
durch hn, mi := {i ∈ Z | n ≤ i ≤ m}. Zusätlich sei noch [n] := h0, n − 1i, wenn n ∈ N0 .
Definition 1.1.
Eine nichtleere Menge A heißt endlich, wenn für eine geeignete
natürliche Zahl n ∈ N eine bijektive Abbildung f : n → A existiert. Die leere Menge ∅
heißt ebenfalls endlich.
Ist A endlich und nichtleer, so heißt |A| := card(A) := #A die Mächtigkeit oder der
Umfang von A. Dabei ist |∅| := 0 und |A| := n, wenn A 6= ∅ und wenn für n ∈ N eine
bijektive Abbildung f : n → A existiert. Wenn |A| = n, so heißt A auch n-elementig
oder eine n-Menge. (Allgemein heißen zwei nicht notwendigerweise endliche Mengen A
und B gleichmächtig, wenn es eine bijektive Abbildung f : A → B gibt.)
Bemerkung 1.1. |A| ist für jede endliche Menge wohldefiniert. Es gilt nämlich:
Sind n, m ∈ N und sind f : n → A, g : m → A bijektiv, so ist n = m.
Dazu genügt es zu zeigen, daß aus der Existenz einer injektiven Abbildung ϕ : n → m folgt,
daß n ≤ m. (Man nehme ϕ := g −1 ◦ f und vertausche dann die Rollen von n und m.) Der
eigentliche Beweis erfolgt durch Induktion über n. Wenn n = 1 ist, ist alles klar, da m ≥ 1.
Für den Schluß von n auf n + 1 unterscheidet man den Fall a) ϕ(n + 1) = m. Dann aber ist
ϕ|n eine injektive Abbildung von n nach h1, m − 1i. Also ist nach Induktionsvoraussetzung
n ≤ m − 1 oder n + 1 ≤ m. Im Falle b) (ϕ(n + 1) beliebig) definieren wir ϕ∗ = τm,ϕ(n+1) ◦ ϕ,
wobei τ := τm,ϕ(n+1) : m → m, definiert durch τ (m) := ϕ(n + 1), τ (ϕ(n + 1)) := m und
τ (x) = x sonst, eine bijektive Abbildung von m in sich ist. Dann ist ϕ∗ injektiv und außerdem
ϕ∗ (n + 1) = m. Also ist nach Fall a) n + 1 ≤ m.
Bemerkung 1.2. Mit den obigen Überlegungen erkennt man sofort, daß es für jede
n-Menge A und jedes a ∈ A eine bijektive Abbildung fa : n → A gibt mit fa (n) = a.
Bemerkung 1.3. Es gelten u.a. die folgenden Aussagen:
1. Ist A endlich und f : A → B bijektiv, so ist B endlich und |A| = |B|.
2. Sind A, B endlich, so folgt aus |A| = |B| die Existenz einer bijektiven Abbildung
f : A → B.
3. Jede Teilmenge B einer endlichen Menge A ist endlich. Ferner ist dann |B| ≤ |A|
mit Gleichheit genau dann, wenn A = B. (Echte Teilmengen einer endlichen Menge
haben echt kleinere Mächtigkeit.)
2
4. Ist A endlich und f : A → B eine Abbildung, so ist f (A) endlich und |f (A)| ≤ |A|
mit = genau dann, wenn f injektiv ist.
5. Für eine Abbildung f : A → A einer endlichen Menge A in sich sind die Eigenschaften injektiv, surjektiv und bijektiv zueinander äquivalent.
6. Sind A, B endlich, so auch A ∪ B. Ferner gilt |A ∪ B| = |A| + |B| − |A ∩ B|; also
ist |A ∪ B| = |A| + |B| genau dann, wenn A ∩ B = ∅.
7. Sind A, B endlich, so auch A × B. Ferner gilt |A × B| = |A| · |B|.
8. Die Potenzmenge P(A) := {B | B ⊆ A} einer endlichen Menge A ist endlich, und
es gilt |P(A)| = 2|A| .
Beweis: Die Aussagen 1) und 2) folgen unmittelbar aus der Definition.
Zum Beweis von 3) genügt es zu zeigen, daß jede echte Teilmenge B der endlichen Menge
A wieder endlich ist und daß |B| < |A|. Dies geschieht durch Induktion über n := |A|.
Im Fall n = 0 ist nichts zu zeigen. Sei jetzt |A| = n + 1 und die Behauptung richtig für
alle n-Mengen A0 . Sei B
A. Dann existiert ein a ∈ A mit a ∈
/ B. Nach Bem. 1.2
existiert eine bijektive Abbildung f : h1, n + 1i → A mit f (n + 1) = a. Dann ist
f |n : n → A0 := A \ {a} bijektiv (weswegen A0 eine n-Menge ist) und B ⊆ A0 . Ist
B = A0 , so ist B endlich und |B| = n < n + 1 = |A|. Im Falle B
A0 kann man die
Induktionsvoraussetzung anwenden.
Bezüglich 4) kann wegen 1) und 2) o.B.d.A A = n (und f (A) = B) angenommen werden.
Wir definieren dann g : B → A durch g(x) := min f −1 (x). Dann ist wegen f (g(x)) = x
die Abbildung g injektiv und g(B) als Teilmenge von A endlich. Also sind B und g(B)
gleichmächtig. Da g(B) als Teilmenge von A endlich ist, ist auch B endlich. Außerdem
ist |B| = |g(B)| ≤ |A|. Da g(B) = A genau dann ist, wenn f −1 (x) für alle x ∈ B
einelementig ist (d.h., wenn f injektiv ist), folgt auch der Rest der Behauptung.
Nun zu 5). Ist f : A → A surjektiv, so folgt aus 4), daß f injektiv ist. Umgekehrt
folgt aus der Injektivität von f , daß |f (A)| = |A|. Wegen f (A) ⊆ A und 3) folgt dann
f (A) = A, also die Surjektivität von f .
Für den Beweis von 6) betrachten wir zunächst denn Fall A ∩ B = ∅. Sind f : n → A
und g : m → B bijektiv, so definieren wir für k := m + n die Abbildung h : k → A ∪ B
durch h(j) := f (j) für 1 ≤ j ≤ n und h(j) := g(j − n) für n + 1 ≤ j ≤ k = n + m. (h
ist wohldefiniert, da A und B disjunkt sind.) Dann rechnet man leicht nach, daß h sogar
bijektiv ist. Im allgemeinen Fall hat man zu beachten, daß A ∪ B = A ∪ (B \ (A ∩ B)),
daß A und B \ (A ∩ B) disjunkt sind und daß wegen der Disjunktheit von A ∩ B und
B\(A∩B) aus dem ersten Teil |B| = |(A ∩ B) ∪ (B \ (A ∩ B))| = |A ∩ B|+|B \ (A ∩ B)|
folgt. (Letzteres bedeutet ja |B \ (A ∩ B)| = |B| − |A ∩ B|.)
Der Beweis von 7) erfolgt durch Induktion über n = |A|. Wegen ∅ × B = ∅ ist der
Induktionsanfang n = 0 klar. Ist |A| = n + 1, so wähle man ein a ∈ A. Mit A0 := A \ {a}
ist dann A die disjunkte Vereinigung von A0 und der einelementigen Menge {a}. Dann
ist aber A × B die disjunkte Vereinigung von A0 × B und {a} × B. Die letzte Menge ist
offensichtlich zu B gleichmächtig (man betrachte x 7→ (a, x)). Dann folgt das Gewünschte
aus der Induktionsvoraussetzung und aus 6).
Die Gültigkeit von 8) erschließt man ebenfalls durch Induktion. Da P(∅) = {∅} ist der
Induktionsanfang n = |A| = 0 wieder klar. Ist |A| = n + 1 (und A0 , a wie in 7)), so
betrachtet man die Abbildung γ : P(A) → P(A) mit γ(B) := B \ {a}, falls a ∈ B, und
3
γ(B) := B ∪ {a}, falls a ∈
/ B. Dann ist γ wohldefiniert und wegen γ ◦ γ = idP(A) sogar
0 .
bijektiv. Da P(A) = P(A )∪γ(P(A0 )) (die erste Menge ist die Menge aller Teilmengen von
A, die a enthalten, die zweite die derjenigen Teilmengen, die a nicht enthalten), folgt aus
der Gleichmächtigkeit von P(A0 ) und γ(P(A0 )), der Induktionsvoraussetzung und aus 6)
die Behauptung.
2
Bemerkung 1.4. (Rechenregeln für Summen und Produkte) Es sei (H, +) eine kommutative Halbgruppe mit neutralem Element 0, d.h., es sei + eine assoziative innere
Verknüpfung auf H, die zusätzlich kommutativ ist, und es gelte x + 0 = x für alle x ∈ H.
Für k, n ∈ N0 und a0 , a1 , . . . , ak , . . . , an , . . . ∈ H erklärt man dann rekursiv
½
n
X
0P
falls n < k
ai :=
( n−1
a
)
+
a
falls n ≥ k
n
i=k i
i=k
Ist die Verknüpfung
Q multiplikativP(mit · anstelle von + und 1 anstelle von 0) geschrieben,
so schreibt man
anstelle von .
Es P
gelten dann
üblichen
Pdie
Pn (und bekannten) Rechenregeln, z.B.
n
m
a) Pi=k ai = Pi=k ai + i=m+1 ai für k ≤ m ≤ n oder
b) ni=k ai = ni=k aϕ(i) , wenn k ≤ n und ϕ : hk, ni → hk, ni eine beliebige Bijektion ist.
Ferner
Pn noch
c)
i=1 ai = na, wenn a1 = a2 = . . . = an = a und n ∈ N0 . Die vorletzte Regel
ermöglicht es den Begriff der ungeordneten Summe einzuführen. Ist I eine n-Menge und,
falls n > 0, f : n → I bijektiv, so erklärt man für eine Familie (ai )i∈I in H, d.h., für eine
Abbildung
i 7→ ai von I nach H,
P
P
P
n
i∈I ai :=
j=1 af (j) . Für I = ∅ setzt man
i∈I ai := 0.
(Entsprechend
P verfährt man bei der Einführung ungeordneter Produkte.)
Der Wert nj=1 af (j) ist von der speziellen Wahl der Bijektion unabhängig. Ist nämlich
g : n → I eine (andere) Bijektion, so ist ϕ := f −1 ◦ g eine Bijektion von n in sich. Mit
bj := af (j) ergibt sich dann
n
X
af (j) =
j=1
n
X
bj =
j=1
n
X
bϕ(j) =
j=1
n
X
af (ϕ(j)) =
j=1
n
X
ag(j) .
j=1
Der Beweis für a) und b) verläuft in etwa folgendermaßen. Bezüglich a) führt man einen
Induktionsbeweis über ` = n − k, wobei für ` = 0 alles klar ist. Für m = n ist ebenfalls
Pn alles
klar.
i=k ai =
Pn−1 Für den Schluß von ` auf ` + 1 und k ≤ m < n = k + ` + 1 schreibt man Pn−1
a
+
a
.
Weil
k
≤
m
≤
n
−
1
=
k
+
`,
ergibt
die
Induktionsvoraussetzung
dann
i
n
i=k
i=k ai =
Pm
Pn−1
a
+
a
und
insgesamt
i=k i
i=m+1 i
n
X
i=k
ai =
m
X
i=k
ai + (
n−1
X
ai + an ) =
i=m+1
m
X
i=k
ai +
n
X
ai .
i=m+1
Um b) zu zeigen, wendet man wieder Induktion nach ` = n − k an. Die Fälle ` = 0, 1 sind
offensichtlich. (Es gibt nur eine bijektive Abbildung einer einelementigen Menge in sich.) Wenn
ϕ(n) = n kann man die Summe zerlegen in die Summe von k bis n − 1 und den restlichen
Term aϕ(n) = an . Auf die erste Summe kann man dann die Induktionsvoraussetzung anwenden.
4
Wenn ϕ(n) 6= n ist ϕ(j) = n für ein j mit k ≤ j < n. Es sei dann ϕ∗ = ϕ ◦ τ und τ := τj,n (vgl.
mit der Definition von τ aus dem Beweis nach Bemerkung 1.1). Dann ist ϕ∗ (n) = n = ϕ(j),
ϕ∗ (j) = ϕ(n) und ϕ∗ (i) = ϕ(i) sonst. Daraus folgt (mit Punkt a) und wegen der Gültigkeit von
b) für ϕ∗ ):
n
X
aϕ(i) =
i=k
j−1
X
aϕ(i) + aϕ(j) +
=
aϕ∗ (i) + aϕ∗ (n) +
=
=
i=k
n
X
n−1
X
aϕ∗ (i) + aϕ∗ (j) =
i=j+1
i=k
j−1
X
aϕ(i) + aϕ(n) =
i=j+1
i=k
j−1
X
n−1
X
aϕ∗ (i) + aϕ∗ (j) +
n−1
X
aϕ∗ (i) + aϕ∗ (n) =
i=j+1
aϕ∗ (i) =
i=k
n
X
ai
i=k
Die Übertragung von a) auf ungeordnete Summen ergibt die folgende Regel: Ist I =
.
J ∪K, I endlich, so ist
X
X
X
X
ai =
ai +
ai .
ai =
.
i∈J
i∈K
i∈I
i∈J ∪K
Bemerkung 1.5. (Potenzmenge und charakteristische Funktionen) Für Mengen M, N
ist Abb(N, M ) := M N die Menge aller Abbildungen f : M → N . Für die Menge
M und für A ∈nP(M ) ist die charakteristische Funktion cA ∈ Abb(M, {0, 1}) definiert
1 falls x ∈ A
durch cA (x) =
Die Abbildung c : P(A) → Abb(M, {0, 1}) ist definiert
0 sonst.
durch c(A) := cA . Dann sieht man schnell, daß c bijektiv ist; c−1 ist gegeben durch
c−1 (f ) = f −1 (1). Faßt man {0, 1} als den Körper mit zwei Elementen auf, so ist, wie aus
der Algebra bekannt, Abb(M, {0, 1}) mit punktweiser Definition von + und · ein Ring.
Für Teilmengen A, B, Ai (i ∈ I, I endlich und nicht leer) von M gilt dann
. = cA + cB ,
1. cA∩B = cA · cB und cA∪B
2. c∅ = 0, cM = 1,
Q
3. cTi∈I Ai = i∈I cAi ,
4. cM \A = 1 − cA
S
T
und mit Hilfe der de Morganschen Regeln M \ ( i∈I Ai ) = i∈I (M \ Ai )
Q
5. cSi∈I Ai = 1− i∈I (1−cAi ), insbesondere cA∪B = 1−(1−cA )(1−cB ) = cA +cB −cA∩B .
(Diese Regeln gelten aber auch dann, wenn man 0 und 1 als Null- bzw. Einselement eines
beliebigen kommutativen Ringes mit Einselement auffaßt.)
Nun sind wir mit Hilfe von Summen und Produkten in der Lage neue Gesetzmäßigkeiten zu formulieren. Zuvor aber noch ein interessanter algebraischer Zusammenhang
zwischen P(M ) und Abb(M, {0, 1}), wobei die Menge {0, 1} hier wieder als Körper mit
zwei Elementen aufgefaßt wird.
5
Für Mengen A, B ist ihre symmetrische Differenz definiert durch A4B := (A ∪ B) \
(A ∩ B). Man rechnet nun leicht nach, daß cA4B = cA∪B − cA∩B = cA + cB − 2cA∩B =
cA + cB . Außerdem ist cA∩B = cA · cB . Daraus folgt, weil (Abb(M, {0, 1}), +, ·) ein
kommutativer Ring mit Eins ist und weil c bijektiv ist, daß (P(M ), 4, ∩) ein ebensolcher
ist und c ein Isomorphismus zwischen ihnen.
Bemerkung 1.6. Es sei (Ij )j∈J eine endliche Familie endlicher Mengen (also J und
alle Ij endlich) und es sei (R, +) eine kommutative Halbgruppe mit neutralem Element.
Dann gilt:
P
S
1. I := j∈J Ij ist endlich und |I| ≤ j∈J |Ij |. Gleichheit gilt genau dann, wenn die
Ij paarweise disjunkt sind.
Q
S
2. Das cartesische Produkt j∈J Ij := {f ∈ Abb(J, j∈J Ij ) | f (j) ∈ Ij für alle j ∈
¯Q
¯ Q
¯
¯
J} ist endlich und ¯ j∈J Ij ¯ = j∈J |Ij |.
3. Insbesondere ist für zwei endliche Mengen I, J die Menge Abb(J, I) = I J endlich
und |Abb(I, J)| = |I||J| .
.
S
4. Sind die Ij paarweise disjunkt, so gilt für alle Familien (ai )i∈I (I := j∈J Ij ):
´
P
P ³P
a
=
a
(Allgemeines Assoziativitätsgesetz).
i
i
i∈I
j∈J
i∈Ij
P
5. Sind I, J endlich und ist (aij )(i,j)∈I×J eine Familie in R, so gilt (i,j)∈I×J aij =
´ P ¡P
¢
P ³P
i∈I aij .
j∈J
i∈I
j∈J aij =
6. Sind
g : J → I bijektiv
und istP(ai )i∈I eine Familie in R, so gilt:
P
P f : I → J,P
i∈I ai
j∈J ag(j) =
i∈I ai und
j∈J af −1 (j) =
7. Ist R sogar ein kommutativer Ring mit Eins und ist für alle j ∈ J eine Familie
(ai,j )i∈Ij in R gegeben, so gilt das allgemeine Distributivitätsgesetz


X Y
Y X

af (j),j .
ai,j  =
j∈J
i∈Ij
f∈
Q
j∈J
Ij j∈J
8. Speziell für Ij = {0, 1}, j ∈ n = J, a0,j = 1, a1,j = aj ergibt sich daraus (mit
einigen Zwischenrechnungen):
n
Y
(1 + aj ) =
j=1
X Y
P
a` .
L∈ (n) `∈L
9. Für jede
P Teilmenge A der endlichen Menge M berechnet sich |A| als
|A| = x∈M cA (x)
Beweis: (Andeutungen) Die Punkte 1, 2 und 4 erledigt man durch Induktion über
m = |J|, wobei frühere Ergebnisse (z.B. über geordnete Summen) heranzuziehen sind.
Punkt 3 ist der Spezialfall Ij = I von 2. Punkt 5 folgt aus 4 mit Ij = I × {j}. Bezüglich
Punkt 6 setze man bj := af −1 (j) und wähle eine bijektive Abbildung h : n → I.PDann
ist f ◦ h eine Bijektion zwischen n und J. Deswegen folgt (nach Definition von j∈J ),
6
P
P
bj = n`=1 b(f ◦h)(`) . Wegen b(f ◦h)(`) = af −1 ((f ◦h)(`)) = ah(`) erhält man j∈J bj =
P
P
−1
`=1 ah(`) =
i∈I ai . (Letzteres ist nach Definition von
i∈I richtig.) Mit f := g
ergibt sich die entsprechende Aussage für g. FürPPunkt 7 verwendet
man ebenfalls
P
Induktion. Ferner muß man zunächst die Regel b i∈I ai =
i∈I bai (ein Spezialfall)
gesondert beweisen. Ist das erledigt, so besteht der wesentliche Schritt in den folgenden
Rechnungen und Überlegungen:



 

Y
X
Y X
X


ai,j  =
ai,j  · 
ai,j0  =
.
i∈Ij
j∈J
i∈Ij
i∈Ij0
j∈J ∪{j0 }





Ã
!
X
X Y
X Y
X

ai,j0  =
af (j),j  
af (j),j ai,j0 
= 
daß
Pn
P
j∈J
f∈
Q
j∈J
Ij j∈J
Q
f ∈ j∈J Ij
i∈Ij0
i∈Ij0
j∈J
Q
Q
. } Ij , wobei eine Bijektion λ gegeben ist
Es ist j∈J Ij × Ij0 gleichmächtig zu j∈J ∪{j
0
Q
∗
∗
∗
. } Ij den
durch (f, i) 7→ f mit f |J := f und f (j0 ) := i. Definiert man für f ∗ ∈ j∈J ∪{j
0
P
P
P
Q
Q
Q
. } af ∗ (j),j , so erhält man wegen f ∈
=
Wert Af ∗ := j∈J ∪{j
(f,i)∈ j∈J Ij ×Ij0
i∈Ij0
0
j∈J Ij
Q
und j∈J af (j),j ai,j0 = Af ∗ = Aλ((f,i)) durch Anwendung von Punkt 6, daß




Ã
!
Y
X
X
X Y
X


ai,j  =
Aλ(f,i) =
af (j),j ai,j0  =
Q
Q
.
i∈Ij
i∈Ij0
j∈J
f ∈ j∈J Ij
(f,i)∈ j∈J Ij ×Ij0
j∈J ∪{j0 }
Y
X
X
af ∗ (j),j .
Af ∗ =
=
Q
Q
.
∗
∗
. 0 } Ij j∈J ∪{j0 }
. 0}
f ∈ j∈J ∪{j
f ∈ j∈J ∪{j
Q
P
Q
Das ergibt für Punkt 8 zunächst nj=1 (1 + aj ) = f ∈{0,1}n j∈n af (j),j . Wegen a1,j = aj ,
a0,j = 1 und mit Hilfe der Bijektion f 7→ f −1 (1) zwischen {0, 1}n und P(n) folgt
n
Y
X
(1 + aj ) =
j=1
Y
f ∈{0,1}n j∈f −1 (1)
aj =
X Y
P
a` .
L∈ (n) `∈L
Der letzte Punkt endlich ergibt sich aus folgender Rechnung:
X
X
X
X
X
cA (x) =
1+
0 = |A| 1 + |M \ A| 0 = |A| .
cA (x) =
cA (x) +
x∈M
x∈A
x∈M \A
x∈A
x∈M \A
2
1.2
Binomialkoeffizienten
Definition 1.2.
Es sei M eine n-Menge und k ∈ N0 . Dann ist Pk (M ) := {A ∈
P(A) | |A| = k} die
¡n¢Menge aller k-elementigen Teilmengen von M . Die Mächtigkeit von
P
(M
)
wird
mit
bezeichnet:
k
¡nk¢
:= |Pk (M )| für jede n-Menge M .
k
Bemerkung 1.7. Diese Definition ist sinnvoll. Es gelten sogar viel allgemeiner folgende Sachverhalte: Sind M, M 0 , N, N 0 endliche Mengen, wobei M zu M 0 und N zu N 0
gleichmächtig sein möge, so folgt
7
1. Für alle k ∈ N sind Pk (M ) und Pk (M 0 ) gleichmächtig.
2. Es ist Abb(M, N ) zu Abb(M 0 , N 0 ) gleichmächtig.
3. Dies gilt auch für die Mengen Inj(M, N ) und Inj(M 0 , N 0 ) bzw. für Surj(M, N )
und Surj(M 0 , N 0 ), aber auch für Bij(M, N ) und Bij(M 0 , N 0 ) und für S(M ) und
S(M 0 ). (Dabei ist Inj(M, N ) die Menge aller injektiven Abbildungen f : M → N ,
Surj(M, N ) die Menge aller surjektiven Abbildungen f : M → N , Bij(M, N ) :=
Inj(M, N ) ∩ Surj(M, N ) die Menge aller bijektiven Abbildungen zwischen M und
N und S(M ) := Bij(M, M ).)
Sind nämlich ϕ : M → M 0 und ψ : N → N 0 bijektiv, so ist für f : M → N die Abbildung
f ∗ := ψ ◦f ◦ϕ−1 eine, die M 0 nach N 0 abbildet. Die Zuordnung Λ = Λϕ,ψ : Abb(M, N ) →
Abb(M 0 , N 0 ), Λ(f ) := f ∗ = ψ ◦ f ◦ ϕ−1 ist dann eine Bijektion, die injektive (surjektive)
Abbildungen auf ebensolche abbildet. Ferner ist offensichtlich die Zuordnung A 7→ ϕ(A)
von P(M ) → P(M 0 ) bijektiv; sie hat außerdem die Eigenschaft, daß dadurch Pk (M ) auf
Pk (M 0 ) abgebildet wird.
Satz 1.1. Für n, k ∈ N0 gilt:
¡ ¢ ¡ n ¢
1. nk = n−k
, wenn 0 ≤ k ≤ n.
¡n¢ ¡n¢
¡ ¢ ¡ n ¢
¡ ¢
2. 0 = n = 1, n1 = n−1
= n, wenn n ≥ 1, nk = 0 für k > n.
Pn ¡n¢
n
3.
k=0 k = 2 .
¡
¢
Pn
k n
4.
(−1)
= 0, wenn n > 0.
k=0
k
¡n+1¢ ¡n¢ ¡ n ¢
5. k = k + k−1 , wenn 0 < k ≤ n.
¡ ¢
¡ ¢
6. n n−1
= k nk , wenn 0 < k ≤ n.
k−1
¡ ¢
n!
k
= k!(n−k)!
, wenn 0 ≤ k ≤ n, wobei (n)k := n(n − 1) . . . (n − k + 1) =
7. nk = (n)
Qk−1 k!
j=0 (n − j) und k! := (k)k = k(k − 1) . . . 2 · 1.
Beweis: Die Abbildung A 7→ M \ A bildet die Potenzmenge von M in sich ab. Sie ist
involutorisch (zu sich selbst invers), also bijektiv. Daher bildet sie Pk (M ) bijektiv auf
Pn−k (M ) ab, wenn 0 ≤ k ≤ n. Damit ist 1) (und auch 2)) erledigt. 3) folgt aus P(M ) =
.n
S
k=0 Pk (M ). Die Aussage aus 4) besagt umformuliert, daß |{A ⊆ M | |A| gerade}| =
|{A ⊆ M | |A| ungerade}|. Wenn a ∈ M fest gewählt wird, ist τ : P(M ) → P(M ) mit
τ (A) := A4{a} wegen τ 2 = id bijektiv. Dabei ist |τ (A)| genau dann gerade (ungerade),
wenn |A| ungerade (gerade) ist. Daher bildet τ die Menge aller Teilmengen von M
mit gerader Mächtigkeit bijektiv auf die der Teilmengen ungerader Mächtigkeit ab. Sie
haben daher dieselbe Mächtigkeit (und zwar 2n−1 , da ihre — disjunkte — Vereinigung
die gesamte Potenzmenge ergibt). Man könnte die beiden eben besprochenen Punkte
auch mit Hilfe des binomischen Lehrsatzes beweisen, da 2n = (1 + 1)n und 0 = (1 − 1)n ,
wenn n > 0.
Der binomische Lehrsatz ergibt sich kombinatorisch aus Bem. 1.6, Punkt 8) mit
aj = a für j = 1, 2, . . . , n so:
(1 + a)n =
X
P
a|L| =
n
X
X
k=0 L∈
L∈ (n)
8
Pk (n)
ak =
=
n
X
k=0



X
L∈
Pk (n)
n µ ¶
X
n k
1 a =
a .
k
k
k=0
Zum Beweis von 5) wählt man aus der (n + 1)-Menge M ein Element a, setzt M 0 :=
.
M \ {a}, P 0 := Pk (M 0 ), P 00 := {A ∈ Pk (M ) | a ∈ A}. Dann ist Pk (M ) = P 0 ∪P 00 und P 00
gleichmächtig mit Pk−1 (M 0 ). (Eine Bijektion zwischen diesen beiden Mengen ist gegeben
durch P 00 3 A 7→ A \ {a}.)
Um 6) zu zeigen, betrachtet man für eine n-Menge M und k > 0 die Menge
B := {(a, A) | A ∈ Pk (M ), a ∈ A}.
Für a ∈ M sei Pa := {(a, A) | (a, A) ∈ B}, für A ∈ Pk (M ) sei QA := {(a, A) | (a, A) ∈ B}.
.
.
S
S
Dann ist B = a∈M Pa = A∈Pk (M ) QA . Da Pa zu Pk−1 (M \ {a}) gleichmächtig ist (man
betrachte (a, A) 7→ A \ {a}) und da QA zu A gleichmächtig ist, folgt
µ
¶
X
X µn − 1¶
n−1
|B| =
|Pa | =
=n
und
k
−
1
k
−
1
a∈M
a∈M
µ ¶
X
n
|QA | =
k.
|B| =
k
Pk (M )
A∈
Der letzte Punkt folgt dann daraus durch Induktion über k.
2
Satz 1.2. (Vandermondesche Identität) Für alle m, n, k ∈ N0 gilt
¡n+m¢ Pk ¡n¢¡ m ¢
¡2n¢ Pn ¡n¢2
=
,
für
m
=
n
=
k
ergibt
das
speziell
= j=0 j .
j=0
k
j
k−j
n
Beweis: Eine erste Möglichkeit des Beweises läuft über sogenannte erzeugende Funktionen (ein vielfältig anwenbares algebraisches Werkzeug in der
Für
PKombinatorik).
∞ ¡ α¢ j
beliebige reelle α konvergiert die binomische Reihe Bα (x) :=
x
absolut
für
j=0 j
α
¡alle
¢ |x| < 1 und es sind für diese x die Werte Bα (x) und (1 + x) gleich. (Dabei ist
α
:= (α)k /k! für alle reellen Zahlen sinnvoll erklärt.) Wenn man in der Beziehung
j
Bα+β (x) = (1 + x)α+β = (1 + x)α (1 + x)β = Bα (x)Bβ (x) die rechte Seite ausmultipliziert,
nach Potenzen von xj ordnet und den Koeffizienten von xk mit dem von xk in der Reihe
Bα+β (x) vergleicht, erhält man
µ
α+β
k
¶
¶
k µ ¶µ
X
α
β
=
.
j
k
−
j
j=0
Eine zweiter (inhaltlich argumentierender) Zugang geht von einer n-Menge N und einer
.
dazu disjunkten m-Menge M aus. Dann erhält man durch (A, B) 7→ A∪B eine Bijektion
.k
S
.
zwischen j=0 Pj (N ) × Pk−j (M ) und Pk (N ∪M ).
2
1.3
Die Siebformel und Anwendungen
Die Siebformel dient der Berechnung der Mächtigkeit der endlichen Vereinigung endlicher
Mengen und stellt die Verallgemeinerung der Formel |A ∪ B| = |A| + |B| − |A ∩ B| dar.
9
Satz 1.3. (Siebformel) Es seien A1 , A1 , . . . An endliche Mengen. Dann gilt
¯
¯
¯
¯
n
¯[
¯
¯\ ¯
X
¯
¯
¯
¯
(−1)|J|−1 ¯ Aj ¯
¯ Aj ¯ =
¯
¯
¯
¯
j=1
j∈J
J∈P(n)\{∅}
¯
¯
¯
¯
n
¯
¯
¯\ ¯
[
X
¯
¯
¯
|J| ¯
Aj ¯ =
(−1) ¯ Aj ¯ ,
¯M \
¯
¯
¯
¯
P
j=1
(1)
(2)
j∈J
J∈ (n)
Dabei wirdTin (2) vorausgesetzt, daß M eine (endliche) Menge ist, die alle Aj enthält.
Ferner ist j∈∅ Aj := M .
Beweis: Es Q
genügt, die zweite Formel zu beweisen. Aus Bemerkung 1.5 ergibt sich
Sn
cM \ j=1 Aj = nj=1 (1 − cAj ), was wegen Punkt 8 aus Bemerkung 1.6
X Y
X
Y
cM \Snj=1 Aj =
(−cAj ) =
(−1)|J|
cAj
P
P
J∈ (n) j∈J
oder
X
cM \Snj=1 Aj =
j∈J
J∈ (n)
P
(−1)|J| cTj∈J Aj
J∈ (n)
bedeutet. Der letzte Punkt der Bemerkung 1.6 liefert dann


¯
¯
n
¯
¯
[
X
X
X
¯
¯

Aj ¯ =
(−1)|J| cTj∈J Aj  (x) =
cM \Snj=1 Aj (x) =
¯M \
¯
¯
j=1
x∈M
x∈M
J∈P(n)
X X
(−1)|J| cTj∈J Aj (x) =
=
P
x∈M J∈ (n)
X
=
P
Ã
(−1)|J|
X
!
cTj∈J Aj (x)
=
x∈M
J∈ (n)
X
P
J∈ (n)
¯
¯
¯\ ¯
¯
¯
(−1)|J| ¯ Aj ¯
¯
¯
j∈J
2
Aus diesem Satz ergibt sich z.B. die explizite Darstellung der Eulerschen ϕ-Funktion.
Satz 1.4. Für n ∈ N sei ϕ(n) := |{j ∈ N | 1 ≤ j ≤ n, (j, n) = 1}|. Dann gilt:
¶
Y µ
1
.
1−
ϕ(n) = n
p
p|n
p prim
Beweis: Es sei n = pα1 1 pα2 2 · . . . · pαmm die Primfaktorzerlegung von n (n > 1 o.B.d.A.);
also die pj prim und paarweiseSverschieden und die αj > 0. Sodann sei Aj := {i | 1 ≤
i ≤ n, pj | i} ⊆ n. Dann ist m
j=1 Aj = {i ∈ N | 1 ≤ i ≤ n, (i, n) > 1}, also ϕ(n) =
¯
¯
T
Q
Sm
¯
¯
¯n \ j=1 Aj ¯. Für J ⊆ m ist j∈J Aj die Menge aller i ∈ n, die Vielfache von j∈J pj
¯T
¯
Q
¯
¯
sind, weswegen ¯ j∈J Aj ¯ = n/ j∈J pj . Dann ergibt die Siebformel
ϕ(n) =
X
|J|
(−1) n
J⊂m
Y
j∈J
p−1
j
=n
XY
J⊂m j∈J
(−p−1
j )
=n
m
Y
(1 − p−1
j ).
j=1
2
10
Für endliche Mengen N, M ist |Abb(N, M )| = |M ||N | . Was aber ist |Surj(N, M )|?
Satz ¡1.5.
Für endliche Mengen N, M mit |N | = n, |M | = m gilt: |Surj(N, M )| =
¢
P
m
m
j
− j)n . Insbesondere folgt aus Surj(N, N ) = Bij(N, N ) = S(N ), daß
j=0 j (−1) (m
Pn ¡n¢
|S(N )| = j=0 j (−1)j (n − j)n .
Beweis: Für b ∈ M sei Ab S
die Menge aller f ∈ Abb(N, M ) mit b ∈
/ f (N ). Dann ist
Surj(N, M ) = Abb(N, M ) \ ( b∈M Ab ). Die Siebformel ergibt dann
¯
¯
¯\ ¯
X
¯
¯
|Surj(N, M )| =
(−1)|J| ¯ Aj ¯ .
¯
¯
j∈J
J⊂M
T
Es ist aber j∈J Aj die Menge aller Abbildungen von N nach M , deren Bild in M \ J
¯T
¯
T
¯
¯
enthalten ist. Daher ist j∈J Aj = Abb(N, M \ J) und ¯ j∈J Aj ¯ = |Abb(N, M \ J)| =
(m − |J|)|N | . Das liefert
|Surj(N, M )| =
=
X
J⊂M
m
X
(−1)|J| |Abb(N, M \ J)| =
X
(−1)|J| (m − |J|)|N | =
J⊂M
X
j=0 J∈
(−1)j (m − j)n =
Pj (M )
m µ ¶
X
m
j=0
j
(−1)j (m − j)n
2
Bald werden wir sehen, daß |S(n)| = n!. Da S(n) = Surj(n, n), folgt daraus die wohl
überraschende Beziehung
n µ ¶
X
n
n! =
(−1)j (n − j)n .
j
j=0
1.4
Auswahlen mit Berücksichtigung der Anordnung
Definition 1.3. Es sei M eine endliche Menge und n ∈ N. Dann heißt f : n → M eine
Auswahl mit Berücksichtigung der Anordnung vom Umfang n und mit Wiederholung aus
M . Sie ist eine ohne Wiederholung, wenn f injektiv ist. ( mit“ bedeutet somit eigentlich
”
nicht notwendigerweise ohne Wiederholung.)
Satz 1.6. Für endliche Mengen N, M ist |Abb(N, M )| = |M ||N | und |Inj(N, M )| =
(|M |)|N | . Insbesondere gibt es aus einer m-Menge M genau mn Auswahlen vom Umfang
n mit Wh. und genau (m)n derartige ohne Wh.
Beweis: Die Mächtigkeit von Abb(N, M ) wurde schon früher bestimmt. Zur Bestimmung
der Mächtigkeit von Inj(N, M ) führen wir einen Induktionsbeweis nach n = |N |. Die Fälle
n = 0 (bei richtiger Interpretation) und n = 1 sind klar. Ist N nun eine (n + 1)-Menge,
a ∈ N fest und Ib := Inj(N \ {a}, M \ {b}), wobei b ∈ M , so ist Inj(N, M ) gleichmächtig
.
S
zu b∈M Ib × {b}. (Eine Bijektion ist gegeben durch f 7→ (f |M \{f (a)} , f (a)).
2
Wie gelangt man von Auswahlen mit Berücksichtigung der Anordnung zu solchen ohne“?
”
Intuitiv gesprochen werden zwei Auswahlen mit Berücksichtigung der Anordnung dieselbe
Auswahl ohne Berücksichtigung der Anordnung definieren, wenn sie sich nur um eine
Umnumerierung der Elemente unterscheiden. Im nächsten Abschnitt wird diese Idee
abstrakt untersucht, im übernächsten konkret.
11
1.5
Operationen von Gruppen auf Mengen
Definition 1.4. Es sei X eine nichtleere Menge und (G, ·) eine Gruppe (mit neutralem
Element e). Dann heißt eine Abbildung ∗ : G × X → X (bzw. das Tripel (G, X, ∗)) eine
Operation (oder Aktion) von G auf X, wenn
i) e ∗ x = x für alle x ∈ X und wenn
ii) (g · h) ∗ x = g ∗ (h ∗ x) für alle x ∈ X und alle g, h ∈ G.
Beispiele
1. Für jede nichtleere Menge X und jede Untergruppe G von (S(X), ◦) definiert
(π, x) 7→ π ∗ x := π(x) eine Operation von G auf X.
2. Sind N, M nichtleere Mengen und ist G eine Untergruppe von S(N ), so ist durch
∗ : G × Abb(N, M ) → Abb(N, M ), π ∗ f := f ◦ π −1 eine Operation von G auf
Abb(N, M ) definiert.
3. Für jede Gruppe G und jede Untergruppe H sind (h, g) 7→ g · h−1 und (h, g) 7→ h · g
Operationen von H auf G.
Bemerkung 1.8. Durch x ∼ y :⇔ ∃g ∈ G : y = g ∗ x ist eine Äquivalenzrelation
auf X definiert, die Äquivalenzklasse x eines x ∈ X ist gegeben durch x = G ∗ x :=
{g ∗ x | g ∈ G}, die Bahn (der Orbit) von x bezüglich G. Für x ∈ X ist Gx := {g ∈
G | g ∗ x = x} eine Untergruppe von G, die Fixgruppe von x. Ferner ist die Menge G/Gx
der Linksnebenklassen von G bezüglich Gx gleichmächtig zur Bahn G ∗ x. Die Menge der
Äquivalenzklassen wird in Verallgemeinerung zur Operation einer Untergruppe auf einer
.
S
Gruppe mit X/G bezeichnet: X/G = {G ∗ x | x ∈ G}. (X = x∈X/G x.)
Beweis: Es ist x ∼ x, da x = e ∗ x. Aus y = g ∗ x =: gx (y ∼ x) folgt g −1 y = g −1 (gx) =
(g −1 g)x = ex = x, also x ∼ y. Aus y = gx, z = hy folgt z = (hg)x, also aus y ∼ x
und z ∼ y auch z ∼ x. Der Ausdruck G ∗ x für die Äquivalenzklasse von x ergibt sich
dann aus der Definition. Es ist e ∈ Gx , also Gx 6= ∅. Für g ∈ Gx gilt gx = x und daher
x = ex = (g −1 g)x = g −1 (gx) = g −1 x oder g −1 ∈ Gx . Ferner folgt aus gx = hx = x
(g, h ∈ Gx ), daß (gh)x = g(hx) = gx = x, also gh ∈ Gx .
Es ist G/Gx = {gGx | g ∈ G} die Menge der Linksnebenklassen gGx , die gerade die
Äquivalenzklassen von G bezüglich der ersten der beiden oben definierten Gruppenaktion
von H := Gx auf G sind. Wenn gGx = g 0 Gx , existiert ein h ∈ Gx mit g = g 0 h. Daher
ist gx = g 0 (hx) = g 0 x. Somit ist τ : G/Gx → G ∗ x =: Gx, τ (gGx ) := gx wohldefiniert
und surjektiv. Wenn τ (gGx ) = τ (g 0 Gx ), ist gx = g 0 x und deswegen g −1 g 0 ∈ Gx bzw.
gGx = g 0 Gx .
2
Daraus ergibt sich das folgende Resultat.
Satz 1.7. Sind in der Gruppenoperation (G, X, ∗) die Gruppe G und die Menge X
endlich, so gilt für alle x ∈ X: |G ∗ x| = |G| / |Gx |.
Beweis: Es ist G/Gx gleichmächtig zu G ∗ x. Die Äquivalenzklassen gGx sind alle zu Gx
.
S
gleichmächtig (h 7→ gh bildet Gx bijektiv auf gGx ab). Wegen G = g∈G/Gx g folgt dann
|G| = |G/Gx | |Gx |.
2
12
1.6
Auswahlen ohne Berücksichtigung der Anordnung
Definition 1.5. Eine Auswahl vom Umfang n ohne Berücksichtigung der Anordnung
mit Wiederholung aus der endlichen Menge M ist eine Bahn Sn ∗ f eines f ∈ Abb(n, M )
bezüglich der Operation von S(n) := Sn auf Abb(n, M ), π ∗ f := f ◦ π −1 . Diese Auswahl
ist eine ohne Wiederholung, wenn f injektiv ist. (Diese Festlegung ist sinnvoll, da mit f
alle g ∈ Sn ∗ f injektiv sind.)
Bemerkung 1.9.
Ist M zu M 0 gleichmächtig und ϕ : M → M 0 bijektiv, so sind
die Mengen der n-Auswahlen ohne Berücksichtigung der Anordung aus M und aus M 0 ,
Abb(n, M )/Sn bzw. Abb(n, M 0 )/Sn , gleichmächtig. Eine Bijektion zwischen ihnen ist
gegeben durch Sn ∗ f 7→ Sn ∗ (ϕ ◦ f ).
Beweis: Als wesentlicher Punkt ist nur die Wohldefiniertheit zu überlegen. Wenn g =
f ◦ π −1 (g ∈ Sn ∗ f ) dann ist ϕ ◦ g = ϕ ◦ f ◦ π −1 , also Sn ∗ (ϕ ◦ g) = Sn ∗ (ϕ ◦ f ).
2
Bemerkung 1.10. Sind f, g ∈ Abb(n, M ), M endlich, so sind die Bahnen von f und
g bezüglich Sn genau dann gleich, wenn |f −1 (m)| = |g −1 (m)| für alle m ∈ M .
Beweis: Aus g = f ◦ π für ein π ∈ Sn folgt natürlich g −1 (m) = π −1 (f −1 (m)), woraus
wegen der Bijektivität von π das Gewünschte folgt. Umgekehrt folgt mit Am := f −1 (m),
Bm := g −1 (m) aus |Am | = |Bm | für alle m ∈ M , daß es Bijektionen πm : Bm → Am gibt.
Weil
.
.
[
[
n=
Am =
Bm ,
m∈M
m∈M
ist ein π ∈ Sn durch π|Bm := πm , m ∈ M , wohldefiniert. Ist x ∈ n, so existiert (genau) ein
m ∈ M , so daß x ∈ Bm . Dann aber ist g(x) = m, π(x) ∈ Am und folglich f (π(x)) = m,
also f ◦ π = g.
2
Bemerkung
1.11. Für f ∈ Abb(n, M ) ist die Fixgruppe S(n)f isomorph zum Produkt
Q
−1
(m)) und daher
m∈M S(f
|S(n) ∗ f | = Q
|S(n)|
n!
=Q
.
−1
−1 (m)|!
(m))|
m∈M |S(f
m∈M |f
Außerdem ist Abb(n, M )/ S(n) gleichmächtig zur Menge gPart(n, MP
) aller geordneten
Partitionen von n in |M | Teile: gPart(n, M ) := {h ∈ Abb(M, N0 ) | m∈M h(m) = n}.
Eine Bijektion Λ ist gegeben durch die Abbildung S(n) ∗ f 7→ (m 7→ |f −1 (m)|) (also
Λ(S(n) ∗ f )(m) := |f −1 (m)|.)
Beweis: Die Permutation π ∈ Sn = S(n) liegt genau dann in S(n)f , wenn f ◦ π =
f , d.h., wenn π −1 (f −1 (m)) = f −1 (m). Das bedeutet, daß die Einschränkung von π
auf die Mengen f −1 (m) diese Mengen (bijektiv) in sich abbildet. Wegen der obigen
.
S
Charakterisierung von S(n) ∗ f und wegen n = m∈M f −1 (m) ist Λ wohldefiniert und
injektiv. Die Surjektivität ist ebenfalls leicht zu
P sehen. (Wenn z.B. M = m mit m ∈ N
und wenn für h(j) =: kj ∈ N0 die Gleichung j kj = n gilt, definiert man f : n → m
durch f (i) := j für k1 + . . . + kj−1 + 1 ≤ i ≤ k1 + . . . + kj−1 + kj ,wenn kj > 0, wobei
k0 := 0. Für dieses f ist dann Λ(S(n) ∗ f ) = h.)
2
13
Nun fragen wir nach den Mächtigkeit von Abb(n, M )/ S(n) und von Inj(n, M )/ S(n), also
nach früheren Darlegungen, nach der Anzahl der Auswahlen vom Umfang n aus einer
m-Menge M ohne Berücksichtigung der Anordnung und mit bzw. ohne Wiederholung.
Dabei können wir o.B.d.A. annehmen, daß M = m für ein m ∈ N.
Satz 1.8. Es seien n, m ∈ N. Dann existiert in jeder Bahn S(n)∗f von Abb(n, m)/ S(n)
genau eine monoton steigende und eine monoton fallend Funktion. Diese sind genau dan
streng monoton, wenn f injektiv ist.
Beweis: Für 1 ≤ j ≤ m sei (wie oben) kj := |f −1 (j)|. Die ebenfalls oben definierte
Funktion g mit g|hk1 +...+kj−1 +1,k1 +...+kj−1 +kj i := j, wenn hk1 + . . . + kj−1 + 1, k1 + . . . +
kj−1 + kj i 6= ∅, ist dann eine monoton steigende Funktion in der Bahn von f . Mit
inv(i) := n + 1 − i (inv ∈ S(n)) ist dann h := g ◦ inv monoton fallend und ebenfalls
eine Funktion in der Bahn von f . Da die injektiven monotonen Funktionen genau die
streng monotonen sind, ist die letzte Behauptung richtig. Wir haben noch zu zeigen, daß
verschiedene monoton steigende Funktionen nicht in derselben Bahn liegen können. (Für
monoton fallende Funktionen folgt dasselbe Resultat durch Anwendung von inv.) Sind
f und g zwei monoton steigende Funktionen in Abb(n, m) und ist f 6= g, so existiert
ein Wert i0 mit f (i0 ) 6= g(i0 ). Wir wählen i0 kleinstmöglich. Dann ist f (i) = g(i) für
i = 1, 2, . . . , i0 −1. Wir können o.B.d.A. auch annehmen, daß f (i0 ) < g(i0 ). Sei j := f (i0 ),
Aj := f −1 (j), Bj := g −1 (j). Dann ist Bj ⊆ {1, 2, . . . , i0 − 1}, da aus i ≥ i0 folgt, daß
g(i) ≥ g(i0 ) > f (i0 ) = j und daher g(i) 6= j. Ferner ist Aj ∩ {1, 2, . . . , i0 − 1} = Bj , da
f (i) = g(i) für i < i0 . Außerdem ist aber i0 ∈ Aj . Daher ist |Aj | > |Bj |. Somit liegen f
und g in verschiedenen Bahnen.
2
Definition 1.6. Für n, m ∈ N sei Mon< (n, m) bzw. Mon≤ (n, m) die Menge derjenigen
f ∈ Abb(n, m), die streng monoton steigen bzw. (schwach) monoton steigen. Ferner sei
für eine beliebige m-Menge M die Menge gPart(n, M ) die Menge aller geordneten
PartiP
tionen von n mit Teilen aus M , also gPart(n, M ) := {h ∈ Abb(M, N0 ) | x∈M h(x) = n}.
Mit Hilfe der schon gewonnenen Resultate erhalten wir dann folgende Ergebnisse.
Satz 1.9. Es seien n, m ∈ N und es sei M eine m-Menge. Dann:
1. Abb(n, M )/ S(n) ist zu gPart(n, M ) gleichmächtig; die Abbildung
¯
¯
Λ : Abb(n, M )/ S(n) → gPart(n, M ), Λ(S(n) ∗ f )(x) := ¯f −1 (x)¯ für alle x ∈ M,
ist wohldefiniert und eine Bijektion zwischen den beiden Mengen.
2. Die Einschränkung von Λ auf Inj(n, M )/ S(n) bildet diese Menge bijektiv auf
gPart∗ (n, M ) := {h ∈ gPart(n, M ) | h(x) ∈ {0, 1} für alle x ∈ M } ab.
3. Mon≤ (n, m) ist zu Abb(n, m)/ S(n), also auch zu Abb(n, M )/ S(n) gleichmächtig,
wenn |M | = m. Eine Bijektion ist gegeben durch Mon≤ (n, m) 3 f 7→ S(n) ∗ f .
4. Die Einschränkung dieser Abbildung auf Mon< (n, m) liefert eine Bijektion zwischen
dieser Menge und Inj(n, m)/ S(n). Also sind Inj(n, m)/ S(n) und Inj(n, M )/ S(n)
für jede m-Menge M zu Mon< (n, m) gleichmächtig.
14
Beweis: Da g genau dann in S(n) ∗ f liegt, wenn |g −1 (x)| = |f −1 (x)| für alle x in M , ist
.
S
Λ(S(n)∗f ) als Abbildung von M nach N0 wohldefiniert. Da ferner n = x∈M f −1 (x), liegt
diese Abbildung auch in gPart(n, M ). Die Bijektivität von Λ zu beweisen, ist dann sehr
einfach. Da f genau dann injektiv ist, wenn alle Urbilder f −1 (x) höchstens einelementig
sind, ist auch der zweite Teil klar. Die restlichen Teile folgen aus dem vorigen Satz und
der Beobachtung, daß eine monotone Funktion genau dann streng monoton ist, wenn sie
injektiv ist.
2
Nun zur ausständigen Bestimmung der Anzahl der Auswahlen ohne Berücksichtigung der
Anordnung.
Satz 1.10. Es seien n, m ∈ N, es sei M eine m-Menge. Dann gilt:
¢
¡
¡ ¢
.
und |Mon≤ (n, m)| = m+n−1
1. |Mon< (n, m)| = m
n
n
¡m¢
2. Es gibt genau n Auswahlen vom Umfang n aus der m-Menge M ohne Berücksicht¡ ¢
igung der Anordnung und ohne Wiederholung; also |Inj(n, M )/ S(n)| = m
.
n
¡m+n−1¢
3. Es gibt genau
Auswahlen vom Umfang n aus der m-Menge M ohne
n
Berücksichtigung
der
Anordnung
und mit Wiederholung; also |Abb(n, M )/ S(n)| =
¡m+n−1¢
.
n
Beweis: Die Menge Mon< (n, m) ist gleichmächtig zur Menge gPart∗ (n, m) := {h ∈
gPart(n, m) | h(m) ⊆ {0, 1}}, welche selbst wiederum gleichmächtig zur Menge Pn (m)
ist. (Dabei beachte man den Zusammenhang zwischen Teilmengen einer Menge und deren
charakteristischen Funktionen.) Damit ist der erste Teil gezeigt. Nun betrachten wir für
f ∈ Mon≤ (n, m) die Abbildung Γ(f ) := f ∗ : n → Z, definiert durch f ∗ (i) := f (i) + i − 1.
Man rechnet leicht nach, daß f ∗ streng monoton steigt und daß 1 ≤ f ∗ (1) und f ∗ (n) ≤
m + n − 1. Also ist Γ eine Abbildung von Mon≤ (n, m) nach Mon< (n, m + n − 1). Durch
Induktion über j erkennt man schnell, daß für jede streng monoton steigende Funktion
g : n → N und alle 1 ≤ j ≤ n der Wert g(j) ≥ j sein muß. Daraus folgt, daß für
g ∈ Mon< (n, m + n − 1) die Funktion g # mit g # (j) := g(j) − j + 1 in Mon≤ (n, m) liegt
und daß die Zuordnung g 7→ g # zu Γ invers ist.¡ Folglich
¢ ist Γ bijektiv und |Mon≤ (n, m)| =
m+n−1
|Γ(Mon≤ (n, m))| = |Mon< (n, m + n − 1)| =
. Die restlichen Aussagen ergeben
n
sich daraus.
2
2
Konstruktive Aspekte der Kombinatorik
In diesem Kapitel soll exemplarisch gezeigt werden, daß kombinatorische Objekte nicht
nur abgezählt werden können, sondern daß man sie explizit bestimmen kann. Die Verwobenheit beider Gesichtspunkte soll ebenfalls aufgezeigt werden.
2.1
Die lexikographische und andere Ordnungen
Wir werden bequemerweise Abbildungen f : hn, mi → X als Vektoren deuten: f =
(fn , fn+1 , . . . , fm ), fj = f (j).
Definition 2.1. Für n, m ∈ N0 mit n ≤ m und für f, g ∈ Abb(hn, mi), R) definieren
wir drei Ordnungsbeziehungen. Es sei
15
1. f ≤p g, wenn fj ≤ gj für alle j (partielle Ordnung).
2. f ≤` g, wenn entweder f = g oder wenn (f 6= g und) ein n ≤ j0 ≤ m existiert, so
daß fj0 < gj0 und fj = gj für alle n ≤ j < j0 (lexikographische Ordnung).
3. f ≤c , wenn f ◦ inv ≤` g ◦ inv, wobei inv(j) := m + n − j (kolexikographische
Ordnung).
Wir schreiben f <p g, f >p g usw. für die offensichtlich damit gemeinten Sachverhalte.
Bemerkung 2.1.
Für f 6= g ist es bequem festzusetzen: µ(f, g) := min{n ≤ j ≤
m | fj 6= gj }. Dann ist f <p g gleichbedeutend mit fµ(f,g) < gµ(f,g) . Ferner bedeutet
f ≤c g anschaulich gesprochen, daß (fm , fm−1 , . . . fn ) ≤` (gm , gm−1 , . . . gn ).
Allgemein erfüllt eine Ordnungsrelation (partielle Ordnung) ≤ auf einer nichtleeren
Menge X die Bedingungen: i) x ≤ x für alle x ∈ X (Reflexivität). ii) Für alle x, y ∈ X
folgt aus x ≤ y und y ≤ x, daß x = y (Antisymmetrie). iii) Für alle x, y, z ∈ X folgt aus
x ≤ y und y ≤ z, daß x ≤ z (Transitivität). Die Ordnung heißt vollständig oder total,
wenn je zwei Elemente aus X miteinander vergleichbar sind; wenn also für alle x, y ∈ X
mindestens eine der Beziehungen x ≤ y oder y ≤ x zutrifft.
Bemerkung 2.2.
1. ≤p ist eine partielle Ordnung. Sie ist außer im Fall n = m nicht total.
2. ≤` und ≤c sind totale Ordnungen.
3. Für alle f, g impliziert f ≤p g, daß f ≤` g und f ≤c g.
Beweis: Es ist offensichtlich, daß ≤p eine partielle Ordnung ist. Im Falle n < m
sind außerdem (1, 0, . . . , 0) und (0, 0, . . . , 1) nicht vergleichbar. Die Reflexivität von ≤`
ist ebenfalls klar. Wenn f 6= g und wenn j0 := µ(f, g), so ist entweder fj0 < gj0
oder gj0 < fj0 , dh., es ist f <` g oder g <` f . Damit ist gleichzeitig gezeigt, daß ≤`
antisymmetrisch und total ist. Ist f ≤` g und g ≤` h, so ist sicher f ≤` h, wenn f = g
oder g = h. Anderenfalls sei j0 := µ(f, g), j1 := µ(g, h) und j2 := min{j0 , j1 }. Dann ist
fj = gj = hj für n ≤ j ≤ j2 − 1. Ferner ist fj2 ≤ gj2 ≤ hj2 , wobei zumindest an einer
Stelle sogar < gilt. Also ist fj2 < hj2 und folglich sogar f <` h. (Die Diskussion von ≤c
ist auf obige rückführbar.) Der letzte Teil ist wieder offensichtlich.
2
Bemerkung 2.3. In jeder totalgeordnete Menge (X, ≤) hat jede nicht-leere endliche
Teilmenge A ein (eindeutig bestimmtes) Minimum, das mit min A bezeichnet wird. (a
ist ein Minimum von A, wenn a ∈ A und wenn a ≤ b für alle b ∈ A.)
(Die Eindeutigkeit ist klar. Die Existenz des Minimums für eine einelementige Menge
A ebenfalls. Minima zweielementiger existieren wegen der Vergleichbarkeit von zwei
Elementen. Induktion liefert dann, daß min{min A, a0 } ein Minimum von A ∪ {a0 } ist.)
Entsprechendes gilt für das Maximum, max A, von A.
Bemerkung 2.4. Es sei (M, ≤) eine endliche totalgeordnete Menge, es sei m = |M |,
und es seien x, y ∈ M . Es sei V (x) := {y ∈ M | y < x}, die Menge der Vorgänger von
x. Dann ist x ≤ y genau dann, wenn V (x) ⊆ V (y). Daher ist auch die Rangfunktion
rang := rang≤ : M → [m − 1] = {0, 1, 2, . . . , m − 1}, rang(x) := |V (x)|, wohldefiniert und
16
bijektiv.
Wenn x ∈ M , x 6= max M , so sei x+ := succ(x) := min{y ∈ M | y > x} der Nachfolger
(Successor) von x. Dann ist y = succ(x) genau dann, wenn x < y und wenn für alle
z ∈ M aus x < z folgt, daß y ≤ z.
Beweis: Offensichtlich impliziert x ≤ y, daß V (x) ⊆ V (y). Im Fall x < y ist sogar
V (x) ( V (y), da x ∈ V (y) \ V (x). Daher ist x ≤ y äquivalent mit V (x) ⊆ V (y). Dann
ist die Abbildung rang (wohldefiniert und) streng monoton steigend, also injektiv. Wegen
|M | = m = |[m]| ist sie bijektiv.
2
Bemerkung 2.5. (Algorithmen zur Auflistung und zufälligen Wahl von Elementen aus
endlichen totalgeordneten Mengen) Ist (M, ≤) eine totalgeordnete Menge und |M | = m,
in der man Minimum und Maximum leicht bestimmen kann, und ist ein Algorithmus
bekannt, der für x < max M den Nachfolger succ(x) bestimmt, so kann man alle Elemente
von M (in aufsteigender Reihenfolge) so gewinnen:
x:=min M;
verwende(x);
(* verwende(x) ist eine Unterprozedur, die man auf x anwenden moechte *)
while x<max M do begin
x:=succ(x);
verwende(x)
end
Ist die Funktion rang−1 leicht zu berechnen, so kann man mit folgendem Verfahren
zufällige Elemente aus M bestimmen:
j:=random(m);(* j eine Zufallszahl im Bereich zwischen 0 und m-1 *)
x:=invrang(j) (* invrang die zu rang inverse Funktion *)
2.2
Produkt- und Potenzmengen
Es sei n ∈ N0 , es seien a0 , a1 , . . . , an ∈ N und es sei Aj := [aj ] = {0, 1, . . . , aj − 1} für
0 ≤ j ≤ n. Dann ist A := A0Q× A1 × . .Q
. × An eine Teilmenge von Abb(h0, ni), R), und
zwar eine endliche mit |A| = j |Aj | = j aj .
Wir wollen die Nachfolgerabbildung und die Rangabbildung mitsamt ihrer Umkehrung
in diesem Fall für ≤` im Detail studieren.
Bemerkung 2.6.
1. Es ist min A = (0, 0, . . . , 0) und max A = (a0 − 1, a1 − 1, . . . , an − 1).
2. Es ist f < max A genau dann, wenn ein i existiert mit 0 ≤ i ≤ n und fi < ai − 1.
3. Für f ∈ A, f 6= max A ist der Nachfolger succ(f ) = f + gegeben durch f + =
(f0 , f1 , . . . , fi0 −1 , fi0 + 1, 0, . . . , 0), wobei i0 := max{i | fi < ai − 1}
Beweis: Punkt 1 folgt daraus, daß (0, 0, . . . , 0) ≤p f ≤p (a0 − 1, a1 − 1, . . . , an − 1)
für alle f ∈ A. Punkt 2 ist dann offensichtlich. Um Punkt 3 zu zeigen, setzen wir
f ∗ = (f0 , f1 , . . . , fi0 −1 , fi0 + 1, 0, . . . , 0). Dann ist f ∗ ∈ A. Wir haben f ∗ = f + zu zeigen.
Natürlich ist f <` f ∗ , da fi = fi∗ für i < i0 und fi0 < fi0 + 1 = fi∗0 . Sei g ∈ A und
17
f <` g und sei i1 := µ(f, g). Wir müssen zeigen, daß f ∗ ≤` g. Dazu unterscheiden wir
die Fälle i) i1 < i0 , ii) i1 = i0 und iii) i1 > i0 . Im Fall i) folgt µ(f ∗ , g) = µ(f, g) = i1
und fi∗1 = fi1 < gi1 , also f ∗ <` g. Im Fall ii) ist fi∗ = fi = gi für 0 ≤ i < i0 und
fi∗0 = fi0 + 1 > fi0 , gi0 > fi0 , also fi∗0 ≤ gi0 . Weil fi∗ = 0 ≤ gi , wenn i > i0 , ist f ∗ ≤p g
und daher auch f ∗ ≤` g. Der dritte Fall (i1 > i0 ) schließlich ist unmöglich, denn sonst
wäre fi1 < gi1 ≤ ai1 − 1 = fi1 und folglich fi1 < fi1 .
2
Mit Hilfe dieser Behauptung ist es nun einfach, den im vorigen Abschnitt angegeben
Algorithmus zur Erfassung aller f ∈ A in diesem Fall zu konkretisieren. Man hat nur
anzugeben wie f + = succ(f ) aus f entsteht (f [i] := fi ).
if f<maxA (* maxA:=(a[0]-1,...,a_[n]-1) *) then begin
succf:=f; (* succf der Nachfolger succ(f) von f *)
i:=n;
while succf[i]=a[i]-1 do begin i:=i-1;succf_i:=0 end;
succf[i]:=succf[i]+1
end
Nun zur konkreten Bestimmung von rang und rang−1 .
Bemerkung 2.7. Für f = (f0 , f1 , . . . , fn ) ist rang(f ) =
Pn
j=0
fj
Qn
`=j+1
a` .
.n
S
Beweis: Es ist rang(f ) = |V (f )| und V (f ) = j=0 Vj (f ), wobei Vj (f ) := {g ∈
V (f ) | µ(f, g) = j}. Man sieht sofort, daß
Q Vj (f ) = {f0 } × {f1 } × . . . × {fj−1 } × [fj ] ×
[aj+1 ] × . . . × [an ], weswegen |Vj (f )| = fj n`=j+1 a` .
2
Daraus ergibt sich der folgende Satz über Zahlensysteme.
Q∗
Satz 2.1. Es seien (b0 , b1 , . . .) eine Folge
natürlicher
Zahlen
und
es
sei
B
:=
j∈N0 [bj ]
Q
die Menge aller Folgen (f0 , f1 , . . .) ∈ j∈N0 [bj ], so daß höchstens endlich viele bj 6= 0.
P
Qj−1
Dann ist die Abbildung ϕ : B Q
→ N0 , ϕ(f ) :=
j∈N0 fj
`=0 b` , bijektiv und streng
n
monoton steigend. Ferner ist ϕ( j=0 [bj ] × {0} × {0} × . . .) = [b0 b1 · . . . · bn ] und ϕ(b0 −
P
Q
1, . . . , bn − 1, 0, . . .) = nj=0 (bj − 1) j−1
`=0 b` = b0 b1 · . . . · bn − 1.
(Der Spezialfall b = b0 = b1 = · · · = bn = · · · gleicher bj liefert die üblichen b-adischen
Ziffernsysteme.)
Q
Beweis: QSei n fest und aj := bn−j für 0 ≤ j ≤ n. Für g ∈ nj=0 [aj ] ist dann rang(g) =
P
n
n
`=j+1 aj . Sei f := (gn , gn−1 , . . . , g0 , 0, . . .). Dann ist ϕ(f ) = rang(g), womit die
j=0 gj
wesentlichen Teile erledigt sind. (Man beachte, daß aj+1 aj+2 · . . . · an = b0 b1 · . . . · bn−j−1 .)
2
Die Umkehrfunktion rang−1 der Rangfunktion erhält man auf folgende Weise: Ist ein
m ∈ [a0 a1 · . . . · an − 1] gegeben, so erhält man ein f ∈ A mit rang(f ) = m so:
m[n]:=m;
j:=n;
while j>0 do begin
f[j]:= m[j] mod a[j];
m[j-1]:=m[j] div a[j];
18
j:=j-1;
(* u div v Quotient bei Division von u durch v *)
(* u mod v Rest bei Division von u durch v *)
end;
f[0]:=m[0]
Q
ManQ
erkennt wegen mj = mj−1 aj +fj nämlich mittels Induktion, daß m = mj n`=j+1 a` +
fj+1 n`=j+2 a` + . . . + fn−1 an + fn , wenn j = n, n − 1, . . . , 0. Für j > 0 liegen die fj nach
Konstruktion in [aj ]. f0 = m0 ist ≥ 0. Wäre f0 > a0 − 1, so m ≥ a0 a1 · · · an >
a0 a1 · · · an − 1, ein Widerspruch zu m ≤ a0 a1 · · · an − 1.
Die Potenzmenge P([n]) ist nichts anderes als Abb([n], {0, 1}) = {0, 1}n . Somit sind
die obigen Algorithmen anwendbar. Will man anstelle der charakteristischen Funktionen
cA ∈ Abb([n], {0, 1}) die Mengen A selbst haben, so muß man anstelle der Funktion
cA , also des Vektors (x0 , x1 , . . . , xn−1 ), wobei alle xj ∈ {0, 1}, die Menge {j | 0 ≤ j ≤
n − 1, xj = 1} betrachten.
2.3
Monotone Funktionen und n-elementige Teilmengen
Obwohl die lexikographische Anordnung Listalgorithmen für die Mengen Mon≤ (n, m) und
Mon< (n, m) in einfacher Form liefert, besprechen wir hier die kolexikographische Ordnung, da hier die Rangfunktion und ihre Umkehrung interessante zusätzliche Einsichten
liefert.
Bezüglich der lexikographischen Ordnung ergibt sich min Mon≤ (n, m) = (1, 1, . . . , 1) und
max Mon≤ (n, m) = (m, m, . . . , m). Ein f ∈ Mon≤ (n, m) ist < max Mon≤ (n, m) genau dann,
wenn ein i existiert, so daß fi < m. In diesem Fall sei i0 das Maximum aller i mit fi < m.
Dann hat der Nachfolger f + die Form f + = (f1 , f2 , . . . , fi0 −1 , fi0 + 1, fi0 + 1, . . . , fi0 + 1). Die
Zuordnung Γ : Mon≤ (n, m − n + 1) → Mon< (n, m), Γ(f )(i) := f (i) + i − 1, ist bijektiv und
bezüglich ≤` streng monoton steigend, also insbesondere succ(Γ(f )) = Γ(succ(f )). Somit hat
man auch Mon< (n, m) im Griff.
Wir schicken voraus: Für zwei Funktionen f, g ∈ Abb(hn, mi, R) mit f 6= g sei
ν(f, g) := max{j | n ≤ j ≤ m, fj 6= gj }. Dann ist f <c g genau dann, wenn fν(f,g) <
gν(f,g) .
Bemerkung 2.8.
Es seien n, m ∈ N. Dann gilt bezüglich der kolexikographischen
Ordnung in Mon≤ (n, m):
1. min Mon≤ (n, m) = (1, 1, . . . , 1) und max Mon≤ (n, m) = (m, m, . . . , m).
2. Mit fn+1 := m gilt für f ∈ Mon≤ (n, m), daß f <c max Mon≤ (n, m) genau dann,
wenn ein j mit 1 ≤ j ≤ n existiert, so daß fj < fj+1 .
3. Für f ∈ Mon≤ (n, m) mit f <c max Mon≤ (n, m) sei j0 := min{j | 1 ≤ j ≤ n, fj <
fj+1 }. Dann ist f + = succ(f ) gegeben durch f + = (1, 1, . . . , 1, fj0 +1, fj0 +1 , . . . , fn ).
Beweis: Punkt 1 ist klar, da (1, 1, . . . , 1) ≤p f ≤p (m, m, . . . , m). Punkt 2 ist ebenfalls
einfach. Wegen fn+1 = m ist nämlich fj = fj+1 für alle 1 ≤ j ≤ n genau dann,
wenn f = (m, m, . . . , m). Um Punkt 3 zu beweisen, sei f <c (m, m, . . . , m) und j0 wie
oben. Ferner sei f ∗ := (1, 1, . . . , 1, fj0 + 1, fj0 +1 , . . . , fn ). Dann liegt f ∗ in Mon≤ (n, m).
Da ν(f, f ∗ ) = j0 und fj0 < fj0 + 1 = fj∗0 ist f <c f ∗ . Sei g ∈ Mon≤ (n, m) und
19
f <c g. Dann haben wir f ∗ ≤c g zu zeigen. Dazu sei j1 := ν(f, g). Falls j1 > j0 , ist
f ∗ <c g, da ν(f ∗ , g) = ν(f, g) = j1 und fj∗ = fj für j > j0 . Im Falle j1 < j0 folgt
fj1 = fj1 +1 , fj1 < gj1 und fj1 +1 = gj1 +1 . Aus der Monotonie von f und g ergibt sich dann
fj1 = fj1 +1 = gj1 +1 ≥ gj1 > fj1 , ein Widersprich. Ist schließlich j1 = j0 , so ist g >c f ∗ ,
falls gj0 sogar > fj0 + 1. Wenn gj0 ≤ fj0 + 1, so ist gj0 = fj0 + 1 = fj∗0 und gj = fj = fj∗
für j > j0 . Außerdem ist gj ≥ 1 = fj∗ , wenn j < j0 . Somit ist f ∗ ≤p g und deswegen
auch f ∗ ≤c g.
2
Algorithmisch formuliert ergibt sich:
If f<maxMon (* maxMon=(m,m,...,m) *) then begin
succf:=f;
succf[n+1]:=m;
j:=1;
while succf[j]=succf[j+1] do begin succf[j]:=1;j:=j+1; end;
succf[j]:=succf[j]+1
end
Die Überlegungen für Mon< (n, m) könnte man analog führen. Günstiger aber ist es
wohl, die Bijektion Γ : Mon≤ (n, m − n + 1) → Mon< (n, m) zu verwenden. Sie bildet ein
f ∈ Mon≤ (n, m−n+1) auf Γ(f ) mit Γ(f )(j) := f (j)+j −1 ab. Deswegen ist Γ bezüglich
≤c streng monoton steigend. Folglich ist auch Γ(succ(f )) = succ(Γ(f )). Daraus und aus
der obigen Behauptung ergibt sich die Begründung für die folgende Bemerkung.
Bemerkung 2.9. Es seien n, m ∈ N und n ≤ m. Dann gilt bezüglich der kolexikographischen Ordnung in Mon< :
1. min Mon< (n, m) = (1, 2, . . . , m) und max Mon< (n, m) = (m − n + 1, m − n +
2, . . . , m).
2. Mit fn+1 := m + 1 gilt für f ∈ Mon< (n, m), daß f <c max Mon< (n, m) genau dann,
wenn ein j mit 1 ≤ j ≤ n existiert, so daß fj + 1 < fj+1 .
3. Für f ∈ Mon< (n, m) mit f <c max Mon< (n, m) sei j0 := min{j | 1 ≤ j ≤ n, fj +
1 < fj+1 }. Dann ist f + = succ(f ) gegeben durch f + = (1, 2, . . . , j0 − 1, fj0 +
1, fj0 +1 , . . . , fn ).
Der modifizierte Algorithmus lautet etwa so:
If f<maxsMon (* maxsMon=(m-n+1,m-n+2,...,m) *) then begin
succf:=f;
succf[n+1]:=m+1;
j:=1;
while succf[j]+1=succf[j+1] do begin succf[j]:=j;j:=j+1; end;
succf[j]:=succf[j]+1
end
Jetzt behandeln wir die Rangfunktion in Mon< (n, m). Für f ∈ Mon< (n, m) und
1 ≤ i ≤ n sei Vi (f ) := {g ∈ V (f ) | ν(f, g) = i}. Diese Menge besteht aus allen g ∈
20
Mon< (n, m) mit gi < fi und gj = fj für j > i. Deswegen ist Vi (f ) zu Mon< (i, fi − 1)
gleichmächtig. Daraus ergibt sich
¯ X
¯[
¶
n µ
¯
¯. n
f
−
1
i
rang(f ) = ¯¯
Vi (f )¯¯ =
.
i=1
i
i=1
Damit ist der Hauptteil der folgenden Behauptung gezeigt.
Bemerkung 2.10. Es seien n, m ∈ N und n ≤ m. Dann gilt bezüglich der kolexikographischen Ordnung in Mon< :
¯
¯S
£¡ ¢¤
Pn ¡fi −1¢
¯
¯.n
.
V
(f
)
ist
gegeben
durch
rang(f
)
=
rang : Mon< (n, m) → m
¯ =
¯
i=1
i=1 i
i
n
Weil rang streng monoton steigt und bijektiv ist, ist insbesondere
¶ µ ¶
n µ
X
m−n+i−1
m
rang(m − n + 1, m − n + 2, . . . , m) =
=
− 1.
i
n
i=1
¡p¢
Mit p := m − n − 1 und wegen 0 = 1 kann das auch so formuliert werden:
¶ µ
¶
n µ
X
p+i
p+n+1
=
.
(3)
i
n
i=0
£¡ ¢¤
Bemerkung 2.11. Die Umkehrabbildung rang−1 : m
→ Mon< (n, m) berechnet
n
¡m¢
¡ ¢
man folgendermaßen: Für 0 ≤ k ≤ n − 1 sei fn := min{j | nj > k} und (rekursiv)
¡ ¢
¡
¢
P
fi = min{j | nj > k − n`=i+1 f`j−1 } für i = n − 1, n − 2, . . . , 1.
¡
¢
¡ ¢
¡ ¢
Beweis: O.B.d.A. sei n ≥ 2. Nach Definition ist fnn−1 ≤ k < fnn und wegen k < m
¡ ¢n
auch fn ≤ m. Außerdem ist nach den Rechenregeln für Binomialkoeffizienten fnn =
¡fn −1¢ ¡fn −1¢
¡fn −1¢
¡fn ¢ ¡fn −1¢
¡fn −1¢
+
,
also
0
≤
k
−
<
−
=
. Daher kann man mit
n
n−1¢
n
n
n
n−1
¡
f
−
k 0 = k − nn , n0 = n − 1 und m0 = fn − 1 weitermachen.
2
Die algorithmische Umsetzung bereitet keine Probleme.
Es folgen zwei Anwendungen.
Satz 2.2. Es ist N × N gleichmächtig zu N. Eine konkrete Bijektion ist gegeben durch
(i, j) 7→ i + (i + j − 1)(i + j − 2)/2 + 1.
Analoge Aussagen und konkrete Bijektionen kann man auch für Nk , k > 2, treffen bzw.
angeben.
Beweis: Die Abbildung (i, j) 7→¡ (i,¢i +¡j) bildet
N × N bijektiv auf N := {(i, k) ∈ N ×
¢
k−1
N | i < k} ab. Dann ist (i, k) 7→ i−1
+
+
1
sicher
injektiv und auch surjektiv. Man
1
2
hat nur die Einschränkung dieser Abbildung auf die Mengen Mon< (2, m) zu betrachten,
deren Eigenschaften nach den obigen Überlegungen bekannt sind.
2
Denkt man sich N × N in der üblichen Weise angeschrieben
(1, 1) (1, 2) . . . (1, n) . . .
(2, 1) (2, 2) . . . (2, n) . . .
(3, 1) (3, 2) . . . (3, n) . . . ,
..
..
..
...
...
.
.
.
21
so geschieht die Abzählung längs Diagonalen:
(1, 1); (2, 1), (1, 2); (3, 1), (2, 2), (1, 3); . . . ; (n, 1), (n − 1, 2), . . . , (1, n); . . .
Bemerkung 2.12. Bekanntlich ist die Zuordnung Mon< (n, m) 3 f 7→ f (n) ∈ Pn (m)
eine Bijektion. Deswegen sind obige Algorithmen gleichzeitig welche, die auf Pn (M ) (M
eine m-Menge) anwendbar sind.
Bemerkung 2.13. Die Menge gPart(n, m) =: Part(n, m) ist ebenfalls zu Mon< (n, m)
gleichmächtig. In Vektorschreibweise ist Part(n, m) = {g ∈ Nm
0 | g1 + g2 + . . . + gm = n};
die Bijektion wird geliefert durch f 7→ (|f −1 (1)| , |f −1 (2)| , . . . , |f −1 (m)|). Auch hier ist
es nicht allzu schwer, die Algorithmen zu übertragen.
Für a1 , a2 , . . . , am ∈ N0 sei Part(n; a1 , a2 , . . . , am ) := {g P
∈ Part(n, m) | gi ≥ ai , 1 ≤
i ≤ m}. Dann ist diese Menge gleichmächtig
zu
Part(n
−
i ai , m), also insbesondere
¡m+n−P ai −1¢
¡m+n−P ai −1¢
i
i
P
. Eine Bijektion ist gegeben
|Part(n; a1 , a2 , . . . , am )| =
=
m−1
n− i ai
durch (g1 , g2 , . . . , gm ) 7→ (g1 − a1 , g2 − a2 , . . . , gm − am ).
¯
¯ ¯
¯
¯
¯
Die Zuordnung Mon≤ (n, m) 3 f 7→ Λ(f ) := (¯f −1 (1)¯ , ¯f −1 (2)¯ , . . . , ¯f −1 (m)¯) ∈ Part(n, m)
ist bijektiv. Λ ist sogar streng monoton steigend, wenn Definitions- und Bildbereich mit der
kolexikographischen Ordnung versehen werden. Ist nämlich f <c g und j0 = ν(f, g), also
fj = gj für j > j0 und fj0 < gj0 , so folgt f −1 (k) = g −1 (k), wenn k > gj0 . Außerdem folgt
f −1 (gj0 ) ⊆ hj0 + 1, ni und f −1 (gj0 ) ( g −1 (gj0 ), da fj = gj für j > j0 und da j0 ∈ g −1 (gj0 ). Das
bedeutet, daß Λ(f )k = Λ(g)k , wenn k > gj0 , und Λ(f )gj0 < Λ(g)gj0 , also Λ(f ) <c Λ(g).
Daher wird das Minimum (1, 1, . . . , 1) auf das kolexikographische Minimum (n, 0, . . . , 0) von
Part(n, m) abgebildet, das kolexikographische Maximum (m, m, . . . , m) auf das kolexikographische Maximum (0, 0, . . . , 0, n) ∈ Part(n, m). Außerdem ist dann Λ(succ(f )) = succ(Λ(f )).
Ist Part(n, m) 3 h <c (0, 0, . . . , 0, n) und Λ(f ) = h, so ist f <c (m, m, . . . , m). Wenn
j0 := min{j | fj < fj+1 } (fn+1 := m), so ist bekanntlich f1 = f2 = · · · = fj0 und succ(f ) =
(1, 1, . . . , 1, fj0 +1, fj0 +1 , . . . , fn ). Daraus ergibt sich, daß fj0 gleich ist k0 , dem Minimum aller k,
so daß hk > 0. Also ist succ(h) = Λ(succ(f )) gegeben durch succ(h) = (hk0 − 1, 0, . . . , 0, hk0 +1 +
1, hk0 +2 , . . . , hm ).
if h[m]<n (* h<maxPart(n,m) *) then begin
succh:=h;
l:=1;
while succh[l]=0 do l:=l+1
succh[1]:=succh[l]-1
succh[l+1]:=succh[l+1]+1
for i:=2 to l do succh[i]:=0
end
Wie daraus der Nachfolgeralgorithmus für Part(n; a1 , . . . , am ) herzuleiten ist, dürfte klar sein.
Beispiel.
(Lottozahlen) In Österreich besteht ein Lottotip aus einer Auswahl vom
Umfang 6 ohne Wiederholung und ohne Berücksichtigung der Anordnung aus einer 45elementigen Menge, in der BRD aus einer solchen aus einer 49-elementigen Menge. (6
aus 45 bzw. 6 aus 49 ).
Beobachtet man die Ziehungen in Österreich, so kann man den Eindruck gewinnen,
daß es etwas mehr gezogene Zahlentips gibt, in denen mindestens zwei Zahlen benachbart
22
sind, als solche, in denen je zwei mindesten den Abstand zwei voneinander haben. Diesem
Problem wollen wir nachgehen, und das gleich im allgemeinen Fall n aus m. Ein f ∈
Mon< (n, m) ist ein möglicher Tip im Spiel n aus m. Dieser ist von der zweiten Art, wenn
fj+1 −fj ≥ 2 für alle 1 ≤ j ≤ n−1. Mit g1 := f1 , gj := fj −fj−1 für j = 2, 3, . . . , n und mit
gn+1 := m − fn liefert die Zuordnung Mon< (n, m) 3 f 7→ (g1 , g2 , . . . , gn+1 ) eine Bijektion
zwischen Mon< (n, m) und Part(m; 1, 1, . . . , 1, 0). Das Bild der Menge der Tips zweiter
| {z }
n-mal
¡
¢
¡
¢
= n+m−1
Art ist dabei Part(m; 1, 2, 2, . . . , 2, 0). Also gibt es genau n+1+m−(2n−1)−1
(n+1)−1
n
| {z }
(n−1)-mal
¡
¢ ¡m¢
Tips zweiter Art. Der Anteil an allen möglichen Tips ist dann m−n+1
/
. Für n = 6
n ¡ ¢ n
¡45¢
40
und m
=
45
(
Österreich)
bzw.
m
=
49
(BRD)
ergibt
das
die
Anteile
/
' 47,13%
6
6
¡44¢ ¡49¢
bzw. 6 / 6 ' 50,48%.
In Österreich gibt es also mehr Tips erster Art als zweiter, in Deutschland ist es
umgekehrt.
2.4
Permutationen mit und ohne Wiederholung, surjektive und
injektive Abbildungen
Wir haben schon erkannt, daß
Abb(n, m) =
.
[
f ∈Mon≤ (n,m)
S(n) ∗ f.
Mit h := Λ(f ) = (h1 , h2 , . . . , hm ) ∈ Part(n, m) kann S(n) ∗ f auch in der Form
Abb(n; h) := Abb(n; h1 , h2 , . . . ,¯hm ) :=¯
= {g ∈ Abb(n, m) | ¯g −1 (j)¯ = hj für alle 1 ≤ j ≤ m}
geschrieben werden. Daher ist
Abb(n, m) =
.
[
h∈Part(n,m)
Abb(n; h).
Diese Darstellung ist nicht unbedingt für eine Übersicht über alle Abbildungen einer nMenge in eine m-Menge wichtig. Bedeutsam ist sie, wenn man alle surjektiven oder alle
injektiven Abbildungen behandeln möchte. Es ist ja
.
[
Abb(n; h)
Surj(n, m) =
h∈Part(n;1,1,...,1)
und
Inj(n, m) =
.
[
h∈Part∗ (n,m)
Abb(n; h),
wobei Part∗ (n, m) := {h ∈ Part(n, m) | hj ∈ {0, 1} für alle 1 ≤ j ≤ m}.
Da Part(n; 1, 1, . . . , 1) algorithmisch leicht beherrschbar ist und das (über die Menge
Mon< (n, m)) auch für Part∗ (n, m) richtig ist, benötigen wir nur noch Überlegungen, die
Algorithmen zur Darstellung von Abb(n; h) betreffen. Die Funktionen aus Abb(n; h)
nennt man Permutationen mit Wiederholung (vom Typ h). Für n = m und h =
(1, 1, . . . , 1) handelt es sich natürlich um die Menge aller Permutationen einer n-Menge.
23
Übrigens: Die Menge Abb(n; h) hat Qmn! hj ! Elemente. Das haben wir bei der Berechj=1
nung von |S(n) ∗ f | auf Seite 13 erkannt.
Wir werden nun n und h fixieren und abkürzend A für Abb(n; h) schreiben. Für
f ∈ A und 1 ≤ i ≤ n sei ferner Ai (f ) die Menge aller g ∈ A, so daß gj = fj für 1 ≤ j ≤ i.
Damit kann das folgende Ergebnis einfach formuliert werden.
Bemerkung 2.14. Betrachtet man auf A die lexikographische Ordnung, ist f ∈ A
fest, ist 1 ≤ i < n fest gewählt und ist g ∈ A beliebig, so ist g genau dann das Minimum
(Maximum) von Ai (f ), wenn die Einschränkung von g auf hi+1, ni monoton steigt (fällt).
Beweis: Sei g das Minimum in Ai (f ). Wäre g auf I := hi + 1, ni nicht monoton steigend,
so müßten i + 1 ≤ i1 < i2 ≤ n existieren, so daß gi1 > gi2 . Dann liegt aber auch
g 0 := g ◦ τi1 ,i2 (τi1 ,i2 die Transposition, die i1 und i2 vertauscht) in Ai (f ), und es wäre
g 0 <` g, ein Widerspruch.
Sei nun umgekehrt g ∈ Ai (f ) monoton steigend und g 0 das lexikographische Minimum
von Ai (f ). Dann ist nach der vorigen Überlegung g 0 ebenfalls monoton steigend. Aus
Satz 1.8 (bzw. einer einfachen Modifikation) folgt dann g = g 0 .
Die Überlegungen für Maximum und monoton fallende Funktionen verlaufen analog.
2
Bei gegebenen a1 , a2 , . . . , ak und h1 , h2 , . . . , hk ∈ N0 schreiben wir für den Vektor
(a1 , a1 , . . . , a1 , a2 , a2 , . . . , a2 , . . . , ak , ak , . . . , ak )
|
{z
} |
{z
}
|
{z
}
h1 −mal
h2 −mal
hk −mal
abkürzend ah1 1 ah2 2 . . . ahk k .
Bemerkung 2.15. Es sei h ∈ Part(n, m), es sei A = Abb(n; h). Dann gilt:
1. min≤` A = 1h1 2h2 . . . mhm , max≤` A = mhm (m − 1)hm−1 . . . 1h1 .
2. Ein f ∈ A ist genau dann (lexikographisch) kleiner als max≤` A, wenn f nicht
monoton fällt, wenn also ein i < n existiert, so daß fi < fi+1 .
3. Ist f ∈ A, f <` mhm (m − 1)hm−1 . . . 1h1 und ist i0 := max{i < n | fi < fi+1 },
so ist fi0 < fi0 +1 und fj ≥ fj+1 für alle j > i0 . Insbesondere existiert dann
j0 := max{j > i0 | fj > fi0 }. Dann ist fj0 +1 ≤ fi0 < fj0 und succ(f ) ist gegeben
durch
succ(f ) = (f1 , f2 , . . . , fi0 −1 , fj0 , fn , fn−1 , . . . , fj0 +1 , fi0 , fj0 −1 , . . . , fi0 +1 ).
Beweis: Punkt 1 folgt aus der vorigen Bemerkung. Punkt 2 ebenfalls, da f genau dann
monoton fällt, wenn fi+1 ≤ fi für alle 1 ≤ i < n. Ist f ∈ A, f <` mhm (m − 1)hm−1 . . . 1h1 ,
so folgt aus 2) die Existenz von i0 := max{i < n | fi < fi+1 }. Es folgt ferner, daß
fi0 +1 ≥ fi0 +2 ≥ . . . ≥ fn
und die Existenz von j0 := max{j > i0 | fj > fi0 }. Die Funktion f ∗ ,
f ∗ := (f1 , f2 , . . . , fi0 −1 , fj0 , fn , fn−1 , . . . , fj0 +1 , fi0 , fj0 −1 , . . . , fi0 +1 ),
24
liegt dann in Ai0 −1 (f ) ⊆ A. Es ist f ∗ 6= f und µ(f, f ∗ ) = i0 , sowie fi0 < fj0 = fi∗0 , also
f <` f ∗ .
Wir haben f ∗ = succ(f ) zu zeigen. Sei also g ∈ A, f <` g und i1 := ν(f, g). Im
Falle i1 < i0 gilt wegen fj = fj∗ für 1 ≤ j < i0 , daß i1 = ν(f ∗ , g) und fi∗1 = fi1 < gi1
oder f ∗ <` g. Ist im Falle i1 = i0 der Wert gi1 größer als fj0 = fi∗0 , so ist wieder
f ∗ <` g. Andernfalls ist fi0 < gi0 ≤ fj0 . Außerdem ist gi0 einer der Werte fj , j ≥ i0 .
Nach Definition ist aber fj0 der kleinste dieser Werte, die größer als fi0 sind. Somit ist
gi0 = fj0 = fi∗0 und g ∈ Ai0 (f ∗ ). Nach Konstruktion von f ∗ ist aber die Einschränkung
von f ∗ auf hi0 + 1, ni monoton steigend, weswegen aus der vorigen Bemerkung f ∗ ≤` g
folgt. Wenn schließlich µ(f, g) = i1 > i0 wäre, so läge g in Ai0 (f ). Da die Einschränkung
von f auf hi0 + 1, ni monoton fällt, müßte g ≤` max Ai0 (f ) = f gelten, ein Widerspruch
zu g <` f . Folglich ist dieser Fall unmöglich.
2
Bei gegebenen h1 , h2 , . . . , hm ∈ N0 mit
P
i
hi = n ergibt das folgende Algorithmen.
(* minA *)
z:=0; for j:=0 to m-1 do begin
if h[j+1]>0 then begin
for i:=1 to h[j+1] do begin z:=z+1;minA[z]:=j+1;end;
end;
end
(* succf *)
(* stelle zunaechst fest ob f<maxA *)
(* d.h. bestimme i:=max{j|f[j]<f[j+1]} *)
i:=0;
j:=n-1;
repeat
if f[j]<f[j+1] then begin i:=j;j:=1 end
else j:=j-1;
until j=1;
if i=0 then exit (* in diesem Fall ist f=maxA *)
else begin
(* Bestimme j:=max{t>i| f[t]>f[i]} *)
t:=n
repeat
if f[i]<f[t] then begin j:=t;t:=i+1 end
else t:=t-1;
until t=i+1;
succf:=f;
(* definiere succf[i] richtig *)
succf[i]:=f[j]
(* setze zunaechst succf[j]:=f[i] *)
succf[j]:=f[i]
(* Kehre die Reihenfolge um; g Hilfsvektor *)
for t:=i+1 to n do g[t]:=f[t];
for t:=0 to n-i-1 do succf[i+t+1]:=g[n-t]
25
3
Der Heiratssatz
Wir gehen von folgender Situation aus. Gegeben sind zwei endliche Mengen D und H
(Damen und Herren, sowie eine Abbildung F : D → P(H) (Freundschaftssystem). Dann
besteht die Aufgabe darin, festzustellen, ob eine injektive Abbildung h : D → H existiert,
sodaß h(d) ∈ F (d) für alle d ∈ D (Heirat).
Wenn eine derartige Heirat
S h existiert, ist für jede Teilmenge D0 von D die Menge
h(D0 ) eine Teilmenge von d∈D0 F (d) mit |D0 | Elementen. Folglich gilt die sogenannte
Partybedingung“
¯
¯
”
¯[
¯
¯
¯
(P )
F (d)¯ ≥ |D0 | für alle D0 ⊆ D.
¯
¯
¯
d∈D0
3.1
Das Resultat
Überraschenderweise ist diese offensichtlich notwendige Bedingung auch hinreichend. Das
ist der Inhalt des folgenden Satzes von Philip Hall aus dem Jahr 1935.
Satz 3.1. (Heiratssatz) Es seien D, H endliche Mengen und es sei F : D → P(H) ein
Freundschaftssystem. Dann existiert genau dann ein System verschiedener (distinkter)
Repräsentanten (SDR) für F , also eine injektive Funktion h : D → H, so daß h(d) ∈ F (d)
für alle d ∈ D, wenn die Partybedingung (P ) erfüllt ist.
Beweis: Die Notwendigkeit von (P ) haben wir schon eingesehen. Es sei nun (P ) gültig.
Wir müssen die Existenz eines SDR h für F nachweisen. Dies geschieht durch Induktion
über n = |D|. Im Falle n = 1 liefert (P ) für D0 = D = {d}, daß F (d) 6= ∅, alo existiert
eine (injektive) Funktion h : {d} → F (d) ⊆ H. Im Fall n ≥ 2 unterscheiden wir zwei
Fälle.
¯
¯S
Fall 1 : Für alle nichtleeren echten Teilmengen D0 von D sei ¯ d∈D0 F (d)¯ ≥ |D0 | + 1.
Dann wählen wir ein d0 ∈ D und dazu ein beliebiges h0 aus der (sicher nichtleeren)
Menge F (d0 ). Die Menge D0 := D \ {d0 } ist eine nichtleere echte Teilmenge von D. Für
d ∈ D0 sei F 0 (d) := F (d) \ {h0 } ⊆ H. Dann gilt für D0 , H und F 0 die Bedingung (P ).
Ist nämlich D0 ⊆ D0 , so ist
Ã
!
[
[
F 0 (d) =
F (d) \ {h0 }
d∈D0
d∈D0
und folglich
¯ ¯Ã
¯ ¯Ã
¯
!¯
!
¯
¯ ¯ [
¯ ¯ [
¯[
¯
¯
¯
¯
¯
¯
F (d) ¯ − 1 ≥ |D0 | + 1 − 1 = |D0 | .
F (d) \ {h0 }¯ ≥ ¯
F 0 (d)¯ = ¯
¯
¯
¯ ¯
¯ ¯
¯
d∈D0
d∈D0
d∈D0
Nach Induktionsvoraussetzung existiert dann eine injektive Abbildung h0 : D0 → H, so
daß immer h0 (d) ∈ F 0 (d). Daher ist h0 (d) 6= h0 für alle d 6= d0 . Wir definieren h : D → H
durch h(d0 ) := h0 und h|D0 := h0 . Dann ist h ein SDR für F .
¯S
¯
Fall 2 : Es existiert eine nichtleere echte Teilmenge D0 von D, so daß ¯ d∈D0 F (d)¯ =
|D0 |.
26
0
0
Nach Induktionsvoraussetzung existiert
S dann ein SDR h : D → H für F |D0 . Es sei D0 :=
0
0
0
D \ D , H0 := H \ H , wobei H := d∈D0 F (d). Dann ist nach unserer Voraussetzung
H 0 = h0 (D0 ) (und ∅ ( H0 ( D). Wir setzen außerdem F0 (d) := F (d) \ H 0 für alle d ∈ D0 .
Dann erfüllen D0 , H0 und F0 die Bedingung (P ).
.
Für D1 ⊆ D0 sei nämlich D10 := D1 ∪D0 . Dann folgt
[
[
F (d) =
d∈D10
F (d) ∪
=
[
F (d) =
d∈D0
d∈D1
Ã
[
!
[
F (d) ∪ H 0 =
d∈D1
.
(F (d) \ H 0 ) ∪H 0 =
Ã
d∈D1
[
!
.
F0 (d) ∪H 0 .
d∈D1
¯
¯S
¯
¯
Voraussetzungsgemäß ist |D10 | ≤ ¯ d∈D0 F (d)¯. Aus der obigen Gleichung folgt aber
1
¯
¯ ¯
¯
¯ ¯[
¯[
¯
¯
¯
¯
¯
F0 (d)¯ + |H 0 | .
F (d)¯¯ = ¯
|D10 | ≤ ¯¯
¯
¯ ¯d∈D1
¯d∈D10
oder, wie verlangt,
¯
¯
¯[
¯
¯
¯
F
(d)
¯
¯ ≥ |D10 | − |H 0 | = |D1 | + |D0 | − |h0 (D0 )| = |D1 | .
0
¯
¯
d∈D1
Somit existiert nach Induktionsvoraussetzung ein SDR h0 für F0 . Dann ist h, definiert
durch h|D0 := h0 und h|D0 := h0 , ein SDR für F , da h0 (D0 ) = H 0 und h0 (D0 ) ⊆ H \ H 0 .
2
Eine Verallgemeinerung ist im folgenden Satz enthalten.
Satz 3.2. (Haremssatz) Es seien D und H endliche Mengen, es sei a = (ad )d∈D ∈ ND
0
und es sei F : D → P(H) gegeben. Dann existiert genau dann eine Abbildung h : D →
P(H) mit den Eigenschaften
i) h(d) ⊆ F (d) für alle d ∈ D, ii) |h(d)| = ad für alle d ∈ D und
iii) h(d) ∩ h(d0 ) = ∅ für alle d, d0 ∈ D mit d 6= d0 ,
wenn die Bedingung
¯
¯
¯ X
¯[
¯
¯
ad für alle D0 ⊆ D
(Pa )
F (d)¯ ≥
¯
¯
¯
d∈D0
d∈D0
erfüllt ist.
.
S
Beweis:
Ist
h
eine
Abbildung
der
obigen
Art,
so
ist
d∈D0 h(d) eine Teilmenge von
S
P
F
(d)
mit
a
Elementen.
Es
gilt
somit
(P
).
Gilt
umgekehrt (Pa ), so setze
a
d∈D0
d∈D0 d
∗
∗
man D := {(d, i) | d ∈ D, 1 ≤ i ≤ ad } und F ((d, i)) := F (d). Dann ist leicht zu sehen,
daß (P ) für F ∗ und D∗ erfüllt ist. Ist dann h∗ : D∗ → H ein SDR für F ∗ , so hat die
Funktion h mit h(d) := {h∗ ((d, i)) | 1 ≤ i ≤ ad } die geforderten Eigenschaften.
2
27
Die nächste Verallgemeinerung betrifft allgemeine (also auch unendliche) Mengen D. Wir
benötigen dazu aber einige Begriffe und Resultate aus der Topologie. Für eine Menge X
und eine Teilmenge O von P(X) heißt das Paar (X, O) ein topologischer Raum, O eine Topologie
auf X und die Mengen in O offen , wenn gilt:
1. ∅, X ∈ O.
2. Für jede beliebige Familie (Oi )i∈I offener Mengen Oi ist auch
S
Oi offen.
T
3. Für je endlich viele offene Mengen O1 , O2 , . . . , On ist auch der Durchschnitt ni=1 Oi offen.
i∈I
Ein typisches Beispiel erhält man mit Hilfe einer Metrik δ auf der Menge X. Die zugeordnete
Topologie Oδ ist die Menge derjenigen Teilmengen O von X, die die Eigenschaft haben, daß
zu jedem x ∈ O ein r > 0 existiert, so daß die offene Kugel mit Mittelpunkt x und Radius r,
nämlich K(x, r) := {y ∈ X | δ(y, x) < r}, ganz in O enthalten ist. Ein weiteres Beispiel (ein
Spezialfall des eben genannten) ist die diskrete Topologie P(X). Man erhält sie, wenn man auf
X die triviale Metrik δ0 betrachtet (δ0 (x, x) = 0, δ0 (x, y) = 1, wenn x 6= y).
Q Ist eine Familie ((Xi , Oi ))i∈I topologischer Räume gegeben, so wird das Produkt X :=
i∈I Xi mit Hilfe der Produkttopologie ebenfalls zu einem topologischen Raum. Eine Teilmenge
O ⊆ X wird dabei offen (bezüglich der Produkttopologie)
genannt, wenn es zu jedem x =
Q
(xi )i∈I ∈ X eine Menge Ux der Form Ux = i∈I Oi gibt, sodaß für alle i ∈ I die Mengen Oi in
Oi liegen, sodaß aber die Menge derjenigen i, für die Oi 6= Xi , endlich ist, und sodaß schließlich
x ∈ Ux und
S Ux ⊆ O. (Die Elemente x = (xi )i∈I ∈ X sind dabei nichts anderes als Abbildungen
x : I → i∈I Xi , x(i) =: xi , sodaß xi ∈ Xi für alle i ∈ I.)
Für eine Teilmenge K eines topologischen Raumes X (mit Topologie O) heißt eine Familie
(Oi )i∈I
S von Teilmengen von X eine offene Überdeckung von K, wenn alle Oi offen sind und wenn
K ⊆ i∈I Oi . Eine Familie (Uj )j∈J heißt endliche Teilüberdeckung der ÜberdeckungS(Oi )i∈I ,
wenn J eine endliche Teilmenge von I ist, wenn Aj = Oj für alle j ∈ J und wenn K ⊆ j∈J Oj .
Eine Teilmenge K des topologischen Raumes X (z.B. X selbst) heißt kompakt, wenn jede
offene Überdeckung von K eine endliche offene Teilüberdeckung enthält.
Es gilt dann der berühmte Satz von Tychonoff:
Jedes Produkt kompakter topologischer Räume ist wieder kompakt.
Satz 3.3. Es seien D und H beliebige (nichtleere) Mengen, es sei Pfin (H) die Menge aller
endlichen (“finite”) Teilmengen von H und F : D → Pfin
Q(H) eine beliebige Abbildung.
Dann existiert genau dann eine injektive Funktion h ∈ d∈D F (d), wenn für alle D0 ∈
Pfin (D) gilt:
¯
¯
¯[
¯
¯
¯
(Pfin )
F (d)¯ ≥ |D0 | .
¯
¯
¯
d∈D0
Beweis: Die Notwendigkeit von (Pfin ) folgt
Q sofort aus der Beobachtung, daß die Einschränkung einer injektiven Funktion h ∈ d∈D F (d) =: F auf eine endliche Teilmenge
D0 von D ein SDR für D0 und F |D0 darstellt. Nun sei umgekehrt (Pfin ) erfüllt. Wir
versehen alle F (d) mit der diskreten Topologie und F mit der dazugehörigen Produkttopologie. Dann sind alle F (d) wegen der Endlichkeit dieser Mengen kompakt und F
aufgrund des Satzes von Tychonoff. Es sei ferner D o.B.d.A. unendlich. Dann ist (P )
für jede endliche Teilmenge D0 von D erfüllt. Somit ist für alle D0 ∈ Pfin (D) die Menge
UD0 := {h ∈ F | h|D0 injektiv}
nicht leer. (Dabei ist noch das Auswahlaxiom zu verwenQ
den, das hier besagt, daß d∈D\D0 F (d) 6= ∅, da D\D0 nicht leer ist und ebenso alle F (d).)
28
Nun zeigen wir, daß F \ UD0 (bezüglich der Produkttopologie) offen ist. Ist h ∈ F \ UD0 ,
0
so ist die Einschränkung von h auf D0 nicht injektiv.
Q Somit existieren d1 , d2 ∈ D mit
d1 6= d2 und h(d1 ) = h(d2 ) =: x. Dann sei O := d∈D Od , wobei Od := F (d), wenn
d 6= d1 , d2 , und Od1 = Od2 := {x}. Dann ist O offen, h ∈ O und O ⊆ F \ UD0 . Folglich
ist F \ UD0 offen. Wäre nun (F \ UD0 )D0 ∈P eine offene Überdeckung von F, so hätte der
fin
Satz von Tychonoff zur Folge, daß diese Überdeckung eine endliche Teilüberdeckung enthielte. Dann müßten also³endliche Teilmengen
D1 , D2 , . . . , Dn von D existieren, so daß
´
¢
Sn ¡
Tn
Tn
S
F = j=1 F \ UDj = F \
U
.
Nun
ist
aber
D
j
j=1
j=1 UDj ⊇ U 1≤j≤n Dj , wie leicht zu
S
sehen ist. D0 := 1≤j≤n Dj ist eine endliche Teilmenge von D, folglich ist UD0 6= ∅ bzw.
³T
´
S
n
F\
U
⊆ F \ UD0 ( F, ein Widerspruch. Deswegen ist D0 ∈P (D) (F \ UD0 ) ( F.
D
j
j=1
fin
´ T
³S
Also existiert ein h ∈ F \
D0 ∈Pfin (D) UD0 . Dieses h hat dann die
D0 ∈Pfin (D) (F \ UD0 ) =
geforderten Eigenschaften.
2
3.2
Anwendungen
Satz 3.4. Es sei V ein Vektorraum über dem Körper K und es seien A und B zwei
Basen von V . Dann sind A und B gleichmächtig, d.h., es existiert eine Bijektion ϕ
zwischen A und B.
Beweis: Der Fall, daß A oder B endlich ist, wird mit Standardargumenten aus der
Linearen Algebra erledigt. (Ist A eine Basis von V mit n Elementen, so sind je n + 1
Vektoren aus V linear abhängig.) Wir können also voraussetzen, daß die beiden Mengen
A und B unendlich sind.
Für a ∈ A existiert eine Familie (λa,b )b∈B von Elementen
P
aus K, so daß a =
b∈B λa,b b und so daß die Menge Ba aller b ∈ B mit λa,b 6= 0
endlich (und nichtleer) ist. Es sei F : A → Pfin definiert durch F (a) := Ba . Wir wollen
nachweisen, daß F die Bedingung (Pfin ) erfüllt. Sei A0 eine beliebige endliche Teilmenge
von A. Dann ist hA0 i, der von A0 erzeugte Unterraum
von V , |A0 |-dimensional. Er ist im
S
endlich-dimensionalen Unterraum,
der
von
F
(a)
erzeugt wird, enthalten. Folglich
¯S
¯ a∈A0
S
¯
¯
ist |A0 | ≤ dimh a∈A0 F (a)i ≤ a∈A0 F (a) . Also ist (Pfin ) erfüllt. Deshalb existiert eine
injektive Abbildung α : A → B (mit α(a) ∈ F (a) für alle a ∈ A). Genau so erschließt
man die Existenz einer injektiven Funktion β : B → A. Der Satz von Bernstein besagt,
daß aus der Existenz von injektiven Abbildungen f : X → Y und g : Y → X die Existenz
einer bijektiven Abbildung h : X → Y folgt. Somit existiert eine bijektive Abbildung
ϕ : A → B. A und B sind folglich gleichmächtig.
2
Eine reelle quadratische (n, n)-Matrix A = (aij ) 1≤i≤n heißt doppelt-stochastisch, wenn alle
1≤j≤n
Zeile und alle Spalten Wahrscheinlichkeitsverteilungen
sind, wenn also alle aij ≥ 0 und
Pn
Pn
wenn für alle i0 , j0 gilt:
i=1 aij0 = 1. Für eine Permutation π ∈ Sn sei die
j=1 ai0 j =
reelle quadratische Matrix Pπ = (πij ) 1≤i≤n definiert durch pij := δπ(i)j . Dann ist Pπ eine
1≤j≤n
(ganz besondere) doppelt-stochastische Matrix. In jeder Zeile und in jeder Spalte von
Pπ kommt genau ein Eintrag mit dem Wert 1 vor; alle anderen Einträge sind 0. Solche
Matrizen nennt man Permutationsmatrizen.
Wir wollen mit Hilfe des Heiratssatzes das (überraschende) Resultat beweisen, daß
jede doppelt-stochastische Matrix eine Konvexkombination von Permutationsmatrizen ist.
29
Hilfssatz. Zu jeder doppelt-stochastischen (n, n)-Matrix A existiert eine Permutation
π ∈ Sn , so daß aiπ(i) > 0 für alle 1 ≤ i ≤ n.
Beweis: Es
P sei H := D := n. Für i ∈ D sei F (i) := {j ∈ H | aij > 0}. (Daraus ergibt
sich, daß j∈F (i) aij = 1.) Dann ist die Bedingung (P ) erfüllt. Ist nämlich D0 ⊆ D, so
folgt


X
X X
X
X

|D0 | =
1=
aij ≤
aij  =
i∈D0
=
i∈D0 j∈F (i)
Ã
X
S
j∈ k∈D F (k)
0
X
!
aij
i∈D0
i∈D0
≤
S
j∈ k∈D F (k)
0
X
S
j∈ k∈D F ()
¯
¯
¯[
¯
¯
¯
1=¯
F (k)¯ .
¯
¯
0
k∈D0
Nach dem Heiratssatz existiert dann eine injektive Abbildung π : D → H mit π(i) ∈ F (i)
für alle i. Da D und H gleich(mächtig) sind, ist π sogar eine Bijektion. Außerdem
bedeutet π(i) ∈ F (i) gerade, daß aiπ(i) > 0.
2
Satz 3.5.
(G. Birkhoff, 1946.) Jede doppelt-stochastische Matrix ist eine Konvexkombination von Permutationsmatrizen. D.h., zu jeder doppelt-stochastischen
(n, n)P
Matrix A existiert eine natürliche Zahl t und existieren λ1 , λ2 , . . . , λt ≥ 0 mit ti=1 λi = 1,
sowie Permutationen π1 , π2 , . . . , πt ∈ Sn , so daß
A=
t
X
λi Pπi .
i=1
Beweis: Wir führen einen Induktionsbeweis nach k = k(A) := |{(i, j) | aij > 0}|. Nach
dem oben formulierten Hilfssatz ist k(A) ≥ n. Im Falle k(A) = n (Induktionsanfang)
sei π ∈ Sn so gewählt, daß aiπ(i) > 0 für alle i. (Das ist wegen des Hilfssatzes möglich.)
Dann ist aber schon A = Pπ (und die Behauptung richtig). Es ist ja aiπ(i) > 0 und wegen
k(A) = n auch aij = 0, wenn j 6= π(i). Deswegen ist aiπ(i) = 1. Wenn k(A) > n, sei
π eine Permutation mit den im Hilfssatz geforderten Eigenschaften und i0 so gewählt,
daß ai0 π(i0 ) = κ := min{a
½ iπ(i) | 1 ≤ i ≤ n}. Es sei B = (bij ) := A − κPπ . Das heißt, daß
aij
falls j 6= π(i)
. Deswegen sind alle bij ≥ 0; außerdem
bij = aij − κδπ(i)j =
aiπ(i) − κ falls j = π(i)
bleibt bij gleich 0, wenn aij schon 0 ist. Zusätzlich ist bi0 π(i0 ) = 0. Nun betrachten wir
die Zeilen- und Spaltensummen von B.
n
X
bij =
j=1
n
X
i=1
bij =
X
aij + aiπ(i) − κ = 1 − κ
j6=π(i)
n
X
n
X
i=1
i=1
(aij − κδπ(i)j ) =
aij − κ = 1 − κ
Im Falle κ = 1 ist B = 0 und daher A = Pπ . Anderenfalls ist B 0 = (1/(1 − κ))B doppeltstochastisch und k(B 0 ) < k(A). Folglich existieren nach Induktionsvoraussetzung t0 ,
P0
P0
λ01 , λ02 , . . . , λ0t0 , π10 , π20 , . . . , πt00 , sodaß B 0 = ti=1 λ0i Pπi0 , bzw. B = ti=1 (1 − κ)λ0i Pπi0 oder
P
A = B + κPπ = ti=1 λi Pπi , wobei t := t0 + 1, λ1 := κ, π1 := π und λi := (1 − κ)λ0i−1 ,
0
für 2 ≤ i ≤ t.
2
πi := πi−1
30
Satz 3.6. (van der Waerden, 1927) Es sei M eine Menge mit nm Elementen, und
es seien D, H m-elementige Teilmengen von Pn (M ), sodaß
M=
.
[
D∈
D
.
[
D=
H∈
H
H.
Dann existiert eine Bijektion π : D → H, so daß D ∩ π(D) 6= ∅ für alle D ∈ D.
(Faßt man H und K als Äquivalenzrelationen auf M auf, so kann man das Ergebnis
auch so formulieren: Haben zwei Äquivalenzrelationen auf einer endlichen Menge M
gleichmächtige Äquivalenzklassen, so existiert eine Teilmenge von M , die gleichzeitig ein
Repräsentantensystem für beide Äquivalenzrelationen ist.)
Beweis: Für D ∈ D sei F (D) := {H ∈ H | D ∩ H 6= ∅}. Wir
weisen ¯die Bedingung
¯S
S
¯
¯.
(P ) nach. Sei D0 ⊂ D und sei H0 := D∈D0 F (D). Dann ist ¯ D∈D0 D¯ = n |D0 | und
¯S
¯
S
S
¯.
¯
H
¯ H∈H0 ¯ = n |H0 |. Außerdem ist D∈D0 D ⊆ H∈H0 H. Ist nämlich x ∈ D ∈ D0 , so
S
existiert ein H ∈ H mit x ∈ H. Folglich ist H ∈ F (D) und somit x ∈ D∈D0 F (D).
Daraus ergibt sich
¯[
¯ ¯[
¯
¯.
¯ ¯.
¯
n |D0 | = ¯¯
D¯¯ ≤ ¯¯
H ¯¯ = n |H0 |
D0
H0
D∈
d.h.,
H∈
¯
¯
¯[
¯
¯
¯
|D0 | ≤ |H0 | = ¯
F (D)¯ .
¯
¯
D∈
D0
Daher impliziert der Heiratssatz die Existenz einer injektiven Abbildung π : D → H, so
daßT π(H) ∈ F (H) für alle H. π ist sogar bijektiv, und π(H) ∈ F (H) bedeutet, daß
H π(H) 6= ∅.
2
Folgerung 3.1. (Miller, 1910) Es sei G eine endliche Gruppe und H eine Untergruppe. Dann existieren Elemente x1 , x2 , . . . , xm in G, so daß
G=
. m
[
i=1
xi H =
. m
[
i=1
Hxi .
Beweis: Es sei n die Ordnung von H und nm die Ordnung von G. Auf G sind zwei
Äquivalenzrelationen definiert durch g ∼` h, wenn g −1 h ∈ H, und g ∼r h, wenn gh−1 ∈
H. Die Äquivalenzklassen sind dann gerade die Links- bzw. Rechtsnebenklassen von H
in G. Diese haben alle die (gleiche) Mächtigkeit n. Der Satz garantiert dann die Existenz
einer Bijektion π zwischen der Menge {u1 H, u2 H, . . . , um H} der Linksnebenklassen und
der Menge {Hv1 , Hv2 , . . . , Hvm } der Rechtsnebenklassen, so daß ui H ∩ π(ui H) 6= ∅.
Abschließend wählt man xi ∈ ui H ∩ π(ui H). (Es ist π(ui H) = Hvj für ein geeignetes j.)
2
3.3
Ein algorithmischer Beweis
In diesem Abschnitt soll für den Heiratssatz eine in [BP] dargelegte konstruktive Beweismethode dargestellt werden. Dabei können wir uns darauf konzentrieren, die Hinlänglichkeit der Bedingung (P ) nachzuweisen.
31
Gegeben seien n endliche Mengen A1 , A2 , . . . , An und eine injektive Funktion
h : {1, 2, . . . , n − 1} →
n−1
[
Ai
mit h(i) ∈ Ai , 1 ≤ i ≤ n − 1.
i=1
Wir werden den folgenden Satz beweisen.
Satz 3.7. Gilt unter obigen Voraussetzungen für alle Teilmengen J ⊆ {1, 2, . . . , n − 1}
¯
¯
¯
¯[
¯
¯
¯ Aj ∪ An ¯ ≥ |J| + 1,
¯
¯
j∈J
S
so existiert eine injektive Funktion h∗ : {1, 2, . . . , n} → ni=1 Ai mit h∗ (i) ∈ Ai für alle
1 ≤ i ≤ n, sodaß außerdem h(i) ∈ h∗ ({1, 2, . . . , n}) für alle 1 ≤ i ≤ n − 1.
Den Beweis kann man den folgenden Überlegungen und Bemerkungen entnehmen.
Fall 1. Wenn An * h({1, 2, . . . , n − 1}), wähle man ein x ∈ An \ h({1, 2, . . . , n − 1}) und
setzte h∗ (n) := x und h∗ |{1,2,...,n−1} := h.
Fall 2. Von nun an sei An ⊆ h({1, 2, . . . , n − 1}) und I := {1, 2, . . . , n − 1}.
Für jede Teilmenge E von h(I) sei ind(E) := h−1 (E) die Menge der Indizes i ∈ I,
so daß h(i) ∈ E. Dann ist h(ind(E)) = E, und aus Sder Injektivität von h folgt, daß
|ind(E)| = |E|. Für beliebige Teilmengen E von A := nj=1 Aj sei
nS
v(E) :=
E
j∈ind(E)
Aj
falls E ⊆ h(I)
sonst.
Behauptung 1. Für alle E ⊆ A ist E ⊆ v(E) ⊆ A und sogar E ( v(E), falls
An ⊆ E ⊆ h(I).
Wenn E * h(I) ist v(E) = E. Im anderen Fall (E ⊆ h(I)) sei x ∈ E beliebig; dann ist
x = h(i) für ein i ∈ ind(E). Folglich ist x = h(i) ∈ Ai und Ai ⊆ v(E) nach Konstruktion
von v(E). Ist An ⊆ ES⊆ h(I), so folgt aus dem eben Gezeigten, daß E ⊆ v(E). Wegen
An ⊆ E ist v(E) = i∈ind(E) Ai ∪ An , woraus mit Hilfe der Voraussetzung folgt, daß
|v(E)| ≥ |ind E| + 1 = |E| + 1. Somit ist v(E) 6= E.
Die Zuordnung E 7→ v(E) ist eine Abbildung der endlichen Menge P(A) in sich.
Deshalb existiert in jeder Folge E ⊆ v(E) ⊆ v(v(E)) ⊆ . . . ⊆ v j (E) ⊆ . . . ein k ≥ 0 mit
v k (E) = v k+1 (E).
Für E0 := An ist E0 ( v(E0 ) =: E1 . Es sei T := min{k ∈ N0 | v k (E0 ) = v k+1 (E0 )}.
Dann ist T ≥ 1 und (mit Ek := v k (E0 ))
E0 ( E1 ( . . . ( ET = ET +1 .
Behauptung 2. Es ist T ≥ 1, ET −1 ⊆ h(I) und ET * h(I), also T das Minimum aller
k ≥ 1 mit v k (E0 ) * h(I).
Daß T ≥ 1 sein muß, haben wir schon gesehen. Wäre ET −1 keine Teilmenge von h(I),
so wäre ET = v(ET −1 ) = ET −1 , ein Widerspruch zur Definition von T .
32
Für 0 ≤ t ≤ T − 1 sei It := ind(Et ). (Da für diese t-Werte Et ⊆ h(I), ist It definiert.)
Dann ist (Injektivität von h)
I0 ( I1 ( . . . ( IT −1 ⊆ I
und
Et+1 = v(Et ) =
[
Ai .
i∈It
Behauptung 3. Für alle 1 ≤ t ≤ T − 1 und für alle x ∈ Et+1 \ Et existiert ein
i ∈ It \ It−1 , so daß x ∈ Ai . Mehr noch: Ist xS∈ Ai für ein i ∈ It , so gilt immer i ∈
/ It−1 .
Aus x ∈ Et+1 \ Et und Et+1 = v(Et ) = i∈It Ai folgt die Existenz eines i ∈ It mit
x ∈ Ai . Wäre i ∈ It−1 , so müßte Ai eine Teilmenge von Et sein, also x in Et liegen, ein
Widerspruch.
Behauptung 4. Ist T = 1, so existiert ein b ∈ E1 \ h(I) und ein i0 ∈ I0 , so daß b ∈ Ai0 .
Ferner ist h(i0 ) ∈ An und h∗ — mit h∗ (n) := h(i0 ), h∗ (i0 ) := b und h∗ (i) := h(i) für alle
anderen i — definiert eine Funktion mit der gewünschten Eigenschaft.
Unter den Voraussetzungen dieser Behauptung exitiert sicher ein b ∈ E1 \ h(I). Also
ist b ∈ Ai0 für ein (geeignetes) i0 ∈ I0 . h(i0 ) liegt in E0 = An ⊂ h(I). Somit ist h(i0 ) 6= b.
Der Rest ist klar.
Von nun an sei T ≥ 2.
Behauptung 5. Es sei T ≥ 2. Dann existiert ein b ∈ ET \ h(I) und eine Folge
(iT −1 , iT −2 , . . . , i1 , i0 ) von Elementen aus I mit den Eigenschaften:
1. b ∈ AT −1 , h(it ) ∈ Ait−1 für 1 ≤ t ≤ T − 1,
2. it ∈ It \ It−1 für 1 ≤ t ≤ T − 1
3. h(i0 ) ∈ E0 = An .
Der Beweis für diese Behauptung verläuft folgendermaßen. Wegen ET * h(I) existiert ein b ∈ ET \ h(I) ⊆ ET \ ET −1 . Folglich gibt es nach Behauptung 3 ein iT −1 ∈
IT −1 \ IT −2 mit b ∈ AIT −1 . Weiter geht es mit Induktion. Wir nehmen an, daß man
(iT −1 , iT −2 , . . . , is+1 ) schon konstruiert hat, so daß die obigen Punkte für i ≥ s + 1 gelten,
wobei s ≥ 1. Dann ist is+1 ∈ Is+1 \ Is und folglich (da h injektiv) h(is+1 ) ∈ h(Is+1 \ Is ) =
h(Is+1 ) \ h(Is ) = Es+1 \ Es . Daher existiert nach Behauptung 3 ein is ∈ Is \ Is−1 mit
his ∈ Ais−1 .
Nun sei (iT −1 , iT −2 , . . . , i1 ) (und b) schon so konstruiert wie gefordert. Dann ist h(i1 ) ∈
h(I1 \ I0 ) = h(I1 ) \ h(I0 ) = E1 \ E0 . Also ist h(i1 ) ∈ E1 = v(E0 ) und es existiert ein
i0 ∈ I0 mit h(i1 ) ∈ Ai0 . Außerdem liegt wegen An = E0 = h(I0 ) das Element h(i0 ) in An .
Behauptung 6. Die Werte i0 , i1 , . . . , iT −1 sind paarweise verschieden und ebenso die
Werte h(i0 ), h(i1 ), . . . , h(iT −1 ), b.
Wäre nämlich i0 = it mit t ≥ 1, so folgte i0 ∈ I0 ∩ (It \ It−1 ) ⊆ I0 ∩ (It \ I0 ) = ∅,
ein Widerspruch. Wäre is = it für 1 ≤ s < t ≤ T − 1, so folgte in analoger Weise der
Widerspruch is ∈ (Is \ Is−1 ) ∩ (It \ It−1 ) ⊆ Is ∩ (It \ Is ) = ∅.
Aus der Injektivität von h ergibt sich dann, daß die Werte h(ij ), 0 ≤ j ≤ T − 1
paarweise verschieden sind. Der Rest ergibt sich aus der Beobachtung, daß b 6∈ h(I) ⊇
{h(i0 ), h(i1 ), . . . , h(iT −1 )}.
Behauptung 7. h∗ , definiert durch
33
1. h∗ (n) := h(i0 ),
2. h∗ (it ) := h(it+1 ) für 0 ≤ t ≤ T − 2,
3. h∗ (iT −1 ) := b und
4. h∗ (i) := h(i) für alle i ∈ I \ {i0 , i1 , . . . , iT −1 },
ist eine injektive Funktion mit Definitionsbereich {1, 2, . . . , n}, so daß h∗ (i) ∈ Ai für alle
1 ≤ i ≤ n.
Das ergibt sich aus den beiden vorigen Behauptungen.
Für den Algorithmus verwenden wir folgende Notationen:
x in A
{}
A<=B
A*B
A+B
A-B
choose(A)
x∈A
∅
A⊆B
A∩B
A∪B
A\B
ein Element aus der
nichtleeren Menge A
(* Input: A[1],A[2],...,A[n-1],A[n]: Mengen
(*
h[1],h[2],...,h[n-1]: Elemente
(* Dabei ist h[i] in A[i] fuer 1<=i<=n-1 und
(* die h[i] sind paarweise verschieden.
(* Output: Entweder "impossible", wenn
(* kein SDR fuer A[1],A[2],...,A[n-1],A[n]
(* existiert, oder ein SDR h’ fuer
(* A[1],A[2],...,A[n-1],A[n], in dem alle
(* gegebenen h[i] vorkommen.
procedure Index(E, var It);
(* Bildet fuer E<=h(I)={h[1],...,h[n-1]} *)
(* die Menge It aller i, s.d. h[i] in E *)
begin
It={};
for i:=1 to n-1 do begin
if (h[i] in E) then It:=It+{h[i]}
end;
end;
procedure v(E, var vE);
(* Bildet fuer E<=h(I)={h[1],...,h[n-1]}, *)
(* wenn E={h[i]| i in It}, die Menge
*)
(* Ev =Vereinigung der A[j] mit j in It
*)
begin
Index(E,It);
Ev:={};
Ithlp:=It;
while not(Ithlp={}) do begin
34
*)
*)
*)
*)
*)
*)
*)
*)
*)
j:=choose(Ithlp);Ev:=Ev+A[j];Ithlp:=Ithlp-{j}
end;
end;
(*************************************************************)
begin
hI:={};
for i:=1 to n-1 do hI:=hI+{h[i]}
(* hI={h[1],...,h[n-1]}
*)
if not((A[n]-hI)={}) then begin
h’[n]:=choose(A[n]-hI);
for i:=1 to n-1 do h’[i]:=h[i];
end
else
begin
(* Es ist A[n]<=hI *)
E[0]:=A[n];
Index(E[0],I[0]);
t:=0;
repeat
v(E[t],E[t+1]);
Index(E[t+1],I[t+1]);
t:=t+1;
until (E[t-1]=E[t]);
If (E[t]<=hI) then h’:="impossible"
else begin
t0:=t-1;
if t0=1 then begin
b:=choose(E[t0]-hI);
Ihlp:=I[0];
repeat
i[0]:=choose(Ihlp);
Ihlp:=Ihlp-{i[0]};
until (b in A[i[0]]);
h’[i[0]]:=b;h’[n]:=h[i[0]];
for i:=1 to n-1 do begin
if not(i=i[0]) then h’[i]:=h[i]
end;
end
else begin
b:=choose(E[t0]-hI);
Ihlp:=I[t0-1];
repeat
i[t0-1]:=choose(Ihlp);
Ihlp:=Ihlp-{i[t0-1]};
until (b in A[i[t0-1]]);
t:=t0-1;
35
repeat
t:=t-1;
Ihlp:=I[t];
repeat
i[t]:=choose(Ihlp);
Ihlp:=Ihlp-{i[t]};
until (h[i[t+1]] in A[[t]]);
until t=0;
for i:=1 to n-1 do h’[i]:=h[i]
h’[n]:=h[i[0]];
for t=0 to t0-2 do h’[i[t]]:=h[i[t+1]];
h’[i[t0-1]]:=b;
end;
end;
Dieses Ergebnisses zeigt, daß man entweder ein SDR für n − 1 Mengen auf eines für
n Mengen erweitern kann, oder daß es für diese n Menge überhaupt kein SDR gibt. Es
dürfte nun klar sein, wie damit (wenn überhaupt möglich) ein SDR für gegebene Mengen
A1 , A2 , . . . , An gewonnen werden kann: Man wendet die obige Prozedur n-mal an; dabei
beginnt man mit n = 0 und A1 (kein h nötig), nimmt als neuen Input A1 , A2 und h1 ,
usw.
Literatur
[BP] Bryant, V. and Perfect, H., Independence Theory in Combinatorics, Chapman and
Hall, London and New York, 1980.
[C]
Comtet, L., Advanced combinatorics. The art of finite and infinite expansions.
Translated from the French by J. W. Nienhuys. Rev. and enlarged ed., D. Reidel
Publishing Company, Dordrecht, Holland - Boston, U.S.A.,1974.
[F]
Flachsmeyer, J., Kombinatorik. Eine Einführung in die mengentheoretische Denkweise, VEB Deutscher Verlag der Wissenschaften, Berlin, 1972.
[J]
Jacobs, K., Einführung in die Kombinatorik. De Gruyter Lehrbuch, Walter de
Gruyter, Berlin – New York, 1983.
[L1] Lüneburg, H., Kombinatorik. Elemente der Mathematik vom höheren Standpunkt
aus. Band VI. Birkhäuser Verlag, Basel und Stuttgart, 1972.
[L2] Lüneburg, H., Tools and fundamental constructions of combinatorial mathematics.
B.I.-Wissenschaftsverlag, Mannheim etc., 1989.
[SW] Stanton, D. and White, D., Constructive combinatorics. Undergraduate Texts in
Mathematics. Springer-Verlag, New York, 1986.
36
Документ
Категория
Без категории
Просмотров
6
Размер файла
375 Кб
Теги
001, pdf, kombinatorik, 3951
1/--страниц
Пожаловаться на содержимое документа