Kombinatorik

Die Kombinatorik hilft bei der Bestimmung der Anzahl möglicher Anordnungen (auch Permutationen genannt) oder Auswahlen (Variationen oder Kombinationen genannt) von Objekten bei Versuchsausgängen.

Bei einer Anordnung bzw. Permutation werden dabei alle Elemente der Grundmenge betrachtet, wohingegen bei Auswahlen, entweder Variationen oder Kombinationen, nur eine Stichprobe der Grundmenge im Fokus des Interesses liegt. Es gibt weiterhin geordnete und ungeordnete Stichproben, je nachdem, ob die Reihenfolge der Elemente berücksichtigt wird, wie bei der Variation, oder nicht, wie bei der Kombination. Bei Anordnungen bzw. Permutationen wird die Reihenfolge immer berücksichtigt.

Die Kombinatorik hat zahlreiche Anwendungen in verschiedenen Gebieten der Mathematik, wie der Geometrie, Wahrscheinlichkeitstheorie, Algebra, Mengenlehre und Topologie. Außerdem wird sie auch in der Informatik und der theoretischen Physik angewendet.

Wichtige Begriffe der Kombinatorik

Um die konkreten Fälle und Formeln zu verstehen, solltest du zunächst einen guten Überblick über die wichtigsten Grundbegriffe in der Kombinatorik haben.

Was ist eine Fakultät?

Die Schreibweise der Fakultät ist n! (gesprochen: „n Fakultät“). Mit der Fakultät, manchmal auch Faktorielle genannt, lässt sich bestimmen, wie viele Möglichkeiten es gibt, n Objekte einer Menge anzuordnen. Die Fakultät lässt sich berechnen, indem man alle natürlichen Zahlen von 1 bis n miteinander multipliziert:

„n“ steht dabei für die Zahl, von der die Fakultät gebildet werden soll.

Was ist der Binomialkoeffizient?

Der Binomialkoeffizient gibt an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann. Ausgeschrieben sieht die Formel für den Koeffizienten folgendermaßen aus:

N über k setzt sich zusammen aus der Fakultät von n, geteilt durch die Fakultät von k, multipliziert mit der Fakultät von n-k.

Was ist das k-Tupel?

Ein k-Tupel ist eine Zusammenfassung von k Zahlen, die sich wiederholen dürfen, und deren Reihenfolge wichtig ist. Zum Beispiel: (1,2,3,4) ist ein 4-Tupel und es gilt (1,2,3,4) (1,2,4,3)

Was ist die k-Menge?

Eine k-Menge ist eine Zusammenfassung von k Zahlen, wobei weder Wiederholungen noch die Reihenfolge beachtet werden. Zum Beispiel: {6,6,5} = {6,5} und {7,3,1} = {1,3,7}

k-Permutation (H3)

Was ist eine Permutation?

Eine k-Permutation ist eine Zusammenfassung von k Zahlen, die sich nicht wiederholen dürfen, und deren Reihenfolge wichtig ist. k-Permutationen sind damit ein Spezialfall von k-Tupeln. Zum Beispiel: (1,2,3,4) ist eine 4-Permutation, aber (1,2,3,3) nicht, da die 3 doppelt vorkommt.

Was ist eine Kombination?

Eine k-Kombination ist eine Zusammenfassung von k Zahlen wobei die Reihenfolge nicht beachtet wird, es aber Wiederholungen gibt. k-Kombinationen sind damit ein Spezialfall von k-Mengen. Zum Beispiel: {6,6,5} {6,5} und {7,3,1} = {1,3,7}

Formeln der Kombinatorik

Für die Berechnungen der Kombinatorik werden verschiedene Formeln bei Permutationen, Kombinationen und Variationen benötigt. Das n in den Formeln steht immer für die Anzahl aller Elemente, also für die Grundgesamtheit. Das k gibt die Anzahl an Ziehungen an.

Um herauszufinden, welche Formel verwendet werden soll, sind folgende Fragen sinnvoll:

