zum Directory-modus

Kombinatorik - ein Exkurs

Variationen

1. Variation ohne Wiederholung (Teilmenge, Ziehung ohne Zurücklegen, mit Beachtung der Reihenfolge)

Alle ( n ) Elemente der Ausgangsmenge unterscheiden sich voneinander. Es werden einige ( k ) Elemente ausgewählt, ein Element kann nicht mehrmals ausgewählt werden. Wieviele Möglichkeiten gibt es, k Elemente auszuwählen und in eine Reihenfolge zu bringen?

V n , k = n ! ( n k ) !

Die Permutation ohne Wiederholung ist ein Spezialfall der Variation ohne Wiederholung. Werden bei der Variation ohne Wiederholung nicht nur eine Auswahl, sondern alle Elemente ausgewählt, ergibt die Formel in beiden Fällen das gleiche Ergebnis: n ! = n ! ÷ ( n - n ) ! , da 0! = 1.

Beispiel

Wieviele Möglichkeiten der Medaillenverteilung gibt es bei 8 Wettkampfteilnehmern?

Jede Medaille kann nur einmal vergeben werden (= ohne Wiederholung). Die Reihenfolge ist entscheidend: Es kommt nicht nur darauf an, wer eine Medaille bekommt, sondern auch, um welche Medaille es sich handelt. Die Lösung:

n = Anzahl der Wettkämpfer = 8, k = Anzahl verschiedener Medaillen = 3; V = n ! ÷ ( n - k ) ! = 8 ! ÷ ( 8 - 3 ) ! = 40320 ÷ 120 = 336

Es gibt 336 Möglichkeiten, wie die drei Medaillen unter 8 Teilnehmern verteilt werden können.

2. Variation mit Wiederholung (Teilmenge, Ziehung mit Zurücklegen, mit Beachtung der Reihenfolge)

Alle ( n ) Elemente der Ausgangsmenge unterscheiden sich voneinander. Es werden einige ( k ) Elemente ausgewählt, ein Element kann mehrmals ausgewählt werden. Frage: Wieviele mögliche Reihenfolgen unter den möglichen auswählbaren Elementen gibt es?

V n , k = n k

Da das Zurücklegen (Wiederholung eines bereits verwendeten Objekts) erlaubt ist und damit jedes Objekt beliebig oft verwendet werden darf, kann k größer als n sein.

Beispiel

Wieviele verschiedene DNA- und Proteinsequenzen lassen sich mit einem 600 Basenpaaren langen DNA-Stück codieren? Die Lösung:

Die DNA enthält vier verschiedene Nucleotide; jeweils ein Triplett codiert eine Aminosäure. Anzahl verschiedener DNA-Sequenzen: n=4, k=600 ; n k =1,722· 10 36 . Anzahl verschiedener Proteine: jede der 20 natürlichen Aminosäure kann von bis zu drei Tripletts codiert werden (redundanter Code): n=20, k=200 ; n k =1,607· 10 26 Möglichkeiten.

Seite 4 von 4>