Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 23. Juli 2019 

Kombinatorik


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Kombinatorik ist ein Teilgebiet der Mathematik das sich mit der Bestimmung der
  • Zahl möglicher Anordnungen oder Auswahlen von
  • unterscheidbaren oder nicht unterscheidbaren Objekten
  • mit oder ohne Beachtung der Reihenfolge
beschäftigt.

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

Inhaltsverzeichnis

Permutationen (Anordnungen)

Unterscheidbare Objekte mit Beachtung der Reihenfolge

Als einführendes Beispiel mag die Zahl Anordnungen von sechs unterscheidbaren Objekten mit Beachtung Reihenfolge dienen. Offensichtlich kann jedes der Objekte den ersten Platz gelangen" es gibt also Möglichkeiten den ersten Platz zu besetzen. Wenn erste Platz besetzt ist bleiben noch fünf für den zweiten Platz ist auch dieser nur noch vier Kandidaten für den dritten und so fort. Für den vorletzen Platz schließlich nur noch zwei Objekte übrig und letzte Platz muss mit dem "übriggebliebenen" Objekt werden.

Es gibt also 6 * 5 4 * 3 * 2 oder 6 = 720 Möglichkeiten sechs unterscheidbare Objekte anzuordnen. Ausrufezeichen steht für " Fakultät " und wird auch so gelesen also Fakultät". Allgemein:

Anzahl der Permutationen von <math>n</math> verschiedenen Elementen: n! </math>

Objekte mehrerer Klassen mit Beachtung der

Für die Zahl der möglichen Anordnungen Objekten aus mehreren Klassen die untereinander jeweils einer Klasse nicht unterscheidbar sind ist es zunächst die mögliche Zahl der Anordnungen der zu betrachten und dann zu überlegen wieviele Anordnungen nicht unterscheidbar sind. Die Zahl der Anordnungen bei unterscheidbaren Objekte wird durch die der nicht unterscheidbaren Anordnungen geteilt.

Wenn die mögliche Zahl von Anordnungen zwei Objekten einer ersten Klasse drei Objekten zweiten Klasse und fünf Objekten einer dritten ermittelt werden soll dann gibt es zunächst + 3 + 5)! oder 3.628.800 mögliche Weil aber Anordnungen nicht unterscheidbar sind bei nur Objekte einer Klasse untereinander den Platz haben weil also jeweils 2! * 3! 5! oder 1.440 der möglichen Anordnungen gleich gibt es nur 3.628.800/1.440 oder 2.520 unterscheidbare dieser Elemente. Allgemein:

Anzahl der Permutationen von <math>n</math> Elementen die <math>k</math> Gruppen von je <math>l_1 l_2 ... gleichen Elementen <math>(\sum^k_{i=1} l_i = n)</math> fallen: l_2!...l_k!}</math>

Auswahlen mit Beachtung der Reihenfolge (Variationen)

Variation ohne Zurücklegen

<math> \frac{n!}{(n-k)!} </math>

Ein wissenschaftlicher Taschenrechner erspart hierbei durch die Funktion(staste) " nPr " viel Tipparbeit: i.d.R. Eingabe n -Wert Taste " nPr " Eingabe k -Wert Taste " = ".

Variation mit Zurücklegen

Wenn aus n Objekten k Objekte Zurücklegen und mit Beachtung der Reihenfolge ausgewählt sollen dann kann jedes der n Objekte jedem der k Plätze der Auswahl erscheinen gibt demzufolge

<math>n^k</math> mögliche Auswahlen.

Wenn also aus 3 Objekten 11 mit Zurücklegen gezogen wird dann sind 3^11 177.147 verschiedene Auswahlen möglich. Als Beispiel aus Genetik mag die Anzahl möglicher 3-er Tupel Codons ) bei 4 verschiedenen Nukleotidbasen dienen: 4^3 64; die tatsächliche Anzahl kodierter Aminosäuren ist geringer (22 (plus Start- und dar der genetische Code degeneriert ist.

Auswahlen ohne Beachtung der Reihenfolge (Kombinationen)

Im Gegensatz zu den Variationen werden den Kombinationen die Anordnungen außer acht gelassen "abc" ist gleichwertig mit "bca". Es muss weniger Kombinationen als Variationen geben.

Kombination ohne Zurücklegen

Auswahlprobleme ohne Zurücklegen können als Anordungsprobleme werden. Die Zahl der möglichen Auswahlen kann werden indem die Zahl der Anordnungen ermittelt bei denen die ausgewählten Objekte auf ausgezeichneten angeordnet sind.

Dieses Auswahlproblem kann auf die Ermittlung Anordnungen zurückgeführt werden bei denen die ausgewählten auf den ersten Plätzen landen wobei es bei den ausgewählten noch bei den nicht Objekten auf die Reihenfolge ankommt.

Wenn aus n Objekten k ohne und ohne Beachtung der Reihenfolge ausgewählt werden so gibt es jeweils die Klasse der ausgewählten Objekte und die Klasse der (n-k) ausgewählten Objekte in der es auf die nicht ankommt.

Demzufolge gibt es <math>{n \choose k} = (n-k)!} </math> mögliche derartige Auswahlen.

Dieser häufig benötigte Ausdruck wird als Binomialkoeffizient bezeichnet.

Wenn aus 49 Objekten nun 6 Zurücklegen und ohne Beachtung der Reihenfolge ausgewählt sollen wie dies z.B. bei der Ziehung Lottozahlen der Fall ist so gibt es mögliche Auswahlen.

Ein wissenschaftlicher Taschenrechner erspart hierbei durch die Funktion(staste) " nCr " viel Tipparbeit: i.d.R. Eingabe n -Wert Taste " nCr " Eingabe k -Wert Taste " = ".

Kombination mit Zurücklegen

<math> {n+k-1 \choose k} = \frac{(n+k-1)!}{k! (n-1)!}</math>
Eine Anwendung davon ist das Gummibärchen Dort wählt man 5 Bärchen von 5 aus (5 Farben). Demnach gibt es 126 Kombinationen.

Weitere Informationen

Siehe auch

Lateinisches Quadrat

Weblinks



Bücher zum Thema Kombinatorik

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Kombinatorik.html">Kombinatorik </a>