\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Mathematik für Informatiker II - Übungsblatt 9
	Übungsgruppe D5, Do 11-13 \\
	Vogel}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
$A$: Ein bestimmter Informatiker muss auf alle Fälle im Auschuss sein.
$$|A|={6 \choose 2} \cdot {5 \choose 2} = \frac{6! \cdot 5!}{2! \cdot 4! \cdot 2! \cdot 3!} = 150$$
$B$: Jeder Mathematiker und jeder Informatiker kann im Ausschuss vertreten sein.
$$|B|={5 \choose 2} \cdot {7 \choose 3} = \frac{5! \cdot 7!}{2! \cdot 3! \cdot 3! \cdot 4!} = 350$$
$C$: Zwei bestimmte Mathematiker dürfen nicht mehr dem zukünftigen Ausschuss angehören.
$$|C|={3 \choose 2} \cdot {7 \choose 3} = 3 \cdot \frac{7!}{3! \cdot 4!} = 105$$

\section*{Aufgabe 2}
Seien $A:= \{x_1,...,x_n\}$ und $B:= \{y_1,...,y_n\}$.
\begin{enumerate}[1.]
	\item Bijektive Abbildungen $f: A \to B$ kann es nur für $m=n$ geben. Also:
		$$f: \{x_1,...,x_n\} \to \{y_1,...,y_n\}$$
		Ordnet man jedem $x_1,...,x_n \in A$ nacheinander je einen der Werte $y_1,...,y_n \in B$ zu, so gilt: \\
		$f(x_1)$ kann auf $n$ Arten festgelegt werden, $f(x_2)$ noch auf $(n-1)$ Arten usw. \\
		Für $f(x_n)$ bleibt schließlich noch ein Wert aus $B$ übrig. \\
		$\Rightarrow$ es gibt insgesamt $n!$ bijektive Abbildungen $f: \{x_1,...,x_n\} \to \{y_1,...,y_n\}$
	\item Betrachte alle Abbildungen $f: A \to B$. \\
		Jedem $x_i \in A = \{x_1,...,x_n\}$ kann jeder Wert $y_k \in B = \{y_1,...,y_m\}$ zugeordnet sein. \\
		Für jedes $i=1,...,n$ kann $f(x_i)$ auf $n$ Arten festgelegt werden. \\
		$\Rightarrow$ es gibt insgesamt $\underbrace{m \cdot m \cdot ... \cdot m}_{n\text{-mal}} = m^n$ Abbildungen $f: A \to B$
\end{enumerate} \QED

\newpage
\section*{Aufgabe 3}
Gesucht: Anzahl der verschiedenen Programme der Länge $n=0,1,...$ aus der 3-elementigen Menge $M:=\{\circ,\Diamond,\Box\}$ mit vorgegebenen Beschränkungen (Wiederholungen) und zwar: \\
$\circ$ darf 0, 1 oder 3 mal vorkommen. \\
$\Diamond$ darf 1 oder 2 mal vorkommen. \\
$\Box$ darf genau 1 mal vorkommen. \\
Bestimme zunächst die Anzahl der Kombinationen der Menge $\{\circ, \Diamond, \Box\}$ mit den oben angegebenen Beschränkungen: \\
\begin{center}
\begin{tabular}{c|c|c}
	Element & Beschränkung & Polynom \\ \hline
	$\circ$ & 0, 1 oder 3-mal & $1+x+x^3$ \\ \hline
	$\Diamond$ & 1 oder 2-mal & $x+x^2$ \\ \hline
	$\Box$ & 1-mal & $x$
\end{tabular}
\end{center}
$\Rightarrow$ Erzeugende Funktion:
\begin{eqnarray*}
	f(x) & = & (1+x+x^3) \cdot (x+x^2) \cdot x \\
	& = & (1+x+x^3) \cdot (x^2+x^3) \\
	& = & x^2 + x^3 + x^3 + x^4 + x^5 + x^6 \\
	& = & x^2 + 2x^3 + x^4 + x^5 + x^6
