Summen « sjochim.com

Posts Tagged ‘Summen’

Endliche Summen und Produkte

Saturday, February 13th, 2010

Für abelsche Gruppen (K, +) spielt die Summationsreihenfolge bei der Summation endlich vieler Elemente $x_k$ keine Rolle. Sei M also eine endlich Menge mit |M| = m, dann gibt es eine Bijektion:
$\varphi : \{ 1, \dots , m \} \rightarrow M$
Für $k \in M$ gilt dann:
$\sum_{k \in M}{x_k} = x_{\varphi(1)} + \dots + x_{\varphi(m)}$
Oftmals sind die Elemente aus M eine Spanne von Zahlen a bis b mit $a, b \in \mathbb{N}_0$ . Dann gilt:
$\sum_{k \in M}{x_k} = \sum_{n=a}^b{x_n}$
Für $M = \emptyset$ gilt $\sum_{x \in \emptyset}{x} = 0$ .

Für abelsche Gruppen (K, ∙) spielt die Produktreihenfolge beim Produkt endlich vieler Elemente $x_k$ keine Rolle. Sei M also eine endlich Menge mit |M| = m, dann gibt es eine Bijektion:
$\varphi : \{ 1, \dots , m \} \rightarrow M$
Für $k \in M$ gilt dann:
$\prod_{k \in M}{x_k} = x_{\varphi(1)} \cdot \dots \cdot x_{\varphi(m)}$
Oftmals sind die Elemente aus M eine Spanne von Zahlen a bis b mit $a, b \in \mathbb{N}_0$ . Dann gilt:
$\prod_{k \in M}{x_k} = \prod_{n=a}^b{x_n}$
Für $M = \emptyset$ gilt $\prod_{x \in \emptyset}{x} = 1$ .

Für Summen und Produkte gilt wegen den Assoziativ- und Kommutativgesetzen:
$\sum_{k \in M}{x_k + y_k} = (\sum_{k \in M}{x_k}) + (\sum_{k \in M}{y_k})$
$\prod_{k \in M}{x_k + y_k} = (\prod_{k \in M}{x_k}) \cdot (\prod_{k \in M}{y_k})$
Für einen Körper K und $a \in K$ ergeben sich darüber hinaus:
$\sum_{k \in M}{ax_k} = a \sum_{k \in M}{x_k}$
$\prod_{k \in M}{ax_k} = a \prod_{k \in M}{x_k}$

Für Summen gibt es zwei Tricks, die zur einfacheren Berechnung beitragen können:
1. Summationsreihenfolge ändern
2. Teleskopsumme bilden

1. $\sum_{n=1}^m{n} = 1 + 2 + 3 + \dots + n = m + (m - 1) + (m - 2) + \dots + 1 = \sum_{n=1}^m{m - (n + 1)}$
$\Rightarrow 2\sum_{n=1}^m{n} = \sum_{n=1}^m{n} + \sum_{n=1}^m{m - (n + 1)} = \sum_{n=1}^m{m + 1} = m(m + 1)$
$\Rightarrow \sum_{n=1}^m{n} = \frac{m(m + 1)}{2}$

2. Kann man $\sum_{n=1}^m{x_n}$ als $\sum_{n=1}^m{(y_n - y_{n+1})}$ schreiben, nennt man die zweite Summe Teleskopsumme:
$\sum_{n=1}^m{x_n} = \sum_{n=1}^m{(y_n - y_{n+1})} = y_1 - y_2 + y_2 - y_3 + \dots + y_n - y_{n+1} = y_1 - y_{n+1}$
Zum Beispiel gilt:
$\sum_{n=1}^m{\frac{1}{n(n + 1)}} = \sum_{n=1}^m{\frac{1}{n} - \frac{1}{n + 1}} = 1 - \frac{1}{m + 1} = \frac{m}{m + 1}$

Eine weitere sehr wichtige Summe ist die geometrische Summe. In einem Körper K mit $q \in K, n \in \mathbb{N}_0$ gilt:
$(1 - q) \sum_{k=0}^n{q^k} = (\sum_{k=0}^n{q^k}) - q^k + 1 = 1 - q^{n + 1}$
Für q ≠ 1 folgt daraus:
$\sum_{k=0}^n{q^k} = \frac{1 - q^{n+1}}{1 - q}$
Für q = 1 gilt offensichtlich: $\sum_{k=0}^n{q^k} = n + 1$ (da die Summe n+1-Summanden umfasst und jedes $q^k = 1$ ist)

Tags: Endlich, Geometrische Summe, Produkte, Summen, Teleskopsumme
Posted in Analysis, Linear Algebra, Mathematics | 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}$