Kombinatorik – Die Kunst des Zählens

Was ist Kombinatorik?

Wer Wahrscheinlichkeiten berechnen will, muss zählen können: Wie viele Dinge einer bestimmten Art gibt es? Wie viele davon haben eine geforderte Eigenschaft? Manchmal genügt es, einfach durchzuzählen. Zum Beispiel: Wie viele Primzahlen zwischen 1 und 20 gibt es? Wir schreiben sie alle auf und achten darauf, keine zu vergessen:

2, 3, 5, 7, 11, 13, 17, 19

Wenn wir eine Primzahl zwischen 1 und 20 auswählen, gibt es dafür also 8 Möglichkeiten.

Nächstes Beispiel: Eine Münze mit den Seiten „Wappen (W)“ und „Zahl (Z)“ wird geworfen. Hier ist die Anzahl der Möglichkeiten (2) schon durch die Aufgabenstellung gegeben.

Doch wie viele Möglichkeiten gibt es, wenn wir die Münze dreimal werfen? Eine davon ist „WWW“ (dreimal Wappen). Eine andere ist „ZZZ“ (dreimal Zahl). Oder „ZWZ“. Wenn wir sicher sein wollen, dass wir alle Möglichkeiten auflisten, müssen wir sie in einer Reihenfolge auflisten. So eine Reihenfolge könnte sein:

WWW, WWZ, WZW, WZZ, ZWW, ZWZ, ZZW, ZZZ

Die Möglichkeiten sind dabei alphabetisch geordnet. Wir beginnen mit „WWW“ und lassen den letzten Wurf alle Möglichkeiten „W“ und „Z“ durchlaufen:

WWW, WWZ

Nun wechseln wir im vorletzten Wurf auf „Z“ und lassen den letzten Wurf wieder alle Möglichkeiten durchlaufen:

WZW, WZZ

Dann wechseln wir im ersten Wurf auf „Z“ und beginnen danach wieder bei „WW“:

ZWW, ZWZ

Und schließlich die Mitte auf „Z“ wechseln:

ZZW, ZZZ

Übungsaufgabe: Zähle alle Möglichkeiten auf, die sich bei vier Münzwürfen mit „W“ und „Z“ ergeben. Beginne bei „WWWW“ und ende bei „ZZZZ“. Wenn du es richtig machst, findest du 16 Ergebnisse.

Produktregel der Kombinatorik

Oft ist es gar nicht nötig, alle Möglichkeiten aufzulisten, die sich bei der mehrfachen Durchführung ergeben. Manchmal sind es auch viel zu viele, um sie alle hinzuschreiben. Man will dann aber wissen, wie viele Möglichkeiten es gibt. Dabei hilft uns eine einfache Regel, nämlich die Produktregel:

Wenn eine Menge n Elemente hat und eine weitere Menge m Elemente, dann gibt es \(m\cdot n\) Möglichkeiten, ein Element der ersten Menge mit einem Element der zweiten Menge zu kombinieren.

Beispiel dreifacher Münzwurf: Beim ersten Wurf gibt es 2 Möglichkeiten, beim zweiten auch und beim dritten ebenfalls. Für den dreifachen Münzwurf gibt es also insgesamt

\(2\cdot 2\cdot 2= 8\) Möglichkeiten.

Ganz viele Kombinatorik-Fragen kann man mit dieser Regel lösen, auch wenn man die Formeln, die wir gleich entwickeln, nicht zur Hand hat. Man multipliziert einfach die Anzahl Möglichkeiten, die man in jeder Auswahlstufe hat.

Nächstes Beispiel: Ein Würfel (6 Seiten) und ein Tetraeder (4 Seiten) werden nacheinander geworfen. Beim Tetraeder soll die untenliegende Zahl als Wurfergebnis gelten. Dann gibt es \(6\cdot 4=24\) mögliche Zahlenpaare aus Würfel- und Tetraeder-Ergebnis.

Geordnete Stichprobe mit Wiederholung

