Mathefrosch
Zählen, ohne abzuzählen

Kombinatorik
in drei Formeln

Produktregel, Auswählen, Mississippi-Regel –
mit Glace, rundem Tisch und einer Ameise.

Der Mathefrosch liest – Titelbild des Lehrmittels
Fahrplan

Drei Formeln – dann Beispiele

1 Produktregel Plätze der Reihe nach besetzen n1 · n2 · n3 · … Fakultät · runder Tisch
2 Auswählen Reihenfolge spielt keine Rolle nk Glace mit und ohne Wiederholung
3 Mississippi-Regel gleiche Objekte anordnen n!k1! · k2! · … MISSISSIPPI · Ameise

danach: Aufgaben

1

Produktregel

Produktregel

Wir werfen 2 Würfel.
Wie viele Möglichkeiten gibt es?

roter Würfel 6
blauer Würfel 6
6 · 6 = 36
Produktregel

Dreistellige Zahlen aus den Ziffern 1 bis 9

HunderterZehnerEiner
Ziffern beliebigz. B. 447 9·9·9 = 729
lauter verschiedene Ziffernz. B. 472 9·8·7 = 504
Produktregel

Multipliziere die Möglichkeiten
pro Platz miteinander!

n1 · n2 · n3 · … · nk
Fakultät

Sechs Personen setzen sich auf 6 Stühle.
Wie viele Möglichkeiten gibt es?

A B C D E F 6 5 4 3 2 1
6 · 5 · 4 · 3 · 2 · 1 = 720
Fakultät

Kurz geschrieben: 6!

6 · 5 · 4 · 3 · 2 · 1 = 6! = 720

gelesen: «6 Fakultät»  ·  Taschenrechner: Taste x!

n! = 1 · 2 · 3 · … · (n − 1) · n

Es gilt 1! = 1.  Man legt fest: 0! = 1.

Fakultät

Fakultäten kürzen

6!5! = 6 · 5 · 4 · 3 · 2 · 15 · 4 · 3 · 2 · 1 = 6

5! steckt in 6!:   6! = 6 · 5!

10!7! = 10 · 9 · 8 = 720
Runder Tisch

6 Personen am runden Tisch

A B C D E F
Alle rücken einen Platz weiter. Alle haben dieselben Nachbarn:
Es ist dieselbe Sitzordnung. In einer Reihe:  6! = 720 Am Tisch ist jede Sitzordnung
6-mal gezählt. 6!6 = 5! = 120
Runder Tisch

Oder: eine Person festhalten

A 5 4 3 2 1
A bleibt sitzen. Die anderen 5 verteilen sich
auf die 5 freien Plätze. 5 · 4 · 3 · 2 · 1 = 5! = 120 n Personen:  (n − 1)!
2

Auswählen

Auswählen

Auf wie viele Arten kann man aus
10 Kugeln 3 auswählen?

1 2 3 4 5 6 7 8 9 10 2 5 9
Der Reihe nach ziehen:  10 · 9 · 8 = 720 Aber: Beim Auswählen spielt die Reihenfolge keine Rolle.
Auswählen

Jede Auswahl ist 6-mal gezählt

259 295 529 592 925 952

3 Kugeln lassen sich auf 3 · 2 · 1 = 3! = 6 Arten ordnen.

10 · 9 · 83 · 2 · 1 = 7206 = 120
Binomialkoeffizient

Schreibweise: «10 tief 3»

103 = 10!3! · 7! = 10 · 9 · 83 · 2 · 1 = 120

Taschenrechner:  10 nCr 3 = 120  («n choose r»)

Auswählen

Euromillions: 5 Zahlen aus 50

8 17 23 36 45 4 11
505 = 2'118'760  Taschenrechner: 50 nCr 5 dazu 2 Sterne aus 12:  122 = 66 Jackpot, Produktregel:  2'118'760 · 66 = 139'838'160
Binomialkoeffizient

Allgemein: k aus n auswählen

nk = n!k! · (n − k)! = n · (n − 1) · … · (n − k + 1)k!

Reihenfolge spielt keine Rolle

Glace: 5 Sorten

Ein Becher mit 3 verschiedenen Kugeln

Vanille
Schokolade
Erdbeer
Pistazie
Heidelbeer
3 aus 5 auswählen:  53 = 5 · 4 · 33 · 2 · 1 = 10
Glace: 5 Sorten

Und wenn eine Sorte mehrfach vorkommt?

2 × Schokolade
1 × Pistazie
3 × Vanille
 
Wie vorhin?  5 · 5 · 5 = 125, dann durch 3! teilen: 1256 = 20.83…  keine ganze Zahl! Der Becher mit 2 × Schokolade und 1 × Pistazie hat nur 3 Reihenfolgen, der mit 3 × Vanille nur eine. Wir brauchen eine andere Idee.
Die Idee mit den Zwischenräumen

Die Sorten stehen nebeneinander

Vanille Schokolade Erdbeer Pistazie Heidelbeer
5 Sorten: dazwischen 4 Zwischenräume Ein Becher: 2 × Schokolade, 1 × Pistazie Von links nach rechts: jede Kugel ein Punkt, jeder Zwischenraum ein Strich 3 Kugeln und 4 Zwischenräume: ein Code mit 7 Zeichen
Die Idee mit den Zwischenräumen

Jeder Becher ist genau ein Code

2 × Schokolade
1 × Pistazie
→
3 × Vanille
→
Erdbeer, Pistazie, Heidelbeer
→
Umgekehrt: → Vanille, Schokolade, Pistazie
Die Idee mit den Zwischenräumen

Wie viele Codes gibt es?

7 Plätze: 3 davon bekommen eine Kugel, die anderen 4 einen Zwischenraum.

1
2
3
4
5
6
7
3 Plätze aus 7 auswählen:  73 = 7 · 6 · 53 · 2 · 1 = 35

35 verschiedene Becher

Kontrolle

Stimmt 35? Nachzählen!

3 verschiedene Sorten53 = 10
2 gleiche und 1 andere5 · 4 = 20
3 gleiche5
10 + 20 + 5 = 35 ✓
Auswählen mit Wiederholung

k Kugeln aus n Sorten

k Kugeln + (n − 1) Zwischenräume = n + k − 1 Zeichen Davon k Plätze für die Kugeln auswählen: n + k − 1k Glace: n = 5, k = 3  73 = 35
3

Mississippi-Regel

Mississippi-Regel

Wie viele Wörter aus O, T, T, O?

OTTO
Wären alle 4 Buchstaben verschieden:  4! = 24 Die zwei O und die zwei T tauschen – das Wort bleibt gleich:
O1T1T2O2 O1T2T1O2 O2T1T2O1 O2T2T1O1
4!2! · 2! = 244 = 6

Die 6 Wörter

OOTT OTOT OTTO TOOT TOTO TTOO
Mississippi-Regel

Wie viele Wörter aus MISSISSIPPI?

MISSISSIPPI
11 Buchstaben:  11! Anordnungen, wenn alle verschieden wären 4 gleiche I, 4 gleiche S, 2 gleiche P: Tauschen ändert nichts,
also durch 4! · 4! · 2! teilen 11!4! · 4! · 2! = 34'650
Mississippi-Regel

n Objekte, einige davon gleich

n!k1! · k2! · …

k1, k2, …: wie oft die gleichen Objekte vorkommen

durch die Vertauschungen teilen, die nichts ändern

Mississippi-Regel

Die Glace-Codes sind Mississippi-Wörter

7 Zeichen: 3 gleiche Kugeln, 4 gleiche Zwischenräume 7!3! · 4! = 35 = 73

zwei Sorten von Zeichen: Mississippi-Regel = Binomialkoeffizient

Zusammenfassung

Drei Formeln

1 Produktregel n1 · n2 · … · nk Plätze der Reihe nach besetzenalle auf alle Plätze: n!  ·  runder Tisch: (n − 1)! 2 Auswählen nk Reihenfolge spielt keine Rollemit Wiederholung:  n + k − 1k 3 Mississippi-Regel n!k1! · k2! · … gleiche Objekte anordnen
Frag dich der Reihe nach

Welches Werkzeug passt?

Zählt die Reihenfolge?→1Produktregel: pro Platz multiplizieren Kommen alle n Objekte auf n Plätze?→1Fakultät: n! Sitzen alle an einem runden Tisch?→1Runder Tisch: (n − 1)! Nur auswählen, Reihenfolge egal?→2Binomialkoeffizient: nk Darf sich dabei etwas wiederholen?→2Mit Wiederholung: n + k − 1k Sind beim Anordnen einige gleich?→3Mississippi-Regel: n!k1! · k2! · … Müssen einige nebeneinander stehen?→TrickBlock bilden, mit 1multiplizieren Heisst es «mindestens» oder «nicht»?→TrickGegenteil zählen, vom Total abziehen
4

Aufgaben

Aufgaben lösen

