Selektionsprobleme

Wir betrachten nun Kombinatorik aus einer anderen Perspektive. Gegeben sei ein Korb mit $5$ verschiedenen Objekten, etwa den Buchstaben A B C D E. Wir selektieren $3$ Buchstaben aus dem Korb - auf wie viele Arten ist dies möglich? Bezeichnen wir diese Anzahl mit $M$ .

Wir müssen dazu vier verschiedene Fälle unterscheiden: mit oder ohne Zurücklegen, und Reihefolge der Selektionen wichtig oder unwichtig.

mit Zurücklegen bedeutet, dass wir vor der nächsten Selektion eines Buchstabens aus dem Korb den zuvor selektierten Buchstaben zuerst wieder in den Korb zurücklegen.
ohne Zurücklegen bedeutet, dass wir die selektieren Buchstaben nicht zurücklegen.
Reihefolge wichtig bedeutet, dass wir die zwei Ergebnisse A B C D und B C A D als verschieden betrachten, obwohl die gleichen Buchstaben vorkommen - sie wurden aber in einer anderen Reihenfolge gezogen. Im ersten Fall wurde zuerst das A, dann das B gezogen, gefolgt vom C und D. Im zweiten Fall wurde zuerst das B gezogen, gefolgt vom C, A, und D.
Reihenfolge unwichtig bedeutet, dass wir die zwei Ergebnisse als geich betrachten, wir zählen sie nur einmal. Die Ziehreihenfolge spielt keine Rolle, nur welche Buchstaben wir gezogen haben.

Aufgabe

Ein Korb enthält die Buchstaben A B C D. Zwei Buchstaben werden gezogen. Bestimme für jeden der vier Fälle auf wie viele Arten dies möglich ist? Erstelle dazu immer eine Liste aller möglichen Ergebnisse.

Diskutieren wir nun die einzelnen Fälle, und versuchen einige Formeln herzuleiten. Wir brauchen immer das Beispiel oben, also $5$ verschiedene Buchstaben, wovon wir dreimal einen Buchstaben aus dem Korb selektieren. Allgemin hätten wir $n$ verschiedenene Objekte, wobei wir $k$ aus dem Korb selektieren.

Ohne Zurücklegen, Reihenfolge wichtig

Die ersten $3$ Generationen des Baumes, also:

M=5\cdot 4 \cdot 3 = \frac{5!}{(5-3)!}

Oder allgemein

\boxed{M=\frac{n!}{(n-k)!}}

Ohne Zurücklegen, Reihenfolge unwichtig

Auf wieviel Arten können Wörter 11100 gebildet werden, wobei 1=ziehe Buchstaben, 0=ziehe Buchstaben nicht. Also gibt es

M=\left(\begin{array}{cc} 5\\ 3\end{array}\right)

Möglichkeiten. Oder allgmein

\boxed{M=\left(\begin{array}{cc} n\\ k\end{array}\right)}

Mit Zurücklegen, Reihenfolge wichtig

Die ersten $3$ Generationen des Baumes, wobei jede Generation $5$ Äste besitzt, also

M=5\cdot5 \cdot 5 = 5^3

Oder allgemein

\boxed{M=n^k}

Mit Zurücklegen, Reihenfolge unwichtig

Es gilt die Formel

\boxed{M=\left(\begin{array}{cc} n+k-1\\ k\end{array}\right)}

(ohne Beweis).

Exercise 1

Aufgaben

F1

Wie viele dreistellige Zahlen gibt es, die man aus den Ziffern

$7$ , $8$ und $9$ bilden kann, wenn gleiche Ziffern erlaubt in der Zahl erlaubt sind.
$7$ , $8$ und $9$ bilden kann, wenn jede Ziffer nur einmal auftreten darf.

F2

Wie viele verschiedene Möglichkeiten gibt es für einen vierstellige Handy-PIN?

wie viele Stunden müsste man maximal ausprobieren, um den richtigen Code zu finden? Nimm an, du brauchst 5 Sekunden, um einen PIN einzugeben.
Um welchen Faktor erhöht sich diese Zeit, wenn wir einen 6-stelligen Handy-PIN haben, und $6$ Sekunden brauchen, um einen PIN einzugeben?

F3

5 Äpfel sollen an 3 Kinder verteilt werden. Da die Kinder kein Messer bei sich haben, können nur ganze Äpfel verteilt werden. Auf wie viele Arten ist das möglich?

F4

Lotto-Spiel. Wie viele Möglichkeiten gibt es, einen Lottoschein auszufüllen (aus den Zahlen $1,2,...,49$ müssen 6 Zahlen angekreuzt werden)?

F5

Zum Ausklang von Judits Geburtstagsfeier wird Eis angeboten. Es gibt sechs Sorten: Erdbeere, Himbeere, Schokolade, Vanille, Zitrone, Apfel.

Jedes Kind muss sich drei Kugeln unterschiedlicher Sorten aussuchen. Wie viele Glace-Kombinationen sind möglich?
Jedes Kind muss sich drei Kugeln aussuchen (gleiche Sorten erlaubt). Wie viele Glace-Kombinationen sind möglich?

