[WS] How-to Kombinatorik

Neue Frage »

Zellerli Auf diesen Beitrag antworten »
[WS] How-to Kombinatorik
Abzählende Kombinatorik - ein How-to

Vorwort

Die Zielgruppe dieses Workshops sind Schüler, sowie Studenten, die Stochastik oder Kombinatorik auf Nebenfachniveau erlernen.
Mein Workshop hat zwar den Anspruch mathematischer Richtigkeit, jedoch wird sehr pragmatisch und aufgabenorientiert vorgegangen, zugunsten eines direkteren und einfacheren Zugangs.
Er unterscheidet sich nur methodisch und in den Beispielen vom gleichnamigen Wikipedia-Artikel (der als Ergänzung und zum Schnellzugriff sehr zu empfehlen ist).

Falls jemand im Folgenden Fehler, Ungenauigkeiten, Doppeldeutigkeiten, Unsinn oder UFOs sichtet, möge er bitte eine PN an mich richten.
Auch über sonstige Kritik freue ich mich sehr!


Der Knackpunkt

Die eigentliche Schwierigkeit in der abzählenden Kombinatorik sind nicht die Formeln, sondern das korrekte Vereinfachen und Abstrahieren eines kombinatorischen Sachverhalts. Danach kann man die Berechnung der Anzahl der Möglichkeiten ganz leicht durchführen.
Es ist also nicht empfehlenswert, weil einfach nicht hilfreich, gleich zu Beginn die Fachbegriffe und Formeln auswendig zu lernen und dann verzweifelt zu versuchen sie auf die Aufgabe zu pressen. "Ist das mit Wiederholung?", "Ist das eine Variation oder Kombination?", etc. sind also eher irreführende Fragen.
Konstruktivere Fragen sind "Macht es einen Unterschied, wenn ich die erste und zweite Karte in der Auswahl vertausche?", "Könnten anstelle der Karten genausogut Kugeln stehen, die nur an der Farbe zu unterscheiden sind?", etc. Dazu sind Skizzen und Gedankenspiele das A und O.


Grundlegende Tipps

Man sollte anfangs für jedes kombinatorische Problem aufs Neue die entsprechende Formel herleiten. Nur so entwickelt man tieferes Verständnis. Mit wachsender Erfahrung wird man später schnell Parallelen zu bekannten Problemen und Modellen erkennen und dann "fertige" Formeln, die man aber längst nachvollzogen und verinnerlicht hat, anwenden.
Zur Überprüfung einer Formel ist es oft sehr hilfreich aus großen Zahlen kleine zu machen. Aus einer Urne mit 100 Kugeln wird eine mit 3 Kugeln, aus einem Zahlenschloss mit 12 Rädchen wird eines mit 2 Rädchen, usw.
So kann man die Anzahl der Fälle leicht abzählen und dann vergleichen, ob das vermutete Schema / die vermutete Formel sinnvoll ist.
Skizzen von möglichen Anordnungen und Auswahlen bis hin zu ausführlichen Baumdiagrammen (wobei die Wahrscheinlichkeiten in der Kombinatorik keine Rolle spielen) können dabei ebenfalls hilfreich sein.
Zellerli Auf diesen Beitrag antworten »
Gliederung
Im folgenden sind die sechs grundlegenden Modelle genauer erläutert.
Die Fachbegriffe stehen zur Ergänzung da. Sie sind absolut unbedeutend für die richtige Lösung.
Weil man von der Aufgabe auf ein Modell schließen sollte und nicht umgekehrt, sind die Beispiele das wichtigste. Nur wer sehr geübt ist, wird aus den bloßen Formeln und Namen etwas mitnehmen können.


1 Anordnung von Objekten (Permutation):

1.1 Modell "Anordnung von Spielkarten (in einer Reihe)":
Permutation unterscheidbarer Objekte

1.2 Modell "Anordnung von Spielkarten, wobei sie nur nach Farbe unterschieden werden. Es gibt Farben mit jeweils Spielkarten"
Permutation von Objekten unterscheidbarer Klassen mit je Elementen


2 Auswählen, wobei die Reihenfolge wichtig ist (Variation):

2.1 Modell "Zahlenschloss mit Rädchen, die jeweils Ziffern tragen" (es ginge auch: "Urne mit unterscheidbaren Kugeln: mal Ziehen mit Zurücklegen")
Variation mit Wiederholung

2.2 Modell "Urne mit unterscheidbaren Kugeln: mal Ziehen ohne Zurücklegen"
Variation ohne Wiederholung


3 Auswählen, wobei die Reihenfolge egal ist (Kombination):

3.1 Modell "Ziehung der Lottozahlen aus "
Kombination ohne Wiederholung

