Kombinatorik

15 Min. · 2 Übungen

Die Kombinatorik beschäftigt sich mit dem Zählen von Objekten. Die gute Nachricht: Alle Aufgaben lassen sich auf wenige Grundformeln zurückführen, die wir im Folgenden behandeln.

Teil 1. Zählprinzipien

Zwei grundlegende Regeln bilden die Basis der gesamten Kombinatorik:

Additionsregel (ODER)

Wenn eine Auswahl auf $m$ Arten ODER auf $n$ Arten getroffen werden kann und sich diese Möglichkeiten nicht überschneiden, dann ist die Gesamtanzahl der Möglichkeiten:

m + n

Beispiel: Eine Speisekarte bietet 5 Suppen und 8 Salate an. Wie viele Optionen gibt es für ein leichtes Mittagessen (ein Gericht)?

5 + + 8 = = 13 Optionen

Multiplikationsregel (UND)

Wenn die erste Auswahl auf $m$ Arten getroffen werden kann UND für jede davon die zweite Auswahl auf $n$ Arten, dann ist die Gesamtanzahl der Möglichkeiten:

m \cdot n

Beispiel: Ein Café bietet 3 Suppen, 4 Hauptgerichte und 2 Getränke an. Wie viele Menü-Kombinationen gibt es?

3 \cdot \cdot 4 \cdot \cdot 2 = = 24 Optionen

Woran erkennt man „ODER" und „UND"?

Schlüsselwort	Operation	Beispiel
oder, entweder, eines von	Addition	Suppe oder Salat
und, beides, jedes	Multiplikation	Suppe und Salat und Getränk

Kombination beider Regeln

Komplexe Aufgaben erfordern oft die Anwendung beider Regeln gleichzeitig.

Beispiel: Eine Gruppe besteht aus 8 Jungen und 5 Mädchen. Zwei Personen sollen gewählt werden: ein Kapitän und ein Stellvertreter unterschiedlichen Geschlechts. Entweder ein Junge als Kapitän und ein Mädchen als Stellvertreter, oder umgekehrt.

Fall 1: $8 \cdot 5 = 40$
Fall 2: $5 \cdot 8 = 40$

40 + + 40 = = 80 M o ¨ glichkeiten

Zählen mit Einschränkungen

Wenn es eine Einschränkung gibt: zuerst die eingeschränkte Position besetzen!

Beispiel: Wie viele gerade dreistellige Zahlen lassen sich aus den Ziffern 1-5 ohne Wiederholung bilden?

Letzte Ziffer (muss gerade sein): 2 Optionen (2 oder 4)
Erste Ziffer: 4 Optionen (jede verbleibende)
Mittlere Ziffer: 3 Optionen

2 \cdot \cdot 4 \cdot \cdot 3 = = 24 Zahlen

Teil 2. Fakultät

Die Fakultät von $n$ ist das Produkt aller positiven ganzen Zahlen von 1 bis $n$ :

n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n

$n$	$n!$
0	1 (per Definition)
1	1
2	2
3	6
4	24
5	120
6	720
7	5040

Wichtige Eigenschaft: $n! = n \cdot (n - 1)!$

Zum Beispiel: $5! = 5 \cdot 4! = 5 \cdot 24 = 120$

Teil 3. Permutationen

Permutationen ohne Wiederholung

Permutation: eine geordnete Anordnung aller $n$ Elemente. Die Reihenfolge ist wichtig: ABC ≠ BAC.

P_{n} = n!

Beispiel: Auf wie viele Arten können 5 Bücher in einem Regal angeordnet werden?

P_{5} = = 5! = = 120 M o ¨ glichkeiten

Variationen (Teilpermutationen)

Variation: die Auswahl von $k$ Elementen aus $n$ unter Berücksichtigung der Reihenfolge.

A_{n}^{k} = = \frac{n !}{( n - k )!} = n \cdot \cdot (n - - 1) \cdot \cdot \dots \cdot \cdot (n - - k + + 1)

Beispiel: Auf wie viele Arten können ein Präsident, ein Vizepräsident und ein Sekretär aus 10 Personen gewählt werden?

A_{10}^{3} = = 10 \cdot \cdot 9 \cdot \cdot 8 = = 720 M o ¨ glichkeiten

Permutationen mit Wiederholung

Wenn unter $n$ Elementen identische vorkommen: $n_{1}$ vom ersten Typ, $n_{2}$ vom zweiten usw.

P_{n}^{n_{1}, n_{2}, \dots, n_{k}} = = \frac{n !}{n _{1} ! \cdot n _{2} ! \cdot \dots \cdot n _{k} !}

Intuition: Wir dividieren durch die Fakultäten der wiederholten Elemente, weil das Umordnen identischer Elemente untereinander Duplikate erzeugt.

Beispiel: Wie viele verschiedene Umstellungen der Buchstaben von MISSISSIPPI gibt es?