• Betrachte ich alle Elemente oder nur eine Stichprobe?
• Spielt die Reihenfolge eine Rolle?
• Können die Elemente mit Wiederholung vorkommen?

Die Grafik gibt einen Überblick darüber, welche Formeln wann zum Einsatz kommen:

via studyhelp.de

Wir schauen uns dazu nun noch die konkreten Fälle an.

Permutationen

Bei Permutationen gilt allgemein, dass alle Elemente der Grundgesamtheit beachtet werden. Es gilt also n = k. Auch die Reihenfolge wird hier immer berücksichtigt. Man muss nun zwischen den Fällen mit Wiederholung und ohne Wiederholung unterscheiden.

Bei der Permutation ohne Wiederholung handelt es sich um die Anordnung von Objekten, die alle verschieden sind. Das Ziel ist es, alle Objekte in einer bestimmten Reihenfolge anzuordnen. Zu Beginn sind noch alle Plätze frei, für das zweite Objekt verbleiben jedoch nur noch n-1 Möglichkeiten, für das dritte analog n-2 und immer so weiter. Führt man diese Reihe fort, so ergibt sich die Fakultät n!, die Formel zur Berechnung der Anzahl der Möglichkeiten. Zentral ist, dass alle Objekte der Menge verschieden sind und dadurch kein Objekt mit den gleichen Merkmalen zwei Mal vorkommen kann.

Im Falle einer Permutation mit Wiederholung sind dagegen nicht mehr alle Objekte voneinander unterscheidbar. Es kann also vorkommen, dass sich die Reihenfolge an sich nicht ändert, auch wenn zwei Objekte mit den gleichen Merkmalen getauscht werden. Man kann dabei Gruppen bilden, die die Objekte mit gleichen Merkmalen zusammenfassen.

Die Anzahl der Möglichkeiten wird dann mit folgender Formel berechnet:

Variationen

Bei Variationen gilt k < n. Für die Berechnungen werden also nur einige Objekte aus der Grundmenge gewählt, es handelt sich also um eine Stichprobe. Dabei sollte man beachten, dass die Reihenfolge der Auswahl entscheidend für das Ergebnis ist.

Bei der Variation ohne Wiederholung kommt jedes Objekt nur einmal vor, das Objekt darf nicht zurückgelegt werden. Für das erste Objekt gibt es noch n Platzierungsmöglichkeiten, für das zweite bleiben n-1 Möglichkeiten und so weiter. Für das letzte Objekt gibt es folglich noch n-k+1 Möglichkeiten.

Man erhält für die Variationen folgende Formel:

Es gibt auch eine Variation mit Wiederholung. In diesem Fall können Objekte auch mehrmals ausgewählt werden. Das bedeutet, dass manche Objekte nicht unterscheidbar sind. Das kann auch der Fall sein, wenn das Objekt nach der Auswahl wieder zu den anderen Elementen zurückgelegt wird. Wie zuvor gibt es für das erste Objekt n Auswahlmöglichkeiten, aufgrund der Mehrfachauswahl gilt das nun auch für alle weiteren Objekte.

Man rechnet also:

Kombinationen

Betrachtet man nun die Kombinationen, so gilt erneut k < n. Es handelt sich also wieder um eine Auswahl von Objekten aus der Grundmenge. Der Unterschied zu den Variationen besteht darin, dass hier die Reihenfolge keine Rolle spielt. Auch hier gibt es den Fall ohne Wiederholung und den Fall mit Wiederholung.

Hat man ein Objekt einmal ausgewählt, so kann dieses nicht wieder vorkommen. Es können also die ausgewählten Objekte k nur auf k! verschiedene Plätze verteilt werden. Mit der Formel für Variationen ohne Wiederholung im Hinterkopf kann man leicht die Formel für diesen Fall herleiten.

Die Formel zu den Kombinationen lautet:

