Kombinatorik üben Klasse 10 – online lernen

Urnenmodell I

Geordnetes Ziehen mit Zurücklegen

Es gilt: |M|I=n⋅n⋅n⋅...⋅n=nk${|M|}_I=n\cdot n\cdot n\cdot ...\cdot n=n^k$ 

Anschaulich:

Es sind n$n$ Kugeln in der Urne, also gibt es beim ersten Zug n$n$ Möglichkeiten. Beim zweiten Zug (die Kugel wurde zurückgelegt) sind es wieder die gleichen n$n$ Möglichkeiten usw. bis zum k$k$-ten Zug. Daher gibt es nk$n^k$  Möglichkeiten.

Beispiel: Wie viele Möglichkeiten gibt es, mit den Zahlen von 0 bis 9 eine 4-stellige Vorwahl zu entwickeln?

Es gibt 10 verschiedene Ziffern zur Auswahl. Diese werden kombiniert. Es gilt also n=10$n=10$. Wir möchten k=4$k=4$ davon auswählen:

|M|I=104=10⋅10⋅10⋅10=10000${|M|}_I={10}^4=10\cdot 10\cdot 10\cdot 10=10000$ 

Daher gibt es 10 000 verschiedene Vorwahlen.

Das Modell |M|I${|M|}_I$ passt deshalb zu dieser Aufgabe, weil die Reihenfolge bei der Telefonnummer eine Rolle spielt und weil eine Ziffer mehrmals verwendet werden darf.

Urnenmodell II

Geordnetes Ziehen ohne Zurücklegen

Es gilt: |M|II=n(n−1)(n−2)⋅...⋅(n−k+1)=n!(n−k)!${|M|}_{II}=n(n-1)(n-2)\cdot ...\cdot (n-k+1)=\frac{n!}{(n-k)!}$

Anschaulich:

Es sind n$n$ Kugeln in der Urne, also gibt es beim ersten Zug n$n$ Möglichkeiten. Beim zweiten Zug ist eine Kugel weniger enthalten, also nur noch n−1$n-1$Möglichkeiten, beim nächsten Zug n−2$n-2$ usw. bis zum k$k$-ten Zug. Die Formel lässt sich anschließend mit der Fakultät zusammenfassen.

Beispiel: Wie viele Möglichkeiten gibt es das Wort SPORT anzuordnen?

Da SPORT fünf verschiedene Buchstaben beinhaltet gilt n=5$n=5$. Da das Wort auch 5 Buchstaben lang ist gilt k=5$k=5$.

Gesucht ist also die Anzahl aller möglichen Vertauschungen (Permutationen) von 5 Objekten: 

