Permutation

Permutations-Chiffre

Letztmalig dran rumgefummelt: 19.07.06 16:14:23

Permutationen, Kombinationen, Variationen, zusammen mit den Variationen Begriffe aus der mathematischen Disziplin Kombinatorik, in der es um Abzählungen von Möglichkeiten geht.

Hierzu ein Beispiel: Eine Kiste oder Urne enthält n durchnummerierte Kugeln, die nacheinander gezogen werden sollen. Zunächst wird eine Kugel blind gezogen und ihre Nummer notiert. Nun gibt es zwei Möglichkeiten: (1) Man legt die Kugel zurück, schüttelt die Urne und zieht erneut, oder (2) man legt die Kugel beiseite und zieht erneut.
Im ersten Fall (1) handelt es sich bei dem Ergebnis, das sich bei k-maligem Ziehen ergibt, um Variationen der Länge k mit Wiederholungen. Hierbei soll das Wort „Wiederholungen” daran erinnern, dass dieselbe Kugel mehrmals gezogen werden kann, d. h., es kann dieselbe Zahl mehrmals unter den k Zahlen auftreten. Im zweiten Fall (2) erhält man Variationen der Länge k. Hier muss k kleiner als n sein, weil höchstens n-mal gezogen werden kann (dann ist die Urne nämlich leer).

Die Anzahl der Möglichkeiten für Fall (2) ist leicht vorherzusagen: Für die erste Kugel bestehen n Möglichkeiten. Nachdem man die erste Kugel gezogen hat, bleiben für die zweite Kugel nur noch n - 1 Möglichkeiten. Dies geht bis zum k-ten Zug weiter, für den schließlich nur noch n - k + 1 Möglichkeiten bestehen. Insgesamt gibt es

n · (n - 1) · … · (n - k + 1)
Möglichkeiten. Jede Möglichkeit im ersten Zug lässt sich mit den (n - 1) Möglichkeiten des zweiten Zuges kombinieren, weshalb alle Möglichkeiten miteinander multipliziert werden müssen.

Zieht man n Kugeln, so beträgt die Anzahl der Möglichkeiten

n! = n · (n - 1) · … · 2 · 1
(n! bedeutet n-Fakultät). Was man erhält, sind die möglichen Reihenfolgen, in denen die Kugeln gezogen werden können, also praktisch die Reihenfolgen, in der sich die Zahlen 1, 2, …, n anordnen lassen. In der Mathematik wird eine Anordnung als Permutation der n Objekte bezeichnet. So besitzt beispielsweise die Buchstabenfolge ABC genau 3! = 3 · 2 · 1 = 6 Permutationen: ABC, ACB, BAC,BCA, CAB, CBA.

Unter allen Variationen der Länge k kommt eine Variation in einer gewissen Anzahl permutiert vor, d. h., es gibt Variationen, in denen zwar die gleichen Zahlen stehen, diese aber in anderer Reihenfolge. Bei dem Buchstabenbeispiel sind AB, BA Variationen der Länge 2, die sich nur durch Permutation der beiden Buchstaben A und B unterscheiden. Sollen diese Permutationen nicht unterschieden werden, d. h., AB und BA sollen eine Möglichkeit darstellen, so spricht man von Kombinationen. Insgesamt gibt es

Kombinationen der Länge k aus n Objekten. (Der Klammerausdruck wird gesprochen als „n über k”.) Derartige Anzahlen kommen u. a. in der Wahrscheinlichkeitsrechnung und beispielsweise im Pascal’schen Dreieck vor:

Der Unterschied zwischen Variationen und Kombinationen lässt sich auch an folgendem Beispiel verdeutlichen: Wie viele Möglichkeiten hat ein Lottospieler, sechs Zahlen aus 49 anzukreuzen? Er kann beispielsweise die Zahlen 1, 3, 38, 24, 15, 42 in angegebener Reihenfolge ankreuzen, oder er kreuzt sie so an: 3, 24, 1, 38, 15, 42. In beiden Fällen handelt es sich um Variationen, von denen es in diesem Beispiel 6! gibt, nämlich alle Permutationen dieser Zahlen. Im Gegensatz dazu entspricht die Kombination in diesem Beispiel nur der Menge der Zahlen {1,3,15,24,38,42}, ungeachtet ihrer Reihenfolge. Die Anzahl von Kombinationen der Länge k aus n Objekten ist auch gleich der Anzahl der k-elementigen Teilmengen einer Menge von n Elementen.

Verfasst von:
M&PHY München

© 1993-2003 Microsoft Corporation. Alle Rechte vorbehalten.

1. Zur Geschichte
2. Der Stuart-Code
3. Marias Code wird geknackt
4. Marias Hinrichtung
5. Die historischen Quellen

Maria Stuart

1. Zur Geschichte

Das Babington-Komplott

2. Der Stuart-Code

Maria Stuarts Geheimnomenklatur - sie besteht aus einem Alphabet und Codewörtern

