Practices « sjochim.com

Archive for ‘Practices’

Übung Äquivalenzrelation

Saturday, February 13th, 2010

Seien M eine endliche Menge und ~ eine Äquivalenzrelation auf M, sodass alle Äquivalenzklassen die gleiche Kardinalität k haben. Wie viele Äquivalenzklassen gibt es? Wie viele solche Äquivalenzrelationen kann man auf der Menge $M = \{ 1, \dots , p \}$ geben, wenn p eine Primzahl ist? Gibt es eine Äquivalenzrelation auf $\{ k \in \mathbb{N} : k \leq 78 \}$ , bei der alle Äquivalenzklassen genau sieben Elemente haben?
Sei k die (immer gleich) Kardinalität der Äquivalenzklassen, dann gilt für $v = [x], w = [y] : v = w \ oder \ v \wedge w = \emptyset$ . Denn sei $\alpha \in v \wedge w \Rightarrow x \sim \alpha \sim y \Rightarrow x \sim y \Rightarrow v = w$ . Damit ist $M = \bigcup_{w \in M/ \sim} w$ eine disjunkte Zerlegung von M. Seien $m = \mid M \mid, q = \mid M/ \sim \mid$ sowie $\varphi : \{ 1, \dots , q \} \rightarrow M/ \sim \ bijektiv$ :
$\Rightarrow m = \mid M \mid = \mid \bigcup_{w \in M/ \sim} w \mid = \sum_{w \in M/ \sim}{\mid w \mid} = \sum_{j=1}^q{k} = qk$
$\Rightarrow q = \frac{m}{k}$
Für $M = \{ 1, \dots , p \}$ und die Äquivalenzrelation ~ mit $\mid [x] \mid = \mid [y] \mid = k \ \forall x, y \leq p$ gilt:
$\mid M/ \sim \mid = \frac{p}{k} \in \mathbb{N} \Rightarrow k \mid p \Rightarrow k = 1 \vee k = p$ (da p Primzahl)
Für k = 1 gilt wegen $j \in [j]: (j, k) \in \sim \Leftrightarrow j = k$ , dann ist ~ gerade die Identität.
Für k = p gilt $k \in [j] \ \forall 1 \leq k, j \leq p \Rightarrow \sim = \{ 1, \dots , p \} \times \{ 1, \dots , p \}$
Eine Äquivalenzrelation auf $\{ k \in \mathbb{N} : k \leq 78 \}$ , bei der alle Äquivalenzklassen genau sieben Elemente haben, existiert nicht, da $\frac{78}{7} = 11 \ Rest \ 1$ und daher eine Klasse 8 oder 1 Element haben müsste.

Tags: Äquivalenzrelation, Übung
Posted in Analysis, Functions, Mathematics, Practices | No Comments »

Übung Kardinalität

Saturday, February 13th, 2010

Seien $n \in \mathbb{N}, k_1, \dots , k_r \in \mathbb{N}_0$ mit $\sum_{j=1}^r{k_j} = n$ . Zu zeigen ist, dass die Menge
$A = \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}(\{ l \} ) \mid = k_l, l = \{ 1, \dots , r \}$
die Kardinalität $\mid A \mid = \frac{n!}{k_1! \cdots k_r!}$ hat.

