Permutationen und Fakultät

Permutationen und Fakultät Übung

• Vervollständige den Text zu Permutationen.

  Tipps

  Es gibt $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ Möglichkeiten, um vier verschiedene Bilder nebeneinander an eine Wand zu hängen.

  Wenn eine Menge identische Elemente enthält, dann können wir Anordnungen, in denen diese vertauscht sind, nicht voneinander unterscheiden. Es ergeben sich daher weniger verschiedene Anordnungsmöglichkeiten.

  Lösung

  Eine Permutation ist eine Anordnungsmöglichkeit von Elementen. Das Wort kommt vom lateinischen permutare, was vertauschen bedeutet. Wenn wir also die Anzahl der Permutationen bestimmter Elemente berechnen, dann bestimmen wir, wie viele unterschiedliche Anordnungsmöglichkeiten dieser Elemente wir durch Vertauschung der Elemente erhalten.

  Neben der Anzahl der Elemente müssen wir dabei noch beachten, ob es identische Elemente gibt, die nicht unterscheidbar sind:

  • Eine Menge mit $n$ verschiedenen Elementen besitzt genau $P_{n} = n!$ verschiedene Permutationen.

  Zum Beispiel gibt es $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ Möglichkeiten, um vier verschiedene Bilder in vier Räumen aufzuhängen.

  • Sind unter den $n$ Elementen einer Menge $k$ Elemente identisch, dann besitzt die Menge genau

  $P_{n}^{k} = \dfrac{n!}{k!}$ verschiedene Permutationen. Wenn zum Beispiel unter den vier Bildern zwei gleiche Fotos sind, dann reduziert sich die Anzahl der Möglichkeiten, die Bilder in den vier Räumen anzuordnen zu:
  $\dfrac{4!}{2!} = \dfrac{24}{2} = 12$ verschiedenen Permutationen.

• Bestimme die Anzahl der Permutationen.

  Tipps

  Wenn es Elemente gibt, die wir untereinander nicht unterscheiden können, dann müssen wir die Vertauschungen dieser Elemente aus der Anzahl der Permutationen herausteilen.

  Beispiel: Wir können die Anzahl der Möglichkeiten, drei Blaubeer- und vier Schokoladen-Muffins in einer Reihe aufzustellen, mit der Formel

  ${\dfrac{7!}{3! \cdot 4!}}$ berechnen.

  Es gibt insgesamt $7$ Muffins, davon sind die $3$ Blaubeer- und die $4$ Schokoladen-Muffins untereinander identisch.

  Lösung

  Wir wollen die Anzahl der Permutationen, also der verschiedenen Anordnungsmöglichkeiten, der Marmeladengläser bestimmen. Dazu müssen wir uns jeweils überlegen, wie viele Gläser wir insgesamt anordnen wollen und ob es unter den Gläsern Gruppen gibt, die untereinander identisch sind. Ist dies der Fall, so müssen wir durch die Vertauschungen innerhalb dieser Gruppen teilen. Es gilt:

  • Eine Menge mit $n$ verschiedenen Elementen besitzt $P_{n} = n!$ verschiedene Permutationen.
  • Eine $n$-elementige Menge mit $k$ identischen Elementen hat $P_{n}^{k} = \dfrac{n!}{k!}$ verschiedene Permutationen.
  • Eine $n$-elementige Menge mit mehreren Gruppen identische Elemente $k_1, k_2, ... k_i$ hat

  $P_{n}^{k_1, k_2, .. k_i} = \dfrac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_i!}$ verschiedene Permutationen.

  
  

  Beispiel 1:
  fünf Gläser Marmelade, darunter dreimal Kirschmarmelade
  Es sind insgesamt $5$ Gläser. Darunter sind $3$ identisch.
  $\Rightarrow \quad \dfrac{5!}{3!}$

  Beispiel 2:
  ein Glas Kirschmarmelade, ein Glas Aprikosenmarmelade und ein Glas Kiwimarmelade
  Es sind $3$ verschiedene Gläser.
  $\Rightarrow \quad 3!$

  Beispiel 3:
  drei Gläser Kirschmarmelade, zwei Gläser Aprikosenmarmelade, zwei Gläser Kiwimarmelade und ein Glas Erdbeermarmelade
  Es sind $8$ Gläser. Darunter sind drei Gruppen mit $3$, $2$ und $2$ identischen Gläser.
  $\Rightarrow \quad \dfrac{8!}{3! \cdot 2! \cdot 2!}$

  Beispiel 4:
  fünf Gläser Marmelade
  Es sind fünf verschiedene Gläser.
  $\Rightarrow \quad 5!$