Das von Thomas Phelippes gefälschte Postscriptum, welches Marias Nachricht hinzugefügt wurde
Die Abbildung oben zeigt das Postskriptum, das zu Marias Brief an Babington hinzugefügt wurde. Es kann anhand von Marias Nomenklator (oben) entschlüsselt werden und ergibt folgenden Klartext:

3. Marias Code wird geknackt

4. Marias Hinrichtung

Maria Stuarts Hinrichtung

5. Die historischen Quellen

	Permutationen, Kombinationen, Variationen, zusammen mit den Variationen Begriffe aus der mathematischen Disziplin Kombinatorik, in der es um Abzählungen von Möglichkeiten geht.
	Hierzu ein Beispiel: Eine Kiste oder Urne enthält n durchnummerierte Kugeln, die nacheinander gezogen werden sollen. Zunächst wird eine Kugel blind gezogen und ihre Nummer notiert. Nun gibt es zwei Möglichkeiten: (1) Man legt die Kugel zurück, schüttelt die Urne und zieht erneut, oder (2) man legt die Kugel beiseite und zieht erneut. Im ersten Fall (1) handelt es sich bei dem Ergebnis, das sich bei k-maligem Ziehen ergibt, um Variationen der Länge k mit Wiederholungen. Hierbei soll das Wort „Wiederholungen” daran erinnern, dass dieselbe Kugel mehrmals gezogen werden kann, d. h., es kann dieselbe Zahl mehrmals unter den k Zahlen auftreten. Im zweiten Fall (2) erhält man Variationen der Länge k. Hier muss k kleiner als n sein, weil höchstens n-mal gezogen werden kann (dann ist die Urne nämlich leer). Die Anzahl der Möglichkeiten für Fall (2) ist leicht vorherzusagen: Für die erste Kugel bestehen n Möglichkeiten. Nachdem man die erste Kugel gezogen hat, bleiben für die zweite Kugel nur noch n - 1 Möglichkeiten. Dies geht bis zum k-ten Zug weiter, für den schließlich nur noch n - k + 1 Möglichkeiten bestehen. Insgesamt gibt es n · (n - 1) · … · (n - k + 1) Möglichkeiten. Jede Möglichkeit im ersten Zug lässt sich mit den (n - 1) Möglichkeiten des zweiten Zuges kombinieren, weshalb alle Möglichkeiten miteinander multipliziert werden müssen. Zieht man n Kugeln, so beträgt die Anzahl der Möglichkeiten n! = n · (n - 1) · … · 2 · 1 (n! bedeutet n-Fakultät). Was man erhält, sind die möglichen Reihenfolgen, in denen die Kugeln gezogen werden können, also praktisch die Reihenfolgen, in der sich die Zahlen 1, 2, …, n anordnen lassen. In der Mathematik wird eine Anordnung als Permutation der n Objekte bezeichnet. So besitzt beispielsweise die Buchstabenfolge ABC genau 3! = 3 · 2 · 1 = 6 Permutationen: ABC, ACB, BAC,BCA, CAB, CBA. Unter allen Variationen der Länge k kommt eine Variation in einer gewissen Anzahl permutiert vor, d. h., es gibt Variationen, in denen zwar die gleichen Zahlen stehen, diese aber in anderer Reihenfolge. Bei dem Buchstabenbeispiel sind AB, BA Variationen der Länge 2, die sich nur durch Permutation der beiden Buchstaben A und B unterscheiden. Sollen diese Permutationen nicht unterschieden werden, d. h., AB und BA sollen eine Möglichkeit darstellen, so spricht man von Kombinationen. Insgesamt gibt es Kombinationen der Länge k aus n Objekten. (Der Klammerausdruck wird gesprochen als „n über k”.) Derartige Anzahlen kommen u. a. in der Wahrscheinlichkeitsrechnung und beispielsweise im Pascal’schen Dreieck vor: Der Unterschied zwischen Variationen und Kombinationen lässt sich auch an folgendem Beispiel verdeutlichen: Wie viele Möglichkeiten hat ein Lottospieler, sechs Zahlen aus 49 anzukreuzen? Er kann beispielsweise die Zahlen 1, 3, 38, 24, 15, 42 in angegebener Reihenfolge ankreuzen, oder er kreuzt sie so an: 3, 24, 1, 38, 15, 42. In beiden Fällen handelt es sich um Variationen, von denen es in diesem Beispiel 6! gibt, nämlich alle Permutationen dieser Zahlen. Im Gegensatz dazu entspricht die Kombination in diesem Beispiel nur der Menge der Zahlen {1,3,15,24,38,42}, ungeachtet ihrer Reihenfolge. Die Anzahl von Kombinationen der Länge k aus n Objekten ist auch gleich der Anzahl der k-elementigen Teilmengen einer Menge von n Elementen. Verfasst von: M&PHY München © 1993-2003 Microsoft Corporation. Alle Rechte vorbehalten.
	1. Zur Geschichte 2. Der Stuart-Code 3. Marias Code wird geknackt 4. Marias Hinrichtung 5. Die historischen Quellen
	*Maria Stuart*