Ein weiteres mögliches Szenario ist, dass die Reihenfolge der Ergebnisse des Zufallsexperimentes keine Rolle spielt und das Ergebnis erneut eintreten kann, wenn es bereits aufgetreten ist. Die Formel für den Fall ohne Wiederholung kann man leicht anpassen.

So ergibt sich folgende Formel:

Wie löst man Kombinatorik-Aufgaben?

Nun schauen wir uns zwei konkrete Beispiele für Kombinatorik-Aufgaben an, damit du die Formeln nicht nur theoretisch beherrschst, sondern auch gut anwenden kannst.

Aufgabe 1:

Du hast den Code für dein Handy vergessen. Wie viele Möglichkeiten gibt es, wenn du zumindest noch weißt, dass dein Code vier Zeichen lang war?

Beim Rechnen von Kombinatorik-Aufgaben sind nun folgende Fragen hilfreich:

1. Betrachte ich alle Elemente oder nur eine Stichprobe?

Man betrachtet nur eine Stichprobe, da man von den 10 möglichen Ziffern von 0-9 nur 4 auswählt.

2. Spielt die Reihenfolge eine Rolle?

Ja, die Reihenfolge spielt natürlich eine Rolle, um das Handy zu entsperren.

3. Können die Elemente mit Wiederholung vorkommen?

Ja, man kann theoretisch auch vier Mal die gleiche Ziffer verwenden.

Folgt man nun dem Lösungsbaum, der weiter oben im Artikel abgebildet ist, gelangt man zur Formel und der dazugehörigen Lösung mit .

Aufgabe 2:

Du hast vor dir einen Teller Buchstabensuppe. Du siehst, dass in deinem Teller noch genau die Buchstaben schwimmen, um das Wort Mississippi zu bilden. Wie viele Möglichkeiten hast, du die Buchstaben anzuordnen?

Auch hier stellst du dir die gleichen Fragen wie bei der vorherigen Aufgabe. Man betrachtet hier alle Elemente, da in dem neuen Wort schließlich alle Buchstaben verbaut werden sollen. Die Reihenfolge spielt auch in diesem Fall eine Rolle.

Aufgabe 3:

Es handelt sich hier nicht etwa um ein Urnenmodell mit Zurücklegen, aber die Elemente können trotzdem wiederholt vorkommen, es macht keinen Unterschied, ob du zuerst das erste oder das zweite s verwendest. Man benutzt zur Berechnung also folgende Formel:

Man erhält damit das Ergebnis:

Alles Wichtige zur Kombinatorik auf einen Blick:

Damit hast du die wichtigsten Fakten, Formeln und Beispiele im Bereich der Kombinatorik bereits verstanden. Damit du für deine nächste Prüfung bestens vorbereitet bist und nichts mehr vergisst, gibt es hier nochmals die wichtigsten Informationen im Überblick. Deiner nächsten erfolgreichen Prüfung steht also nichts mehr im Weg!

• Die Kombinatorik hilft bei der Bestimmung der Anzahl möglicher Anordnungen/Permutationen oder Auswahlen (Variationen oder Kombinationen) von Objekten bei Versuchsausgängen.
• Für die Berechnungen der Kombinatorik werden verschiedene Formeln bei Permutationen, Kombinationen und Variationen benötigt. Das n in den Formeln steht immer für die Anzahl aller Elemente, also für die Grundgesamtheit. Das k gibt die Anzahl an Ziehungen an.
• Um herauszufinden, welche Formel verwendet werden soll, sind folgende Fragen sinnvoll: Betrachte ich alle Elemente oder nur eine Stichprobe? Spielt die Reihenfolge eine Rolle? Können die Elemente mit Wiederholung vorkommen?
• Bei Permutationen gilt n = k. Auch die Reihenfolge wird hier immer berücksichtigt.
• Bei Variationen gilt k < n, die Reihenfolge ist entscheidend für das Ergebnis.
• Bei Kombinationen gilt erneut k < n, die Reihenfolge spielt hier aber keine Rolle.