Mathematik-Grundbegriffe für Programmierer

Abzählende Kombinatorik – Permutation und Binomialkoeffizient

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Zwei der wichtigsten Theorien der abzählenden Kombinatorik sind die Permutation und der Binomialkoeffizient. Auf beide Verfahren geht der Trainer in diesem Video ein.
03:57

Transkript

Für die verschiedensten Algorithmen und Aufgaben der Programmierung ist die sogenannte abzählende Kombinatorik sehr interessant. Diese basiert explizit auf der Fakultät und einigen Formeln daraus, die Sie für die verschiedensten Anwendungen kennen werden. Die einfachste Variante ist normalerweise die sogenannte Permutation. Permutationen basieren direkt auf Fakultäten, weil die Fakultät einer Zahl die Anzahl der Möglichkeiten beschreibt, mit der sogenannte unterscheidbare Objekte in einer Reihe angeordnet werden können. Es gilt insbesondere auch für den Fall n = 0, denn 0 Fakultät ist 1 und die sogenannte leere Menge kann nur auf genau eine Art und Weise auf sich selbst abgebildet werden. Als Beispiel für eine Permutation könnte man an ein Rennen denken, beispielsweise ein Pferderennen. Wenn Sie 10 Pferde haben, dann kann es für einen Zieleinlauf genau 10 Fakultät Möglichkeiten geben. Für den ersten Platz kommen 10 Pferde mit ihren Reitern in Frage. Ist der erste Reiter angekommen, können nur noch 9 weitere Reiter, um den zweiten Platz kämpfen, ist auch der da, können noch 8 weitere um den dritten Platz kämpfen und so weiter. Für den ersten Platz kommen alle 10 Reiter in Frage, für den zweiten Platz ist es aber von Bedeutung, wer bereits auf dem ersten Platz sitzt, denn der Reiter muss natürlich nicht mehr berücksichtigt werden, er ist ja bereits auf Platz 1 platziert. Deshalb ist die Fakultät die einzig sinnvolle Möglichkeit, so eine Menge an Permutationen, an möglichen Anordnungen, zu beschreiben. Weiter ist in der abzählenden Kombinatorik sehr oft der sogenannte Binomialkoeffizient von Bedeutung. Dieser gibt die Anzahl der Möglichkeiten an, eine Teilmenge aus k Elementen, aus einer größeren Menge von Elementen auszuwählen. Das klingt sehr abstrakt, aber eine sehr bekannte Anwendung davon ist die Lottozahlenziehung: 6 aus 49. Es gibt dafür eine Formel, die wieder auf der Fakultät beruht und die sieht so aus: n über k ist gleich n Fakultät geteilt durch k Fakultät mal n minus k Fakultät. n ist die Anzahl der Elemente der großen Menge, aus der ausgewählt wird und k ist die Anzahl der Elemente, die gezogen werden. Das ist dann ein sogenanntes Ziehen ohne Zurücklegen, denn wenn eine Zahl aus der großen Menge gezogen wurde, wird die nächste Zahl natürlich aus der kleineren Menge gezogen, der um 1 reduzierten Menge. Berechnen wir mal die möglichen Kombinationen, um 6 Zahlen aus 49 zu ziehen, sprich, wie viele Möglichkeiten gibt es, die Lottozahlen zu ziehen? Wir haben also n -- das ist 49 -- Fakultät und das teilen wir durch k -- das ist also 6 -- Fakultät mal n minus k, also 49 minus 6 ist 43 Fakultät. Und hier sehen Sie das Ergebnis. Sie haben also in diesem Video die sogenannte abzählende Kombinatorik kennengelernt und zwei wichtige Anwendungen davon, die sogenannten Permutationen und den Binomialkoeffizienten.

Mathematik-Grundbegriffe für Programmierer

Lernen Sie die Themenbereiche und Verfahren aus der Mathematik kennen, die bei der täglichen Programmierarbeit zum Einsatz kommen.

2 Std. 54 min (40 Videos)
Derzeit sind keine Feedbacks vorhanden...
Exklusiv für Abo-Kunden
Erscheinungsdatum:03.10.2016
Aktualisiert am:19.12.2016

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!