• Entscheide, wer die meisten Möglichkeiten hat, seine Bücher im Regal zu platzieren.

  Tipps

  Überlege dir, wie viele Bücher die Freunde jeweils insgesamt haben.

  Beispiel:

  Wenn Rune $4$ blaue, $3$ grüne und ein weißes Buch hat, dann besitzt er insgesamt $4 + 3 + 1 = 8$ Bücher.

  Es gibt dafür $\dfrac{8!}{4! \cdot 3!} = 280$ Anordnungsmöglichkeiten, da wir die Vertauschungen der gleichfarbigen Bücher aus den $8!$ Anordnungen von $8$ Büchern herausrechnen müssen.

  Lösung

  Wenn Anni und ihre Freunde Bücher in einem Regal aufstellen, dann gibt es zunächst für $n$ Bücher $n!$ Anordnungsmöglichkeiten. Wenn es dabei $k$ Bücher gibt, die wir untereinander nicht unterscheiden können, dann müssen wir die Möglichkeiten herausrechnen, bei denen nur diese Exemplare vertauscht sind. Dazu teilen wir durch die möglichen Vertauschungen und erhalten: $\dfrac{n!}{k!}$ mögliche Anordnungen. Gibt es mehrere Gruppen solcher identischen Bücher $k_1, k_2, ... k_i$, dann müssen wir für jede dieser Gruppen dividieren:

  $\dfrac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_i!}$.

  Betrachten wir die Büchersammlungen der vier Freunde:

  • Anni hat $15$ grüne und $5$ blaue Bücher. Das sind insgesamt $15 + 5 = 20$ Bücher, für die es:

  $\dfrac{20!}{15! \cdot 5!} = \color{#669900}{15\,504}$ Anordnungsmöglichkeiten gibt.

  • Ben hat $2$ rote, $3$ blaue und $7$ gelbe Bücher. Das sind insgesamt $2 + 3 + 7 = 12$ Bücher, für die es:

  $\dfrac{12!}{2! \cdot 3! \cdot 7!} = \color{#669900}{7920}$ Anordnungsmöglichkeiten gibt.

  • Chen-Lu hat $5$ blaue, $5$ weiße, ein gelbes und ein grünes Buch. Das sind insgesamt $5 + 5 + 1 + 1 = 12$ Bücher, für die es

  $\dfrac{12!}{5! \cdot 5!} = \color{#669900}{33\,264}$ Anordnungsmöglichkeiten gibt.

  • Daja hat $50$ rote Bücher und ein weißes Buch. Das sind insgesamt $50 + 1 = 51$ Bücher, für die es

  $\dfrac{51!}{50!} = \color{#669900}{51}$ Anordnungsmöglichkeiten gibt.

  
  

  Es gilt:
  $51 \lt 7920 \lt 15\,504 \lt 33\,264$

  Damit hat Chen-Lu die meisten Möglichkeiten ihre Büchersammlung anzuordnen. Danach kommen Anni und Ben. Daja hat die geringste Anzahl an Möglichkeiten, obwohl sie insgesamt die meisten Bücher besitzt. Das liegt daran, dass sich ihre Bücher im Regal größtenteils nicht unterscheiden lassen.

• Untersuche die Anzahl der Anordnungsmöglichkeiten.

  Tipps

  Anni ist nur die Anordnung der Farben wichtig. Die einzelnen Bücher einer Farbe unterscheidet sie dabei nicht.

  Anni hat Bücher in sechs verschiedenen Farben.

  Beispiel:

  Wenn Klaus seine Büchersammlung nach hohen und niedrigen Büchern sortiert, dann hat er nur zwei Möglichkeiten, sie auf dem Regalbrett zu präsentieren: die hohen Bücher rechts und die niedrigen links oder umgekehrt.

  Lösung

  Da Anni ihre Bücher der Farbe nach sortiert in das Regal stellen möchte, müssen wir hier die möglichen Anordnungen der Farben betrachten. Du kannst dir das so vorstellen, dass die Bücher einer Farbe einen festen Block bilden und wir nun diese Blöcke nebeneinander stellen.
  Anni hat Bücher in insgesamt sechs Farben: gelb, grün, blau, violett, rot und orange. Das macht insgesamt $6! = \color{#669900}{\mathbf{720}}$ Anordnungsmöglichkeiten. Da wir die Bücher einer Farbe untereinander nicht unterscheiden, müssen wir deren Vertauschungen nicht weiter berücksichtigen.

  Falsche Antworten:

  • $15!$ ist die Anzahl der Möglichkeiten, $15$ einzeln unterscheidbare Bücher anzuordnen.
  • $6$ ist die Anzahl der verschiedenen Farben, in denen Anni Bücher hat. Diese kann sie auf $6!$ unterschiedliche Weisen bei sich im Regal anordnen.
  • $\dfrac{15!}{3! \cdot 3! \cdot 3! \cdot 4! \cdot 2! \cdot 2!} = 63\,063\,000$, also ca. $63~\text{Millionen}$ Anordnungsmöglichkeiten gäbe es, wenn wir nur die Anordnung der Farben von Annis Büchern betrachten. Dabei ist aber nicht berücksichtigt, dass Bücher derselben Farbe stets nebeneinander stehen sollen.

• Gib die Werte für die Fakultät an.

  Tipps

  Es gilt:

  $n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1$

  Beispiel:

  $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

  Lösung

  Bei der Berechnung von Anordnungsmöglichkeiten von Elementen, den Permutationen, tauchen häufig Terme der Form $n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1$ auf. Diese können wir mit der sogenannten Fakultät mathematisch auch kürzer schreiben. Es gilt für $n!$, sprich "$n$ Fakultät":
  $n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1$

  Das Symbol des Ausrufezeichens findest du wahrscheinlich auch auf deinem Taschenrechner. Damit ist auch die Berechnung der Werte schneller.

  $\begin{array}{c|l|r} \mathbf{Fakultät} & \text{Rechnung} & \mathbf{Ergebnis} \\ \hline 2! & 2 \cdot 1 & 2 \\ \hline 3! & 3 \cdot 2 \cdot 1 & 6 \\ \hline 5! & 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 & 120 \\ \hline 7! & 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 & 5040 \\ \hline 10! & 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 & 3\,628\,800 \\ \end{array}$

• Berechne, wie viele Permutationen es gibt.

  Tipps

  Überlege dir zunächst, was durch die Bedingungen festgelegt wird und was noch variabel ist.

  Beispiel:

  Die roten Kochbücher stehen nebeneinander.
  Die drei roten Bücher können nur als Block verschoben werden. Für sie gibt es daher $5$ mögliche Positionen im Regal. Es verbleiben das braune, das weiße und die zwei blauen Bücher, die an den vier freien Plätzen angeordnet werden: $\dfrac{4!}{2!} = 12$

  Insgesamt gibt es daher $5 \cdot 12 = 60$ Anordnungsmöglichkeiten.

  Lösung

  Wenn es zusätzliche Bedingungen für die Anordnung von Elementen, wie hier Frau Vivils Kochbüchern, gibt, dann müssen wir unsere Formel entsprechend an die Situation anpassen.

  Es gilt, die folgenden Kochbücher im Regal zu platzieren:

  • ein braunes Buch
  • ein weißes Buch
  • drei rote Bücher
  • zwei blaue Bücher

  
  

  Beispiel 1:
  Die blauen Kochbücher stehen ganz rechts.
  Die Position der beiden blauen Kochbücher ist hier fest vorgegeben. Wir müssen uns also nur darum kümmern, wie die verbleibenden $5$ Kochbücher angeordnet werden können.
  Es gibt $\dfrac{5!}{3!} = \color{#669900}{\mathbf{20}}$ Anordnungsmöglichkeiten.

  Beispiel 2:
  Das braune und das weiße Kochbuch stehen nebeneinander.
  Das braune und das weiße Kochbuch können nur zusammen als Block verschoben werden. Für diesen Block aus zwei Büchern gibt es $6$ mögliche Positionen, wobei die beiden Bücher stets vertauscht werden können: $6 \cdot 2 = 12$ mögliche Anordnungen.
  Die restlichen fünf Kochbücher werden jeweils auf den freien Plätzen im Regal platziert. Dafür gibt es: $\dfrac{5!}{2! \cdot 3!} = 10$ Möglichkeiten.
  Insgesamt erhalten wir somit:
  $12 \cdot 10 = \color{#669900}{\mathbf{120}}$ mögliche Anordnungen.

  Beispiel 3:
  Die beiden äußeren Bücher haben dieselbe Farbe.
  Es gibt hier zwei Varianten: Die beiden äußeren Bücher sind rot oder sie sind blau, da es je nur ein braunes und ein weißes Buch gibt, können diese nicht außen stehen. Betrachten wir also die beiden Fälle:

  • Die beiden äußeren Bücher sind blau:

  Es verbleiben das braune, das weiße und drei rote Bücher für die fünf Plätze in der Mitte: $\dfrac{5!}{3!} = 20$ mögliche Anordnungen.

  • Die beiden äußeren Bücher sind rot:

  Es verbleiben das braune, das weiße, ein rotes und zwei blaue Bücher für die fünf Plätze in der Mitte: $\dfrac{5!}{2!} = 60$ mögliche Anordnungen.

  Zusammen ergeben sich $20 + 60 = \color{#669900}{\mathbf{80}}$ Anordnungsmöglichkeiten.