close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Karate – kestnerlg_20150321

EinbettenHerunterladen
Permutationen
1-E
Lubov Vassilevskaya
Elemente einer Menge
Wir haben verschiedene Mengen von n Elementen:
● n Kugeln gleicher Größe und unterschiedlicher Farbe
● n Kugeln gleicher Farbe und unterschiedlicher Größe
1-1
Lubov Vassilevskaya
Elemente einer Menge
● n verschiedene flache geometrische Figuren: ein Kreis, ein Dreieck, ein
Quadrat, ein Rechteck, ein Parallelogramm u.s.w.
● n verschiedene Buchstaben
1-2
Lubov Vassilevskaya
Anordnen von Elementen einer Menge
Abb.: 5 Personen werden auf 5 Plätzen verteilt. Wie viele Möglichkeiten gibt es?
Wie kann man n Personen auf n Plätzen verteilen?
1-3
Lubov Vassilevskaya
Anordnung von Elementen: Aufgabe 1
Abb. A1-1: Illustration der Aufgabe 1b
In wieviel verschiedenen Reihenfolgen lassen sich Quadrate anordnen?
Wir haben dabei
a) ein rotes und graues Quadrat,
b) ein rotes, graues und blaues Quadrat.
2-1
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 1a
Abb. A1-2: Zwei verschiedene Quadraten kann man auf zwei verschiedene Arten anordnen
Offensichtlich kann man zwei verschiedene Quadrate auf zwei verschiedene Arten
anordnen: das rote Quadrat und dann das graue Quadrat und umgekehrt.
2-2
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 1b
Abb. A1-3: Drei verschiedene Quadraten kann man auf sechs verschiedene Arten anordnen
Empirisch kann man zeigen, dass es 6 Reihenfolgen für 3 verschiedene Quadrate gibt. Die Anzahl der Varianten kann man mathematisch so beschreiben: Es
gibt 3 Möglichkeiten das erste Quadrat zu wählen, für das zweite Quadrat bleiben dann nur 2 Möglichkeiten, für das dritte nur eine.
2-3
Lubov Vassilevskaya
Anordnung von Elementen: Aufgabe 2
Abb. A2-1: Illustration der Aufgabe: vier verschiedene Quadrate
Wir haben 4 verschiedene Quadrate: ein dunkelrotes, rotes, graues und blaues
Quadrat. In wie vielen Reihenfolgen lassen sich diese Quadrate anordnen?
2-4a
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 2
Abb. A2-2: Illustration der Lösung der Aufgabe: drei verschiedene Quadrate können
die drei übrigen Plätze besetzen
Wir nehmen ein bestimmtes Quadrat, z.B. ein dunkelrotes, und stellen dieses
Quadrat auf den ersten Platz. Die drei weiteren Plätze nummerieren wir 1, 2
und 3. Jetzt stellen wir die Frage: Wie kann man diese freien Plätze mit den
anderen Quadraten, dem roten, grauen und blauen besetzen? Oder anders formuliert: Wie viele verschiedene Varianten gibt es, um drei Elemente auf drei
Plätzen anzuordnen? Es gibt 6 Varianten, was wir schon in der Lösung der
vorigen Aufgabe gezeigt haben.
2-4b
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 2
Abb. A2-3: Illustration der Lösung der Aufgabe: drei verschiedene Quadrate können drei
gebliebene Plätze besetzen
Jetzt stellen wir das dunkelrote Quadrat auf den zweiten Platz. Die drei anderen Plätze, 1, 2 und 3, werden auf die gleiche Weise mit dem roten, grauen
und blauen Quadrat besetzt. Wieder gibt es 6 Varianten diese drei Quadrate
auf den drei Plätzen anzuordnen.
2-4c
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 2
Abb. A2-4: Illustration der Lösung der Aufgabe: rotes, graues und blaues Quadrat können
auf sechs verschiedene Arten die Plätze 1, 2 und 3 besetzen
2-4d
Lubov Vassilevskaya
Anordnung von Elementen: Lösung 2
Abb. A2-5: Illustration der Lösung der Aufgabe 2: rotes, graues und blaues Quadrat können
auf sechs verschiedene Arten die Plätze 1, 2 und 3 besetzen
Für jede der möglichen vier Plazierungen des dunkelroten Quadrates gibt
es sechs verschiedene Anordnungen des roten, grauen und blauen Quadrates. Insgesamt haben wir 4 · 6 = 24 Möglichkeiten vier verschiedene Quadrate auf vier Plätzen anzuordnen.
Solche Aufgaben führen auf den Begriff Permutation.
2-4e
Lubov Vassilevskaya
Anordnung von Elementen: Permutationen
Definition:
Eine Anordnung von n verschiedenen Elementen in einer bestimmten Reihenfolge heißt eine Permutation der n Elemente.
Wenn wir nach der Anzahl der Möglichkeiten fragen, n verschiedene Elemente anzuordnen, so ist dies die Frage nach
der Anzahl der Permutationen.
Aufgabe 3:
n Studenten sollen n vorhandene Plätze besetzen. Wie groß ist
die Anzahl der Permutationen?
3-1
Lubov Vassilevskaya
Permutationen: Lösung 3
Abb. A3: n Studenten sollen n vorhandene Plätze besetzen. Die Illustration der Besetzungsmöglichkeiten
Erklärung: Den ersten Platz kann jeder von n Studenten besetzten. Für den Platz 2.
gibt es dann noch (n – 1) Studenten, für den Platz 3. (n – 2) u.s.w. Für den letzten
Platz gibt es noch einen Studenten. Für die Besetzung von n Plätzen durch n Studenten gibt es n! Möglichkeiten:
P (n) = n (n − 1) (n − 2) . . . 2⋅1 = n!
3-2
Lubov Vassilevskaya
Permutationen von n Elementen
Die Anzahl der Permutationen von n verschiedenen Elementen
ist P (n) = n!
Wie groß wird dann die Anzahl der Permutationen, wenn k von
n Elementen einer Menge gleich sind?
Aufgabe 4:
Auf wieviel verschiedene Arten lassen sich die Quadrate anordnen?
Wir haben
a) ein rotes und zwei blaue Quadrate,
b) ein rotes und drei blaue Quadrate.
3-3
Lubov Vassilevskaya
Permutationen von n Elementen mit k gleichen (k < n): Lösung 4a
Abb. A-4a: Illustration der Lösung der Aufgabe 4a: ein rotes und zwei blaue Quadrate kann
man auf drei verschiedene Arten anordnen. Vertauschen von zwei blauen Quadraten ergibt
keine neue Anordnung
Drei Anordnungen von drei Elementen, von denen zwei gleich sind.
3-4
Lubov Vassilevskaya
Permutationen von n Elementen mit k gleichen (k < n): Lösung 4b
Abb. A-4b: Illustration der Lösung der Aufgabe 4b: ein rotes und drei blaue Quadrate kann man auf
vier verschiedene Arten anordnen. Vertauschen der blauen Quadrate ergibt keine neue Anordnung.
Vier Anordnungen von vier Elementen, von denen drei gleich sind.
3-5
Lubov Vassilevskaya
Permutationen mit k gleichen Elementen
Die Anzahl der Permutationen von n Elementen, von denen k gleich sind, ist
n!
P (n , k ) =
k!
Jetzt werden die empirische Ergebnisse der Aufgabe 4 geprüft.
Aufgabe 4a: ein rotes und zwei blaue Quadrate, d.h. n = 3, k = 2.
Aufgabe 4b: ein rotes und drei blaue Quadrate, d.h. n = 4, k = 3.
4 a ) P (3, 2) =
3!
= 3,
2!
4 b ) P (4, 3) =
4!
=4
3!
Die Anzahl der Permutationen von n Elementen, von denen k 1 , k 2 , k 3 , . . . , k n
gleich sind, ist
n!
P (n , k 1 , k 2 , k 3 , . .. , k n ) =
k 1! k 2! . . . k n!
4
Lubov Vassilevskaya
Permutationen: Aufgaben 5-9
Aufgabe 5:
Auf wie viele verschiedene Arten lassen sich die Zahlen 1, 2, 3 und 4
anordnen?
Aufgabe 6:
Wie viele verschiedene sechsstellige Zahlen kann man mit 5, 5, 7, 7, 7 und 7
zusammensetzen?
Aufgabe 7:
Auf wie viele Arten kann man die Buchstaben des Wortes Betttuch zu Folgen
von 8 Buchstaben anordnen?
Aufgabe 8:
Auf wie viele Arten kann man die Buchstaben des Wortes Balletttanz zu Folgen von 11 Buchstaben anordnen?
Aufgabe 9:
Auf wie viele Arten kann man die Buchstaben des Wortes Brennnesselstoff zu
Folgen von 16 Buchstaben anordnen?
5-1
Lubov Vassilevskaya
Permutationen: Lösungen 5-9
Lösung 5:
P (n) = P (4) = 4! = 1⋅2⋅3⋅4 = 24
Lösung 6:
P (n , k 1 , k 2 ) = P (6, 2, 4) =
6!
5⋅6
=
= 15
2! 4!
2
P (n , k t ) = P (8, 3) =
Lösung 7: für Betttuch
8!
= 4⋅5⋅6⋅7⋅8 = 6 720
3!
Lösung 8: für Balletttanz
P (n , k t , k a , k l ) = P (11, 3, 2, 2) =
11!
11!
=
=
3! 2! 2!
4!
= 5⋅6⋅7⋅8⋅9⋅10⋅11 = 1 663 200
Lösung 9: für Brennnesselstoff
P (n , k e , k n , k s , k f ) = P (16, 3, 3, 3, 2) =
=
5-2
16!
4⋅5⋅6 . . . 16
=
=
3! 3! 3! 2!
3! 3! 2!
4⋅5⋅6 .. . 16
5
10
= ⋅7⋅8⋅9 . .. 16 ≃ 4.843⋅10
2⋅3⋅2⋅3⋅2
3
Lubov Vassilevskaya
Document
Kategorie
Bildung
Seitenansichten
2
Dateigröße
606 KB
Tags
1/--Seiten
melden