Ing Mathematik: Permutationen, Kombinationen, binomischer Lehrsatz

Zurück zu Vollständige Induktion | Hoch zu Gesamtinhaltsverzeichnis | Vor zu Vektoren

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{cases}1,&n=0,\\n\cdot (n-1)!,&n>0.\end{cases}}$

Siehe auch  Fakultät (Mathematik).

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  Permutation.

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+3ab^{2}+b^{3}$

etc.

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

Binomialkoeffizient

"n über k":

${\begin{aligned}{\binom {n}{k}}&={\frac {n!}{k!(n-k)!}}\end{aligned}}$

Siehe auch  Binomialkoeffizient.

Binomische Formel

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

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

Siehe auch  Pascalsches Dreieck,  Binomischer Lehrsatz.

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.

${\overline {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 $\neq$ 00010 etc.). Somit gibt es ${\overline {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  Variation_(Kombinatorik).

Kombinationen

Kombinationen ohne Wiederholungen

Kombinationen ohne Wiederholungen sind ungeordnete Stichproben ohne Zurücklegen.

$K_{n,k}={\binom {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}={\binom {46}{5}}={\frac {46!}{5!(46-5)!}}=1370754$.

Kombinationen mit Wiederholungen

Kombinationen mit Wiederholungen sind ungeordnete Stichproben mit Zurücklegen.

${\overline {K}}_{n,k}={\binom {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 ${\overline {K}}_{10,5}={\binom {10+5-1}{5}}={\binom {14}{5}}={\frac {14!}{5!(14-5)!}}=2002$ Möglichkeiten.

Siehe auch  Kombination (Kombinatorik).

Siehe allgemein auch  Abzählende Kombinatorik.

Zurück zu Vollständige Induktion | Hoch zu Gesamtinhaltsverzeichnis | Vor zu Vektoren