Ing Mathematik: Permutationen, Kombinationen, binomischer Lehrsatz

Hier soll eine Einführung in die abzählende Kombinatorik gegeben werden. Dabei stehen Anordnungs- oder Auswahlmöglichkeiten im Mittelpunkt der Betrachtungen.

Permutationen

Permutationen stellen Anordnungsmöglichkeiten dar.

Fakultät

Der Ausdruck $n!=1\cdot 2\cdot 3\cdots n=\prod _{i=1}^{n}i$ wird "n Fakultät" genannt.

Per Definition gilt $0!=1$

Rekursive Definition:

$n!=\{\begin{array}{cc}1,& n=0,\\ n\cdot (n-1)!,& n>0.\end{array}$

Siehe auch Vorlage:W.

Permutationen ohne Wiederholungen

Beispiel: In welchen Reihenfolgen lassen sich eine rote, eine grüne und eine blaue Kugel anordnen? Nachfolgend ist das grafisch dargestellt

In eine Formel umgemünzt gibt es also 6 Möglichkeiten $P_3=3\cdot 2\cdot 1=3!$.

Allgemein gilt also

$P_n=n!$

Permutationen mit Wiederholungen

Gibt es mehrere gleiche (nicht unterscheidbare) Elemente, so gibt es

$P_{n;k_1,k_2,\cdots ,k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}$

Möglichkeiten.

An einem Beispiel grafisch dargestellt:

Siehe auch Vorlage:W.

Binomische Formel

Pascalsches Dreieck

• 
  Pascalsches Dreieck
• 
  Blaise Pascal (1623 - 1662) französischer Mathematiker und Physiker

$(a+b{)}^0=1$

$(a+b{)}^1=a+b$

$(a+b{)}^2=(a+b)(a+b)=a^2+2ab+b^2$

$(a+b{)}^3=(a+b)(a+b)(a+b)=a^3+3a^{2}b+3a{b}^2+b^3$

etc.

Übung: Berechnen Sie $(a+b{)}^4$ mittels pascalschem Dreieck.

Binomialkoeffizient

"n über k":

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k})& =\frac{n!}{k!(n-k)!}\end{array}$

Siehe auch Vorlage:W.

Binomische Formel

$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$

Übung: Beweisen Sie die binomische Formel mittels vollständiger Induktion.

Siehe auch Vorlage:W, Vorlage:W.

Variationen

Variationen ohne Wiederholungen

Variationen ohne Wiederholungen sind geordnete Stichproben ohne Zurücklegen. Man zieht also k Kugeln aus einer Gesamtheit von n Kugeln.

$V_{n,k}=\frac{n!}{(n-k)!}$

Beispiel: Ein Team besteht aus 10 Personen (diese sind Universalisten, alle können also alles gleich gut). Daraus sollen ein CAD-Konstrukteur, ein Projektleiter und ein Abwickler ausgewählt werden. Wieviele Möglichkeiten gibt es?

Es werden also Personen aus einer "Urne" gezogen. Das Problem entspricht einer Stichprobe ohne Zurücklegen (eine Person kann nur eine Tätigkeit ausüben). Die Stichprobe ist geordnet (Projektleiter ist etwas anderes als CAD-Konstrukteur oder Abwickler etc). Es gibt also $V_{10,3}=\frac{10!}{(10-3)!}=720$ Möglichkeiten.

Variationen mit Wiederholungen

Variationen mit Wiederholungen sind geordnete Stichproben mit Zurücklegen.

${\bar{V}}_{n,k}=n^k$

Beispiel: Sie fertigen KFZ-Kennzeichen. Ihr Auftraggeber will 5-stellige Kennzeichen mit Ziffern aus 0 bis 9. Wieviele Möglichkeiten gibt es, verschiedene Kennzeichen anzufertigen? D.h. also 00000; 00001; 00002; 00003; ...; 99998; 99999.

Es ist dies ein Ziehen mit Zurücklegen (es können Ziffern mehrfach vorkommen). Außerdem ist das Problem geordnet (00001 $\ne$ 00010 etc.). Somit gibt es ${\bar{V}}_{10,5}=10^5=100000$ Möglichkeiten. Mit scharfen Blick hätte man das Ergebnis auch direkt aus der Aufgabenstellung erkennen können (99999 Stück + die 5-fache 0 = 100000). Aber würde man statt Ziffern z.B. Buchstaben nehmen, dann wäre das nicht mehr so offensichtlich.

Siehe auch Vorlage:W.

Kombinationen

Kombinationen ohne Wiederholungen

Kombinationen ohne Wiederholungen sind ungeordnete Stichproben ohne Zurücklegen.

$K_{n,k}=(\genfrac{}{}{0ex}{}{n}{k})$

Beispiel: Klassisches Beispiel ist hier das Lotto-Spiel, z.B. 5 aus 46. 5 Kugeln mit Ziffern zwischen 1 und 46 werden aus einer Urne gezogen. Wieviele Möglichkeiten gibt es?

Es handelt sich hier um eine ungeordnete Stichprobe (es ist egal in welcher Reihenfolge die Zahlen gezogen werden). Es erfolgt kein Zurücklegen der Kugeln (es darf also keine Zahl doppelt aufscheinen). Die Lösung ist $K_{46,5}=(\genfrac{}{}{0ex}{}{46}{5})=\frac{46!}{5!(46-5)!}=1370754$.

Kombinationen mit Wiederholungen

Kombinationen mit Wiederholungen sind ungeordnete Stichproben mit Zurücklegen.

${\bar{K}}_{n,k}=(\genfrac{}{}{0ex}{}{n+k-1}{k})$

Beispiel: Ein Drehautomat hat 5 Werkzeughalter. Insgesamt gibt es 10 verschiedene Werkzeugtypen. Es können auch gleiche Werkzeuge an verschiedenen Werkzeughaltern angebracht werden. Die Reihenfolge der Belegung ist egal. Wie viele Möglichkeiten gibt es, den Drehautomaten mit Werkzeugen zu bestücken?

Dieses Beispiel entspricht einer Stichprobe mit Zurücklegen (gleiche Werkeuge können verwendet werden). Die Stichprobe ist ungeordnet. Somit gibt es ${\bar{K}}_{10,5}=(\genfrac{}{}{0ex}{}{10+5-1}{5})=(\genfrac{}{}{0ex}{}{14}{5})=\frac{14!}{5!(14-5)!}=2002$ Möglichkeiten.

Siehe auch Vorlage:W.

Siehe allgemein auch Vorlage:W.

Vorlage:Navigation zurückhochvor buch