1.4 Kombinatorik: Die Kunst des Abzählens
1.4 Kombinatorik: Die Kunst des Abzählens
Natürliche Zahlen und das Prinzip der Vollständigen Induktion spielen eine entscheidende Rolle, wenn es darum geht, Dinge, Möglichkeiten, Kombinationen etc. abzuzählen.
Das Café Dreistein bietet auf seiner Karte fünf verschiedene Kaffeesorten (Americano, Latte, Caribbean Special, Cappuccino und Espresso), die mit sieben verschieden "‘flavours"’ (Sirup) aromatisiert werden können und wahlweise mit oder ohne Milchschaum erhältlich sind.
Wieviele "‘Kaffee-Kreationen"’ sind so möglich?
Jede Kaffeesorte lässt sich mit jedem Sirup kombinieren
\(\Rightarrow \) \(5\cdot 7 =35\) Kaffee-Sirup-Kombinationen
Jede
Kaffee-Sirup-Kombination kann man mit oder ohne Milchschaum genießen.
\(\Rightarrow \) es gibt \(35\cdot 2 =70\) Kaffeekreationen
Prof.Dr. A.B.Wechslung geht jeden Tag ins Café Dreistein und trinkt eine Tasse Kaffee. Er möchte an jedem Tag der Woche einen anderen der sieben "‘flavours"’ wählen. Wieviele Möglichkeiten hat er, sich einen solchen Wochen-Sirupplan zusammenzustellen?
Siebenmaliges Auswählen ohne Zurücklegen = keine Wiederholung erlaubt
Am Montag hat er noch die volle Auswahl \(\to\) 7 Möglichkeiten
Am Dienstag bleiben noch 6 Varianten übrig \(\rightarrow \) \(7\cdot 6\) Kombinationen
Am Mittwoch sind noch 5 Varianten übrig \(\rightarrow \) \(7\cdot 6\cdot 5\) Kombinationen
Am Samstag sind nur noch 2 Varianten übrig \(\rightarrow \) \(7\cdot 6\cdot \ldots \cdot 2\) Kombinationen
Am Sonntag hat er gar keine Auswahl mehr! \(\rightarrow \) \(7\cdot 6\cdot \ldots \cdot 1\) Möglichkeiten
Insgesamt hat er also \(7\cdot 6\cdot 5\cdot 4\cdot3\cdot 2\cdot1=5040\) Möglichkeiten.
Wir können dieses Problem auch auf eine andere Weise betrachten. Prof. Wechslung könnte schon am Sonntag entscheiden, welchen Sirup er in der kommenden Woche an welchem Wochentag trinken möchte. Es geht also darum abzuzählen, auf wieviele verschiedene Arten er die sieben flavours anordnen kann.
Etwas allgemeiner betrachten wir daher das Problem, auf wie viele verschiedene Arten man n Objekte in eine Reihenfolge bringen kann. Da man jedes Objekt (in Gedanken…) mit einer Nummer versehen könnte, ist das genau dasselbe wie die Anzahl verschiedener Möglichkeiten, die Zahlen 1,2,3,...,n anzuordnen.
Es gibt
\(1 \cdot 2 \cdot 3 \cdot \ldots\cdot(n-1)\cdot n=n! \) ("n Fakultät")
Möglichkeiten, die Zahlen \(1,2,3,\ldots ,n\) anzuordnen, oder anders ausgedrückt: Die Anzahl der Permutationen von \(\{ 1,2,\ldots ,n\} \) ist \(n!\).
Diese Behauptung begründen wir auf zwei verschiedene Arten.
1.Begründung: So wie oben
Es gibt n Möglichkeiten, die erste Zahl auszuwählen,
dann bleiben noch n-1 Möglichkeiten, die zweite Zahl auszuwählen,
noch n-2 Möglichkeiten, die dritte Zahl auszuwählen,
\(\vdots \qquad \vdots \qquad \vdots \)
noch \(2\) Möglichkeiten, die (n-1)-te Zahl auszuwählen und schließlich
und nur noch \(1\) Möglichkeit, die letzte Zahl auszuwählen.
Insgesamt sind das \(n\cdot (n-1)\cdot (n-2) \cdot \; \ldots \; \cdot 2\cdot 1\) Möglichkeiten.
2.Begründung: Mit Vollständiger Induktion
Induktionsanfang (n=1):
Es gibt genau eine Möglichkeit, ein einzelnes Objekt anzuordnen. Da 1!=1 ist, stimmt die Formel für n=1.
Induktionsschritt von n nach n+1:
Wenn unsere Behauptung für die Zahl n stimmt, dann gibt es genau n! Möglichkeiten, n Objekte anzuordnen.
Wir müssen daraus folgern, dass die Behauptung auch für die Zahl n+1 richtig ist. Dabei will man n+1 Objekte anordnen. Man hat also n+1 Möglichkeiten, um das Objekt, das an erster Stelle stehen soll, auszuwählen.
Nach der Wahl des ersten Objekts bleiben noch n Objekte übrig für die n Plätze 2 bis n+1.
Für diese n Objekte gibt es nach der Induktionsvoraussetzung genau n! Anordnungsmöglichkeiten. Da beide Wahlmöglichkeiten unabhängig voneinander sind, gibt es insgesamt \((n+1)\cdot(n!)=(n+1)!\) Anordnungsmöglichkeiten.
Das Restaurant im Baumarkt bietet neuerdings Do-it-yourself-Pizzen an, bei denen man sich den Belag selbst zusammenzustellen kann. Aus 12 verschiedenen Belägen kann man drei auswählen und eine Pizza damit belegen lassen.
Wieviele verschiedene Pizzen stehen damit "im Prinzip" auf der Speisekarte?
Eine andere Formulierung dieser Aufgabe wäre: Auf wieviele Arten kann man aus 12 Pizzabelägen 3 auswählen, wobei es nicht auf die Reihenfolge ankommt?
Dies ist eine spezielle Situation des folgenden allgemeine Problems:
Auf wieviele verschiedene Arten kann man k Objekte (hier eben Pizzabeläge) aus n Objekten auswählen?
Wenn man sich wieder vorstellt, dass die Objekte mit \(1,2,\ldots ,n\) durchnummeriert sind, dann ist dieses Problem dasselbe wie die folgende Aufgabe:
Auf wieviele Arten kann man genau k Zahlen aus der Menge \(\{ 1,2,3,\ldots ,n\} \) auswählen?
Wir überlegen uns wieder, auf wie viele Arten man die k Zahlen nacheinander auswählen kann:
Für die Wahl der ersten Zahl gibt es n Möglichkeiten
Für die zweite Zahl noch n-1 Möglichkeiten
\(\vdots \qquad \vdots \qquad \vdots \)
Für die \(k\)-te Zahl hat man immer noch \(n-k+1\) Möglichkeiten.
Insgesamt sind das \(n \cdot (n-1)\cdot (n-2)\cdot\ldots \cdot (n-k+1)\) Möglichkeiten.
Da aber die Reihenfolge unwichtig ist, werden viele Möglichkeiten mehrfach gezählt. Ob man zuerst die Zahl 7 und dann die 2 wählen oder umgekehrt, soll nicht unterschieden werden.
Dies bedeutet, dass die \(k!\) Permutationen der ausgewählten k Zahlen nur als eine Möglichkeit gezählt werden dürfen. Man muss also noch durch \(k!\) teilen, um die Anzahl der Möglichkeiten ohne Berücksichtigung der Reihenfolge zu erhalten.
\(\left(\!\begin{array}{c}n\\ k\end{array}\!\right)=\displaystyle\frac{n\cdot(n-1)\cdot (n-2){\cdot}\ldots \cdot(n-k+1)}{k!}=\displaystyle\frac{n!}{(n-k)!\;k!}\;\;\;\) ("\( n\) über \(k\)")
\(\left(\begin{array}{c}8\\3\end{array}\right)=\displaystyle\frac{8\cdot 7\cdot 6}{1 \cdot 2 \cdot 3}=72.\)