Quelltext der Seite Abzählende Kombinatorik

[[Datei:Kombinationen und Variationen.png|mini|330px|Zahl der Variationen und Kombinationen von 10 Elementen zur k-ten Klasse und der partiellen Derangements (fixpunktfreie Permutationen) von 10 Elementen.<br />'''P*(10;k)'''&nbsp;k-Permutationen oder Variationen mit Wiederholung<br />'''P(10;k)'''&nbsp;k-Permutationen oder Variationen ohne Wiederholung<br />'''K*(10;k)'''&nbsp;k-Kombinationen mit Wiederholung<br />'''K(10;k)'''&nbsp;k-Kombinationen ohne Wiederholung<br />'''D(10;10-k)'''&nbsp;partielle Derangements<br />(bei denen nur k der 10 Elemente die Plätze wechseln)]]

Die '''abzählende Kombinatorik''' ist ein Teilbereich der [[Kombinatorik]]. Sie beschäftigt sich mit der Bestimmung der [[Anzahl]] möglicher Anordnungen oder Auswahlen
* unterscheidbarer oder nicht unterscheidbarer [[Mathematisches Objekt|Objekte]] (d.&nbsp;h. „ohne“ bzw. „mit“ Wiederholung derselben Objekte) sowie
* mit oder ohne Beachtung ihrer [[Reihenfolge]] (d.&nbsp;h. „geordnet“ bzw. „ungeordnet“).

In der modernen Kombinatorik werden diese Auswahlen oder Anordnungen auch als [[Funktion (Mathematik)|Abbildungen]] betrachtet, so dass sich die Aufgabe der Kombinatorik in diesem Zusammenhang im Wesentlichen darauf beschränken kann, diese Abbildungen zu zählen.

