Kombinatorik

n-Tupel:

Ein n-Tupel ist eine Zusammenfassung von n Objekten x₁, x₂, x₃, …, x_n in einer Liste. Die Objekte müssen nicht verschieden sein. Tupel werden meist mit runden Klammern und Kommas (Strichpunkten) notiert  (x₁, x₂, x₃, …, x_n)
oder kurz ohne Klammern und Kommas  x₁ x₂ x₃ … x_n.

Permutation:

Eine bestimmte Reihenfolge von n Objekten im n-Tupel heißt Permutation,
wenn die n Objekte verschieden sind (n Elemente einer Menge), dann Permutation ohne Wiederholung, wenn gleiche Elemente vorkommen, dann Permutation mit Wiederholung.

Anzahl der Permutationen ohne Wiederholung

Anzahl der n-Tupel mit n verschiedenen Elementen einer Menge:

Anzahl der Möglichkeiten für die 1. Stelle:  n
Anzahl der Möglichkeiten für die 2. Stelle:  n – 1
Anzahl der Möglichkeiten für die 3. Stelle:  n – 2
...
Anzahl der Möglichkeiten für die n. Stelle:  1

Nach dem Zählprinzip gibt es insgesamt  n٠(n – 1)٠(n – 2)٠ … ٠3٠2٠1 
mögliche Permutationen oder n-Tupel mit n verschiedenen Elementen.

Als Abkürzung schreibt man  n!  =  1٠2٠3٠…٠n   (lies: “n-Fakultät“)

Beispiele:

3! = 6 mögliche 3-Tupel in Kurzform

mit den Ziffern 1, 2, 3:  123, 132, 213, 231, 312, 321,

mit den Buchstaben a, b und c:  abc, acb, bac, bca, cab, cba,

mit Dreieck, Kreis und Quadrat: 

Anzahl der k-Tupel mit n verschiedenen Elementen aus einer n-Menge mit k ≦ n⸱: 

Bemerkung: n-Menge = n-elementige Menge

Beispiel:

20 2-Tupel aus der Menge {a, b, c, d, e}

ab, ba, ac, ca, ad, da, ae, ea, bc, cb, bd, db, be, eb, cd, dc, ce, ec, de, ed

Anzahl der Permutation mit Wiederholung

Beispiel:

Es gibt 10 mögliche 5-Tupel mit zweimal 1 und dreimal 0:

(1,1,0,0,0), (1,0,1,0,0), (1,0,0,1,0), (1,0,0,0,1), (0,1,1,0,0), (0,1,0,1,0), (0,1,0,0,1), (0,0,1,1,0), (0,0,1,0,1), (0,0,0,1,1).
Die 5! möglichen Reihenfolgen bei 5 verschiedenen Ziffern muss geteilt werden durch die 2! nicht unterscheidbaren Vertauschungen der beiden Einser und durch die 3! nicht unterscheidbaren Vertauschungen der drei Nullen, also insgesamt 5! / (2!٠3!) = 10 mögliche Reihenfolgen.

Die 10 möglichen 5-Tupel mit zweimal a und dreimal b in Kurzschreibweise:

aabbb, ababb, abbab, abbba, baabb, babab, babba, bbaab, bbaba, bbbaa

Allgemein gilt:

Es gibt verschiedene n-Tupel mit k-mal x₁ und (n – k)-mal x₂.

Dafür wurde folgende abkürzende Schreibweise eingeführt:

= ,   (lies: "k aus n")

Entsprechend gibt es verschiedene n-Tupel mit k₁-mal x₁, mit k₂-mal x₂ und mit k₃-mal x₃ und k₁ + k₂ + k₃ = n.

Beispiel:

Dreimal a, zweimal b, einmal c liefert  = 60 verschiedene 6-Tupel:

aaabbc, aaabcb, aaacbb, aababc, aabacb, aabbac, aabbac, aabbca, aabcab, aabcba,
abaabc, abaacb, ababac, ababca, abacab, abacba, baaabc, baaacb, baabac, baabca,
baacab, baacba, bababc, babacb, babbac, babbca, babcab, babcba, bbaaac, bbaaca,
bbacaa, bbcaaa, aacabb, aacbab, aacbba, acaabb, acabab, acabba,  caaabb, caabab,
caabba, abcaab, abcaba, abcbaa, acbaab, acbaba, acbbaa, bacaab, bacaba, bacbaa,
bcaaab, bcaaba, bcabaa, cabaab, cababa, cabbaa, cbaaab, cbaaba, cbabaa, cbbaaa.

Verallgemeinerung:

k-elementige Teilmengen einer n-Menge

Die Anzahl der k-elementigen Teilmengen einer n-elemntigen Menge mit k ≦ n ist

=

Beispiele:

Lotto 6 aus 49:

Es gibt  = 13 983 816 Möglichkeiten 6 Zahlen aus 49 Zahlen auszuwählen. Darunter befinden sich die 6 ausgelosten Zahlen.

2-elementige Mengen aus der Menge {A, B, C, D, E}:

Es gibt  = 10 verschiedene 2-elemntige Mengen aus der Menge {A, B, C, D, E}:

{A, B}, {A, C}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E}, {C, D}, {C, E}, {D, E}.

Zurück
Zurück zur Startseite