Einführung
Nicht immer werden sich Aufgaben nach den hier dargestellten Formeln direkt lösen lassen. Dann muss man auf die Grundlagen zurückgreifen. Diese sind neben der Fakultät und dem Binomialkoeffizienten das Zählprinzip auch Produktregel genannt.Definition: Produktregel
Aus k nichtleeren Mengen M1,M2,...,Mk mit n1,n2,...,nk Elementen kann man
n1·n2·...·nk
verschiedene k-Tupel (x1,x2,...,xk), also Kombinationen, mit ni ∈ Mi.
Interpretationen
- Dies entspricht der Anzahl an Pfaden in dem entsprechenden Baumdiagramm.
Beispiel
Aufgabe
Ein Autokennzeichen besteht nach dem Ortskürzel aus 2 Buchstaben und 4 Ziffern, wobei die erste nicht Null sein darf. Wie viele Kennzeichen gibt es?
Lösung
Es gibt 26 Buchstaben, daher: 26·26·9·10·10·10 = 6084000. Da die erste Ziffer nicht 0 sein darf, gibt es hier nur 9 Möglichkeiten.
Viele der hier dargestellten Regeln lassen sich auf das Ziehen von Kugeln aus einer Urne zurückführen. Beim Lösen von Anwendungsaufgaben sollte man daher auch immer versuchen, das Problem auf das Urnenmodell zu reduzieren.
Sollte es mehr um das Verteilen gehen, so muss man sich den Zusammenhang bewusst machen: Das Verteilen von Kugeln auf Urnen ist auffassbar als Ziehen der Urnennummer für die zu verteilenden Kugeln.
Permutation - Anordnung
Permutationen sind eine wichtige Grundlage im Bereich der Kombinatorik, da die Reihenfolge von Ereignissen oft eine Rolle spielt.
Definition: Permutation ohne Wiederholung
Einer Gesamtheit von n verschiedenen Elementen lassen sich auf
n! = n·(n-1)·(n-2)·...·2·1
Möglichkeiten anordnen. Die Reihenfolge der Elemente muss berücksichtigt werden. Es gilt 0! = 1.
Sprich: "n Fakultät"
Interpretationen
- Anzahl der Möglichkeiten, eine geordnete Stichprobe von n Kugeln aus einer Urne mit n Kugeln ohne Zurücklegen zu ziehen.
- Anzahl der Möglichkeiten, n verschiedene (unterscheidbare) Objekte so auf n Urnen zu verteilen, dass in jeder Urne ein Objekt liegt.
- Anzahl der n-stelligen Sequenzen von n verschiedenen Zeichen, in denen jedes Zeichen genau einmal vorkommt.
Berechnung
Beispiel 1
Aufgabe
Auf wie viele Arten können sich 3 Menschen hintereinander aufstellen?
Lösung
Der erste hat 3 Plätze zum Hinstellen zur Verfügung, der zweite 2, der Dritte 1 Platz zur Verfügung. Somit sind folgende Permutationen (Vertauschungen) denkbar: (1,2,3), (2,1,3), (2,3,1), (3,1,2), (1,3,2), (3,2,1). Die Anzahl der Möglichkeiten beträgt damit 3! = 3 · 2 · 1 = 6.
Definition: Permutation mit Wiederholung
mit k1+k2+...+kn = k.
Interpretationen
- Anzahl der Möglichkeiten, eine geordnete Stichprobe von k Kugeln aus einer Urne mit n Kugeln mit zurücklegen so zu ziehen, dass, dass die Kugel ai genau ki-mal gezogen wird.
- Anzahl der Möglichkeiten, k unterscheidbare Objekte auf n Urnen so zu verteilen, dass in der i-ten Urne ki Objekte liegen.
Beispiel 2
Aufgabe
Auf wieviele Arten kann man die Buchstaben des Wortes "MISSISSIPPI" anordnen, so dass Wörter entstehen?
Lösung
Man kann die 11 Buchstaben auf 11! Möglichkeiten anordnen. Da sich die "S" aber nicht unterscheiden, muss 11! durch die Anzahl der Anordnungen der 4 "S" teilen. Bislang ergibt sich somit 11!/4!. Das Gleiche gilt für die vier "I" und die zwei "P". Insgesamt ergibt sich somit 11!/(2!·4!·4!·1!). Die 1! wurde hinzugenommen, da k1+k2+...+kn = k also 2+4+4+1 = 11 gelten muss. Es ergeben sich 34650 Möglichkeiten.
Auswahl oder Variation
In vielen Fällen werden gar nicht alle Elemente einer Menge angeordnet, sondern nur eine Teilmenge. Ein Beispiel ist die Ziehung der Lottozahlen. Hier werden nur 6 von 49 Zahlen gezogen, wobei die Reihenfolge der Ziehung der Lottozahlen keine Rolle spielt. Ist die Reihenfolge aber entscheidend dann gilt folgende Regel:
Definition: Ziehen ohne Zurücklegen mit Reihenfolge
Einer Gesamtheit von n verschiedenen Elementen kann man
viele Tupel mit k Elementen und Berücksichtigung der Reihenfolge entnehmen, wobei k≤n gilt.
Da n!:(n-k)! = [n·(n-1)·(n-2)·...·1] : [(n-k)·(n-k-1)·...·1] = n·(n-1)·(n-2)·...·(n-k+1) gilt.
Interpretationen
- Anzahl der Möglichkeiten, k≤n verschiedene (unterscheidbare) Objekte auf n Urnen zu verteilen, wobei in jeder Urne nur 1 Objekt liegt.
- Anzahl der k-stelligen Sequenzen aus n verschiedenen Zeichen.
- Entspricht auf Taschenrechner der Taste nPr
Berechnung
Beispiel 3
Aufgabe
In einer Urne liegen 10 verschiedene Kugeln beschriftet von 1 bis 10. Aus dieser Urne werden nun nacheinander 3 Kugeln gezogen. Wenn die Reihenfolge nun eine Rolle spielt, also 1,2,3 eine andere Lösung ist als 3,2,1, wieviele Lösungen gibt es?
Lösung
Stellt man sich vor, dass die gezogenene Kugeln in Eierbecher abgelegt werden, so können im ersten Eierbecher 10 verschieden Kugeln liegen. Im zweiten nur noch 9, da eine bereits im ersten Becher liegt. Im dritten und letzten können nur noch 8 verschiedene liegen.
Es ergeben sich: 10·9·8 = 720 Möglichkeiten.
In Bezug auf die Formel ist hier n=10, d.h. man musste rechnen: n·(n-1)·(n-2). Die letzte 2 entspricht k+1, wenn k die Anzahl der zu ziehenden Kugeln ist.
Beispiel 4a
Aufgabe
Ein Flugzeug hat 250 Sitzplätze es sind aber nur 243 Personen an Bord. Wie viele Möglichkeiten für die freie Sitzplätze gibt es?
Lösung
Die Sitzplätze sind von 1 bis 250 durchnummeriert, d.h. man kann sich die Anzahl der Möglichkeiten so überlegen, dass aus einer Urne mit 250 Kugeln sieben gezogen werden. Damit ergeben sich 250 Möglichkeiten für den ersten Platz, 249 für den zweiten etc. Insgesamt also 250·249·248·247·246·245·244 = 56076255733680000. >>
Definition: Ziehen ohne Zurücklegen ohne Reihenfolge (Binomialkoeffizient B(n,k) )
Aus einer Menge von n Elementen lassen sich ohne Berücksichtigung der Reihenfolge
viele Tupel mit k Elementen bilden.
Sprich: "n über k"
Interpretationen
- Anzahl der Möglichkeiten, aus einer Urne mit n verschiedenen Kugeln k Kugeln ohne Zurücklegen und ohne Beachtung der Reihenfolge zu ziehen (k≤n). Die Kugeln können gleichzeitig gezogen werden.
- Anzahl der Möglichkeiten, k gleiche (nicht unterscheidbare) Kugeln auf n unterscheidbare Urnen zu verteilen, wobei jede Urne höchstens eine Kugel erhalten kann.
- Anzahl der n-stelligen Sequenzen mit k-Mal dem Zeichen "1" und (n-k)-Mal dem Zeichen "0".
- Anzahl der k-elementigen Teilmengen einer n-elementigen Menge.
- Entspricht der Taste nCr.
Berechnung
Im Folgenden soll kurz der Beweis skizziert werden:
Da man genauso gut die verbleibenden Kugeln untersuchen kann, gilt das erste Gleichheitszeichen.
Beispiel 4b
Jetzt wird nicht mehr in der Reihenfolge unterschieden. Die sieben gezogenen Kugeln lassen sich auf 7! = 5040 Arten anordnen. Denn es ist unerheblich ob der Sitzplatz 137 am Anfang als freier Platz gezogen wird oder am Schluss. Es ergeben sich somit 11126241217000 Möglichkeiten wie die freien Sitzplätze sich verteilen.
Beispiel 5
Auswahl von k=2 elementigen Tupel aus einer Grundmenge {1,2,3,4} mit n=4.
Es ergebn sich 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43 zweielementige Tupel ( n!/(n-k)! ), aus denen die Vertauschungsgleichen herausgenommen werden. Da es 2! Möglichkeiten gibt 2 Elemente zu permutieren ergeben sich nur noch 6 Ergebnistupel: 12, 13, 14, 23, 24, 34. Dies entspricht n!/k!(n-k)! .
Eine andere einfache Möglichkeit ist folgendes Szenario: Man hat n=10 Kugeln, k=4 rot, n-k=6 schwarz. Wie viele verschieden Kombination gibt es? Zunächst hat man prinzipiell 10! Möglichkeiten. Davon fallen 4! weg, da die roten Kugeln ja nicht unterschieden werden können. Ebenso fallen 6! Kombinationen weg, da die schwarzen sich auch nicht unterscheiden lassen.
Definition: Ziehen mit Zurücklegen ohne Reihenfolge
Aus einer Menge von n Elementen lassen sich ohne Berücksichtigung der Reihenfolge
viele Tupel mit k Elementen bilden, wobei die Elemente gleich sein können.
Interpretationen
- Anzahl der Möglichkeiten, aus einer Urne mit n verschiedenen Kugeln k Kugeln mit Zurücklegen und ohne Beachtung der Reihenfolge (ungeordnete Stichprobe) zu ziehen, wobei k>n sein kann.
- Anzahl der Möglichkeiten, k gleiche (nicht unterscheidbare) Kugeln auf n unterscheidbare Urnen zu verteilen, wobei jede Urne mehrere Kugeln erhalten kann und k>n möglich ist.
Berechnung
Beispiel 6a
Auswahl von k=2 elementigen Tupel aus einer n=4 elementigen Grundmenge.
Ein mögliches Ergebnis sähe so aus: 11, 12, 13, 14, 22, 23, 24, 33, 34, 44 und besteht folglich aus 10 Elementen. Man beachte, dass die zweite Stelle immer größer oder gleich der ersten Stelle ist.
Beispiel 6b
Sechs gleichwertige Ämter sollen auf 20 Schüler verteilt werden, wobei ein Schüler auch mehrere Ämter besitzen kann.
Ein erster Ansatz sähe wie folgt aus: Man legt 20 unterscheidbare Kugeln in eine Urne und zieht mit Zurücklegen (da ein Schüler ja mehrere Ämter haben kann). Der erste Zug ist der Schüler für das erste Amt, der zweite Schüler wird beim zweiten Zug dem zweiten Amt zugeordnet etc. Dennoch ist dieser Ansatz falsch, da die Reihenfolge der Ämter berücksichtigt wird. 1,2,5,2,4,7 (der Schüler mit der Nummer 2 hat also zwei Ämter) wäre ein anderes Ergebnis als 1,5,2,2,4,7.
Richtig wäre es die 6 Ämter auf die 25 Schüler zu verteilen. Die Ämter seine A,B,C,D,E,F und ein Lösung so wie folgt aus:
||A||B,D|||||C||||E|||F|||.
Die senkrechte Striche sollen die Schüler voneinander trennen (man benötigt also 19 Stück. In dem Beispiel hat der dritte Schüler das Amt A, der Schüler mit der Nummer 5 die Ämter B und D usw.
Da es keine Rolle spielen soll, welches Amt jemand ausübt, kann man an Stelle von sechs verschiedenen Buchstaben auch nur A wählen:
||A||A,A|||||A||||A|||A|||
Das wäre dadurch zu realisieren, dass der Name des Amts in einem Briefumschlag steckt, wobei die Umschläge nicht zu unterscheiden sind.
Die Anzahl der Anordnungen dieser Striche und A's entsprechen damit der Anzahl der möglichen Ämterverteilungen wobei die
Striche und die A's vertauschbar sind. Das erinnert gleich an den Mississippi-Ansatz. Es sind (20-1)+6 Objekte, die permutiert werden.
Wobei man ein Vertauschen der As und der Striche nicht erkennt, daher müssen diese herausgenommen werden.
Man erhält also [(20-1)+6]!/(20-1)!*6!=177.100 . Oder mit n=20 und k=6 die obige allgemeine
Formel.
||A||A,A|||||A||||A|||A||| |||||||||||||||||||
Das Ziehen mit Zurücklegen ohne Berücksichtigung darf nicht mit Verwechselt werden mit dem Ziehen mit Zurücklegen unter Berücksichtugung der Reihenfolge. Ein typisches Beispiel ist das Würfeln mit 2 Würfeln. Im ersten Fall gibt es nur 21 Möglichkeiten. Wenn man aber die Unterscheidung (1,2)≠(2,1) zu lässt, erhält man 36 Möglichkeiten.
Definition: Ziehen mit Zurücklegen mit Reihenfolge
Aus einer Menge von n Elementen lassen sich unter Berücksichtigung der Reihenfolge
nk
viele Tupel mit k Elementen bilden, wobei die Elemente gleich sein können.
Interpretationen
- Anzahl der Möglichkeiten, eine geordnete Stichprobe von k Kugeln aus einer Urne mit n unterscheidbaren Kugeln mit Zurücklegen zu ziehen.
- Anzahl der Möglichkeiten, k verschiedene (unterscheidbare) Objekte auf n Urnen zu verteilen, wobei jede Urne beliebig viele Objekte aufnehmen kann.
- Anzahl der k-stelligen Sequenzen, in denen jede Stelle mit irgendeinem von n verschiedenen, beliebig oft wiederholbaren Zeichen besetzt ist.
Berechnung
Beispiel 7
Auswahl von k=2 elementigen Tupel aus einer n=4 elementigen Grundmenge und der Unterscheidung bzgl der Reihenfolge.
Das Ergebnis lautet: 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44 und besteht folglich aus 16 Elementen. Hier durchläuft sowohl die erste Stelle die Werte 1 bis 4 als auch die zweite Stelle.
Formelsammlung
mit Reihenfolge | ohne Reihenfolge | |
mit Wiederholung | nk | |
ohne Wiederholung |
Rechner
Beispiele
Für die Beispiele wurde n=4 und k=2 gewählt.
mit Reihenfolge | ohne Reihenfolge | |
mit Wiederholung | 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44 Alle denkbaren Kombinationen: 16 Elemente | 11, 12, 13, 14, 22, 23, 24, 33, 34, 44 Alle Permutationsdoppelten wie z.B. (1,2), (2,1) werden weggenommen: 10 Elemente |
ohne Wiederholung | 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43 Die Diagonale wird weggenommen: 12 Elemente | 12, 13, 14, 23, 24, 34 Die Permutationsdoppelten und die Diagonale wird rausgenommen: 6 Elemente |
Aufgaben mit Lösungen
Aufgabe 1
a) Berechnen Sie die Anzahl der 3-Tupel aus {1,2,3,4}.
b) Berechnen Sie die Anzahl der 3-Tupel aus {1,2,3,4}, die mit 2 beginnen.
Lösung von Aufgabe 1
Aufgabe 2
Wie können sich 10 Vögel auf 5 Bäume verteilen?
Lösung von Aufgabe 2
Aufgabe 3
In der Schifffahrt gibt es das Winkeralphabet. Eine Art Morsealphabet mit Flaggen. Für den rechten Arm gibt es 7 Positionen. Wie viele muss es für den linken Arm geben, damit alle 26 Buchstaben des Alphabets angezeigt werden können?
Lösung von Aufgabe 3
Links
- Mathe-Prisma
Urnenmodell: 4 Grundformeln