Die Aufgabe ist vergleichbar mit folgendem Szenario:
Sei $S = \{ 1, \dots , n \}$ eine Schule mit n Kindern und r Klassen. Jede Klasse j darf nur (und muss) $k_j$ Kinder haben.
$A = \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid \{ x : f(x) = j \} \mid = k_j \}$ ist die Menge der verschiedenen Klassenzusammenstellungen. Zum Beispiel für r=2 gilt $k_1 + k_2 = n$ und damit $k_2 = n - k_1$ . Dann gilt $\mid A \mid = \mid \mathbb{P}_{k_1}( \{ 1, \dots , n \} ) \mid$ (denn es gibt genau diese Anzahl an Möglichkeiten, die Kinder der ersten Klasse (und somit gleichzeitig alle anderen Kinder) zu verteilen).
$\Rightarrow \mid A \mid = {n \choose k_1} = \frac{n!}{k_1! \cdot (n - k_1)!} = \frac{n!}{k_1! \cdot k_2!}$
Induktionsanfang: n = 1:
$\exists 1 \leq j_0 \leq r : k_{j_0} = 1$ und A enthält nur die Abbildung $f(1) = j_0$
$\Rightarrow \mid A \mid = 1 = \frac{1!}{(1 \cdots 1)} = \frac{n!}{k_1! \cdots k_r!}$
Induktionshypothese:
$\mid A \mid = \mid \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}( \{ j \} ) \mid = k_j \} \mid = \frac{n!}{k_1! \cdots k_r!}$
Induktionsschritt: $n \mapsto n + 1$ :
Seien nun $k_1, \dots , k_r \in \mathbb{N}_0, \sum_{k=1}^r{k_j} = n + 1$ , dann ist:
$A = \{ f : \{ 1, \dots , n + 1 \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}( \{ j \} ) \mid = k_j \} = \bigcup_{j=1}^r \{ f \in A : f(n+1) = j \}$
Mit $A_j := \{ f \in A : f(n+1) = j \}$ ist $A = \bigcup_{j=1}^r A_j$ .
Für $j \not= l$ ist $A_j \cap A_l = \emptyset$ , weil für $f \in A_j \cap A_l$ gilt $j = f(n+1) = 1$ – Widerspruch
$\Rightarrow \mid A \mid = \mid \bigcup_{j=1}^r A_j \mid = \sum_{j=1}^r{ \mid A_j \mid}$
Falls $k_j = 0$ , dann ist $A_j \not= 0$ :
Angenommen $f \in A_j \Rightarrow \mid f^{-1}( \{ j \} ) \mid = k_j = 0, f(n+1) = j \Rightarrow n+1 \in f^{-1}( \{ j \} ) = \emptyset$ – Widerspruch
Also gilt: $\mid A_j \mid = 0 = k_j \frac{n!}{k_1! \cdots k_r!}$
Falls $k_j \geq 1$ , dann ist:
$\lambda_l = \{ {k_l \ falls \ l \not= j \atop k_{j-1} \ falls \ l = j}$
$f^{-1}( \{ l \} ) = f \mid_{ \{ 1, \dots , n \} }$ von $A_j$ in $\{ \lambda : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid \lambda^{-1}( \{ l \} ) \mid = \lambda_l \}$
$\Rightarrow \mid A_j \mid = \frac{n!}{\lambda_1! \cdots \lambda_r!} = k_j \cdot \frac{n!}{k_1! \cdots k_r!}$
Somit erhält man:
$\mid A \mid = \sum_{j=1}^r{\mid A_j \mid} = \sum_{j=1}^r{(k_j \cdot \frac{n!}{k_1! \cdots k_r!})} = (\sum_{j=1}^r{k_j}) \cdot \frac{n!}{k_1! \cdots k_r!} = \frac{(n + 1)n!}{k_1! \cdots k_r!} = \frac{(n + 1)!}{k_1! \cdots k_r!}$

Tags: Funktionen, Kardinalität, Mengen, Übung
Posted in Analysis, Functions, Mathematics, Practices | No Comments »

Übungen Binomialkoeffizient

Friday, February 12th, 2010

1. Seien $T \in \mathbb{P}_6( \{ 1, \dots , 49 \} )$ ein Tipp beim Lotto “6 aus 49″ und k ≤ 6. Zu berechnen ist die Wahrscheinlichkeit w bei einer Ziehung genau k richtige Zahlen zu haben.
Sei X die Menge der sechs-elementigen Teilmengen mit k Treffern:
$X = \{ A \in \mathbb{P}_6( \{ 1, \dots , 49 \} ) : \mid A \cap T \mid = k \}$
Seien darüber hinaus $T_k = \mathbb{P}_k(T)$ die Menge der k-elementigen Teilmengen der Treffer und $N_k = \mathbb{P}_{6-k}( \{ 1, \dots , 49 \} \backslash T \} )$ die Menge an 6-k-elementigen Teilmengen der Nieten.
Dann ist die folgende Abbildung eine Bijektion:
$G : X \rightarrow T_k \times N_k, x \mapsto (t, n)$
$\Rightarrow \mid X \mid = \mid T_k \mid \mid N_k \mid = { \mid T \mid \choose k} { \mid \{1, \dots , 49 \} \backslash T \mid \choose 6-k } = {6 \choose k} {43 \choose 6-k}$
$\Rightarrow w = \frac{ {6 \choose k} {43 \choose 6-k} }{ {49 \choose 6} }$

2. Zu zeigen ist, für alle $m, n \in \mathbb{N}$ gilt: $\sum_{k=1}^{n}{{k + m - 1 \choose m}} = {m + n \choose m + 1}$
Induktionsanfang: n = 1:
Sei $m \in \mathbb{N}$ , dann gilt:
$\sum_1^1{{k + m - 1 \choose m}} = {1 + m - 1 \choose m} = {m \choose m} = 1 = {m + 1 \choose m + 1}$
Induktionsannahme: $\sum_{k=1}^n{{k + m - 1 \choose m}} = {m + n \choose m + 1}$
Induktionsschritt: $n \mapsto n + 1$ :
$\sum_{k=1}^{n+1}{{k + m - 1 \choose m}} = \sum_{k=1}^n{{k + m - 1 \choose m}} + {n + 1 + m - 1 \choose m}$
$= {m + n \choose m + 1} + {m + n \choose m} = {m + n + 1 \choose m + 1}$

