Abzählende Kombinatorik

Zahl der Variationen und Kombinationen von 10 Elementen zur k-ten Klasse mit und ohne Wiederholung sowie der partiellen Derangements (fixpunktfreien Permutationen) von 10 Elementen. P*(10;k) – k-Permutationen oder Variationen mit Wiederholung; P(10;k) – k-Permutationen oder Variationen ohne Wiederholung; D(10;10-k) – partielle Derangements (bei denen nur k der 10 Elemente die Plätze wechseln); K*(10;k) – k-Kombinationen mit Wiederholung; K(10;k) – k-Kombinationen ohne Wiederholung.

Die abzählende Kombinatorik ist ein Teilbereich der Kombinatorik, der sich mit der Bestimmung der Anzahl möglicher Anordnungen oder Auswahlen

• unterscheidbarer oder nicht unterscheidbarer Objekte (d. h. „ohne“ bzw. „mit“ Wiederholung derselben Objekte) sowie
• mit oder ohne Beachtung ihrer Reihenfolge (d. h. „geordnet“ bzw. „ungeordnet“)

beschäftigt. In der modernen Kombinatorik werden diese Auswahlen oder Anordnungen auch als Abbildungen betrachtet, so dass sich die Aufgabe der Kombinatorik in diesem Zusammenhang im Wesentlichen darauf beschränken kann, diese Abbildungen zu zählen.

Für das Rechnen mit Wahrscheinlichkeiten auf der Basis des Wahrscheinlichkeitsbegriffs von Laplace bildet die Kombinatorik eine wichtige Grundlage.

Ein verblüffendes Phänomen der Kombinatorik ist, dass sich oftmals wenige Objekte auf vielfältige Weise kombinieren lassen. Beim Zauberwürfel können beispielsweise die 26 Elemente auf rund 43 Trillionen Arten kombiniert werden. Dieses Phänomen wird oft als kombinatorische Explosion bezeichnet und ist auch die Ursache für das so genannte Geburtstagsparadoxon.

Permutationen, Variationen und Kombinationen

→ Hauptartikel: Permutation, Variation (Kombinatorik) und Kombination (Kombinatorik)

Begriffsabgrenzungen

Aufgrund der Vielfalt der Herangehensweisen sind die Schreibweisen und Begrifflichkeiten im Bereich der Kombinatorik leider oft recht uneinheitlich. So bezeichnen übereinstimmend alle Autoren die Vertauschung der Reihenfolge einer Menge von $n$ unterscheidbaren Elementen als Permutation. Wählt man dagegen von diesen $n$ Elementen nur $k<n$ Elemente aus, deren Reihenfolge man anschließend vertauscht, bezeichnen viele Autoren das nun als Variation, geordnete Stichprobe bzw. Kombination mit Berücksichtigung der Reihenfolge, andere dagegen (namentlich im englischsprachigen Raum) weiter als Permutation. Lässt man schließlich in einer solchen Auswahl von Elementen deren Reihenfolge außer Acht, wird solch eine Auswahl nun für gewöhnlich ungeordnete Stichprobe, Kombination ohne Berücksichtigung der Reihenfolge oder einfach nur Kombination genannt. Kombinationen sind also, sofern nichts weiter zu ihnen gesagt wird, in der Regel ungeordnet, Permutationen und/oder Variationen dagegen geordnet, wobei die Frage, ob man Permutationen als Sonderfälle von Variationen (oder umgekehrt) betrachtet, gegebenenfalls von Autor zu Autor unterschiedlich beantwortet wird.

Alles in allem gibt es also zunächst einmal drei (oder auch nur zwei) verschiedene Fragestellungen, die ihrerseits noch einmal danach unterteilt werden, ob es unter den ausgewählten Elementen auch Wiederholungen gleicher Elemente geben darf oder nicht. Ist ersteres der Fall, spricht man von Kombinationen, Variationen oder Permutationen mit Wiederholung, andernfalls solchen ohne Wiederholung. Stellt man sich schließlich vor, dass die ausgewählten Elemente dabei einer Urne oder Ähnlichem entnommen werden, wird dementsprechend auch von Stichproben mit oder ohne Zurücklegen gesprochen:

	Ohne Wiederholung bzw. Zurücklegen	Mit Wiederholung bzw. Zurücklegen
Mit Berücksichtigung der Reihenfolge und k = n	Permutation ohne Wiederholung (engl. n-permutation)	Permutation mit Wiederholung
Mit Berücksichtigung der Reihenfolge und k < n	Variation ohne Wiederholung (engl. k-permutation)	Variation mit Wiederholung
Ohne Berücksichtigung der Reihenfolge und k < n	Kombination ohne Wiederholung (engl. k-combination)	Kombination mit Wiederholung

Anzahlen

Bezeichnet $n$ die Zahl der vorhandenen Elemente und $r,s,\ldots ,t$ die Zahl der Elemente, die nicht unterscheidbar sind, dann gilt für die Anzahl möglicher Permutationen:

	ohne Wiederholung $(a,b,c)$	mit Wiederholung $(a,a,b)$
Permutation $(a,b)\neq (b,a)$	$~n!~$	${\frac {(r+s+\ldots +t)!}{r!\cdot s!\cdot \ldots \cdot t!}}={\frac {n!}{r!\cdot s!\cdot \ldots \cdot t!}}$

Bezeichnet $n$ die Zahl der vorhandenen Elemente und $k$ die Zahl der Elemente, die ausgewählt werden, dann gilt für die Anzahl möglicher Variationen und Kombinationen:

	ohne Wiederholung $(a,b,c),\{a,b,c\}$	mit Wiederholung $(a,a,b),\{a,a,b\}$
Variation $(a,b)\neq (b,a)$	${n \choose k}\cdot {k!}={\frac {n!}{\left(n-k\right)!}}$	$~n^{k}~$
Kombination $\{a,b\}=\{b,a\}$	${n \choose k}={\frac {n!}{{\left(n-k\right)!}\cdot k!}}$	$\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {\left(n+k-1\right)!}{\left(n-1\right)!\cdot k!}}$

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1. 
• Karl Bosch: Elementare Einführung in die Wahrscheinlichkeitsrechnung. Vieweg, 2003, ISBN 3-528-77225-5. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1. 
• Joachim Hartung, Bärbel Elpelt, Karl-Heinz Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. Oldenbourg, 2005, ISBN 3-486-57890-1. 

Weblinks

Wiktionary: Kombinatorik – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Wikibooks: Algorithmensammlung: Statistik: Binomialkoeffizient – Lern- und Lehrmaterialien

• V.N. Sachkov: Combinatorial analysis. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 
• Modul Kombinatorik beim MathePrisma
• Empfehlungen zur Behandlung der Kombinatorik in der Schule (PDF; 230 kB)
• Abzählende Kombinatorik (PDF; 554 kB) Vorlesungsskript von Michael Stoll