5 Die rationalen Zahlen

5.1 Konstruktion von $\mathbb{Q}$.
Wir wollen nun nach der additiven Gleichung $a=b+x$ die uns in (4.1) zu den ganzen Zahlen geführt hat analog die multiplikative Gleichung $a=b\cdot x$ behandeln. Nur für $b\ne 0$ dürfen wir die Existenz einer Lösung $x$ erhoffen, den in jedem Ring gilt $0\cdot x=0$ für alle $x\in R$ nach (2.6). Leider haben wir für $\mathbb{Z}$ gesehen, daß die Gleichung $a=b\cdot x$ genau dann eine Lösung $x\in\mathbb{Z}$ besitzt, wenn $a$ durch $b$ teilbar ist. Z.B. für $a=1$ ist das nur für $b\in\{\pm1\}$ der Fall.

Also versuchen wir wie in (4.1) wieder mit virtuellen Lösungen $x=x_{a,b}$ diesmal der Gleichungen $a=b\cdot x$ für $b\ne 0$ zu rechnen. Analog zum Übergang von $\mathbb{N}$ auf $\mathbb{Z}$ sollte $x_{a,b}\cdot x_{a',b'}=x_{a\cdot a',b\cdot b'}$ sein und $x_{a,b}=x_{a',b'}$, falls $a\cdot b'=a'\cdot b$ ist. Wir definieren also die Menge der rationalen Zahlen als

$$\mathbb{Q}:=\mathbb{Z}\times (\mathbb{Z}\setminus\{0\})/{\sim},$$ wobei $$(a,b)\sim (a',b'):\Leftrightarrow a\cdot b=a'\cdot b.$$

Dann ist $(\mathbb{Q},\cdot)$ eine kommutative Halbgruppe mit $1:=[(1,1)]_\sim$ und $(\mathbb{Q}\setminus\{0\},\cdot)$ eine Gruppe, wobei $0:=[(0,1)]_\sim$.