3.2 Modell "Urne mit verschieden farbigen Kugeln: -mal Ziehen mit Zurücklegen"
Kombination mit Wiederholung
Zellerli Auf diesen Beitrag antworten »
1.1 Permuation n unterscheidbarer Objekte
1.1 Modell "Anordnung von Spielkarten"
Permutation unterscheidbarer Objekte

Allgemein gibt es Möglichkeiten.

Beispiel: Ein Pokerdeck mit 52 Karten wird in einer Reihe angeordnet:
Erste Stelle: 52 Möglichkeiten. Zweite Stelle: noch 51 Möglichkeiten. Dritte Stelle: noch 50 Möglichkeiten. ... 51. Stelle: Noch 2 Möglichkeiten. 52. Stelle: nur noch 1 Möglichkeit. Insgesamt: Möglichkeiten.
Zellerli Auf diesen Beitrag antworten »
1.2 Permutation von n Objekten j unterscheidbarer Klassen mit je k Elementen
1.2 Modell "Anordnung von Spielkarten wobei es nur auf deren Farben ankommt"
Permutation von Objekten unterscheidbarer Klassen mit je Elementen

Allgemein gibt es Möglichkeiten.

Klingt hässlich, ist aber halb so wild.
Beispiel: Pokerkarten werden in einer Reihe angeordnet, wobei nur die Farbe wichtig ist.
Man hat vier Farben, also vier Klassen.
Klasse "Herz" hat 13 Elemente.
Klasse "Pik" hat 13 Elemente.
Klasse "Karo" hat 13 Elemente.
Klasse "Kreuz" hat 13 Elemente.
Wie im Beispiel oben gibt es für die unterscheidbaren Karten Möglichkeiten.
Wir müssen aber noch korrigeren, denn es ist egal, ob z.B. an Stelle 4 ein Karo Ass oder ein Karo Bube steht. Wichtig ist: Karo.
Man betrachtet also die Anordnung der Reihe mit den 52 Karten: Man darf nun die Karo beliebig untereinander vertauschen - es bleibt die selbe Farbe an jeder Stelle. Das gleiche darf man mit den anderen Farben machen. Wieviele Möglichkeiten gibt es, die Karo untereinander anzuordnen? Analog 1.1 sind es . Genau soviele Fälle werden pro Farbe zuviel gezählt, wenn man nimmt. Man muss also korrigeren und erhält Möglichkeiten.

Ergänzung:
Das Beispiel ist etwas speziell, denn im Allgemeinen hat nicht jede Klasse gleich viele Elemente - so wie im Pokerdeck jeder Farbe gleich viele Karten angehören.
Betrachten wir nun ein fiktives Kartendeck mit 52 Karten, aber diesmal mit 14mal Karo und dafür 12mal Kreuz (Herz und Pik sollen bei 13 bleiben).
Dann müsste man für Karo mit korrigieren und für Herz mit , denn soviele Möglichkeiten gäbe es die 14 Karo bzw. die 12 Kreuz untereinander anzuordnen. Man erhielte dann Möglichkeiten.
Zellerli Auf diesen Beitrag antworten »
2.1 Variation mit Wiederholung
2.1 Modell "Zahlenschloss mit Rädchen, die jeweils Ziffern tragen" (es ginge auch: "Urne mit unterscheidbaren Kugeln: mal Ziehen mit Zurücklegen")
Variation mit Wiederholung

Allgemein gibt es Möglichkeiten.

Beispiel: Zahlenschloss mit 4 Rädchen mit jeweils 8 Ziffern.
Erste Stelle: 8 Möglichkeiten. Zweite Stelle: 8 Möglichkeiten. Dritte Stelle: 8 Möglichkeiten. Vierte Stelle: 8 Möglichkeiten. Insgesamt: Möglichkeiten.
Anmerkung: Wären es 4 Rädchen mit je 10 Ziffern, so erhielte man Möglichkeiten - genausoviele Zahlen gibt es von 0000, 0001, ... bis 9999. Jede Kombination stellt dann eine Zahl im Dezimalsystem dar.

Alternatives Beispiel: Urne mit 8 unterscheidbaren (z.B. nummierierten) Kugeln. 4mal ziehen mit Zurücklegen.
Erster Zug: 8 Möglichkeiten. Man legt die Kugel wieder zurück. Zweiter Zug: 8 Möglichkeiten. Man legt die Kugel wieder zurück. Dritter Zug: 8 Möglichkeiten. Man legt die Kugel wieder zurück. Vierter Zug: 8 Möglichkeiten. Ingesamt: Möglichkeiten.
Zellerli Auf diesen Beitrag antworten »
2.2 Variation ohne Wiederholung
2.2 Modell "Urne mit unterscheidbaren Kugeln: mal Ziehen ohne Zurücklegen"
Variation ohne Wiederholung