== Anwendungen ==
Für das Rechnen mit [[Wahrscheinlichkeit]]en auf der Basis des [[Wahrscheinlichkeitsbegriff]]s von [[Pierre-Simon Laplace|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 [[Trillion]]en Arten kombiniert werden. Dieses Phänomen wird oft als ''kombinatorische Explosion'' bezeichnet und ist auch die Ursache für das [[Geburtstagsparadoxon]].

== Permutationen, Variationen und Kombinationen ==
{{Hauptartikel|Permutation|Variation (Kombinatorik)|Kombination (Kombinatorik)}}

=== Begriffsabgrenzungen ===
Aufgrund der vielfältigen Herangehensweisen sind die Schreibweisen und Begrifflichkeiten in der Kombinatorik oft recht uneinheitlich. Zwar bezeichnen übereinstimmend alle Autoren die Vertauschung der Reihenfolge einer Menge von <math>n</math> unterscheidbaren Elementen als ''Permutation''. Wählt man dagegen von diesen <math>n</math> Elementen nur <math>k < n</math> Elemente in einer bestimmten Reihenfolge aus, bezeichnen viele Autoren das als ''Variation'' oder ''geordnete Stichprobe'', 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'' oder ''Kombination'' genannt. Kombinationen sind also, sofern nichts weiter zu ihnen gesagt wird, in der Regel ungeordnet, Permutationen und Variationen dagegen geordnet, wobei die Frage, ob man Permutationen als Sonderfälle von Variationen 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 [[Urnenmodell|Urne]] oder Ähnlichem entnommen werden, wird dementsprechend auch von ''Stichproben mit oder ohne Zurücklegen gesprochen''.

{| class="wikitable"
|+ Übersicht der Terminologie
|-
!rowspan=2 colspan=3| 
! Elemente paarweise verschieden !! Elemente können mehrfach vorkommen 
|-
! ohne Zurücklegen, <br>ohne Wiederholung !! mit Zurücklegen, <br>mit Wiederholung
|-
!rowspan=2| geordnete Stichprobe, <br>mit Berücksichtigung der Reihenfolge, <br>d.&nbsp;h. Reihenfolge relevant
! <math>k = n</math>
| Permutation
| [[Permutation#Permutation ohne Wiederholung|Permutation ohne Wiederholung]]<br>(engl. ''n-permutation'') 
| [[Permutation#Permutation mit Wiederholung|Permutation mit Wiederholung]]<br>(engl. ''n-tuple'') 
|-
!rowspan=2| <math>k < n</math>
| Variation
| [[Variation (Kombinatorik)#Variation ohne Wiederholung|Variation ohne Wiederholung]]<br>(engl. ''k-permutation'') 
| [[Variation (Kombinatorik)#Variation mit Wiederholung|Variation mit Wiederholung]]<br>(engl. ''k-tuple'') 
|-
! ungeordnete Stichprobe, <br>ohne Berücksichtigung der Reihenfolge, <br>d.&nbsp;h. Reihenfolge irrelevant
| Kombination
| [[Kombination (Kombinatorik)#Kombination ohne Wiederholung|Kombination ohne Wiederholung]]<br>(engl. ''k-combination'') 
| [[Kombination (Kombinatorik)#Kombination mit Wiederholung|Kombination mit Wiederholung]]<br>(engl. ''k-multiset'') 
|}

=== Anzahlen ===
Im Folgenden bezeichnet <math>n</math> die Zahl der vorhandenen Elemente und <math>k</math> die Zahl ausgewählten Elemente bzw. <math>k_1, \ldots, k_s</math> die jeweiligen Anzahlen der Elemente, die nicht unterscheidbar sind.

{| class="wikitable"
|+ Anzahl möglicher Permutationen, Variationen und Kombinationen
! &nbsp;
! ohne Wiederholung <br><math>(a,b,c), \{a,b,c\}</math>
! mit Wiederholung <br><math>(a,a,b), \{a,a,b\}</math>
|-
!rowspan=2| Permutationen <br><math>(a,b) \ne (b,a)</math>
| <math>~n!~</math>
| <math>\frac{(k_1 + \ldots + k_s)!}{k_1! \cdot \ldots \cdot k_s!} = \frac{n!}{k_1! \cdot \ldots \cdot k_s!}= \binom{n}{k_1, \ldots , k_s}</math>
|-
| → [[Fakultät (Mathematik)|Fakultät]]
| → [[Multinomialtheorem|Multinomial]]
|-
!rowspan=2| Variationen <br><math>(a,b) \ne (b,a)</math>
| <math>n^{\underline{k}} = {n \choose k}\cdot {k!} = \frac{n!}{ \left( n-k \right) !}</math>
| <math>~n^k~</math>
|-
| → [[Fallende und steigende Faktorielle|Fallende Fakultät]]
| → [[n-Tupel|k-Tupel]]
|-
!rowspan=2| Kombinationen <br><math>\{a,b\} = \{b,a\}</math>
| <math>{n \choose k} = \frac{n!}{{\left( n-k \right) !} \cdot k!}</math>
| <math>\left(\!\!{n \choose k}\!\!\right) = {n + k -1 \choose k} = \frac{ \left( n + k -1 \right)! }{{\left( n-1 \right)! \cdot k!} }</math>
|-
| → [[Menge (Mathematik)|Mengen]] (k-Teilmengen)
| → [[Multimenge#Anzahl der möglichen Multimengen|Multimengen]]
|}

== Bälle und Fächer ==
Eine Verallgemeinerung des Urnenmodells ist ein von [[Gian-Carlo Rota]] popularisiertes Modell mit Bällen und Fächern, im Englischen nach einem Vorschlag von [[Joel H. Spencer|Joel Spencer]] auch ''Twelvefold Way'' („Zwölffacher Weg“) genannt.<ref>[[Richard P. Stanley]]: ''Enumerative combinatorics'' (Band 1), Cambridge University Press, 2. Auflage 2012, ISBN 978-1-107-01542-5, S. 79 ff. und 107 f. (englisch; Stanleys Webseite zum Buch mit der letzten Vorabversion und Errata als PDF: ''[http://www-math.mit.edu/~rstan/ec/ec1/ Enumerative Combinatorics, volume 1, second edition]'')</ref><ref>Aigner: ''Diskrete Mathematik'', 2006, [http://books.google.de/books?id=HZMpSNv1rncC&pg=PA10 S. 10]</ref> Gesucht ist dabei die Anzahl der Möglichkeiten, <math>k</math> Bälle auf <math>n</math> Fächer zu verteilen, wobei die Bälle und Fächer jeweils entweder unterscheidbar oder nicht unterscheidbar sind und entweder keine weitere Bedingung gilt oder in jedes Fach höchstens ein Ball kommen darf oder mindestens ein Ball kommen muss. Man erhält folgende Übersicht:

{| class="wikitable" style="text-align:center;"
! <math>k</math> Bälle
! <math>n</math> Fächer
!colspan="3"| Beschränkung auf Anzahl der Bälle pro Fach
|-
!colspan="2"| unterscheidbar?
! —
! max. 1
! mind. 1
|-
! <math>\checkmark</math>
! <math>\checkmark</math>
| <math>n^k</math>
| <math>n^{\underline{k}} = \tfrac{n!}{(n-k)!} = k!\,\tbinom{n}{k}</math>
| <math>n!\,S_{k,n}</math>
|-
! <math>\times</math>
! <math>\checkmark</math>
| <math>\left(\!\!\tbinom{n}{k}\!\!\right)=\tbinom{k+n-1}{n-1}</math>
| <math>\tbinom{n}{k}</math>
| <math>\left(\!\!\tbinom{n}{k-n}\!\!\right)=\tbinom{k-1}{n-1}</math>
<!-- Spalten werden außerdem weggelassen, da nicht zur 12fold Way gehört (zu viele Verallgemeinerungen möglich) -->
<!-- zw. 0 und c-1 // zw. 1 und c. Eine Quelle muss noch gefunden werden: -->
<!--
|style="text-align:left"| <math>\sum_{r=0}^{n}(-1)^{r}\tbinom{n}{r}\left(\!\!\tbinom{n}{k-rc}\!\!\right)</math>
|style="text-align:left"| <math>\sum_{r=0}^{n}(-1)^{r}\tbinom{n}{r}\left(\!\!\tbinom{n}{k-rc}\!\!\right)^{+}</math>
-->
|-
! <math>\checkmark</math>
! <math>\times</math>
| <math>\sum_{r=0}^{n}S_{k,r}</math>
| <math>\begin{array}{lll} 1 &: &k\leq n \\ 0 &: &k>n \end{array}</math>
| <math>S_{k,n}</math>
|-
! <math>\times</math>
! <math>\times</math>
| <math>\sum_{r=0}^{n}P_{k,r} = P_{k+n,n}</math>
| <math>\begin{array}{lll} 1 &: &k\leq n\\ 0 &: & k>n \end{array}</math>
| <math>P_{k,n}</math>
|}

Dabei ist <math>S_{k,n}</math> die Anzahl der Möglichkeiten, eine <math>k</math>-elementige Menge in <math>n</math> nichtleere disjunkte Teilmengen aufzuteilen ([[Stirling-Zahl]] zweiter Art), und <math>P_{k,n}</math> die Anzahl der Möglichkeiten, die Zahl <math>k</math> als Summe von <math>n</math> positiven ganzen Zahlen ohne Beachtung der Reihenfolge darzustellen (siehe [[Partitionsfunktion]]).

== Äquivalente Darstellungen ==
Wird in einem diskreten Wahrscheinlichkeitsraum <math>(\Omega,P)</math> die Anzahl der möglichen Ereignisse durch eine der obigen kombinatorischen Formeln gegeben, dann können über die vollständige Zerlegung des Ereignisraums äquivalente Darstellungen für sie abgeleitet werden. Die folgenden beiden Modelle verdeutlichen dies. Es werden <math>k</math> Bälle zufällig auf <math>n \le k</math> Fächer verteilt. Man betrachte die Ereignisse <math>E_{j}</math>, dass <math>j</math> Fächer, <math>j=1, \ldots ,n</math>, mindestens einen Ball enthalten unter der Prämisse:
# Kein Ball wird von vornherein einem Fach zugeordnet.
# Jeder Ball wird von vornherein einem Fach zugeordnet, kann aber in einem anderen Fach landen.

Der erste Fall entspricht der Variante „nicht unterscheidbare Bälle, unterscheidbare Fächer“. Die vollständige Zerlegung des Ereignisraums in die disjunkten Ereignisse <math>E_{j}</math> ergibt dann

:<math>|\Omega| = \binom {n+k-1} {k} = \sum_{j=1}^ {n} \binom {n} {j} \binom {k-1} {k-j}</math>.

Der zweite Fall entspricht der Variante „unterscheidbare Bälle, unterscheidbare Fächer“. Die vollständige Zerlegung des Ereignisraums analog zum ersten Fall ergibt die äquivalente Darstellung

:<math>|\Omega| = n^k = \sum_{j=1}^{n} \binom{n}{j} \sum_{i=0}^{j-1} (-1)^{i} \binom{j}{j-i} (j-i)^{k} = 
                        \sum_{j=1}^n \binom{n}{j} (-1)^j \sum_{i=1}^j (-1)^{i} \binom{j}{i} i^k</math>,

wobei sich die zweite Summe durch Umkehrung der Summierungsreihenfolge (bzw. <math>i \to j-i</math>) aus der ersten ergibt.

Für <math>n=k</math> ist das Ereignis, dass alle Fächer mindestens einen Ball besitzen, gleich dem Ereignis, dass alle Fächer genau einen Ball besitzen, und enthält <math>n!</math> Elemente. Daraus folgt

:<math>n! = \sum_{i=0}^{n-1}(-1)^{i}\binom{n}{n-i}(n-i)^{n} = (-1)^n\sum_{i=1}^n(-1)^i\binom{n}{i}i^n</math>.

== Literatur ==
* {{Literatur
   |Autor=[[Martin Aigner]]
   |Titel=Diskrete Mathematik
   |Verlag=Vieweg
   |Datum=2006
   |ISBN=3-8348-9039-1}}
* {{Literatur
   |Autor=[[Karl Bosch (Statistiker)|Karl Bosch]]
   |Titel=Elementare Einführung in die Wahrscheinlichkeitsrechnung
   |Verlag=Vieweg
   |Datum=2003
   |ISBN=3-528-77225-5}}
* {{Literatur
   |Autor=[[Norbert Henze]]
   |Titel=Stochastik für Einsteiger
   |Verlag=Springer Spektrum
   |Datum=2013
   |ISBN=978-3-658-03076-6
   |DOI=10.1007/978-3-658-03077-3}}
* {{Literatur
   |Autor=[[Konrad Jacobs]], [[Dieter Jungnickel]]
   |Titel=Einführung in die Kombinatorik
   |Verlag=de Gruyter
   |Datum=2003
   |ISBN=3-11-016727-1}}
* {{Literatur
   |Autor=[[Joachim Hartung]], Bärbel Elpelt, Karl-Heinz Klösener
   |Titel=Statistik: Lehr- und Handbuch der angewandten Statistik
   |Verlag=Oldenbourg
   |Datum=2005
   |ISBN=3-486-57890-1}}

== Weblinks ==
{{Wiktionary|Kombinatorik}}
{{Wikibooks|Algorithmensammlung: Kombinatorik: Binomialkoeffizient}}
* {{EoM|Autor=V.N. Sachkov|Titel=Combinatorial analysis|Url=http://eom.springer.de/c/c023250.htm}}
* [http://www.matheprisma.uni-wuppertal.de/Module/Kombin/ Modul Kombinatorik] beim MathePrisma
* Michael Stoll: [https://www.mathe2.uni-bayreuth.de/stoll/vorlesungen/Kombinatorik-WS1999.pdf Abzählende Kombinatorik] (PDF; 554&nbsp;kB) Vorlesungsskript
* [http://www.stefanbartz.de/dateien/Kombinatorik.pdf Empfehlungen zur Kombinatorik in der Schule] (PDF; 612&nbsp;kB) aus: ''Stochastik in der Schule'', 33, 2013, 1, S.&nbsp;21–25

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4132720-2}}

{{SORTIERUNG:Abzahlende Kombinatorik}}
[[Kategorie:Kombinatorik| Abzahlende Kombinatorik]]
[[Kategorie:Teilgebiet der Mathematik]]