3. Berechnung von $\sum_{k=1}^n{k^2}$
$k = {k \choose 1}$ , deshalb gilt m = 1, woraus sich Folgendes ergibt:
$\sum_{k=1}^n{{k + 1 - 1 \choose 1}} = {n + 1 \choose 2} = \frac{n(n - 1)}{2}$ (und somit die Summe den Zahlen 1 bis n)
Für m = 2 ergibt sich:
${n + 2 \choose 3} = \sum_{k=1}^n{k + 1 \choose 2} = \sum_{k=1}^n{\frac{(k + 1)k}{2}} = \frac{1}{2} \sum_{k=1}^n{k^2 + k}$
$= \frac{1}{2} \sum_{k=1}^n{k^2 + \frac{1}{2} \sum_{k=1}^n{k}}$
$\Rightarrow \sum_{k=1}^n{k^2} = 2{n + 2 \choose 3} - \sum_{k=1}^n{k} = 2{n + 2 \choose 3} - {n + 1 \choose 2}$

4. Berechnung von $\sum_{k=1}^n{k^3}$
Für m = 3 ergibt sich:
${n + 3 \choose 4} = \sum_{k=1}^n{k + 2 \choose 3} = \sum_{k=1}^n{\frac{(k + 2)(k + 1)k}{2 \cdot 3}}$
$= \sum_{k=1}^n{\frac{(k^2 + 3k + 2)k}{6}} = \frac{1}{6} \sum_{k=1}^n{k^3 + 3k^2 + 2k}$
$= \frac{1}{6} \sum_{k=1}^n{k^3 + \frac{1}{6} \sum_{k=1}^n{3k^2 + \frac{1}{6} \sum_{k=1}^n{2k}}}$
$\Rightarrow \sum_{k=1}^n{k^3} = 6{n + 3 \choose 4} - 3(2 {n + 2 \choose 3} - {n + 1 \choose 2}) - 2{n + 1 \choose 2}$
$= 6{n + 3 \choose 4} - 6{n + 2 \choose 3} + {n + 1 \choose 2}$

5. Zu zeigen ist: $\sum_{l=0}^k{{n \choose l}{m \choose k - l}} = {n + m \choose k}$
Wie schon in 1. wird eine bijektive Funktion für Potenzmengen definiert:
$\phi : \mathbb{P}_k( \{ 1, \dots , n + m \} ) \rightarrow \bigcup_{l=0}^k \mathbb{P}_l( \{ 1, \dots , n \} ) \times \mathbb{P}_{k-l}( \{n + 1, \dots , m \} )$ ,
$\phi (A) = \{ A \cap \{ 1, \dots , n \}, A \cap \{ n + 1, \dots , m \} )$
a) Sei $\phi (A) = (C, D) = \phi (B) \Rightarrow A = (A \cap \{ 1, \dots , n \} ) \cup (A \cap \{n + 1, \dots , m \} ) = C \cup D$
$= (B \cap \{ 1, \dots , n \} ) \cup (B \cap \{n + 1, \dots , m \} ) = B \Rightarrow$ Injektivität
b) Sei $X \in \bigcup_{l=0}^k \mathbb{P}_l \times \mathbb{P}_{k-l}$ , dann gilt:
$\exists l \in \{ 1, \dots , k \} : X \in \mathbb{P}_l \times \mathbb{P}_{k-l}$
$\Rightarrow \exists Y \in \mathbb{P}_l( \{ 1, \dots , n \} ) \wedge Z \in \mathbb{P}_{k-l}( \{ n + 1, \dots , m \} \ mit \ X = (Y, Z) \Rightarrow$ Surjektivität
Weiter wird $A = Y \cup Z$ definiert, was durch die Disjunktheit dazu führt, dass:
$\mid A \mid = \mid Y \cup Z \mid = \mid Y \mid + \mid Z \mid = l + k - l = k \Rightarrow A \in \mathbb{P}_k( \{ 1, \dots , n + m \} ), \phi (A) = (Y, Z)$
Die Vereinigung $\bigcup_{l=0}^k \mathbb{P}_l( \{ 1, \dots , n \} ) \times \mathbb{P}_{k-l}( \{ n + 1, \dots , m \} )$ ist disjunkt. Damit ergibt sich für die Aufgabenstellung:
${n + m \choose k} = \mid \mathbb{P}_k( \{ 1, \dots , n + m \} ) \mid = \mid \bigcup_{l=0}^k \mathbb{P}_l \times \mathbb{P}_{k-l} \mid = \sum_{l=0}^k{\mid \mathbb{P}_l \cdot \mathbb{P}_{k-l} \mid}$
$= \sum_{l=0}^k{n \choose l}{m \choose k-l}$