Permutationen und Kombinationen: Grundformeln der Kombinatorik

Author

Norbert Henze

Participating institute

Institut für Stochastik (STOCH)
Fakultät für Mathematik (MATH)

Genre

Lehrmaterialien

Description

In diesem Video geht es um zwei Grundbegriffe der Kombinatorik, nämlich $k$-Permutationen und $k$-Kombinationen aus einer $n$-elementigen Menge $M$. Sowohl $k$-Permutationen als auch $k$-Kombinationen sind $k$-Tupel, also geordnete Auflistungen der Art $(a_1,\ldots ,a_k)$ von Elementen aus $M$. Man nennt $a_1, \ldots ,a_k$ auch die Komponenten des $k$-Tupels. Bei einer $k$-Permutation mit Wiederholung müssen nicht notwendig alle Komponenten des Tupels verschieden sein, bei einer $k$-Permutation ohne Wiederholung (die nur für den Fall, dass $k$ höchstens gleich $n$ ist, möglich sind) schon. Die Anzahlen der $k$-Permutationen mit bzw. ohne Wiederholung lassen sich unmittelbar mithilfe der Multiplikationsregel der Kombinatorik abzählen siehe auch https://mediaservice.bibliothek.kit.edu/#/details/DIVA-2019-184
​ $k$-Kombinationen aus $M$ mit bzw. ohne Wiederholung sind $k$-Permutationen mit bzw. ohne Wiederholung, bei denen die Komponenten nach aufsteigender Größe angeordnet sind. Hierfür setzen wir $M$ als Menge der Zahlen von $1$ bis $n$ (oder allgemein als totalgeordnete Menge) voraus. $k$-Kombinationen ohne Wiederholung entsprechen $k$-elementigen Teilmengen von $M$; deren Anzahl ist somit durch den Binomialkoeffizienten $\binom{n}{k}$ gegeben. Eine geeignete bijektive Abbildung von $k$-Kombinationen mit Wiederholung einer $n$-elementigen Menge auf $k$-Kombinationen ohne Wiederholung aus einer $ (n+k-1)$-elementigen Menge komplettiert die vier Grundformeln der Kombinatorik. Einige Beispiele illustrieren die Begriffsbildungen. Das Video setzt ein begriffliches Verständnis von Binomialkoeffizienten voraus, siehe
https://mediaservice.bibliothek.kit.edu/#/details/DIVA-2019-978

Keywords

Stochastik, Kombinatorik, Permutation, Kombination, mit Wiederholung, ohne Wiederholung

Duration (hh:mm:ss)

00:18:31

Published on

11.05.2021

Subject area

Mathematics

License

Creative Commons Attribution – NonCommercial – NoDerivatives 4.0 International