Insgesamt 11 Buchstaben: M(1), I(4), S(4), P(2)

P_{11}^{1, 4, 4, 2} = = \frac{11 !}{4 ! \cdot 4 ! \cdot 2 !} = = \frac{39 916 800}{1152} = = 34650

Kreispermutationen

Anordnung von $n$ Elementen im Kreis (kein fester Startpunkt). Jede lineare Anordnung kann $n$ -mal „gedreht" werden, also dividieren wir durch $n$ :

P_{Kreis} = (n - 1)!

Beispiel: 6 Personen an einem runden Tisch: $(6 - 1)! = 5! = 120$ Möglichkeiten.

Teil 4. Kombinationen

Was ist eine Kombination?

Kombination: eine Auswahl von $k$ Elementen aus $n$ , bei der die Reihenfolge keine Rolle spielt.

Vergleich:

Situation	Reihenfolge	Formel
Ein Team von 3 Personen wählen	Spielt keine Rolle	Kombinationen $C_{n}^{k}$
1., 2., 3. Platz vergeben	Ist wichtig	Variationen $A_{n}^{k}$

Woher kommt die Formel?

Schritt 1. Mit Reihenfolge: 3 aus 5 wählen = $5 \cdot 4 \cdot 3 = 60$ (das ist $A_{5}^{3}$ )

Schritt 2. Jedes Trio wurde $3! = 6$ Mal gezählt (alle internen Permutationen)

Schritt 3. Dividieren: $C_{5}^{3} = \frac{60}{6} = 10$

Die Formel

C_{n}^{k} = (k n) = \frac{n !}{k ! ( n - k )!}

In EPM-Prüfungen ist die Schreibweise $(k n)$ üblich, gelesen als „n über k".

Schnelle Berechnungsmethode

Statt volle Fakultäten zu berechnen, sofort kürzen:

C_{n}^{k} = = \frac{n \cdot ( n - 1 ) \cdot \dots \cdot ( n - k + 1 )}{k !}

Im Zähler stehen $k$ aufeinanderfolgende Zahlen beginnend bei $n$ , im Nenner steht $k!$ .

Beispiele:

C_{5}^{2} = = \frac{5 \cdot 4}{2 \cdot 1} = = 10

C_{8}^{3} = = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = = 56

C_{7}^{3} = = \frac{7 \cdot 6 \cdot 5}{3 !} = = \frac{210}{6} = = 35

Eigenschaften der Kombinationen

Symmetrie:

C_{n}^{k} = = C_{n}^{n - k}

3 aus 10 auszuwählen ist dasselbe wie 7 übrig zu lassen. Das hilft bei Berechnungen: $C_{100}^{98} = C_{100}^{2} = \frac{100 \cdot 99}{2} = 4950$ .

Spezialfälle:

$C_{n}^{0} = 1$ : eine Möglichkeit, nichts auszuwählen
$C_{n}^{n} = 1$ : eine Möglichkeit, alles auszuwählen
$C_{n}^{1} = n$

Pascalsche Formel:

C_{n}^{k} = = C_{n - 1}^{k - 1} + + C_{n - 1}^{k}

Das letzte Element ist entweder in der Auswahl ( $C_{n - 1}^{k - 1}$ ) oder nicht ( $C_{n - 1}^{k}$ ).

Zusammenhang mit Variationen:

A_{n}^{k} = = C_{n}^{k} \cdot \cdot k!

Variationen = Kombinationen × Permutationen der ausgewählten Elemente.

Kombinationen $(k n)$ werden auch in der Binomialverteilung (Bernoulli-Formel) zur Berechnung von Wahrscheinlichkeiten bei wiederholten unabhängigen Versuchen verwendet. Mehr dazu im eigenen Thema.

EPM-Prüfungsaufgaben

Aufgabe 1: Kugeln aus einer Urne

Eine Urne enthält 5 rote und 4 blaue Kugeln. Man zieht 3 Kugeln. Auf wie viele Arten kann man genau 2 rote ziehen?

2 rote aus 5 wählen: $C_{5}^{2} = 10$
1 blaue aus 4 wählen: $C_{4}^{1} = 4$
Nach der Multiplikationsregel: $10 \cdot 4 = 40$ Möglichkeiten

Aufgabe 2: Wahrscheinlichkeit

Aus derselben Urne zieht man 3 Kugeln. Wie groß ist die Wahrscheinlichkeit, dass alle drei dieselbe Farbe haben?

Gesamtergebnisse: $C_{9}^{3} = 84$

Günstige: alle rot $C_{5}^{3} = 10$ + alle blau $C_{4}^{3} = 4$ = 14

P = = \frac{14}{84} = = \frac{1}{6}

Aufgabe 3: Ausschuss mit Einschränkungen

Aus 6 Männern und 4 Frauen soll ein Ausschuss von 5 Personen gebildet werden. Es müssen mindestens 2 Frauen dabei sein. Auf wie viele Arten?