Allgemein gibt es Möglichkeiten.

Beispiel: Urne mit 5 verschieden farbigen Kugeln, 3 davon werden gezogen.
Erste Stelle: 5 Möglichkeiten. Zweite Stelle: noch 4 Möglichkeiten. Dritte Stelle: noch 3 Möglichkeiten. Insgesamt: Möglichkeiten.
 
 
Zellerli Auf diesen Beitrag antworten »
3.1 Kombination ohne Wiederholung
3.1 Modell "Ziehung der Lottozahlen"
Kombination ohne Wiederholung

Allgemein gibt es Möglichkeiten.

Beispiel: Aus 49 Lottozahlen werden 6 gezogen.
Man stellt sich die Lottozahlen (z.B. auf Tischtennisbällen) sortiert in einer Reihe angeordnet vor. Es werden dann zufällig 6 Bälle nacheinander von ihrem Platz genommen.
Ein äquivalentes Vorgehen, das aber anschaulicher zu berechnen ist, ist das folgende: Es werden nicht zufällige Bälle aus einer sortierten Reihe genommen, sondern man bildet eine unsortierte Reihe durch zufälliges Mischen und sagt dann: Es werden die ersten 6 genommen.

Für die Anordnung der 49 Bälle gibt es (siehe 1.1) Möglichkeiten.
Nehmen wir an die ersten 6 Bälle sind die Nummern 4, 6, 19, 32, 33, 41 (in dieser Reihenfolge). Dann käme das selbe "Endergebnis" zu Stande, wenn sie zum Beispiel die Reihenfolge 41, 33, 32, 4, 6, 19 hätten. Insgesamt gibt es Möglichkeiten die "auserwählten" Bälle anzuordnen.
Analog geht man für die restlichen, nicht gezogenen 43 Bälle vor: Für sie gibt es noch Möglichkeiten, angeordnet zu werden.
All diese Fälle werden zu viel gezählt, wenn man mit ansetzt.
Man muss also korrigieren und erhält: Möglichkeiten.
Zellerli Auf diesen Beitrag antworten »
3.2 Kombination mit Wiederholung
3.2 Modell "Urne mit verschieden farbigen Kugeln: -mal Ziehen mit Zurücklegen."
Kombination mit Wiederholung

Allgemein gibt es Möglichkeiten.

Diese Formel kann man erst auf den zweiten Blick nachvollziehen, mit dem richtigen Modell geht es jedoch ganz leicht.
Beispiel: Aus einer Urne mit 3 Kugeln, die die Farben rot, grün und blau haben, wird 5mal gezogen mit Zurücklegen.
Ein möglicher Fall ist zum Beispiel: (die erste Kugel ist rot, die zweite blau, die dritte blau, die vierte rot und die fünfte grün).
Weil die Reihenfolge egal ist, ist dieser Fall identisch mit zum Beispiel oder , wobei letzterer interessant ist, weil er sortiert ist:
Allgemein kann man jeden Fall so notieren, dass zuerst blau, dann grün, dann rot aufgeführt wird.
Man kann noch einen Schritt weitergehen und jeden Fall so notieren, dass zuerst eine 0 für jedesmal blau notiert wird, dann eine 1 (vorstellbar als "Trennwand"), dann eine 0 für jede grüne Kugel gefolgt von einer 1 und schließlich eine 0 für jede rote Kugel. Am Anfang und am Ende sind keine Trennwände, also keiner 1en nötig. Somit erhält man eine eindeutige Zuordnung.
Unser Beispielfall , der ja identisch ist mit , sieht dann so aus: .
Der Fall sähe zum Beispiel so aus: (der Raum für die roten Kugeln, nach der letzten Trennwand, ist leer.)
Der Fall sähe zum Beispiel so aus: (die ersten beiden Räume, also die für blau und grün, sind leer.)
Man erkennt: Es gibt immer 5 0en, weil 5mal gezogen wird. Und es gibt 2 1en, weil man um die 3 Farben zu trennen 2 Wände braucht (bei 17 Farben bräuchte man zum Beispiel 16 Wände).
Man muss also nur noch wissen wieviele Möglichkeiten es gibt, die 5 0en und die 2 1en auf die Stellen (oder besser: Stellen) anzuordnen.
Dieses Problem lässt sich auf 7 Spielkarten mit 2mal der Farbe "1" und 5mal der Farbe "0" zurückführen.
Und man erhält gemäß 1.2 Möglichkeiten, oder besser (wir wissen ja, dass die 2 die Anzahl der Trennwände ist um die 3 Farben zu trennen): .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »