TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/13. VO 10.11.2005

Abzählen:

Kombinatioen: ungeordnete k-Tupel von versch. Elementen aus Menge A

$C_{n}^{K}={\begin{pmatrix}n\\k\end{pmatrix}}$

Beispiel: Loto 6 aus 45: (45!)/(6!*39!) = (45*44*43*42*41*40)/(6!)

Eine Kombination mit Wiederholung ist ein ungeordnetes k_Tupel {$a_{1},...,a_{r}$} von nicht notwendig verschiedenen Elementen aus A, also eine k-elementige Multigenge von A.

Gesucht: $^{W}C_{n}^{K}='$

Menge: A = {1, ..., n }

$C_{n}^{K}=|\{(a_{1},a_{2},...,a_{k}):1\leq a_{1}\leq a_{2}\leq a_{3}\leq ...\leq a_{k}\leq n\}|$

$^{W}C_{n}^{K}=|\{(a_{1},a_{2},...,a_{k}):1\leq a_{1}\leq a_{2}\leq a_{3}\leq a_{k}\leq n\}|=|\{(a_{1},a_{2},...,a_{k}):1\leq a_{1}\leq a_{2}+1<a_{3}+2<a_{4}+3<...<a_{K}+K-1\leq n+K-1\}|$

Definiere: $b_{i}:=a_{i}+i-1=|\{(b_{1},b_{2},...,b_{k}):1\leq b_{1}<b_{2}<b_{3}<...<b_{k}\leq n+k-1\}|=C_{n+K-1}^{K}={\begin{pmatrix}n+K-1\\K\end{pmatrix}}$

Beispiel: 3 Würfe, # verschiedene Würfe

n = 6 .... Augensumme in jedem Wurf $\in \{1,...,6\}$

K = 3

$\#=^{W}C_{6}^{3}={\begin{pmatrix}6+3-1\\3\end{pmatrix}}={\begin{pmatrix}8\\3\end{pmatrix}}=56$

Menge A = {a,b,c,d}

Permutationen von A: #Permutationen := $P_{4}$ = 4! = 24

abcdm abdc, acbd, .....

Multimenge B={a,a,b,b}

$\#$ mit Wiederholungen = $P_{4}^{2,2}={\frac {4!}{2!*2!}}=6$

aabbm abab, abba, baab, baba, bbaa

Variationen von A nur 2-ten Klasse

geordnete Paare von verschiedenen Elementen aus A

$\#$ Variationen = V_4^2 = 4*3 = 12

  ab ac ad
  ba bc bd
  ca cb cd
  da db dc

Variationen mit Wiederholung:

geordnete Paare von nicht notwendigerweise verschiedenen Elementen

$\#=^{W}V_{4}^{2}=4^{2}=16$

Wie oben, nur zusätzlich

  aa bb cc dd

Kombinationen: 2 elementige Mengen von A (ungeordnetes Paar)

$\#=C_{4}^{2}={\begin{pmatrix}4\\2\end{pmatrix}}={\frac {24}{4}}=6$

Kombination mit Wiederholung 2-elementige Multimengen

$\#=^{W}C_{4}^{2}={\begin{pmatrix}4+2+1\\2\end{pmatrix}}={\frac {5*4}{2}}=10$

Inklusive-Exklusive-Prinzip (Zeichnungen werden nachgetragen!)

(2 Mengen)

endliche Grundmenge G, Teilmengen $A,b\subseteq G$

$|A\cup B|=|A|+|B|-|A\cap B|$

(3 Mengen)

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Satz: Inkl.-Exkl.-Prinzip (Siebformel)

Gegeben: $A_{1},...,A_{n}$ Teilmengen einer endlichen Menge A.

Dann gilt:

$|\bigcup _{i=1}{n}A_{i}|=|A_{1}|+|A_{2}|+...+|A_{n}|-|A_{1}\cap A_{2}|-|A_{1}\cap A_{3}|-...-|A_{n-1}\cap A_{n}|+|A1\cap A_{2}\cap A_{3}|+...+|A_{n-2}\cap A_{n-1}\cap A_{n}|+...+(-1)^{n-1}*|A_{1}\cap A_{2}\cap ...\cap A_{n}|=\sum _{i=1}^{n}-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|+(-1)^{n-1}|A_{1}\cap A_{2}\cap ...\cap A_{n}|=\sum _{I\leq \{1,...,n\},I\neq 0}*|\bigcap _{i\in I}A_{i}|$