Vorgelöst: voll easy!

Selber lösen: anspruchsvoll!

Aufgabe 1

Passwort

Ein Passwort hat 8 Zeichen. Erlaubt sind Kleinbuchstaben, Grossbuchstaben und Ziffern. (a)Wie viele Passwörter gibt es? (b)Ein Rechner probiert 10 Milliarden Passwörter pro Sekunde. Wie lange braucht er für alle? (c)Und wenn das Passwort 12 Zeichen hat?

Produktregel: 8 Plätze mit je 26 + 26 + 10 = 62 Zeichen (a) 628 ≈ 2.18 · 1014 (b) 2.18 · 10141010 s ≈ 21'800 s ≈ 6 Stunden (c) 6212 ≈ 3.23 · 1021,   3.23 · 10211010 s ≈ 3.2 · 1011 s ≈ 10'000 Jahre
Aufgabe 2

Familienfest am runden Tisch

7 Personen sitzen an einem runden Tisch, darunter Oma und Opa. (a)Wie viele Sitzordnungen gibt es? (b)Oma und Opa wollen nebeneinander sitzen. (c)Oma und Opa sollen nicht nebeneinander sitzen.

(a) runder Tisch:  (7 − 1)! = 6! = 720 (b) Oma und Opa zusammenkleben:
6 «Personen»: 5! = 120,  tauschen: 120 · 2 = 240 (c) alle minus (b):  720 − 240 = 480
Oma Opa
Aufgabe 3

Mündliche Prüfung

Es gibt 12 Themen. 3 davon werden ausgelost. (a)Wie viele Auslosungen gibt es? (b)Du hast 9 Themen gelernt. Bei wie vielen Auslosungen kennst du alle 3? (c)Bei wie vielen kommen genau 2 gelernte Themen und 1 ungelerntes dran?

Auswählen: Die Reihenfolge der Themen spielt keine Rolle (a) 123 = 12 · 11 · 103 · 2 · 1 = 220 (b) nur aus den 9 gelernten:  93 = 84 (c) 2 der 9 gelernten und 1 der 3 ungelernten:
92 · 31 = 36 · 3 = 108
123456 789101112
Aufgabe 4

Stoppschild

Ein Stoppschild ist ein Achteck. Wie viele Diagonalen hat es?

Auswählen: Je 2 Ecken legen eine Strecke fest 82 = 8 · 72 · 1 = 28  Strecken davon sind 8 Seiten:  28 − 8 = 20  Diagonalen
STOP
Aufgabe 5

Zmorge

Du kaufst beim Beck 9 Brötli. Es gibt Gipfeli, Weggli und Bürli. Wie viele verschiedene Einkäufe sind möglich?

Auswählen mit Wiederholung: die Idee mit den Zwischenräumen
4 Gipfeli 3 Weggli 2 Bürli
9 Brötli und 2 Zwischenräume:  11 Zeichen 119 = 55  Einkäufe
Aufgabe 6

Eine Fussballsaison

Ein Team hat 10 Spiele gespielt: 5 Siege, 3 Unentschieden und 2 Niederlagen. In wie vielen verschiedenen Reihenfolgen können diese Resultate gekommen sein?

Mississippi-Regel: ein Wort aus S, U und N
SSUNSUSNSU
10!5! · 3! · 2! = 2'520
Aufgabe 7

Die Ameise

Eine Ameise läuft auf den Gitterlinien von A(2, 3) nach B(8, 10), immer nur nach rechts oder nach oben. (a)Wie viele Wege gibt es? (b)Wie viele Wege gibt es, wenn die Ameise nicht durch den Punkt C(5, 5) will?

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 0 A(2, 3) B(8, 10)
Aufgabe 7 (a)

Jeder Weg ist ein Wort

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 0 A B
R: nach rechts    O: nach oben OORROOOROORRR RRRROROROOOOO Jeder Weg: 6-mal R und 7-mal O,
also 13 Buchstaben Mississippi-Regel 13!6! · 7! = 1'716
Aufgabe 7 (b)

Nicht durch C(5, 5)

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 0 A B C(5, 5)
A nach C: 3 R, 2 O   5!3! · 2! = 10 C nach B: 3 R, 5 O   8!3! · 5! = 56 über C, Produktregel:  10 · 56 = 560 alle Wege minus die über C: 1'716 − 560 = 1'156
Kombinatorik

Plätze besetzen, auswählen
oder gleiche Objekte anordnen?
Erst fragen, dann rechnen.

Mathefrosch Viel Erfolg!