• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Einführung in die abzählende Kombinatorik

Contents

  • Begriffe
    • Permutation
    • k-Permutation
    • Kombination und k-Kombination
  • Formeln
  • Siehe auch

Die abzählende Kombinatorik beschäftigt sich mit der Bestimmung der Anzahl möglicher Anordnungen oder Auswahlen.

Begriffe

Permutation

Eine Permutation ist eine Veränderung der Reihenfolge einer geordneten Anzahl von Objekten. (Weil die Objekte in irgend einer Art geordnet sein müssen, damit sich eine Reihenfolge ändern kann, will ich diese Ansammlung nicht "Menge" nennen.)

Beispiel: Wir haben eine Liste von Zahlen: [1, 2, 5, -7, -1, 3] Eine Permutation davon ist: [1, 2, 5, -7, 3, -1]

Anagramme sind Permutationen: "ANGSTBUDE" und "BUNDESTAG"

Das Wesentliche ist also, dass es bei Permutationen auf die Reihenfolge ankommt.

k-Permutation

Eine k-Permutation wählt aus n Objekten k aus.

Wenn wir also die 6 Objekte [1, 2, 5, -7, -1, 3] haben, wären [1, 2, 5], [5, 2, 1], [-7, 2, 3] und [-7, 3, 3] verschiedene 3-Permutationen davon.

Kombination und k-Kombination

Bei einer Kombination kommt es nicht auf die Reihenfolge an. Sonst ist alles analog zu den Permutationen.

Formeln

Es gibt nur vier Formeln, die man sich merken sollte. Dabei sei n die Anzahl aller wählbaren Objekte:

 mit Wiederholungenohne Wiederholungen
k-Permutation$n^k$$\frac{n!}{(n-k)!}$
k-Kombination$\binom{n-1+k}{k}$$\binom{n}{k}$

Warum stimmt das?

Wenn man n Objekte hat und k-mal eines davon auswählt, wobei die Reihenfolge eine Rolle spielt und man das Objekt danach immer wieder zurück legt (also Wiederholungen haben kann), dann hat man beim ersten mal n verschiedene Wahlmöglichkeiten. Beim zweiten, dritten, ... k.-Zug auch. Es sind also $\underbrace{n \cdot n \cdot ... \cdot n}_\text{k mal} = n^k$ Möglichkeiten.

Wenn man die Objekte nicht wieder zurück legt, die Reihenfolge aber eine Rolle spielt, hat man beim ersten Zug wieder n Möglichkeiten. Beim zweiten Zug sind es (n-1), beim dritten (n-3), ... beim k.-Zug (n-k+1) Möglichkeiten. Also gilt: $\underbrace{(n-0) \cdot (n-1) \cdot ... \cdot (n- (k-1))}\text{k Faktoren} = \prod$}^{k-1} (n-i)= \frac{n!}{(n-k)!

Angenommen es spielt nun nur eine Rolle, welche Objekte man ausgewählt hat, aber nicht wann. Dann gibt es, wenn man die Objekte nicht wieder zurücklegt, $\frac{n!}{(n-k)!}$ Möglichkeiten, abzüglich der Möglichkeiten, die nur bei Beachtung der Reihenfolge eine Rolle spielen. Das bedeutet, es muss noch durch k! geteilt werden. Das kann man sich klar machen, indem man eine bestimmte Menge an k ausgewählten Objekten betrachtet. Dann muss man entscheiden, welches das erste ist. Dafür gibt es k Möglichkeiten. Für das zweite hat man (k-1) Möglichkeiten, usw. Das Bedeutet, es gibt für diesen Fall $\frac{n!}{(n-k)! \cdot k!} = \binom{n}{k}$ Möglichkeiten.

Der schwerste Fall sind k-Kombinationen mit zurücklegen. Dafür denkt man sich am besten, dass man eine Liste der Objekte hat. Nun macht man, um die n Objekte zu trennen, zwischen diese (n-1) Sternchen. Die Anzahl wird durch k Striche repräsentiert. Nun kann man sich fragen, wie viele Möglichkeiten es gibt diese k Striche und (n-1) Sternchen anzuordnen. Das sind, wenn man die k Striche auf (n-1)+k Plätze verteilt: $\frac{(n-1+k)!}{(n-1)!} \cdot \underbrace{\frac{1}{k!}}_\text{Reihenfolge ist egal} = \frac{(n-1+k)!}{(n-1)!k!}$

Dies entspricht genau dem Binomialkoeffizienten: $\binom{n-1+k}{k} = \frac{(n-1+k)!}{k!((n-1+k)-k)!} = \frac{(n-1+k)!}{k!(n-1)!}$

Siehe auch

Wikipedia:

  • Kombinatorik (Der Artikel ist leider sehr mager. Eventuell hat jemand lust ihn zu ergänzen?)
  • Abzählende Kombinatorik
  • Permutation
  • Anagramm
  • Binomialkoeffizient

Published

Okt 24, 2011
by Martin Thoma

Category

German posts

Tags

  • lecture-notes 11
  • mathematics 61

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor