Aus Online Mathematik Brückenkurs 1

Kombinatorik

A - Permutationen

Permutationen sind die Möglichkeiten die eine Anordnung von Gegenständen zu Vertauschen, also die Anzahl der Weisen Objekte anzuordnen.

Allgemein: Für eine Gruppe von n Elementen gibt es \displaystyle n! := n (n-1) (n-2) … \cdot 3 \cdot 3 \cdot 2 \cdot 1 Möglichkeiten („n Fakultät“) die Objekte hintereinander anzuordnen (n! Permutationen). Zusätzliche Definition : \displaystyle 0! := 1 .

Beispiele: (1)Möglichkeiten der Anordnung von \displaystyle a, m, b, u ? \displaystyle 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 (2)\displaystyle \dfrac{5!}{3!} = \dfrac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 5 \cdot 4 (3)\displaystyle \dfrac{(n+1)!}{(n-1)!} = \dfrac {(n+1) n (n-1) (n-2) \cdot ... \cdot 2 \cdot 1}{(n-1)(n-2) \cdot …. \cdot 2 \cdot 1} = (n+1) n (4)\displaystyle 2n! = 2 \cdot n \cdot (n-1) \cdot … \cdot 2 \cdot 1 \displaystyle (2n)! = 2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1

Stichproben aus n- elementigen Mengen:

Beispiel 1: Wie viele Worte mit 4 Buchstaben kann ich mit den Buchstaben A, R, T, E, N und S bilden? (mit Doppelbenutzung) 1. Buchstabe 2. Buchstabe 3. Buchstabe 4. Buchstabe 6 Möglichkeiten 6 Möglichkeiten 6 Möglichkeiten 6 Möglichkeiten

Also gibt es \displaystyle 6 \cdot 6 \cdot 6 \cdot 6 = 6^4 Möglichkeiten.

Allgemein: Es gibt \displaystyle n^k Möglichkeiten der Anordnung, die beim k- maligen Auswählen aus n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge entstehen können.

Beispiel 2: Wie vorher nur ohne Doppelbenutzung.

1.Ziehen : 6 Möglichkeiten 2.Ziehen : 5 Möglichkeiten 3.Ziehen : 4 Möglichkeiten 4.Ziehen : 3 Möglichkeiten insgesamt: \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 Möglichkeiten. \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{6!}{2!} = \dfrac{6!}{(6-4)!}

Allgemein: Es gibt \displaystyle n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \dfrac{n!}{(n-k)!} Möglichkeiten aus n Objekten k Stück unter Berücksichtigung der Reihenfolge und ohne Zurücklegen auszusuchen.

Beispiel 3: „Lotto“ mit Reihenfolge

Anzahl der Möglichkeiten: $\backslash dfrac\{49!\}\{(49-6)!\}\; =\; 49\; \backslash cdot\; 48\; \backslash cdot\; 47\; \backslash cdot\; 46\; \backslash cdot\; 45\; \backslash cdot\; 44\; \backslash approx\; 10\; \backslash cdot\; 10^9\; (*)$

Aber: Die Reihenfolge ist bei echtem Lotto unwichtig. Für sechs feste Zahlen sind 6! Kombinationen in (*) enthalten.

Beispiel 4: Also: „echtes“ Lotto \displaystyle \dfrac{49!}{(49-6)!} \cdot \dfrac{1}{6!} = \dfrac{49!}{(49-6)!6!} = (49 6) \approx 13 \cdot 10^6 Möglichkeiten.

Auswahlmöglichkeiten für k aus n Elementen ohne Zurücklegen und ohne Reihenfolge:

\displaystyle (n k) = \dfrac{n!}{(n-k)!k!} „Binomialkoeffizient“

mit n /in N , k /in N , n /ge k