F6

In einem Fach wird ein Hausheft und ein Schulheft geführt. Heftumschläge gibt es in 7 verschiedenen Farben. Leider hat der Lehrer vergessen zu sagen, welche Farben für die Umschläge verwendet werden sollen. Wie viele Möglichkeiten gibt es, wenn

Haus- und Schulheft immer verschiedenfarbig eingebunden werden sollen oder
die Hefte auch in der gleichen Farbe eingebunden werden können?

F7

In einem Topf hat es 6 Karten mit den Zahlen $2,3,5,6,7,9$ .

Wie viele dreistellige Karten lassen sich mit den Karten legen?
Wie viele sind gerade?
Wie viele sind kleiner als $400$ ?
Wie viele sind teilbar durch $5$ ?
Wie viele sind grösser als $653$ ?

F8

In einem Schachturnier mit $10$ Teilnehmern spielt jeder gegen jeden. Wie viele Partien gibt es?

F9

$4$ faire und identische Würfel werden geworfen.

Wie viele verschiedene 4-stellige Zahlen können so geworfen werden?
Wie gross ist die Wahrscheinlichkeit, eine Zahl zu werfen, in der alle Ziffern verschieden sind?
Wie gross ist die Wahrscheinlichkeit, eine Zahl zu werfen, in der mindestens zwei Ziffern gleich sind?

F10: Das Geburtstagsproblem

Am ersten Schultag sitzen in einer Klasse $25$ SchülerInnen. Die Lehrperson kennt die Geburtsdaten der SchülerInnen nicht und bietet folgende Wette an: "Wetten, dass zumindest zwei von euch am selben Tag Geburtstag feiern?" Die SchülerInnen wetten dagegen. Wer hat mehr Aussicht, die Wette zu gewinnen?

Um diese Frage entscheiden zu können, muss die Wahrscheinlichkeit, dass zumindest zwei SchülerInnen am selben Tag des Jahres Geburtstag feiern, berechnet werden. Der Einfachheit halber können zwei Idealisierungen gemacht werden:

Schalttage werden ignoriert, d.h. das Jahr wird mit 365 Tagen angenommen.
Es wird angenommen, dass alle Geburtstermine gleich wahrscheinlich und voneinander unabhängig sind (d.h. also etwa, dass keine Zwillinge anwesend sind).

Tip: Überlege dir, ob dies ein Laplace Experiment ist. Berechne dann zuerst die Wahrscheinlichkeit, dass alle 25 Personen in der Klasse an verschiedenen Tagen Geburtstag haben.

Show

Lösungen

A1

Im Korb sind die Zahlen $1, 2, 3$ .

Reihenfolge wichtig, mit Zurücklegen: $3^3=\underline{27}$
Reihenfolge wichtig, ohne Zurücklegen: $\frac{3!}{(3-3)!}=3!=\underline{6}$ .

A2

Im Korb sind die Zahlen 0, 1, ..., 10. Reihefolge wichtig, mit Zurücklegen, da eine Nummer ja mehrmals eingetippt werden kann.

Es gibt $10^4=10\,000$ Möglichkeiten. Also insgesamt $50\,000$ Sekunden, was $\frac{50\,000}{60\cdot 60}=\underline{14}$ Stunden.
Es gibt $10^6=1\,000\,000$ Möglichkeiten. Also insgesamt $6\,000\,000$ Sekunden, was $\frac{6\,000\,000}{60\cdot 60}=1\,667$ Stunden. Also $\underline{119}$ -mal länger.

A3

Kinder 1, 2, 3 im Korb, $5$ -mal ziehen mit Zurücklegen (um $5$ Äpfel zu vergeben) und Reihenfolge ist unwichtig (da es keine Rolle spielt, wer welchen Apfel bekommt).

Die Anzahl Möglichkeiten ist also $\left(\begin{array}{c} 5+3-1\\ 3\end{array}\right)=\left(\begin{array}{c}7\\ 3\end{array}\right)=\underline{21}$

A4

Ziehe 6 Zahlen aus den 49 Zahlen. Die Reihenfolge ist unwichtig, da es nicht darauf ankommt, welche Zahl zuerst angekreuzt wurde. Zurücklegen ist nicht möglich, da eine Zahl nicht zweimal angekreuzt werden kann. Es gibt also $\left(\begin{array}{c} 49\\ 6\end{array}\right)=13\,983\,816$ Möglichkeiten. Die Wahrscheinlichkeit, dass genau diese Kombination gezogen wird

A5

Glacesorten im Topf, $3$ -mal ziehen, Reihenfolge unwichtig (da es nicht darauf ankommt, welche Sorte zuerst gezogen wird).

Da es verschiedene Sorten sein müssen, ist zurücklegen nicht möglich. Also $\left(\begin{array}{c} 6\\ 3\end{array}\right)=\underline{20}$ mögliche Kombinationen.
Da auch gleiche Sorten erlaubt sind, ist zurücklegen möglich. Also $\left(\begin{array}{c} 6+3-1\\ 3\end{array}\right)=\left(\begin{array}{c}8\\ 3\end{array}\right)=\underline{56}$ mögliche Kombinationen.