\end{eqnarray*}
Mit Wiederholung gibt es unter den vorgegebenen Beschränkungen
\begin{enumerate}[1.]
	\item 1 Möglichkeit, 2 Objekte aus $M$ zu wählen, nämlich $$\Diamond \; \Box$$
	\item 2 Möglichkeiten, 3 Objekte aus $M$ zu wählen, nämlich
		\begin{enumerate}[(a)]
			\item $$\Diamond \; \Diamond \; \Box$$
			\item $$\circ \; \Diamond \; \Box$$
		\end{enumerate}
	\item 1 Möglichkeit, 4 Objekte aus $M$ zu wählen, nämlich $$\circ \; \Diamond \; \Diamond \; \Box$$
	\item 1 Möglichkeit, 5 Objekte aus $M$ zu wählen, nämlich $$\circ \; \circ \; \circ \; \Diamond \; \Box$$
	\item 1 Möglichkeit, 6 Objekte aus $M$ zu wählen, nämlich $$\circ \; \circ \; \circ \; \Diamond \; \Diamond \; \Box$$
\end{enumerate}
\begin{enumerate}[(I)]
	\item (zu 1.) \\
		$\Diamond \; \Box$ können auf $2!=2$ Arten permutiert werden
	\item
		\begin{enumerate}[(a)]
			\item (zu 2(a)) \\
				$\Diamond \; \Diamond \; \Box$ können auf $\displaystyle \frac{3!}{2! \cdot 1!}=3$ Arten angeordnet werden
			\item (zu 2(b)) \\
				$\circ \; \Diamond \; \Box$ können auf $3!=6$ Arten permutiert werden
		\end{enumerate}
	\item (zu 3.) \\
		$\circ \; \Diamond \; \Diamond \; \Box$ können auf $\displaystyle \frac{4!}{1! \cdot 2! \cdot 1!}=12$ Arten angeordnet werden
	\item (zu 4.) \\
		$\circ \; \circ \; \circ \; \Diamond \; \Box$ können auf $\displaystyle \frac{5!}{3! \cdot 1! \cdot 1!} = 20$ Arten angeordnet werden
	\item (zu 5.) \\
		$\circ \; \circ \; \circ \; \Diamond \; \Diamond \; \Box$ können auf $\displaystyle \frac{6!}{3! \cdot 2! \cdot 1!} = 60$ Arten angeordnet werden
\end{enumerate}
Ergebnis: \\
Die Anzahl der verschiedenen Programme der Länge $n=0,1,2,...$ beträgt:
\begin{center}
\begin{tabular}{lcll}
	für $n=0$: & & 0 Programme & \\
	für $n=1$: & & 0 Programme & \\
	für $n=2$: & & 2 Programme & gemäß (I) \\
	für $n=3$: & & 3 Programme & gemäß (II)(a) \\
	& und & 6 Programme & gemäß (II)(b) \\
	für $n=4$: & & 12 Programme & gemäß (III) \\
	für $n=5$: & & 20 Programme & gemäß (IV) \\
	für $n=6$: & & 60 Programme & gemäß (V)
\end{tabular}
\end{center}
Hieraus ergibt sich als Gesamtanzahl der verschiedenen Programme 103.

\newpage
\section*{Aufgabe 4}
Wurf einer idealen Münze: bei Kopf wählt er Paket $A$, bei Zahl wählt er Paket $B$ und greift aus dem gewählten Paket ein Bauteil heraus.

\subsubsection*{(a)}
{\bfseries Gesucht:} $P(CD)$ \\
{\bfseries Lösung:} \\
Aus dem Baumdiagramm folgt:
$$P(CD) = \frac{1}{2} \cdot \frac{3}{5} + \frac{1}{2} \cdot \frac{2}{10} = \frac{3}{10} + \frac{1}{10} = \frac{4}{10} = 0.4$$

\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=8cm]{a4.jpg}\\[0.2cm]
			\caption{Baumdiagramm zu Aufgabe 4 (a)}
	\end{center}
\end{figure}

\subsubsection*{(b)}
Der Angestellte hat recht, wenn das CD-Laufwerk tatsächlich aus Paket $A$ stammt. Gesucht ist also die bedingte Wahrscheinlichkeit dafür, dass das Laufwerk aus Paket $A$ stammt, wenn bekannt ist, dass es sich um ein CD-Laufwerk handelt. \\[0.3cm]
Ereignis $A$: Das Laufwerk stammt aus Paket $A$ \\
Ereignis $CD$: Das Laufwerk ist ein CD-Laufwerk \\[0.3cm]
Berechne $P(A|CD)$:
\begin{eqnarray*}
	P(A|CD) & = & \frac{P(A \cap CD)}{P(CD)} \\
	& = & \frac{\frac{1}{2} \cdot \frac{3}{5}}{0.4} \\
	& = & \frac{0.3}{0.4} \\
	& = & \frac{3}{4} \\
	& = & 0.75