Nun aber gleich ans Eingemachte. Wir ignorieren zunächst die Überschrift und schauen uns folgende Aufgabe an:

Ein Würfel wird dreimal geworfen und jeweils die Augenzahl notiert. Wie viele Zahlenfolgen können dabei entstehen?

Ein Versuch, bei dem etwas mehrfach durchgeführt wird, heißt mehrstufiges Experiment. Wir schauen uns die Durchführungen einzeln an:

  • Im ersten Versuch gibt es 6 Möglichkeiten – die 6 Augenzahlen.
  • Im zweiten Versuch gibt es auch 6 Möglichkeiten, denn auch die bereits gewürfelte Zahl kann wieder drankommen.
  • Auch im dritten Versuch gibt es 6 Möglichkeiten.

Die Ergebnisse aller drei Versuche können beliebig miteinander kombiniert werden, daher gibt es insgesamt

$$6\cdot 6\cdot 6=6^3$$

mögliche Zahlenfolgen. Allgemein können wir für diesen Fall formulieren:

Aus einer Menge mit n Elementen werden k ausgewählt, und zwar mit Berücksichtigung der Reihenfolge und mit Wiederholung. Dann gibt es nk Auswahlmöglichkeiten.

Mit dieser Formel können wir diese und weitere Aufgaben nun schneller lösen:

Ein Glücksrad mit 6 gleich großen und verschieden farbigen Sektoren wird dreimal gedreht und jeweils die erdrehte Farbe notiert. Wie viele Kombinationen sind möglich? Bei wie vielen davon ist die erste Farbe rot? Dabei gehen wir natürlich davon aus, dass es auch einen roten Sektor gibt.

Zur ersten Frage: Wir erkennen, dass es eine geordnete Stichprobe ist, da die Ergebnisse in der Reihenfolge des Auftretens notiert werden. Und es ist mit Wiederholung, denn alle Farben können bei den weiteren Drehs wieder auftauchen. Es ist n = 6, denn es gibt in jeder Stufe 6 Auswahlmöglichkeiten. Und es ist k = 3, denn es wird dreimal gedreht. Damit gibt es insgesamt 63 mögliche Ergebnisse.

Auch wenn wir die Formel so klar anwenden können wie in diesem Beispiel, sollten wir uns immer daran erinnern, wie sie entstanden ist: nämlich durch Multiplikation der Möglichkeiten in jeder Stufe. Dann können wir die Rechnung an veränderte Aufgabenstellungen anpassen, wie die zweite Frage zeigt:

Wenn die erste Farbe „rot“ sein soll, gibt es in dieser Runde nur eine Möglichkeit. Die weiteren Runden haben dann wieder 6 Ergebnisse, und die Gesamtzahl der Möglichkeiten mit „Erster Dreh rot“ ist:

1 x 6 x 6 = 36

Urnenmodelle

Fakultät

An einem 100m-Lauf nehmen 5 Schüler teil. Wie viele Möglichkeiten des Zieleinlaufs gibt es?

Lösung: Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten noch 4, dann 3, 2, 1, also gibt es insgesamt 5 x 4 x 3 x 2 x 1 Möglichkeiten des Zieleinlaufs. Diese Rechnung, bei der die Zahlen von 1 bis zu einer Zahl n multipliziert werden, kommt sehr oft vor, daher bekommt sie ein eigenes Rechenzeichen. Wir definieren für alle natürlichen Zahlen n:

n! = 1 x 2 x 3 x … x n

und nennen den Term „n Fakultät„. Die Anzahl der möglichen Zieleinläufe mit 5 Teilnehmern ist also kurz 5!.

Geordnete Stichprobe ohne Wiederholung

Am olympischen 100m-Finale nehmen 8 Läufer teil. Wie viele Möglichkeiten der Medaillenvergabe für Gold, Silber und Bronze gibt es?

Wir schauen die Medaillenplätze wieder einzeln an: Für den ersten Platz gibt es 8 Möglichkeiten, für den zweiten noch 7 und für den dritten 6. Also gibt es 8 x 7 x 6 Möglichkeiten der Medaillenvergabe.

