TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/14. VO 14.11.2005

$A_{1},...,A_{n}\leq A$, endlich

$|\bigcup A_{i}|=|A_{1}|+...+|A_{n}|-|A_{1}\cap A_{2}|-|A_{1}\cap A_{n}|-...-|A_{n-1}1\cap A_{2}|+|A_{1}\cap A_{2}\cap A_{3}+...+(-1)^{n-1}*|A_{1}\cap ...\cap A_{n}|=\sum _{I\subseteq \{1,...,n\},I\neq 0}(-1)*|\bigcup A_{i}|$

Beweis: Vollständige Induktion nach n

n = 1 : $|A_{1}|=|A_{1}|$ OK

n = 2 : $|A_{1}\vee A_{2}|=|A_{1}|+|A_{2}|-|A_{1}\wedge A_{2}|$

Beweis: Venn-Diagramm

$|A_{1}\cup A_{2}|=(A_{1}\ A_{2})\cup (A_{2}\ A_{1})\cup (A_{1}\cap A_{2})$

$|A_{1}\cup A_{2}|=|A_{1}\ A_{2}|+|A_{2}\ A_{1}|+|A_{1}\cap A_{2}|$

$A_{1}=(A_{1}\ A_{2})\cup (A_{1}\cap A_{2})$

$A_{2}=(A_{2}\ A_{1})\cup (A_{1}\cap A_{2})$

$n\rightarrow n+1$

$\bigcup _{i=1}^{n}A_{i}:=B$

$|\bigcup _{i=1}^{n+1}A_{i}|=|B\cup A_{n+1}|=|B|+|a_{n+1}|-|B\cap A_{n+1}|$

$=\sum _{I\subseteq \{1,...,n\}}(-1)^{|I|-1}|\bigcup A_{I}|+|A_{n+1}|-\sum _{j\subseteq \{1,...,n\}}(-1)^{|j|-1}|\bigcup _{i\in j}B_{i}|$

$=\sum _{I\subseteq \{1,...,n\},I\neq 0}(-1)^{|I|-1}|\bigcup _{i\in I}A_{i}|+|A_{n+1}|-\sum _{I\subseteq \{1,...,n+1\},\{n+1\subseteq I'\}}(-1)^{|I|}|\bigcup _{i\in I}A_{i}|$

$\sum _{I\subseteq \{1,...,n+1\}}(-1)^{|I|-1|}|\bigcup _{i\in I}A_{i}|$

Alte Formulierung (Grafik)

${\overline {A}}=A'IA^{C}:=G\ A$

"Komplement von A"

$|{\overline {A}}\cap {\overline {B}}|=|{\overline {A\cup B}}|=|G\ (A\cup B)|=|G|-|A\cup B|=|G|-|A|-|B|+|A\cap B|$

(De Morgan)

$A_{1},...,A_{n}\subseteq A$

$|\bigcap _{i=1}^{n}{\overline {A_{i}}}|=|{\overline {\bigcap _{i=1}^{n}A_{i}}}|=|A\ \bigcup _{i=1}^{n}A_{i}|-|A|-|bigcup_{i=1}^{n}A_{i}|=$

$|A|-|A_{1}-|A_{2}|-...-|A_{n}|+|A_{1}\cap A_{2}|+|A_{1}\cap A_{3}|+...+|A_{n-1}\cap A_{n}|-|A_{1}\cap A_{2}\cap A_{3}|+...+(-1)^{n}*|A_{1}\cap ...\cap A_{n}|$

{a,b,c,d,e}

Wörter der Länge 4

W ... Menge aller Wörter der Länge 4 mit den Buchstaben {a, ..., e}

$W_{a}$ ... Menge aller Wörter der Länge 4 die den Buchstaben a nicht enthalten

${\overline {W_{a}}}$ ... Menge aller Wörter der Länge 4 die den Buchstaben a mindestens einmal enthalten

Andere Mengen analog

Gesucht: ${\overline {W_{a}}}\cap {\overline {W_{b}}}\cap {\overline {W_{c}}}=$

$|W|-|W_{a}|-|W_{n}|-|W_{c}|+|W_{a}\cap W_{b}|+|W_{a}\cap W_{c}|+|W_{b}\cap W_{c}|-|W_{a}\cap W_{b}\cap W_{c}|=625-3*256+3*81-16=84$

$|W|=5^{4}$ (Variationen mit Wiederholung)

$|W_{a}|=|W_{b}|=|W_{c}|=4^{4}$

$|W_{a}\cap W_{b}|=...=3^{4}$

$|W_{a}\cap W_{b}\cap W_{c}|=2^{4}$

? Wie viele Permutationen der Länge n haben zumindst einen Fixpunkt

A = {1, ..., n }

${\begin{pmatrix}1,2,3...n\\\pi _{1}\pi _{2}\pi _{3}...\pi _{n}\end{pmatrix}}$

2-Zeilen-Darstellung

j Fixpunkt : $j=\pi _{j}$

$A_{1},...,A_{n}$

$A_{j}:{\text{Menge aller Permutationen der Länge n, wo j ein Fixpunkt ist}}$

${\begin{pmatrix}123\\123\end{pmatrix}},{\begin{pmatrix}123\\132\end{pmatrix}}{\begin{pmatrix}123\\213\end{pmatrix}}{\begin{pmatrix}123\\231\end{pmatrix}}{\begin{pmatrix}123\\312\end{pmatrix}}{\begin{pmatrix}123\\321\end{pmatrix}}$

$x_{3}=4$ (überall dort wo gleiche Ziffern übereinander

$x_{n}=|\bigcup _{i=1}^{n}A_{i}|=\sum _{i=1}^{n}|A_{i}|-\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}|$

$|A_{1}|=..=|A_{n}|=(n-1)!$

${\begin{pmatrix}123..n\\12\pi _{3}\pi _{4}...\pi _{n}\end{pmatrix}}|A_{1}\cap A_{2}=(n-2)!$

$x_{n}=(n-1)!*n-(n-2)!*{\begin{pmatrix}n\\2\end{pmatrix}}+(n-3)!*{\begin{pmatrix}n\\3\end{pmatrix}}+..+(-1)^{n-1}*0!*{\begin{pmatrix}n\\n\end{pmatrix}}=n!-(n-2)!*{\frac {n(n-1)}{2!}}+(n-3)!*{\frac {n(n-1)(n-2)}{3!}}+...+(-1)^{n-1}*{\frac {n!}{n!}}=n!(1-{\frac {1}{2!}}+{\frac {1}{3!}}-+...+(-1)^{n-1}*{\frac {1}{n!}})=n!\sum _{k=1}^{n}{\frac {(-1)^{k+1}}{k!}}$

$e^{\pi }=\sum _{k\geq 0}{\frac {z^{k}}{k!}}$