\end{eqnarray*}


\section*{Aufgabe 5}

\subsubsection*{(a)}
Seien $A,B \subset \Omega$. \\
{\bfseries Zu zeigen:} $A$ und $B$ unabhängig $\Leftrightarrow \Omega \backslash A$ und $B$ unabhängig. \\
{\bfseries Beweis:}
\begin{itemize}
	\item \glqq $\Rightarrow$\grqq : \\
		Nach Voraussetzung sind $A$ und $B$ unabhängig, d.h. $$P(A \cap B) = P(A) \cdot P(B)$$
		Setzt man $\overline{A} := \Omega \backslash A$, so ist zu zeigen:
		$$P(\overline{A} \cap B) = P(\overline{A}) \cdot P(B) \quad \quad (*)$$
		Beweis von $(*)$: \\
		Es gilt: $B = (A \cap B) \cup (\overline{A} \cap B)$ \\
		Hierbei ist:
		\begin{eqnarray*}
			(A \cap B) \cap (\overline{A} \cap B) & = & (B \cap A) \cap (\overline{A} \cap B) \\
			& = & B \cap (\underbrace{A \cap \overline{A}}_{= \emptyset}) \cap B \\
			& = & \emptyset
		\end{eqnarray*}
		\begin{eqnarray*}
			\Rightarrow P(B) & = & P(A \cap B) + P(\overline{A} \cap B) \\
			\Leftrightarrow P(\overline{A} \cap B) & = & P(B) - P(A \cap B) \\
			\Rightarrow P(\overline{A} \cap B) & \stackrel{\text{n.Vor.}}{=} & P(B) - P(A) \cdot P(B) \\
			& = & (1-P(A)) \cdot P(B) \\
			& = & P(\overline{A}) \cdot P(B)
		\end{eqnarray*}
		d.h. $\overline{A}$ und $B$ sind unabhängig.
	\item \glqq $\Leftarrow$\grqq : \\
		Nach Voraussetzung sind $\overline{A}$ und $B$ unabhängig, d.h. $$P(\overline{A} \cap B) = P(\overline{A}) \cdot P(B)$$
		zu zeigen: $$P(A \cap B) = P(A) \cdot P(B) \quad \quad (**)$$
		Beweis von $(**)$: \\
		Es gilt: $B = (A \cap B) \cup (\overline{A} \cap B)$ \\
		Hierbei sind $(A \cap B)$ und $(\overline{A} \cap B)$ disjunkt.
		\begin{eqnarray*}
			\Rightarrow P(B) & = & P(A \cap B) + P(\overline{A} \cap B) \\
			\Leftrightarrow P(A \cap B) & = & P(B) - P(\overline{A} \cap B) \\
			\Rightarrow P(A \cap B) & \stackrel{\text{n.Vor.}}{=} & P(B) - P(\overline{A}) \cdot P(B) \\
			& = & (1-P(\overline{A})) \cdot P(B) \\
			& = & P(A) \cdot P(B)
		\end{eqnarray*}
		d.h. $A$ und $B$ sind unabhängig.
\end{itemize} \QED

\subsubsection*{(b)}
$\Omega = \{1,2,3,4\}$ mit $\displaystyle P(\{i\}) = \frac{1}{4}$ für $i=1,2,3,4$. \\
Sei $\displaystyle A:=\{1,2\} \Rightarrow P(A)=\frac{1}{2}$. \\
Gesucht: Alle Mengen $B \subset \Omega$, die von $A$ unabhängig sind. \\[0.3cm]
Lösung: Die Potenzmenge $\mathcal{P}(\Omega)$ hat die folgenden $2^4 = 16$ Teilmengen:
\begin{eqnarray*}
	B_0 & = & \emptyset \\
	B_1 & = & \{1\} \\
	B_2 & = & \{2\} \\
	B_3 & = & \{3\} \\
	B_4 & = & \{4\} \\
	B_5 & = & \{1,2\} \\
	B_6 & = & \{1,3\} \\
	B_7 & = & \{1,4\} \\
	B_8 & = & \{2,3\} \\
	B_9 & = & \{2,4\} \\
	B_{10} & = & \{3,4\} \\
	B_{11} & = & \{1,2,3\} \\
	B_{12} & = & \{1,2,4\} \\
	B_{13} & = & \{1,3,4\} \\
	B_{14} & = & \{2,3,4\} \\
	B_{15} & = & \{1,2,3,4\} = \Omega