Diese Lösungsformel können wir mit Fakultäten schreiben, obwohl die Zahlenfolge nicht bei 1 beginnt:

$$8\cdot 7\cdot 6=\frac{8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{5\cdot 4\cdot 3\cdot 2\cdot 1}=\frac{8!}{5!}$$

Anhand dieser Aufgabe wollen wir eine Formel entwickeln, wie wir solche Aufgaben allgemein lösen können. Es handelt sich um eine geordnete Stichprobe, da die Reihenfolge des Zieleinlaufs entscheidend ist. Es gibt aber keine Wiederholung, denn jeder Läufer kommt nur einmal ins Ziel.

Wenn der Zieleinlauf aller Läufer betrachtet wird, gibt es 8! Möglichkeiten, das haben wir im vorigen Beispiel schon gesehen. Wenn aber nur die ersten drei Plätze entscheidend sind, dann führen die folgenden Zieleinläufe alle zu dem gleichen Ergebnis:

ABC DEFGH
ABC FHDGE
ABC EHGFD

Diese Fälle führen alle zur gleichen Medailllenvergabe und wurden bei den 8! Ergebnissen zu oft aufgeführt. Es gibt 5! Möglichkeiten, die weiteren Plätze mit den Läufern D,E,F,G,H zu besetzen. Also hat die obige Liste mit den Medaillen für A,B,C insgesamt 5! Einträge. Deshalb müssen wir die Gesamtliste mit 8! Einträgen durch 5! teilen und bekommen die Anzahl Möglichkeiten der Medaillenvergabe:

$$\frac{8!}{5!}=\frac{8\cdot 7\cdot 6\cdot\ldots\cdot 1}{5\cdot 4\cdot\ldots\cdot 1}=8\cdot 7\cdot 6$$

Allgemein werden aus n Elementen k ausgewählt und zwar mit Berücksichtigung der Reihenfolge und ohne Wiederholung. Wenn man alle auswählt, gibt es n! Möglichkeiten, dabei ist aber jede Anordnung der k Elemente nicht nur einmal berücksichtigt, sondern so oft, wie man die übrigen n-k Elemente anordnen kann., also (n-k)! Mal. Deshalb lauter die Formel für eine geordnete Stichprobe ohne Wiederholung:

$$\frac{n!}{(n-k)!}$$

Binomialkoeffizient

Ungeordnete Stichprobe ohne Wiederholung

Ungeordnete Stichprobe mit Wiederholung

Zusammenfassung: Kombinatorik-Formeln

Vorlage

\chapter{Kombinatorik}
Bei der Berechnung von Wahrscheinlichkeiten muss man sehr häufig die Mächtigkeit von Mengen berechnen, also zählen, wieviele Elemente sie enthalten. Das haben wir bei den Laplace-Experimenten schon gesehen. Das Teilgebiet, das sich mit dem Abzählen von Mengen beschäftigt, heißt \df{Kombinatorik} und stellt Formeln bereit, mit denen man die Mächtigkeit vieler Mengen berechnen kann. Einige davon stellen wir nun vor. Parallel dazu erklären wir Ausdrücke wie \df{Fakultät} und \df{Binomialkoeffizient}, die dabei helfen, die entstehenden Terme darzustellen.

\section{Produktregel der Kombinatorik}
Ganz viele Problemstellungen der Kombinatorik beruhen auf der folgenden einfachen Regel: Die Menge $A$ habe $m$ Elemente, und die Menge $B$ habe $n$ Elemente. Wenn man jedes Element von $A$ mit jedem Element von $B$ kombiniert, entstehen
$$m\cdot n$$
Paare aus Elementen von $A$ und $B$. Dazu gleich ein Beispiel: Wir würfeln mit einem „`normalen“‚ Würfel mit den Augenzahlen $A={1,2,3,4,5,6}$ und mit einem Tetraeder mit den Augenzahlen $B={1,2,3,4}$. Beim Tetraeder soll die unten liegende Augenzahl das Wurfergebnis sein. Dann gibt es $6\cdot 4=24$ mögliche Paare von Augenzahlen:
$${(1,1),(1,2),(1,3),(1,4),(2,1),\ldots,(2,4),\ldots,(6,1),\ldots,(6,4)}$$
Alle Kombinatorik-Formeln basieren auf der Produktregel, und insbesondere bei geordneten Stichproben kann man sich mit ihr das Ergebnis schnell selbst herleiten, wenn man die auswendig gelernte Formel vergessen hat.

\section{Geordnete Stichprobe mit Wiederholung}

Ein Würfel wird dreimal geworfen. Wie viele Zahlenfolgen können dabei entstehen? Beim ersten Wurf gibt es 6 mögliche Ergebnisse, beim zweiten auch, und beim dritten ebenfalls. Also gibt es nach der Produktregel $6\cdot 6\cdot 6=6^3$ verschiedene Zahlenfolgen.
Allgemein gibt es $k$ Entscheidungen und bei jeder Entscheidung $n$ Auswahlmöglichkeiten, also gibt es insgesamt
$$\underbrace{n\cdot n\cdot…\cdot n}_{k}=n^k$$
mögliche Kombinationen. Die Reihenfolge der Entscheidungen wird berücksichtigt, und die Elemente dürfen sich wiederholen.

\section{Urnenmodelle}
Die Probleme der abzählenden Kombinatorik kommen aus ganz verschiedenen Anwendungsgebieten. Es werden Würfelergebnisse, Buchstaben, Menschen und viele andere Dinge gezählt. Deshalb hat es sich bewährt, diese Anwendungen in ein Modell zu übersetzen. In diesem Modell gibt es keine Würfel, Tetraeder, Menschen oder was man sonst gerade abzählen will. Es gibt stattdessen eine \df{Urne}. Das ist ein Topf, der für jedes Würfelergebnis, jeden auszuwählenden Menschen (oder worum es gerade geht) eine Kugel enthält. Die \df{Grundgesamtheit} der Kugeln in der Urne wird mit $n$ bezeichnet.
Statt eine Person auszuwählen, entnehmen wir der Urne gedanklich eine Kugel und notieren das Ergebnis. Diese Ziehung wiederholen wir $k$ Mal (das ist der \df{Stichprobenumfang}) und berücksichtigen dabei folgende Fragestellungen:
\bes
\item Spielt die Reihenfolge der gezogenen Kugeln eine Rolle (geordnete/ungeordnete Stichprobe)?
\item Werden die gezogenen Kugeln wieder zurückgelegt (mit/ohne Wiederholung)?
\ees
Bevor wir das auf den Fall „`Geordnete Stichprobe ohne Wiederholung“‚ anwenden, führen wir noch eine Schreibweise ein.

\section{Fakultät}
Das Produkt der ersten $n$ natürlichen Zahlen heißt $n!$ (sprich: \anf{$n$ Fakultät}). Beispiele:
\begin{itemize} \item $3!=1\cdot 2\cdot 3=6$ \item $6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=720$ \item $7!=6!\cdot 7=720\cdot 7=5040$ \end{itemize}
Das dritte Beispiel zeigt, dass man die Fakultät einer Zahl schnell berechnen kann, wenn man die Fakultät des Vorgängers kennt. Das nutzen wir aus, um den Fakultätsbegriff etwas formaler zu beschreiben: Die \df{Fakultät} $n!$ einer natürlichen Zahl $n\in\N_0$ (das Ausrufungszeichen wird als \anf{Fakultät} gelesen) ist wie folgt definiert:
\bes
\item Ist $n=0$, so ist $n!=1$.
\item Ist $n>0$, so ist $n!=n\cdot(n-1)!$.
\ees
Dies ist ein Beispiel für eine sogenannte \df{induktive Definition}. Für die Zahl 0 wird festgelegt, was $0!$ sein soll, und für jede andere natürliche Zahl $n$ wird $n!$ aus der Fakultät des Vorgängers $n-1$ berechnet. Auf diese Weise ist für jede natürliche Zahl $n$ festgelegt, was $n!$ sein soll. Das zeigen wir am Beispiel $3!$:
$$3!=3\cdot 2!=3\cdot 2\cdot 1!=3\cdot 2\cdot 1\cdot 0!=3\cdot 2\cdot 1=6$$

\section{Geordnete Stichprobe ohne Wiederholung}
Beim \SI{100}{m}-Lauf treten fünf Schüler gegeneinander an. Wie viele verschiedene Zieleinläufe sind möglich? Wir modellieren den Lauf durch eine Urne mit fünf Kugeln, eine für jeden Schüler. Für den Sieger entnehmen wir eine Kugel, dafür gibt es fünf Möglichkeiten. Da der Sieger aus dem Rennen ist, legen wir diese Kugel nicht wieder hinein. Für den zweiten Platz sind nur noch 4 Kugeln in der Urne. Nach der Produktregel gibt es also $5\cdot 4$ Möglichkeiten für die Besetzung der ersten beiden Plätze. So geht es weiter, bis die Urne leer ist. Insgesamt gibt es dafür
$$5\cdot 4\cdot 3\cdot 2\cdot 1=5!$$
Möglichkeiten. Allgemein gibt es für $n$ Dinge $n!$ Möglichkeiten, sie ohne Wiederholung anzuordnen.
Wir ordnen aber nicht immer alle Dinge an, sondern entnehmen meist eine \df{Stichprobe}. Wie viele Möglichkeiten der Medaillenvergabe gibt es beim olympischen \SI{100}{m}-Finale mit acht Teilnehmern? Für den ersten Platz gibt es 8 Möglichkeiten, für den zweiten 7 und für den dritten noch 6. Also gibt es insgesamt $8\cdot 7\cdot 6=336$ unterschiedliche Anordnungen auf dem Treppchen. Obwohl die Faktoren nicht bei 1 beginnen, können wir diesen Ausdruck auch mit Fakultäten darstellen. Es ist nämlich
$$8\cdot 7\cdot 6=\frac{8!}{5!}$$
Der Nenner kürzt die überflüssigen Faktoren heraus. Allgemein gibt es
$$\frac{n!}{(n-k)!}$$
Möglichkeiten, aus $n$ Dingen $k$ geordnet und ohne Wiederholung auszuwählen.

\section{Binomialkoeffizient}
Bevor wir zu den ungeordneten Stichproben kommen, führen wir einen weiteren Begriff ein. Für zwei natürliche Zahlen $n,k\in\N_0$ mit $n\ge k$ ist der Binomialkoeffizient $\binom nk$ (sprich: \anf{$n$ über $k$}) definiert als
$$\binom nk=\frac{n!}{(n-k)!\cdot k!}$$
Der Binomialkoeffizient gibt an, wie viele Möglichkeiten es gibt, aus $n$ Dingen $k$ auszuwählen, und zwar ohne Wiederholung und ohne Berücksichtigung der Reihenfolge. Etwas mathematischer: Die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge ist $\binom nk$. Die Begründung hierfür folgt im nächsten Abschnitt. Zum Beispiel ist
$$\binom {12}8=\frac{12!}{8!\cdot 4!}=495\text.$$
Es gibt also 495 Möglichkeiten, aus 12 Dingen acht auszuwählen. Der Binomialkoeffizient hat einige Eigenschaften, die seine Berechnung einfacher machen. Damit läßt sich sogar $\binom{12}8$ mit dem Kopf ausrechnen.
\be
\item $\binom nk$ ist, obwohl als Bruch defininert, immer eine natürliche Zahl. Die Faktoren im Nenner lassen sich also immer
vollständig wegkürzen.
\item Es ist $\binom n0=\frac{n!}{n!\cdot 0!}=1$. Anschaulich: Es gibt genau eine Möglichkeit, aus n Dingen keines auszuwählen.
\item Es ist $\binom nn=\frac{n!}{(n-n)!\cdot n!}=1$. Ebenfalls kann man auf eine Weise aus n Dingen n auszuwählen, nämlich indem man alle auswählt.
\item Außerdem gilt $\binom nk=\binom n{n-k}$, wie man durch Einsetzen in die Definition feststellt. Im Nenner vertauschen sich nämlich genau die Faktoren. Dies kann man wie folgt plausibel machen: Statt aus $n$ Dingen $k$ auszuwählen, kann ich auch die $n-k$ Dinge festlegen, die ich nicht auswähle.
\item Zur Berechnung von $\binom nk$ ohne Taschenrechner gibt es folgende Regel: Im Zähler stehen k Faktoren \anf{von oben}, im Nenner k Faktoren \anf{von unten}. Das sieht dann so aus: $\binom 83=\frac{8\cdot 7\cdot 6}{1\cdot 2\cdot 3}=4\cdot 7\cdot 2=56$ (immer kürzen!).
Man kann die Regeln auch kombinieren. So ist $\binom{12}{8}=\binom{12}{4}=\frac{12\cdot 11\cdot 10\cdot 9}{1\cdot 2\cdot 3\cdot 4}=3\cdot 11\cdot 5\cdot 3=495$.
\item Der Term $\binom n2$ läßt sich recht einfach berechnen, denn es ist $\binom n2=\frac{n\cdot (n-1)}{2}$. Da eine der Zahlen n und n-1 durch 2 teilbar ist, läßt sich der Bruch immer vor dem Ausrechnen kürzen. So ist $\binom{10}2=\frac{10\cdot 9}{2}=5\cdot 9=45$.
\item Und wer auf diese Rechenspiele keine Lust hat, gibt in den Taschenrechner für $\binom{12}4$ ein: \anf{12 nCr 4}.
\ee

\section{Ungeordnete Stichprobe ohne Wiederholung}
Nun kommen wir zur Abzählung von Mengen zurück. Aus den 24 Schülern der Klasse soll ein fünfköpfiger Ausschuß gebildet werden, der die nächsten Klassenfahrt plant. Wie viele Möglichkeiten gibt es, diesen Ausschuß zusammenzustellen? Der Aufgabenstellung ist zu entnehmen, dass die fünf Mitglieder alle gleichberechtigt sein sollen. Der Ausschuß (Arne, Franziska, Bente, Johann, Henry) ist derselbe wie (Johann, Franziska, Arne, Henry, Bente). Deshalb handelt es sich um eine ungeordnete Stichprobe, und natürlich ist kein Schüler zweimal im Ausschuß vertreten. Im vorigen Abschnitt haben wir schon erwähnt, dass die Anzahl der Auswahlmöglichkeiten durch den Binomialkoeffizienten
$$\binom{24}{5}=42504$$
geliefert wird. Am Beispiel dieser Aufgabe wollen wir dies nun begründen. Obwohl die Stichprobe ungeordnet ist, nähern wir uns der Lösung wieder schrittweise und wählen die Schüler der Reihe nach aus. Für den ersten Schüler gibt es 24 Möglichkeiten, für den zweiten 23 und so weiter, so dass wir zunächst bei
$$24\cdot 23\cdot 22\cdot 21\cdot 20=\frac{24!}{19!}$$
Möglichkeiten landen. Dadurch haben wir die Schüler in einer bestimmten Reihenfolge ausgewählt, was aber gerade keine Rolle spielen soll. Wir haben also jede Ausschußbesetzung mehrfach gezählt und müssen noch bestimmen, wie oft wir die Mitglieder untereinander vertauschen können. Es gibt $5!$ Möglichkeiten, die fünf Schüler untereinander anzuordnen. Deshalb müssen wir für den Ausdruck $$\frac{24!}{19!}$$ noch durch $5!$ teilen und erhalten als Endergebnis: Es gibt
$$\frac{24!}{19!\cdot 5!}=\binom{24}{5}$$
Möglichkeiten, aus 24 Schülern einen fünfköpfigen Ausschuß zu bilden.

\section{Ungeordnete Stichprobe mit Wiederholung}
Es fehlt noch der Fall einer ungeordneten Stichprobe, in der die Elemente mehrfach auftreten können. Wir geben zunächst die allgemeine Formel an und erläutern sie anschließend an einem Beispiel. Die Anzahl der Möglichkeiten, aus einer $n$-elementigen Menge $k$ ohne Berücksichtigung der Reihenfolge, aber mit Wiederholung auszuwählen, beträgt
$$\binom{n+k-1}k\text.$$
Gleich eine Beispielaufgabe dazu: Bei einem Sonderangebot kann man sich eine Getränkekiste (12 Flaschen) aus drei verschiedenen Getränkesorten beliebig zusammenstellen. Wie viele Möglichkeiten gibt es dafür? Bei Kombinatorikaufgaben ist man oft geneigt, die größte vorkommende Zahl als $n$ zu bezeichnen. Das ist in diesem Fall aber falsch. Bei Stichproben mit Wiederholung (also mit Zurücklegen) kann $k$ auch größer sein als $n$. Die Grundgesamtheit ist hier die Anzahl der Getränkesorten, also $n=3$. Die Zahl der Flaschen in der Kiste entspricht den gezogenen Kugeln, also ist $k=12$. In die Formel eingesetzt, ergeben sich
$$\binom {3+12-1}{12}=\binom{14}{12}=\binom{14}2=\frac{14\cdot 13}2=7\cdot 13=91$$
verschiedene Kombinationsmöglichkeiten. Die Rechnung zeigt auch, wie man den Binomialkoeffizienten ohne Taschenrechner berechnen kann.

Anhand der Getränkeaufgabe klären wir nun, wie die Formel $\binom {n+k-1}k$ zustande kommt. Wir nennen die drei Getränkesorten A,B,C und betrachten die Stichprobe ABBACCABCCBB. Da es eine ungeordnete Stichprobe ist, können wir sie auch als AAABBBBBCCCC schreiben. (Umsortieren der Flaschen in der Kiste verändert die Auswahl nicht.) Nun fügen wir zwischen den verschiedenen Sorten Trennstriche ein: AAA|BBBBB|CCCC. Für drei Sorten brauchen wir zwei Trennstriche, und die Stichprobe ist nun eindeutig durch die Position der Trennstriche festgelegt. Da wir nun 12 Flaschen und zwei Trennstriche haben, benötigen wir in unserem Gedankenexperiment nun 14 Plätze.

Anstatt die Getränkesorten auszuwählen, verteilen wir nun zwei Trennstriche auf 14 Plätze und legen fest, dass die Zwischenräume jeweils mit den Getränkesorten A,B,C aufgefüllt werden sollen. Für die Anordnung der Trennstriche gibt es wie schon berechnet $\binom{14}2$ Plätze.

Allgemein benötigen wir für $n$ Getränkesorten $n-1$ Trennstriche und haben dann insgesamt $k+n-1$ Plätze zu besetzen ($k$ Getränkeflaschen und $n-1$ Trennstriche). Auf diese Plätze werden die $n-1$ Trennstriche verteilt, und wir erhalten
$$\binom {k+n-1}{n-1}=\binom{n+k-1}{(n+k-1)-(n-1)}=\binom{n+k-1}k$$
Möglichkeiten. Bei dieser Umformung wurde das Gesetz $\binom nk=\binom n{n-k}$ angewendet.

\section{Zusammenfassung: Kombinatorik-Formeln}
Auf diese Weise entstehen vier verschiedene Fälle, für die es Formeln zur Berechnung der Anzahl Möglichkeiten gibt. Dabei ist jeweils $n$ die Grundgesamtheit und $k$ die Anzahl der Ziehungen.
$$\begin{array}{|c|c|c|}
\hline
&\text{mit Wiederholung}&\text{ohne Wiederholung}\
\hline
\text{geordnete Stichprobe}&n^k&\frac{n!}{(n-k)!} \
\hline
\text{ungeordnete Stichprobe}&\binom{n+k-1}k&\binom nk\
\hline
\end{array}$$

Schreibe einen Kommentar