TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/12. VO 09.11.2005

Permutationen: lineare Anordnungen einer Menge A

$A=\{a_{1},...,a_{n}\}$ ... n wohlunterscheidbare Objekte

$\#{\text{Perm. von A }}=:P_{n}$ (# ... Anzahl)

  n n-1 n-2 n-3 ... ... 1 = $P_{n}$ = 1*2*3*...*n =: n!

n! .... "n-Faktorielle" oder "n-Fakultät"

$\{a_{1},a_{1},...,a_{2},a_{2},...,....,a_{r},...a_{r}\}$

Zusammengefasst: $K_{1},K_{2},K_{3},...K_{r}$

$K_{1}+K_{2}+...K_{r}=n$ - eine Zusammenfassung von $K_{1}{\text{ Elemente }}a_{1},K_{2}{\text{ Elemente }}a_{2},...,K_{r}{\text{ Elemente }}a_{r}$ heißt Multimenge.

Eine Permutation mit Wiederholung ist die Anordnung einer Multimenge

Beispiel: $A=\{B,B,W\}$ (A ist eine Multimenge)

Möglichkeiten der Anordnungen: BBW BWB WBB

Behauptung: # verschiedener Anordnungen einer Multimenge A (mit $K_{1}+...+K_{r}=n$

$P_{n}^{K_{1},K_{2},...,K_{r}}={\frac {n!}{K_{1}!*K_{2}!*...*K_{r}!}}$

$P_{3}{2,1}={\frac {3!}{2!*1!}}=3$

Beweis: Insgesamt gibt es n! Anordnungen von n Elementen.

Es fallen aber jeweils $K_{1}!*K_{2}!*...*K_{r}!$ Permutationen zusammen (weil es nicht auf die Anordnung der $K_{1}$ Elemente $a_{1}$, $K_{2}$ Elemente $a_{2}$, ... , $K_{r}$ Elemente $a_{r}$ ankommt).

$P_{n}{K_{1},K_{2},...,K_{r}}={\frac {n!}{K_{1}!*K_{2}!*...*K_{r}!}}$

Binominalkoeefizient: ${\begin{pmatrix}n\\k\end{pmatrix}}={\frac {n*(n-1)*...*(n-K+1)}{K!}}={\frac {n!}{K!*(n-K)!}}$

"n über k"

Konvention: 0! := 1

Pascal'sches Dreieck:

  n         => K           Summe
  0           1               1
  1         1   1             2
  2       1   2   1           4
  3     1   3   3  1          8
  4   1   4   6   4  1       16
  5 1   5   10  10  5  1     32

${\begin{pmatrix}n\\k\end{pmatrix}}+{\begin{pmatrix}n\\k+1\end{pmatrix}}={\begin{pmatrix}n+1\\k+1\end{pmatrix}}$

$\sum _{k=0}{n}{\begin{pmatrix}n\\k\end{pmatrix}}=2^{n}$

Betrachte Binom $(a+b)^{n}$

n-te Potenz

Entwickeln?

Beispiel: $(a+b)^{2}=1*a^{2}+2ab+1b^{2}$

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

(Pascal'sches Dreieck)

$(a+b)^{n}=(a+b)*(a+b)*...*(a+b)$ (n Mal)

$=\sum _{K=0}^{n}{\begin{pmatrix}n\\k\end{pmatrix}}*a^{k}*b^{n-k}$

Multimenge A = $\{a,a,..a,b,b,...,b\}$

a entspr. n, b entspr. n-k

$\#$ ANordung von A = $P_{n}^{k*(n-k)^{k}}={\frac {n!}{k!*(n-k!)}}$

(Nachtrag hier und oben)

Betrachte n-elementige Menge A

Betrachte "Auswählen"

• Eine "Variation"

  (K-Permutation)
  (Variation ohne Wiederholung)

ist ein geordnetes K-Tupel $a_{1},...,a_{k}$ von verschiedenen Elementen aus A.

1. Variationen =: $V_{n}^{k}$

$V_{n}^{k}$ ... Variationen von n zur k-ten Klasse

$V_{n}^{k}=n*(n-1*...*(n-k+1)={\frac {n!}{(n-k!)}}$

  n n-1 n-2 ... n-k+1
 a_1 a_2 ...     a_k

Beispiel: Elemente (= Buchstaben ) "W","I","E","N"

Gesucht: # der versch. Wörter, die man aus 3 der 4 Buchstaben bilden kann (ohne Wiederholung)

$V_{4}^{3}=4*3*2=24$

• Eine "Variation" mit Wiederholung ist ein geordnetes k-Tupel von nicht notwendigerweise verschiedenen Elementen aus A.

1. Var. mit Wiederh. = $^{W}V_{n}^{k}=n^{k}$

  n   n   n     = n^k  
  a1  a2  a_k

Beispiel: Fussballtoto ... 12 Tips, Möglichkeiten "1","2","X"

n = 3, k = 12

Anzahl versch. Totoscheine: $^{W}V_{3}^{12}=3^{12}$

• Eine "Kombination" (Komb. ohne Wiederholungen) ist ein ungeordnetes k-Tupel von verschiedenen Elementen aus A

$\#$ Kombinationen =: $C_{n}^{k}$

$C_{n}^{k}*k!=V_{n}^{k}\Rightarrow C_{n}^{k}={\frac {V_{n}^{k}}{k!}}={\frac {n!}{k!(n-k)!}}={\begin{pmatrix}n\\k\end{pmatrix}}$

Ungeordnetes k-Tupel verschiedener Elemente - auf wie viele Arten kann ich die ungeodneten Elemente anordnen?

Antwort: auf k!-Arten