\end{eqnarray*}
$$\left. \begin{array}{rl}B_0 \cap A = \emptyset \Rightarrow & P(B_0 \cap A) = 0 \\ & P(B_0) \cdot P(A) = 0 \cdot \frac{1}{2} = 0\end{array} \right\} =$$
$\Rightarrow B_0 = \emptyset$ ist von $A=\{1,2\}$ unabhängig. \\
Für $i=1,2$ gilt:
$$\left. \begin{array}{rl}B_i \cap A = \{i\} \Rightarrow & P(B_i \cap A) = \frac{1}{4} \\ & P(B_i) \cdot P(A) = \frac{1}{4} \cdot \frac{1}{2} = \frac{1}{8}\end{array} \right\} \ne$$
Für $i=3,4$ gilt:
$$\left. \begin{array}{rl}B_i \cap A = \emptyset \Rightarrow & P(B_i \cap A) = 0 \\ & P(B_i) \cdot P(A) = \frac{1}{4} \cdot \frac{1}{2} = \frac{1}{8}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_5 \cap A = \{1,2\} \Rightarrow & P(B_5 \cap A) = \frac{1}{2} \\ & P(B_5) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_6 \cap A = \{1\} \Rightarrow & P(B_6 \cap A) = \frac{1}{4} \\ & P(B_6) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \Rightarrow B_6 = \{1,3\} \text{ ist von } A \text{ unabhängig}$$
$$\left. \begin{array}{rl}B_7 \cap A = \{1\} \Rightarrow & P(B_7 \cap A) = \frac{1}{4} \\ & P(B_7) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \Rightarrow B_7 = \{1,4\} \text{ ist von } A \text{ unabhängig}$$
$$\left. \begin{array}{rl}B_8 \cap A = \{2\} \Rightarrow & P(B_8 \cap A) = \frac{1}{4} \\ & P(B_8) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \Rightarrow B_8 = \{2,3\} \text{ ist von } A \text{ unabhängig}$$
$$\left. \begin{array}{rl}B_9 \cap A = \{2\} \Rightarrow & P(B_9 \cap A) = \frac{1}{4} \\ & P(B_9) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \Rightarrow B_9 = \{2,4\} \text{ ist von } A \text{ unabhängig}$$
$$\left. \begin{array}{rl}B_{10} \cap A = \emptyset \Rightarrow & P(B_{10} \cap A) = 0 \\ & P(B_{10}) \cdot P(A) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_{11} \cap A = \{1,2\} \Rightarrow & P(B_{11} \cap A) = \frac{1}{2} \\ & P(B_{11}) \cdot P(A) = \frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_{12} \cap A = \{1,2\} \Rightarrow & P(B_{12} \cap A) = \frac{1}{2} \\ & P(B_{12}) \cdot P(A) = \frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_{13} \cap A = \{1\} \Rightarrow & P(B_{13} \cap A) = \frac{1}{4} \\ & P(B_{13}) \cdot P(A) = \frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}B_{14} \cap A = \{2\} \Rightarrow & P(B_{14} \cap A) = \frac{1}{4} \\ & P(B_{14}) \cdot P(A) = \frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}\end{array} \right\} \ne$$
$$\left. \begin{array}{rl}\Omega \cap A = A \Rightarrow & P(\Omega \cap A) = P(A) = \frac{1}{2} \\ & P(\Omega) \cdot P(A) = 1 \cdot \frac{1}{2} = \frac{1}{2}\end{array} \right\} =$$
$\Rightarrow \Omega = \{1,2,3,4\}$ ist von $A=\{1,2\}$ unabhängig. \\
Zusammenfassung: \\
Folgende Mengen $B \subset \Omega$ sind von $A$ unabhängig: \\
$$\emptyset; \; \{1,3\}; \; \{1,4\}; \; \{2,3\}; \; \{2,4\}; \; \Omega$$ \QED

\end{document}