A6

7 Farben im Topf, zweimal ziehen (erste Ziehung für Fachheft, 2. Ziehung für Schulheft). Reihenfolge ist also wichtig.

Da verschiedenfarbig, ist Zurücklegen nicht gestattet, also gibt es $\frac{7!}{(7-2)!}=42$ Farbkombinationen von Fachheft-Schulheft.
Da Hefte gleiche Farbe haben können, ist Zurücklegen gestattet. Es gibt also $7^2=49$ Farbkombinationen von Fachheft-Schulheft.

A7

Zahlen $2,3,5,6,7,9$ .

Reihenfolge wichtig, ohne zurücklegen: $\frac{6!}{(6-3)!}=120$
Zahl muss mit $2$ oder $6$ enden. Also ziehe diese Karten, und dann noch $2$ von den übrigen Karten: Anzahl Zahlen **2 ist also $\frac{5!}{(5-2)!}=5\cdot 4=20$ (Baum), Anzahl Zahlen **6 ist $\frac{5!}{(5-2)!}=5\cdot 4 =20$ , insgesamt also $\underline{40}$ Zahlen.
Anzahl Zahlen der Form 2**, 3**, also ebenfalls $\underline{40}$ .
Alle Zahlen der Form **5 sind durch $5$ teilbar, also $\underline{20}$ Zahlen.
Alle Zahlen der Form $655, 657, 659$ , 67*, 69*, 7**, 9** sind grösser als $653$ , also insgesamt $3+4+4+20+20=\underline{50}$ Zahlen.

A8

$10$ Personen im Topf, zwei ziehen ohne zurücklegen, Reihenfolge unwichtig: $\left(\begin{array}{c} 10\\ 2\end{array}\right)=\frac{10\cdot 9}{2}=\underline{45}$

A9

Die möglichen Ziffern sind $1,2,3,4,5,6$ (im Topf). Es wird $4$ -mal gezogen. Mit Zurücklegen, Reihenfolge wichtig, also $6^{4}=\underline{1296}$ mögliche Zahlen.
Laplace experiment, daher

p(E)=\frac{\vert E\vert}{\vert S\vert}

wobei

\vert S\vert =6^{4}=1296

die Anzahl möglichen Ausgänge sind. $E$ ist das Ereignis "alle $4$ Ziffern verschieden". Das heisst, Wiederholungen sind nicht erlaubt, und somit ist

\vert E\vert = \frac{6!}{(6-4)!}=6\cdot 5\cdot 4\cdot 3=360

Es ist somit $p=\frac{360}{1296} = \underline{0.2\overline{7}}$.

3. Es sei $\vert F\vert$ die Anzahl möglichen Zahlen, welche mindestens zwei gleiche Ziffern besitzen. Dies ist gerade

\vert F\vert =\vert S\vert - \vert E\vert = 1296-360=936

Es ist also

p(F)=\frac{\vert F\vert}{\vert S\vert}=\frac{936}{1296}=\underline{0.7\overline{2}}

A10

Im Topf sind 365 Tage. Wir betrachten das Zufallsexperiment "25-mal ziehen mit Zurücklegen", wobei die erste gezogene Zahl dann der Geburtstag für SchülerIn $1$ ist, die zweite gezogene Zahl der Geburtstag für SchülerIn $2$ , usw. Ein typischer Ausgang des Experiments ist also zum Beispiel "1, 30, 50, 2, 301, ..., 27".

Da jeder Geburstag gleichwahrscheinlich ist, ist dies ein Laplace Experiment, mit

p(E)=\frac{\vert E\vert}{\vert S\vert}

wobei $\vert S\vert$ die Anzahl möglichen Ausgänge sind, und $\vert E\vert$ die Anzahl Ausgänge mit mindestens zwei gleichen Tagen. Da die Reihenfolge wichtig ist, haben wir

\vert S\vert = 365^{25}

und

\vert E\vert = \vert S\vert -\vert F\vert =365^{25}-\frac{365!}{(365-25)!}=\frac{365!}{340!}

wobei $F$ die Anzahl Möglichkeiten sind, in der die Klasse alle verschiedene Geburtstage haben (siehe auch Aufgabe 9).

Es ist also

\begin{array}{lll} p(E) &=&\frac{\vert S \vert -\vert F\vert}{\vert S\vert}\\ &=& \frac{\vert S\vert}{\vert S\vert}-\frac{\vert F\vert}{\vert S\vert}\\ &=& 1-\frac{\vert F\vert}{\vert S\vert}\\ &=& 1- \frac{365\cdot ...\cdot 341}{365\cdot ... \cdot 365}\\ &=& 1- \frac{365}{365}\cdot\frac{364}{365}\cdot ... \cdot \frac{341}{365}\\ &=& \underline{0.569} \end{array}