Weiters sollte $x_{a,b}+x_{a',b'}=x_{a\cdot b'+a'\cdot b,b\cdot b'}$ sein, denn $a\cdot b'+a'\cdot b=(x_{a,b}\cdot b)\cdot b'+(x_{a',b'}\cdot b')\cdot b= (x_{a,b}+x_{a',b'})\cdot (b\cdot b')$. Einfache Rechnungen zeigen, daß damit $(\mathbb{Q},+,\cdot)$ zu einem Körper wird, der Körper der rationalen Zahlen. Man schreibt natürlich üblicherweise $\frac{a}{b}$ an Stelle von $[(a,b)]_\sim$. Beachte dabei, daß wir ganze Zahlen $x\in\mathbb{Z}$ als spezielle rationale Zahlen vermöge der Abbildung $x\mapsto \frac{x}{1}$, $\mathbb{Z}\to\mathbb{Q}$ auffassen können.

Kombinatorik (Fortsetzung)

5.2 Definition.
Unter einer Kombination ohne Wiederholung von $k$ vielen Objekten aus $n$ vielen, versteht man eine Auswahl von $k$-verschiedenen Elementen aus einer Grundmenge von $n$ vielen, wobei es auf die Reihenfolge der Auswahl nicht ankommen soll. Also wenn z.B. der Vorstand bestehend aus 3 gleichberechtigen Personen, deren jeweilige Aufgaben/Ämter nicht explizit festgelegt sind, eines Vereins mit 100 Mitgliedern gewählt werden soll (ohne das Ämterkummulierung zulässig), so ist eine Kombination ohne Wiederholungen von 3 aus 100 zu bestimmen.

Kombinationen ohne Wiederholung von $k$ aus $n$ werden also gerade durch $k$-Elementige Teilmenge einer $n$-Elementigen Menge beschrieben.

5.3 Proposition.
Die Anzahl der Kombinationen ohne Wiederholung von $k$ vielen Objekten aus $n$ vielen ist gerade der Binomialkoeffizient

$$\binom{n}{k}:=\frac{(n)_k}{k!}=\prod_{j=1}^k \frac{n-j+1}{j} =\frac{n!}{k!\cdot (n-k)!}.$$

Beweis. Der Unterschied zwischen Variationen und Kombinationen ohne Wiederholung besteht gerade darin, daß es bei ersteren auf die Reihenfolge der Auswahlen ankommt. Aus jeder Auswahl einer Kombination ohne Wiederholung kann erhält man etliche Variationen ohne Wiederholung indem man die $k$ gewählten Elemente irgendwie anordnet. Dafür gibt es nach (3.19) gerade $k!$ viele Möglichkeiten. Wenn wir also die Anzahl der Kombinationen mit $\binom{n}{k}$ bezeichnen, dann ist die Anzahl der Variationen $(n)_k=k!\cdot\binom{n}{k}$, also $\binom{n}{k}=\frac{(n)_k}{k!}$.     []

Beachte, daß es genau eine Möglichkeit gibt aus $n$-Elementen keines Auszuwählen, nämlich die leere Menge, also ist $\binom{n}{0}=1$.

5.4 Folgerung. Binomsche Lehrsatz.
Für $n\in\mathbb{N}$ ist

$$(x+y)^n=\sum_{k=0}^n \binom{n}{k} x^{n-k}y^k$$

Beweis. Ausmultiplizieren von $(x+y)^n=(x+y)\cdot\dots\cdot(x+y)$ vermöge dem distributiv-Gesetz funktioniert so, daß man aus jeder der $n$ Klammern jeweils $x$ oder $y$ auswählt, die gewählten Variablen miteinander multipliziert und die Summe über alle diese Auswahlen bildet. Um die jeweiligen Produkte zu bestimmen genügt es festzustellen wie oft (sagen wir $k$ mal) $y$ gewählt wurde. In den anderen $n-k$ vielen Klammern wurde dann $x$ gewählt, also ist (wegen Kommutativgesetz) das Produkt $x^{n-k}y^k$ und die Anzahl der Möglichkeiten bei den $n$-Klammern gerade $k$ mal $y$ zu wählen wird gerade durch Kombinationen ohne Wiederholung von $k$ (den Klammern wo wir $y$ gewählt haben) aus $n$-vielen (Klammern) beschrieben. Also folgt die Formel.     []

5.5 Lemma.
Rekursionsformel für Binomialkoeffizienten: $\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$

Veranschaulichen kann man diese Rekursionsformel durch das Pascal'sches Dreieck, in welchen sich die Eintragungen als Summe des direkt darüber sowie des links darüberstehenden Elements ergeben:

$$\begin{array}{ccccccc} \binom{0}{0} \\ [0.2cm]... ...& \binom{n+1}{k+1}&\hdots&\hdots&\binom{n+1}{n+1} \\ [0.2cm] \end{array}$$

Beweis. Dies läßt sich leicht mit Induktion zeigen, oder indem man beachtet, daß $k+1$-elementige Teilmengen von $\{0,\dots,n\}$ eingeteilt werden können in solche die $n$ nicht enthalten und somit $k+1$-elementige Teilmengen von $\{0,\dots,n-1\}$ sind und solche die $n$ enthalten und somit eindeutig als Vereinigung von $\{n\}$ und einer $k$-elementige Teilmenge von $\{0,\dots,n-1\}$ geschrieben werden können.     []

5.6 Bemerkung.
Beachte, daß Kombinationen ohne Wiederholung von $k$-Elementen aus der Menge $\{0,1,2,\dots,n-1\}$, also $k$-elementige Teilmengen $\{x_0,\dots,x_{k-1}\}\subseteq \{0,\dots,n-1\}$, o.B.d.A. so geschrieben werden können, daß $x_0<\dots< x_{k-1}$, also gerade durch streng monoton wachsende Folgen von $k$ natürlichen Zahlen $0\leq x_0<\dots<x_{k-1}< n$ beschrieben werden können.

5.7 Definition.
Unter einer Kombination mit Wiederholung von $k$ vielen Objekten aus $n$ vielen, versteht man eine Auswahl von $k$ Elementen aus einer Grundmenge von $n$ vielen, wobei es auf die Reihenfolge der Auswahl nicht ankommen soll, und man durchaus auch mehrmals gleiche Elemente wählen kann. Man spricht auch von Auswählen mit Zurücklegen.

5.8 Bemerkung.
Jede Kombination mit Wiederholung von $k$ vielen Objekten aus $n$ vielen wird also durch $x_0,\dots,x_{k-1}\in\{0,\dots,n-1\}$ beschrieben, wobei wir verschiedene Reihenfolgen der $x_0,\dots,x_{k-1}$ als gleichbedeutend ansehen müssen. Wir können aber wie bei Kombinationen ohne Wiederholung die natürliche Reihenfolge $x_0\leq\dots\leq x_{k-1}$ benutzen, und somit Kombinationen mit Wiederholung als monoton wachsende Folgen von natürlichen Zahlen $0\leq x_0\leq\dots\leq x_{k-1}< n$ auffassen.

5.9 Proposition.
Die Anzahl der Kombinationen mit Wiederholung von $k$ vielen Objekten aus $n$ vielen ist $\binom{n+k+1}{k}$.

Beweis. Wir können aus jeder Kombination mit Wiederholung aufgefaßt als monotone Folge $0\leq x_0\leq\dots\leq x_{k-1}< n$ eine streng monotone Folge $0\leq y_0<\dots<y_{k-1}<n+k-1$ vermöge $y_i:=x_i+i$ machen. Umgekehrt können wir aus jeder solchen streng monoton wachsenden Folge von $y$'s eine monoton wachsende Folge von $x$'en zurückgewinnen, indem wir $x_i:=y_i-i$ setzen. Also entsprechen den Kombinationen mit Wiederholung von $k$ aus $n$ gerade die Kombinationen ohne Wiederholung von $k$ aus $n+k-1$, von welchen es $\binom{n+k-1}{k}$ viele nach (5.3) gibt.     []

Beispiel.
Es werden in einer Übungsstunde 10 Beispiele von gewissen der anwesenden 20 StudentInnen gerechnet. Wieviele Möglichkeiten bestehen dafür, wenn es nur darauf ankommt dranzukommen, aber nicht welches Beispiel man rechnet.
Antwort: Kombinationen mit Wiederholung von 10 aus 20, also $\binom{20+10-1}{10}=20 030 010$.

Zusammenfassung.
Wir haben also folgende Anzahlen für Auswahlen von $k$ aus $n$ bestimmt:

	mit Wiederholung	ohne Wiederholung
mit Reihenf. (Variationen)	$n^k$	$(n)_k$
ohne Reihenf. (Kombinationen)	$\binom{n+k-1}{k}$	$\binom{n}{k}$

Elementare Wahrscheinlichkeitstheorie

5.10 Definition.
Es sei eine Menge $X$ möglicher und gleich-wahrscheinlicher Ereignisse gegeben. Also z.B. $\{$Kopf$,$Zahl$\}$ bei Werfen einer Münze, oder $\{1,2,3,4,5,6\}$ bei Werfen eines Würfels, oder $\{0,1,2,3,\dots,36\}$ beim Roulette. Sei $E$ eine Teilmenge von $X$. Die Wahrscheinlichkeit $P(E)$ dafür, daß ein Ereignis aus $E$ eintritt ist per Definition

$$P(E):=\frac{\vert E\vert}{\vert X\vert},$$

also der Quotient aus der Anzahl der günstigen Fälle (d.h. der Fälle aus $E$) dividiert durch die Anzahl aller möglicher Fälle die auftreten können. Voraussetzung für diese Definition ist allerdings, daß die einzelnen Fälle gleichwahrscheinlich sind!

Offensichtlich ist $0\leq P(E)\leq 1$. Es ist $P(E)=1$, wenn $E$ ein sicher( eintretend)es Ereignis ist; und $P(E)=0$, wenn $E$ ein unmögliches Ereignis ist.

So ist z.B. beim einmaligen Würfeln, ein einzelner Fall gerade ein einzelner Wurf, der durch die oben liegende Ziffer des Würfels beschrieben werden kann. Es gibt also 6 mögliche Fälle. Sei nun das Ereignis $E$ gegeben, daß die Augenzahl gerade ist, dann sind die Fälle $2$, $4$ und $6$ günstig und somit $P(E)=\frac{3}{6}=\frac12$.

Beim Roulette hingegen ist die Anzahl der möglichen Fälle $1+36$ und die für ``rouge''(=rot) gerade $18$, somit $P(E)=\frac{18}{37}\sim 0.4865$.

Beachte jedoch, daß es beim Werfen 2'er Münzen (oder auch beim zweimaligen Werfen einer Münze) 4 mögliche Fälle gibt: (Kopf,Kopf), (Kopf,Zahl), (Zahl,Kopf), (Zahl,Zahl). Wenn wir also die Wahrscheinlichkeit des Ereignisses $E$, daß genau eine Zahl kommt, bestimmen, so ergibt sich $P(E)=\frac{2}{4}=\frac12$, und nicht ein Drittel wie an vielleicht fälschlich wie folgt vermuten könnte: Es gibt 3 Fälle: Keinmal Kopf, genau einmal Kopf und zweimal Kopf. Einer davon ist günstig, also $P(E)=\frac13$. Diese Argumentation ist falsch, denn genau einmal Kopf zu werfen, kann auf zwei Arten zustande kommen, nämlich dadurch, daß die eine oder (ausschliesend) die andere Münze auf Kopf fällt. Es ist also doppelt so wahrscheinlich als, daß beide Münzen auf Kopf fallen.

5.11 Additionssatz.
$P(E_1\cup E_2)=P(E_1)+P(E_2)-P(E_1\cap E_2)$.

Beweis. Dies folgt aus $\vert E_1\cup E_2\vert+\vert E_1\cap E_2\vert=\vert E_1\vert+\vert E_2\vert$.     []

Beispiel.
Z.B. ist die Wahrscheinlichkeit bei 2 maligen Würfeln mindestens einen 6'er zu haben wie folgt bestimmbar. Die Wahrscheinlichkeit $P(E_i)$ beim $i$-ten Wurf einen 6'er zu Würfeln ist 1/6. Die Wahrscheinlichkeit $P(E_1\cap E_2)$ bei beiden Würfen einen 6'er zu Würfeln ist $1/36$, also ist $P(E\cup E_2)=1/6+1/6-1/36=11/36$. Dies hätten wir natürlich auch recht schnell durch Abzählen der günstigen Fälle erhalten.

5.12 Satz über das Komplementärereignis.
$P(E^c)=1-P(E)$.

Beweis. Wegen $X=E\cup E^c$ und $E\cap E^c=\emptyset$ folgt dies aus dem Additionssatz.     []

Beispiel.
Die Wahrscheinlichkeit dafür, daß mindestens zwei Personen auf einer Party mit $n$ Personen am gleichen Tag Geburtstag haben berechnen wir wie folgt. Das komplementäre Ereignis, daß keine 2 der Personen am gleichen Tag Geburtstag haben ist $\frac{365\cdot364\cdot\dots\cdot(365-n+1)}{365^n}$. Bereits bei $n=23$ ist dies $\sim 0.4927$ also ist die Chance für 2 mit gleichen Geburtstag bereits mehr als 50%.

5.13 Definition.
Unter der bedingten Wahrscheinlichkeit $P(E/E_0)$ versteht man die Wahrscheinlichkeit dafür, daß das Ereignis $E$ eintritt, wenn man schon weiß, daß das Ereignis $E_0$ eintritt (oder eingetreten ist).

Z.B. sei beim zweimaligen Werfen einer Münze $E_0$ das Ereignis, daß die erste Münze auf Kopf fällt und $E$ das Ereignis, daß die zweite Münze auf Kopf fällt. Dann hängt $E$ offensichtlich nicht von $E_0$ ab, also ist $P(E/E_0)=P(E)$.

Hingegen ist beim zweifachen Ziehen einer Karte aus $4\cdot 8$ Karten (ohne die erste zurückzustecken) die Wahrscheinlichkeit, daß die erste Karte ein As ist $\frac{4}{4\cdot 8}=\frac18$. Jene, daß die zweite ein As ist hängt nun aber davon ab ob wir bereits ein As gezogen und somit entfernt haben, dann ist sie $\frac{3}{4\cdot 8-1}=\frac{3}{31}<\frac18$, oder ob wir beim ersten Zug kein As erwischt haben, dann ist sie $\frac{4}{4\cdot 8-1}=\frac{4}{31}>\frac18$.

5.14 Satz über die bedingte Wahrscheinlichkeit.
Es ist $P(E/E_0)=P(E\cap E_0)/P(E_0)$.

Beweis. Es ist $P(E/E_0)=\vert E\cap E_0\vert/\vert E_0\vert=(\vert E\cap E_0\vert/\vert X\vert)/(\vert E_0\vert/\vert X\vert)=P(E\cap E_0)/P(E_0)$.     []

Diese Formel kann umgekehrt verwendet werden, um die Wahrscheinlichkeit für das Eintreffen zweier Ereignisse $E_1$ und $E_2$ wie folgt zu bestimmen:

5.15 Multiplikationssatz.
Es ist $P(E_1\cap E_2)=P(E_1)\cdot P(E_2/E_1)$. Genau dann wenn $E_1$ und $E_2$ unabhängig voneinander sind, d.h. $P(E_1)=P(E_1/E_2)$ gilt, ist $P(E_1\cap E_2)=P(E_1)\cdot P(E_2)$.

Beweis. Die allgemeine Formel folgt sofort aus der Formel für die bedingte Wahrscheinlichkeit. Die spezielle Formel $P(E_1\cap E_2)=P(E_1)\cdot P(E_2)$ gilt somit genau dann, wenn $P(E_1)=P(E_1/E_2)$ gilt, d.h. daß die Wahrscheinlichkeit von $E_1$ übereinstimmt mit jener von $E_1$ unter der Voraussetzung, daß $E_2$ eingetreten ist, also $E_1$ unabhängig von $E_2$ ist.     []

Beispiel.
Die Wahrscheinlichkeit $P(E_1)$ bei einem Kartenspiel von 32 Karten ein As zu ziehen ist $\frac{4}{32}$. Ist die gezogene Karte ein As, so ist die Wahrscheinlichkeit $P(E_2/E_1)$ beim Ziehen einer weiteren Karten wieder ein As zu ziehen $\frac{3}{31}$. Die Wahrscheinlichkeit zwei Asse zu ziehen ist somit $P(E_1\cap E_2)=P(E_1)\cdot P(E_2/E_1)=\frac{4}{32}\cdot\frac{3}{31}=\frac{3}{248}\sim 0.012$.

Vergleiche dies auch mit der Rechnung im Beispiel nach (5.12).

5.16 Formel für totale Wahrscheinlichkeit.

$$E\subseteq E_1\sqcup\dots\sqcup E_k\;\Rightarrow\; P(E)=\sum_i P(E_j)\cdot P(E/E_j),$$

wobei $\sqcup$ für eine Vereinigung disjunkter Mengen steht.

Beweis. Es ist $E=E\cap \bigsqcup_j E_j=\bigsqcup_j(E\cap E_j)$ und somit

$$P(E) =\sum_j P(E\cap E_j) =\sum_j P(E_j)\cdot P(E/E_j)$$

    []

5.17 Formel von Bayes.

$$E\subseteq E_1\sqcup\dots\sqcup E_k\;\Rightarrow\; P(E_i/E)=\frac{P(E_i)\cdot P(E/E_i)}{\sum_j P(E_j)\,P(E/E_j)}$$

Beweis.

$$P(E_i)\cdot P(E/E_i) =P(E\cap E_i)=P(E_i\cap E)=P(E)\cdot P(E_i/E)$$

$$=\Bigl(\sum_j P(E_j)\cdot P(E/E_j)\Bigr)\cdot P(E_i/E)$$

    []

5.18 Beispiele.
Die Wahrscheinlichkeit bei Würfelpokern eine große Straße zu Würfeln können wir wie folgt bestimmen. Es gibt $6^5$ möglichen Fälle für die 5 Würfe. Ein günstiger wäre 10,B,D,K,A für 1.,2.,3.,4. und 5. Würfel, aber auch jede andere der $5!$ Anordnungen ist günstig, also ist $P=\frac{5!}{6^5}=\frac{5}{324}\sim 0.015$.

Die Wahrscheinlichkeit bei Kartenpokern (wobei das Kartenspiel aus 9, 10, B, D, K, A in den 4 Farben bestehen soll) eine große Straße zu erhalten kann wie folgt bestimmt werden: Die Wahrscheinlichkeit $P(E_1)$ als erste Karte ein As zu erhalten ist $\frac{4}{4\cdot 6}$, jene $P(E_2/E_1)$ für die zweite Karte einen König zu erhalten, wenn die erste ein As war ist $\frac{4}{4\cdot 6-1}$. Die Wahrscheinlichkeit $P(E_1\cap E_2)$ ist somit $\frac{4}{4\cdot 6}\cdot\frac{4}{4\cdot 6-1}$. Jene, daß dann die 3.te Karte eine Dame ist, ist $\frac{4}{4\cdot 6-2}$, und somit ist die Wahrscheinlichkeit, daß die ersten 3 Karten $(A,K,D)$ in dieser Reihenfolge sind, gerade $\frac{4}{4\cdot 6}\cdot\frac{4}{4\cdot 6-1}\cdot\frac{4}{4\cdot 6-2}$. Das wir $(A,K,D,B,10)$ in dieser Reihenfolge erhalten hat analog die Wahrscheinlichkeit

$$\frac{4}{4\cdot 6}\cdot\frac{4}{4\cdot 6-1}\cdot\frac{4}{4\cdot 6-2}\cdot\frac{4}{4\cdot 6-3}\cdot\frac{4}{4\cdot 6-4}$$

Und da es uns auf die Reihenfolge der Karten nicht ankommt erhalten wir insgesamt als Wahrscheinlichkeit

$$5!\cdot \frac{4}{4\cdot 6}\cdot\frac{4}{4\cdot... ...rac{4}{4\cdot 6-3}\cdot\frac{4}{4\cdot 6-4} =\frac{128}{5213}\sim 0.024$$

Bei $4\cdot 9$ Karten wäre das entsprechend

$$5!\cdot \frac{4}{36}\cdot\frac{4}{36-1}\cdot\f... ...-2}\cdot\frac{4}{36-3}\cdot\frac{4}{36-4} =\frac{512}{129591}\sim 0.004$$

Bei $4\cdot 5$ Karten wäre das entsprechend

$$5!\cdot \frac{4}{20}\cdot\frac{4}{19}\cdot\frac{4}{18}\cdot\frac{4}{17}\cdot\frac{4}{16} =\frac{64}{969}\sim 0.066$$

Die Wahrscheinlichkeit beim Würfelpoker ein full-hand mit sagen wir 2 Assen und 3 Könige zu würfeln können wir analog wie folgt bestimmen: Ein günstiger (der $6^5$ möglichen) Würfe wäre $A,A,K,K,K$. Es gibt soviel Umordnungen dieses Falles wie 2-elementige Teilmengen der Plätze 1 bis 5 die den Positionen der Asse entsprechen, also ist die Wahrscheinlichkeit $\binom{5}{2}\,\frac1{6^5}=\frac{5}{3888}\sim 0.0013$. Es gibt $6\cdot 5$ verschiedene Arten von full-houses, also ist die Wahrscheinlichkeit irgendein full-house zu würfeln $6\cdot 5\cdot \frac{5}{3888}=\frac{25}{648}\sim 0.039$.

Beim Kartenspiel hingegen erhalten wir als Wahrscheinlichkeit von 2 Assen und 3 Königen

$$\binom{5}{2}\cdot \frac{4}{4\cdot 6}\cdot\frac... ...ac{3}{4\cdot 6-3} \cdot\frac{2}{4\cdot 6-4} =\frac{1}{1771}\sim 0.00056$$

und somit für irgend ein full-house $30\cdot \frac{1}{1771}\sim 0.017$.