|M|II=5!(5−5)!=5⋅4⋅3⋅2⋅11=120${|M|}_{II}=\frac{5!}{(5-5)!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{1}=120$

Daher gibt es 120 verschiedene Anordnungen der Buchstaben SPORT.

Das Modell |M|II${|M|}_{II}$ passt deshalb zu dieser Aufgabe, weil die Reihenfolge bei der Bildung der Wörter eine Rolle spielt und weil kein Buchstabe öfter verwendet werden darf, als er bereits vorkommt.

Beachte: 0!=1$0!=1$, die Fakultät der 0 ist mit 1 definiert.

Urnenmodell III 

Ungeordnetes Ziehen ohne Zurücklegen

Es gilt: |M|III=|MII|k!=n!k!(n−k)!=nk${|M|}_{III}=\frac{{|M}_{II}|}{k!}=\frac{n!}{k!(n-k)!}=\begin{array}{cc}n& \\ k& \end{array}$

Anschaulich:

|M|III${|M|}_{III}$ ergibt sich einfach aus |M|II${|M|}_{II}$. Der einzige Unterschied ist die Berücksichtigung der Ziehungsreihenfolge. Jedes Element aus |M|III${|M|}_{III}$ ist daher k!$k!$-mal in |M|II${|M|}_{II}$ enthalten, nämlich in all seinen möglichen Vertauschungen (Permutationen). Das heißt, die k!$k!$. Vielen Permutationen müssen ‚herausdividiert‘ werden. Das Ergebnis ist der Binomialkoeffizient n$n$ über k$k$.

Beispiel: Auf 15 Personen werden 3 Karten für das Kino verteilt. Auf wie viele Arten können die Karten verteilt werden, wenn jeder höchstens eine Karte erhält und sich die Karten auf nicht nummerierte Sitzplätze beziehen?

15 Karten werden verteilt, daher gilt n=15$n=15$. Sie werden auf 3 Personen verteilt, also gilt k=3$k=3$. Mit oben genannter Formel folgern wir:

153=15!3!(15−3)!=15!3!12!=455$\begin{array}{cc}15& \\ 3& \end{array}=\frac{15!}{3!(15-3)!}=\frac{15!}{3!12!}=455$

Daher gibt es 455 verschiedene Anordnungen die Karten zu verteilen.

Das Modell |M|III${|M|}_{III}$ passt deshalb zu dieser Aufgabe, weil die Reihenfolge bei der Verteilung der Karten keine Rolle spielt (die Sitze sind nicht nummeriert, legen also keine Sitzreihenfolge fest) und weil keine Person mehr als ein Ticket erhalten kann.

Urnenmodell IV

Ungeordnetes Ziehen mit Zurücklegen

Es gilt: |M|IV=(n+k−1)!k!(n−1)!=n+k−1k${|M|}_{IV}=\frac{(n+k-1)!}{k!(n-1)!}=\begin{array}{cc}n+k-1& \\ k& \end{array}$

Beispiel: In einer Bäckerei werden vier verschiedene Kuchensorten, die in ausreichender Menge vorhanden sind (daher „mit Zurücklegen“), verkauft. Wie viele Kombinationsmöglichkeiten gibt es, wenn man sieben Stücke kaufen möchte?

Es gibt vier Kuchensorten, daher gilt n=4$n=4$; sieben Stücke sollen gekauft werden, also folgt k=7$k=7$.

Da Wiederholungen möglich sind, man also z. B. mehrere Stücke Erdbeerkuchen kaufen kann, es aber egal ist, in welcher Reihenfolge man sie kauft, kann man hier das Urnenmodell IV mit Ergebnismenge |M|IV${|M|}_{IV}$ wählen:

4+7−17=(4+7−1)!7!(4−1)!=(10)!7!3!=8⋅9⋅101⋅2⋅3=7206=120$\begin{array}{cc}4+7-1& \\ 7& \end{array}=\frac{(4+7-1)!}{7!(4-1)!}=\frac{(10)!}{7!3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=\frac{720}{6}=120$

Urnenmodelle 

Ein erster Einblick

Oft ist es in der Stochastik nötig, die Kardinalität (Mächtigkeit) von Mengen zu betrachten, oft als Anzahl von Möglichkeiten.

Ein Urnenmodell ist ein Gedankenexperiment. Man stellt sich eine Urne vor, in der n$n$ Kugeln liegen. Jede Kugel hat die gleiche Wahrscheinlichkeit gezogen zu werden und alle Kugeln sind voneinander unterscheidbar. Will man nun eine Anzahl von k$k$ Kugeln ziehen (k≤n)$(k\le n)$, gibt es vier Möglichkeiten das Experiment durchzuführen:

1. Was passiert nach dem Ziehen einer Kugel?
   1. Sie wird zurückgelegt
   2. Sie wird nicht zurückgelegt
2. Wie betrachten wir die gezogenen Kugeln (k≥2)$(k\ge 2)$:
   1. Die Ziehungsreihenfolge wird berücksichtigt: (a,b)≠(b,a)$(a,b)\ne (b,a)$
   2. Die Ziehungsreihenfolge spielt keine Rolle: {a,b$a,b$} = {b,a$b,a$}

Die Mengen, welche alle möglichen Ziehungsergebnisse enthalten, nennen wir MI,MII,MIII$M_I,M_{II},M_{III}$ und MIV$M_{IV}$ mit folgendem Schema:

Jedes dieser möglichen Modelle hat ein eigenes Wiki mit entsprechendem Namen.

Mehrstufige Wahrscheinlichkeit

Hier soll ein Wahrscheinlichkeitsexperiment mit unterschiedlichen Wahrscheinlichkeiten der Ergebnisse in einer mehrstufigen Variante betrachtet werden.

Beispiel:

Ausgehend von einer Klasse mit 30 Kindern (18 Mädchen, 12 Jungen), ruft der Lehrer nacheinander drei (Wiederholungen möglich) Kinder an die Tafel, wobei jedes Kind die gleiche Chance hat dran zu kommen. Wie hoch ist dann die Wahrscheinlichkeit, dass…

a) … genau 2 Jungen an die Tafel müssen.

b) … es mindestens 2 Mädchen trifft.

