| Auf wieviel Arten lässt sich ein 7×2 Schachbrett mit 2×1-Dominos pflastern? |
|
| Wieviel Wege führen von A nach B, wenn es verboten ist sich nach Süden oder Westen zu bewegen? Zwei Beispielswege sind gezeigt. |
|
| Auf wieviel Arten lassen sich rechteckige Flächen mit diagonal zweigeteilten Kacheln kacheln, wenn Anstoßkanten von Kacheln immer verschieden gefärbt sein sollen? |
|
Eine (endliche) Menge M hat n Elemente, |M| = n, , wenn es eine
bijektive Abbildung
von M auf {1,2,...,n} gibt.
Gleichheitsregel: Gibt es eine bijektive Abbildung von der (endlichen)
Menge A auf B, so ist |A|=|B|.
Summenregel:
Sind A und B disjunkte (endliche) Mengen, so ist
| A  B | = | A | + | B |.
|
Beispiel 1:
Trotz seiner Einfachheit führt dieses Prinzip oft schon zu
Rekursionsgleichungen.
Sei etwa pn die Anzahl der Pflasterungen des n ×2 Schachbretts
mit 2*1-Dominos. Offensichtlich ist p1 = 1, p2 = 2,
p3 = 3, p4 = 5.
Jede solche Pflasterung hat aber ganz links entweder ein vertikales
Domino, oder zwei horizontale Dominos. Jede solche Pflasterung gehört
also genau zu einer der folgenden
beiden Mengen: Entweder zu der Menge Pf1 aller Pflasterungen
der Form
oder zur Menge Pf2 aller Pflasterungen der Form
.
Weil somit die Menge aller Pflasterungen des n ×2 Schachbretts
die disjunkte Vereinigung von Pf1 und Pf2 ist,
gilt nach der Summenregel
pn = | Pf1 | + | Pf2 |.
Da aber ganz offensichtlich | Pf1 | =
pn-1 und
| Pf2 | =
pn-2 gilt,
folgt durch Einsetzen die Rekursionsgleichung
|
2 ist.
Damit lassen sich pn für
beliebig grosse n automatisch berechnen.
Trotzdem hat diese Gleichung noch einen Nachteil:
Anzahlen von Pflasterungen werden durch
Anzahlen von Pflasterungen ausgedrückt, allerdings zum
Glück (oder leider?) kleineren Ausmaßes.
Beispiel 2: Als zweites Beispiel betrachten wir die Anzahl wn,m aller Wege von A nach B im n ×m Schachbrett. Zeigen Sie daß wn,m = wn-1,m + wn,m-1 gilt.
|
Produktregel:
Sind A und B endliche Mengen, so ist
| A ×B | =
| A | |B|.
|
Spezieller als die Produktregel, folgt folgende Regel aus der Summenregel, die ich Wahlregel nennen will, da wir die zu zählenden Elemente mit der Wahl von zwei Parameter erzeugen können. Wir wählen zuerste den ersten Parameter, und die Entscheidung dieses Parameters bestimmt die Anzahl der Möglichkeiten, die wir dann für die Wahl des zweiten Parameters haben. Rekursiv lässt sich das Prinzip natürlich auf beliebig viele Parameter erweitern.
Wahlregel:
Die Anzahl einer Relation R  A × B
sei zu bestimmen. Mit der Abkürzung R(a,.) =
{b  B/ (a,b) R}
ist
| R | =  aA
|R(a,.)|.
|
Oft ist entscheidend, in welcher Reihenfolge man die Wahlen trifft.
Betrachten wir die Anzahl aller Anordnungen der Buchstaben
"A", "B", "C", "D", "E", "F", "G", bei der "A" an erster Stelle,
aber an der letzten Stelle "B" oder "C" stehen muß.
Wählen wir die Buchstaben an den Stellen der Reihe nach,
so wird die Analyse schwierig: Wir haben nur eine Möglichkeit
an der ersten Stelle, 6 Möglichkeit an der zweiten Stelle.
Die Anzahl der Wahlmöglichkeiten an der dritten Stelle
hängt davon ab, ob wir "B" oder "C" an der zweiten Stelle
wählten. Falls ja, dürfen wir "C" oder "B"
an der dritten Stelle nicht wählen, haben also nur
4 Möglichkeiten, sonst 5.
Ganz einfach wird die Analyse, wenn wir zuerst
den Buchstaben an der ersten Stelle (1 Möglichkeit),
dann den Buchstaben an der letzten Stelle
(2 Möglichkeiten), dann den Buchstaben an der
zweiten, dritten, ... sechsten Stelle
(5, 4, 3, 2, 1 Möglichkeiten) wählen.
Es gibt also 1*2*5*4*3*2*1 = 240 solche Anordnungen.
Hier ist ein
weiteres Beispiel dazu.
Prinzip der doppelten Abzählung
Für eine gegebene Matrix berechen wir die Zeilensummen
und die Spaltensummen. Dann ist die Summe aller Spaltensummen
gleich der Summe aller Zeilensummen (gleich der Summe aller Einträge
der Matrix). In der Zeit manuellen Rechnens wurde diese Beobachtung
zur Kontrolle verwendet.
Für einen gegebenen bipartiten Graphen mit Bipartition A und B gibt es zwei einfache Möglichkeiten die Zahl der Kanten zu bestimmen. Einerseits ist sie gleich der Summe der Grade aller Ecken in A, aber natürlich auch gleich der Summe der Grade aller Ecken in B.
Prinzip der doppelten Abzählung:
Sei R
{a1,a2, ... ,am}
×{b1,b2, ... ,
bn}
eine Relation.
Für jedes 1  i
m sei d(ai) die Zahl der bj mit
(ai,bj) R,
und genauso sei für jedes 1 j
n d(bj)
die Zahl der ai die mit bj in Relation stehen.
Dann gilt
|
B gezählt,
aber die Elemente von A 
B
doppelt. Deshalb gilt | A B | =
| A | + | B | - | A
B |.
|
Wie sieht es bei drei Mengen A, B, und C aus?
Überlegen Sie sich wie oben daß gelten muss:
| A B
C | =
| A | + | B | + | C | - | A
B |
- | A C | - | B
C | + | A B
C |.
|
|
Siebformel:
Sind A1, A2, ... , An endliche Mengen, so ist
S
{1,2,...,n}, |S |
= i
|
x
S Ax | ist.
Beweis |
D.h. wir haben
a1 =
|A1|+
|A2|+ ... +|An
|,
a2 =
|A1
A2|+
|A1
A3|+ ... +
An-1
An|,
usw, bis schliesslich
an =
|A1 A2
...
An|.
Noch eine etwas andere Formulierung:
|
Als Folgerung ergibt sich:
Die Anzahl der surjektiven Abbildungen von {1,2,...,n} nach {1,2,...,k} ist gleich
|
Beweis Für jedes j {1,2,...,k}
sei Aj die Menge aller Abbildungen f von
{1,2,...,n} nach {1,2,...,k}, die j nicht treffen, d.h. mit
f-1({j}) =  .
Aj hat so viele Elemente wie es Abbildungen von
{1,2,...,n} nach {1,2,...,j-1,j+1,...k} gibt, also (k-1)n
nach obigen Bemerkungen.
Für Teilmengen S von {1,2,...,k} ist
|x
S Ax| = (k - |S|)n.
Da es genau (k über i) solcher Mengen S gibt,
ist in obiger Formel
ai = (k über i)(k-i)n
für jedes 1 i k ist.
Die Zahl aller nicht surjektiven Abbildungen ist
|A1
A2
...
An| =
a1
-
a2
+ a3
- ... + (-1)n-1
an
von der Geamtzahl kn aller Abbildungen
abgezogen ergibt obige Formel.
|
|
Von den 73 Studenten einer Vorlesung spielen 52 Klavier (!), 25 Violine, 20 Flöte. 17 Studenten beherrschen Klavier und Violine, 12 Klavier und Flöte, 7 Violine und Flöte, aber nur ein Student beherrscht alle drei Instrumente. Wieviel Studenten spielen keins dieser drei Instrumente? Jeder Student besucht genau 3 der 7 angebotenen Vorlesungen. Diese sieben Vorlesungen haben 73, 20, 20, 11, 4, 4 und 3 Hörer. Wieviel Studenten gibt es? |
|
I