Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge – Einführung

Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge – Einführung Übung

• Bestimme die Anzahl möglicher Kombinationen.

  Tipps

  Jede Chilisorte soll pro Gericht nur einmal vorkommen. Zudem macht es keinen Unterschied, welche Chilisorte zuerst in den Topf gelegt wird – das Gericht ist das gleiche.

  Du rechnest „Anzahl aller Elemente“ über „Anzahl gezogener Elemente“.

  Die Fakultät $n!$ einer natürlichen Zahl $n$ ist das Produkt aller Zahlen von $1$ bis $n$. Es gilt also:

  $n!=1\cdot 2\cdot 3\cdot\ ...\ \cdot n$

  Lösung

  Da jede Chilisorte pro Gericht nur einmal vorkommen soll und es keinen Unterschied macht, welche Chilisorte zuerst in den Topf gelegt wird, handelt es sich hierbei um den Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“. Die Anzahl möglicher Kombinationen wird dann über folgende Beziehung berechnet:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  Dabei setzt sich der Binomialkoeffizient aus diesen Größen zusammen:

  • $n$: Anzahl aller Elemente
  • $k$: Anzahl gezogener Elemente

  Wir rechnen also die „Anzahl aller Elemente“ über der „Anzahl gezogener Elemente“. Für die Zubereitung eines Chilligerichtes werden $3$ unterschiedliche Chilisorten aus insgesamt $10$ unterschiedlichen Sorten verarbeitet. Demnach ist $10$ die Gesamtzahl aller Elemente und $3$ die Anzahl gezogener Elemente.

  Jetzt nimmt man die Werte von Cayennes Reise: $n=10$ und $k=3$. Man setzt sie in den Binomialkoeffizienten ein und erhält folgende Rechnung für die Anzahl möglicher Kombinationen:

  $\binom {10}3=\frac{10!}{3!\cdot\left( 10-3\right)!}=\frac{10!}{3!\cdot 7!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot \not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=\frac{720}{6}=120$

  Bis Cayenne den „Scharfen Pfad der Erleuchtung“ erklommen hat, dauert es demnach $120$ Tage.

• Berechne die Anzahl der möglichen Chili-Kombinationen.

  Tipps

  Hier hast du wieder den Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“. Die Anzahl möglicher Kombinationen erhältst du über die folgende Beziehung:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  In dem Binomialkoeffizienten $\binom nk$ ist $n$ die Gesamtzahl aller Elemente und $k$ die Anzahl gezogener Elemente.

  Lösung

  Wir möchten wissen, wie lange Cayennes „Scharfer Pfad der Erleuchtung“ gedauert hätte, wenn er jeden Tag ein Chiligericht mit genau $4$ unterschiedlichen Chilisorten aus insgesamt $15$ verschiedenen Chilisorten bekommen hätte.

  Dabei betrachten wir den Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“. Die Anzahl möglicher Kombinationen erhalten wir dann über die folgende Beziehung:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  Die Größen $n$ und $k$ sind dabei so definiert:

  • $n$: Gesamtzahl aller Elemente
  • $k$: Anzahl gezogener Elemente

  Demnach ist hier $n=15$ und $k=4$.

  Die Rechnung für die Anzahl möglicher Chili-Kombinationen, also die Dauer des „Scharfen Pfades der Erleuchtung“, lautet wie folgt:

  $d=\binom {15}4=\frac{15!}{4!\cdot\left( 15-4\right)!}=\frac{15!}{4!\cdot\left( 11\right)!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot \not 11\cdot 12\cdot 13\cdot 14\cdot 15}{1\cdot 2\cdot 3\cdot 4\cdot \not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot \not 11}=\frac{12\cdot 13\cdot 14\cdot 15}{1\cdot 2\cdot 3\cdot 4}=1 365$.

  Cayennes Selbstfindungstrip hätte also 1 365 Tage gedauert. Oh je!

• Bestimme den Binomialkoeffizienten $n$ über $k$ für die gegebenen Werte.

  Tipps

  Der Binomialkoeffizient ist wie folgt definiert:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  Die Fakultät einer natürlichen Zahl $n$ ist das Produkt aller Zahlen von $1$ bis $n$. Es gilt also:

  $n!=1\cdot 2\cdot 3\cdot\ ...\cdot n$

  Schaue dir die Rechnung für das Beispiel $n=4$ und $k=2$ an:

  $\binom 42=\frac{4!}{2!\cdot\left( 4-2\right)!}=\frac{4!}{2!\cdot 2!}=\frac{\not 1\cdot \not 2\cdot 3\cdot 4}{\not 1\cdot \not 2\cdot 1\cdot 2}=\frac{3\cdot 4}{1\cdot 2}=6$

  Lösung

  Bei dem Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“ wird die Anzahl möglicher Kombinationen über den Binomialkoeffizienten berechnet. Dieser ist wie folgt definiert:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  Dabei ist $n$ die Gesamtzahl aller Elemente und $k$ die Anzahl gezogener Elemente. Die Fakultät einer natürlichen Zahl $n$ ist das Produkt aller Zahlen von $1$ bis $n$. Es gilt also:

  $n!=1\cdot 2\cdot 3\cdot\ ...\cdot n$

  Mit dieser Formel können wir nun die Binomialkoeffizienten der gegebenen Werte bestimmen:

  Beispiel 1: $n=8;\ k=2$

  $\binom 82=\frac{8!}{2!\cdot\left( 8-2\right)!}=\frac{8!}{2!\cdot 6!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot 7\cdot 8}{1\cdot 2\cdot \not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6}=\frac{7\cdot 8}{1\cdot 2}=28$

  Beispiel 2: $n=20;\ k=18$

  $\binom {20}{18}=\frac{20!}{18!\cdot\left( 20-18\right)!}=\frac{20!}{18!\cdot 2!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot \not 11\cdot \not 12\cdot \not 13\cdot \not 14\cdot \not 15\cdot \not 16\cdot \not 17\cdot \not 18\cdot 19\cdot 20}{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot \not 11\cdot \not 12\cdot \not 13\cdot \not 14\cdot \not 15\cdot \not 16\cdot \not 17\cdot \not 18\cdot 1\cdot 2}=\frac{19\cdot 20}{1\cdot 2}=190$

  Beispiel 3: $n=2;\ k=1$

  $\binom {2}{1}=\frac{2!}{1!\cdot\left( 2-1\right)!}=\frac{2!}{1!\cdot 1!}=\frac{\not 1\cdot 2}{\not 1\cdot 1}=\frac{2}{1}=2$

  Beispiel 4: $n=13;\ k=10$

  $\binom {13}{10}=\frac{13!}{10!\cdot\left( 13-10\right)!}=\frac{13!}{10!\cdot 3!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot 11\cdot 12\cdot 13}{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot \not 9\cdot \not 10\cdot 1\cdot 2\cdot 3}=\frac{11\cdot 12\cdot 13}{1\cdot 2\cdot 3}=286$

• Ermittle die Anzahl möglicher Kombinationen einer Vierergruppe.

  Tipps

  Bei der Zusammenstellung der Vierergruppe ist es egal, in welcher Reihenfolge die Personen gezogen werden. Außerdem kann natürlich jede Person nur einmal gelost werden.

  Der Binomialkoeffizient lässt sich wie folgt bestimmen:

  $\binom{n}{k}=\frac{n!}{k!\cdot\left(n-k\right)!}$

  Lösung

  Von den $12$ Mitgliedern eines Nachhilfevereins sollen $4$ Mitglieder gelost werden. Bei der Zusammenstellung der Vierergruppe kann jede Person nur einmal gelost werden und es wird keine Reihenfolge beachtet. Also handelt es sich hierbei um den Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“.

  Wie verwenden deshalb für die Berechnung der Anzahl möglicher Kombinationen den Binomialkoeffizienten $n$ über $k$. Für diesen gilt:

  $\binom{n}{k}=\frac{n!}{k!\cdot\left(n-k\right)!}$

  In unserem Beispiel ist $n=12$ die Gesamtzahl aller Mitglieder und $k=4$ die Anzahl ausgeloster Mitglieder. Es ergibt sich folgende Rechnung:

  $\binom{12}{4}=\frac{12!}{4!\cdot 8!}=\frac{\not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8\cdot 9\cdot 10\cdot 11\cdot 12}{1\cdot 2\cdot 3\cdot 4\cdot \not 1\cdot \not 2\cdot \not 3\cdot \not 4\cdot \not 5\cdot \not 6\cdot \not 7\cdot \not 8}=\frac{9\cdot 10\cdot 11\cdot 12}{1\cdot 2\cdot 3\cdot 4}=495$.

  Es gibt also $495$ verschiedene Möglichkeiten, eine Vierergruppe zusammenzustellen.

• Beschrifte die Formel für die Berechnung der Anzahl möglicher Kombinationen.

  Tipps

  Eine Potenz ist die abgekürzte Schreibweise der mehrfachen Multiplikation eines Faktors mit sich selbst. Es gilt:

  $a^n=\underbrace{a\cdot a\cdot\ ...\ \cdot a}_{n\text{-mal}}$

  Die Fakultät $n!$ einer natürlichen Zahl $n$ ist das Produkt aller Zahlen von $1$ bis $n$. Es gilt also:

  $n!=1\cdot 2\cdot 3\cdot\ ...\ \cdot n$

  Lösung

  Betrachten wir ein Beispiel zum Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“, berechnen wir die Anzahl möglicher Kombinationen über die folgende Beziehung:

  $\binom nk=\frac{n!}{k!\cdot\left( n-k\right)!}$

  Diese Beziehung setzt sich so zusammen:

  • $\binom{n}{k}$: Binomialkoeffizient
  • $n$: Gesamtzahl aller Elemente
  • $k$: Anzahl gezogener Elemente
  • $!$: Fakultät

  Der Binomialkoeffizient $\binom nk$ liefert die Anzahl möglicher Kombinationen für den Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“.

  Die Fakultät $n!$ einer natürlichen Zahl $n$ ist das Produkt aller Zahlen von $1$ bis $n$. Es gilt also:

  $n!=1\cdot 2\cdot 3\cdot\ ...\ \cdot n$

• Arbeite die Beispiele zum Fall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“ heraus.

  Tipps

  Die Belegung des Parkplatzes ändert sich bereits, wenn man die Plätze von zwei Autos tauscht.

  Das Dreieck $\measuredangle 123$ sieht genauso aus wie das Dreieck $\measuredangle 312$.

  Lösung

  Wir betrachten nun die gegebenen Beispiele gemeinsam:

  Beispiel 1: Parkplatz-Problem

  Hat ein Auto auf einem Platz geparkt, so kann dieses Auto bei derselben Parkplatzbelegung nicht an einem weiteren Platz stehen. Also betrachten wir den Fall „Ziehen ohne Zurücklegen“. Allerdings ändert sich die Belegung des Parkplatzes bereits durch das Vertauschen der Plätze zweier Autos, die Reihenfolge ist also wichtig. Somit liegt der Kombinatorikfall „Ziehen ohne Zurücklegen und mit Beachtung der Reihenfolge“ vor.

  Beispiel 2: Würfel-Problem

  Da bei jedem Wurf die Zahlen $1$ bis $6$ gewürfelt werden können, handelt es sich hierbei um den Fall „Ziehen mit Zurücklegen“. Zudem spielt die Reihenfolge der gewürfelten Zahlen eine Rolle, denn die dreistellige Zahl $123$ entspricht nicht der dreistelligen Zahl $312$. Also haben wir hier den Kombinatorikfall „Ziehen mit Zurücklegen und mit Beachtung der Reihenfolge“.

  Beispiel 3: Dreieck-Problem

  Da man für die Konstruktion eines Dreiecks drei unterschiedliche Punkte verbindet, wird für jedes Dreieck jeder Punkt genau einmal verwendet. Wir betrachten also das „Ziehen ohne Zurücklegen“. Zudem macht es keinen Unterschied, ob wir zuerst die $1$ mit der $2$, dann die $2$ mit der $3$, dann die $3$ mit der $1$ verbinden oder ob wir zuerst die $2$ mit der $1$, dann die $1$ mit der $3$, dann die $3$ mit der $2$ verbinden. Das resultierende Dreieck ist gleich. Es ist also der gesuchte Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“.

  Beispiel 4: Passwort-Problem

  Bei einem sechsstelligen Passwort aus Zahlen können wir eine Zahl auch mehrmals verwenden, was dem „Ziehen mit Zurücklegen“ entspricht. Zudem ist die Reihenfolge sehr wichtig, denn das Passwort $123456$ entspricht nicht dem Passwort $654321$. Es ist also der Kombinatorikfall „Ziehen mit Zurücklegen und mit Beachtung der Reihenfolge“.

  Beispiel 5: Kaugummi-Problem

  Sobald Lukas an dem Automaten dreht, fällt einer der $9$ Kaugummis heraus. Da im Automaten jede Farbe genau einmal liegt, kann diese Farbe kein weiteres Mal vorkommen. Wir haben also den Fall „Ziehen ohne Zurücklegen“. Außerdem interessiert bei der Farbkombination der $3$ Kaugummis nicht die Reihenfolge der Farben. Es ist also der Kombinatorikfall „Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge“.