Vorüberlegungen: Der Ergebnisraum lautet: Ω=$\mathrm{\Omega }=$ {JJJ,JJM,JMJ,JMM,MJJ,MJM,MMJ,MMM$JJJ,JJM,JMJ,JMM,MJJ,MJM,MMJ,MMM$}, wobei nicht alle Ergebnisse die gleiche Wahrscheinlichkeit haben.

Aufgrund der Kommutativität der Multiplikation gilt aber, dass alle Ergebnisse mit genau zwei Jungen (2J) gleich wahrscheinlich sind. Gleiches gilt für alle Ergebnisse mit genau zwei Mädchen (2M).

Pro Aufruf eines Schülers beträgt die Wahrscheinlichkeit P(J)=1230=0,4$P(J)=\frac{12}{30}=0,4$ und P(M)=1830=0,6$P(M)=\frac{18}{30}=0,6$.

a) Das Ereignis 2J$2J$ steht für die Menge {JJM,JMJ,MJJ$JJM,JMJ,MJJ$}. Laut Vorüberlegung sind diese jeweils gleich wahrscheinlich. Also genügt es, die Wahrscheinlichkeit einer dieser Fälle zu berechnen und zu verdreifachen:

P(2J)=3⋅P(JJM)=3⋅1230⋅1230⋅1830=3⋅0,096=0,288=28,8$P(2J)=3\cdot P(JJM)=3\cdot \frac{12}{30}\cdot \frac{12}{30}\cdot \frac{18}{30}=3\cdot 0,096=0,288=28,8$%

b) Die gesuchte Menge setzt sich  zusammen aus 2M∪3M=$2M\cup 3M=$ {JMM,MJM,MMJ,MMM$JMM,MJM,MMJ,MMM$}. Die Wahrscheinlichkeit für 2M$2M$lässt sich analog zu a) berechnen. Hinzu addieren wir die Wahrscheinlichkeit von 3M$3M$: 

3⋅P(MMJ)+P(MMM)=3⋅1830⋅1830⋅1230+(1830)3=0,432+0,216=0,648=64,8$3\cdot P(MMJ)+P(MMM)=3\cdot \frac{18}{30}\cdot \frac{18}{30}\cdot \frac{12}{30}+{(\frac{18}{30})}^3=0,432+0,216=0,648=64,8$%

Fakultäten

Die Fakultät, seltener Faktorielle genannt, bezeichnet eine Funktion, die einer natürlichen Zahl das Produkt aller natürlichen Zahlen bis zu eben dieser zuordnet.

Für die Fakultät einer natürlichen Zahl n$n$ schreibt man n!$n!$:

Beispielaufgabe:

Wie lauten die Fakultäten von 3$3$, 5$5$ und 10$10$?

Lösung:

3!=3⋅2⋅1=6$3!=3\cdot 2\cdot 1=6$

5!=5⋅4⋅3⋅2⋅1=120$5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$

10!=10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1=3628800$10!=10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=3628800$