Frauen	Männer	Möglichkeiten
2	3	$C_{4}^{2} \cdot C_{6}^{3} = 6 \cdot 20 = 120$
3	2	$C_{4}^{3} \cdot C_{6}^{2} = 4 \cdot 15 = 60$
4	1	$C_{4}^{4} \cdot C_{6}^{1} = 1 \cdot 6 = 6$

Gesamt: $120 + 60 + 6 = 186$

Aufgabe 4: Bücherregal mit Gruppierung

In einem Regal stehen 4 Mathematik- und 3 Physikbücher. Auf wie viele Arten können sie angeordnet werden, wenn Bücher desselben Fachs zusammenstehen müssen?

Gruppen: $2! = 2$ Möglichkeiten für die Anordnung (M und P)
Innerhalb M: $4! = 24$
Innerhalb P: $3! = 6$

2! \cdot \cdot 4! \cdot \cdot 3! = = 2 \cdot \cdot 24 \cdot \cdot 6 = = 288 M o ¨ glichkeiten

Aufgabe 5: Permutationen mit Wiederholung

Wie viele verschiedene fünfstellige Zahlen lassen sich aus den Ziffern 1, 1, 2, 2, 3 bilden?

P_{5}^{2, 2, 1} = = \frac{5 !}{2 ! \cdot 2 ! \cdot 1 !} = = \frac{120}{4} = = 30

Häufige Fehler

Fehler 1: Verwechslung von „oder" und „und"

Suppe oder Salat wählen: Addition. Suppe und Salat wählen: Multiplikation.

Fehler 2: Verwechslung von Kombinationen und Variationen

Fragen Sie sich: Ist die Reihenfolge wichtig?

„Ein Team wählen": Reihenfolge unwichtig → Kombinationen
„Plätze vergeben": Reihenfolge wichtig → Variationen

Fehler 3: Nicht mit der Einschränkung beginnen

Wenn es eine Bedingung gibt (gerade Zahl, beginnt mit einer bestimmten Ziffer): zuerst die eingeschränkte Position besetzen.

Fehler 4: Addieren statt Multiplizieren bei Auswahl aus verschiedenen Gruppen

Bei gleichzeitiger Auswahl aus verschiedenen Gruppen gilt: multiplizieren, nicht addieren:

$C_{5}^{2} \cdot C_{4}^{1} = 40$ (richtig)

$10 + 4 = 14$ (falsch)

Fehler 5: Wiederholte Elemente vergessen

Wort MAMA: nicht $4! = 24$ , sondern $\frac{4 !}{2 ! \cdot 2 !} = 6$

Wie wählt man die richtige Formel?

Ist die Reihenfolge wichtig?
- JA: Alle Elemente?
  - JA: Permutationen, $P = n!$
  - NEIN: Variationen, $A = \frac{n !}{( n - k )!}$
- NEIN: Kombinationen, $C = \frac{n !}{k ! ( n - k )!}$

Überprüfen Sie Ihr Wissen

Jetzt Sie1 von 2

Ein Zugangscode besteht entweder aus zwei verschiedenen Buchstaben aus A, B, C, D, E oder aus drei verschiedenen Ziffern aus 1, 2, 3, 4. Wie viele verschiedene Codes gibt es?

14

44

480

40

Jetzt Sie2 von 2

Fünf Personen setzen sich an einen runden Tisch, und zwei von ihnen, Anna und Ben, wollen nebeneinander sitzen. Sitzordnungen, die durch Drehen ineinander übergehen, gelten als gleich. Wie viele Sitzordnungen gibt es?

24

12

48

6

Alle Formeln

Additionsregel (ODER): $m + n$

Multiplikationsregel (UND): $m \cdot n$

Fakultät: $n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$ , wobei $0! = 1$

Permutationen: $P_{n} = n!$

Variationen: $A_{n}^{k} = \frac{n !}{( n - k )!}$

Permutationen mit Wiederholung: $P_{n}^{n_{1}, \dots, n_{k}} = \frac{n !}{n _{1} ! \cdot \dots \cdot n _{k} !}$

Kreispermutationen: $P_{Kreis} = (n - 1)!$

Kombinationen: $C_{n}^{k} = (k n) = \frac{n !}{k ! ( n - k )!}$

Schnelle Berechnung: $C_{n}^{k} = \frac{n \cdot ( n - 1 ) \cdot \dots \cdot ( n - k + 1 )}{k !}$

Symmetrie: $C_{n}^{k} = C_{n}^{n - k}$

Pascalsche Formel: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$

Zusammenhang: $A_{n}^{k} = C_{n}^{k} \cdot k!$

Jetzt üben

Kombinatorik

Trainer · Wahrscheinlichkeit

Üben

Weiter: Bedingte Wahrscheinlichkeit

0/2

Übungen gelöst