Posts Tagged ‘Binomialkoeffizient’

Binomialsatz

Saturday, February 13th, 2010

Die Binomialkoeffizient {n \choose k} ist die Kardinalität, also die Anzahl an Elementen, eines Systems von k-elementigen Elementen einer n-elementigen Menge N = \{ 1, \dots , n \}. Für beliebige a_k, b_k ensteht beim Ausmultiplizieren des Produktes von (a_1 + b_1)(a_2 + b_2) \dots (a_n + b_n) eine Summe über alle Produkte \prod_{j \in E}{a_j} \cdot \prod_{j \in E^c}{b_j}, E \subseteq N. Somit gilt:
\prod_{k=1}^n{(a_k + b_k)} = \sum_{E \subseteq N} {( \prod_{j \in E}{a_j} \cdot \prod_{j \in E^c}{b_j})}
Für a_j = a, b_j = b, \mid E \mid = k ist der entsprechende Summand a^kb^{n-k}, womit gilt:
\prod_{k=1}^n{(a + b)} = (a + b)^n = \sum_{k=0}^n{ \sum_{\mid E \mid=k}{a^kb^{n-k}}}
= \sum_{k=0}^n{ \mid \mathbb{P}_k(N) \mid a^kb^{n-k}} = \sum_{k=0}^n{{n \choose k} a^kb^{n-k}}
Somit gilt kurzgesagt:
(a + b)^n = \sum_{k=0}^n{{n \choose k} a^kb^{n-k}}
Dies ist der sogenannte Binomialsatz, der üblicherweise auch durch Induktion bewiesen wird.
Für n = 2 ergeben sich die binomischen Formeln. Auch die dritte binomische Formel hat eine Verallgemeinerung:
a^{n+1} - b^{n+1} = (a - b) \sum_{k=0}^n{a^kb^{n-k}}

Tags: , ,
Posted in Analysis, 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}

Tags: , ,
Posted in Analysis, Mathematics, Practices | No Comments »

Endliche Mengen & Kardinalität

Thursday, February 11th, 2010

Eine Menge M = \{ 1, \dots , n \} ist für n \in \mathbb{N}_0 genau dann leer, falls n = 0:
M = \{ 1, \dots , 0 \} = \emptyset
In diesem Fall besitzt die Menge die sogenannte Kardinalität \mid M \mid = 0. Die Kardinalität beschreibt die Anzahl von Elementen in einer Menge. Man unterscheidet endliche und unendliche Mengen. Die Menge der natürlichen Zahlen beispielsweise ist unendlich. Man schreibt dann auch \mid \mathbb{N} \mid = \infty. Eine Menge M wird genau dann als endlich bezeichnet, wenn es eine injektive Abbildung f : M \rightarrow \{ 1, \dots , n \} , n \in \mathbb{N}_0 gibt. Die Kardinalität dieser Menge ist dann:
\mid M \mid = min \{ n \in \mathbb{N}_0 : \exists M \rightarrow \{ 1, \dots , n \} \ injektiv \}
Das heißt also, dass quasi jedes Element von M abgezählt und so die Anzahl der Elemente festgestellt wird.

Für zwei Mengen A und B und m \in \mathbb{N}_0 gilt:
1. \mid A \mid = m \Leftrightarrow \exists A \rightarrow \{ 1, \dots , m \} \ bijektiv (d.h. es werden alle Elemente von A durch {1, … , m} abgezählt und keines wird doppelt zugewiesen)
2. Falls es eine Bijektion A \rightarrow B gibt, dann gilt offensichtlich \mid A \mid = \mid B \mid
3. Gilt \mid A \mid = \mid B \mid und ist A oder B endlich, dann gibt es eine Bijektion A \rightarrow B
4. Falls A \cap B = \emptyset, dann ist \mid A \cup B \mid = \mid A \mid + \mid B \mid

Sind M und N zwei endliche Mengen mit \mid M \mid = m, \mid N \mid = n, dann gilt:
1. \mid M \times N \mid = \mid M \mid \mid N \mid
2. \mid \{ f : M \rightarrow N : f \ ist \ Abbildung \} \mid = \mid N \mid^{\mid M \mid} = \mid N^M \mid, wobei n^0 = 1 \ \forall n \in \mathbb{N}_0
3. \mid \mathbb{P} (M) \mid = 2^{\mid M \mid}
4. \mid \mathbb{P}_k(M) \mid = {m \choose k}, wobei \mathbb{P}_k(M) = \{ A \in \mathbb{P}(M) : \mid A \mid = k \}

Beweise:
1. Ist f : N \rightarrow \{ 1, \dots , n \} eine Bijektion, dann ist auch M \times N \rightarrow M \times \{ 1, \dots , n \} eine Bijektion.
Induktionsanfang: n = 0:
\Rightarrow M \times \emptyset = \emptyset \Rightarrow \mid M \times \emptyset \mid = \mid M \mid \mid \emptyset \mid = m0 = 0
Induktionshypothese: \mid M \times N \mid = \mid M \mid \mid N \mid
Induktionsschritt: n - 1 \mapsto n:
M \times N = M \times \{ 1, \dots , n - 1 \} \cup M \times \{ n \}
\Rightarrow M \times \{ 1, \dots , n - 1 \} \cap M \times \{ n \} = \emptyset
\Rightarrow \mid M \times N \mid = \mid M \times \{ 1, \dots , n \} \mid + \mid M \times \{ n \} \mid = \mid M \mid \mid \{ 1, \dots , n \} \mid + \mid M \mid \mid \{ n \} \mid =
= m(n - 1) + m(1) = mn

2. Für die Menge aller Abbildungen von M \rightarrow N schreibt man auch N^M.
Für M = \emptyset existiert genau eine Funktion M \rightarrow N, da jede Relation von der leeren Menge nach N leer ist und damit Teilmenge von \emptyset \times N. Diese leere Relation ist eine Funktion. Für M \not= \emptyset \exists x \in M. Dadurch ist folgende Abbildung eine Bijektion, wodurch die Mengen, dieselben Kardinalitäten haben:
F : N^M \rightarrow N^{M \backslash \{ x \} } \times N, f \mapsto (f(M \backslash \{ x \} ), f(x))
\Rightarrow per Induktion \mid N^M \mid = \mid N^{M \backslash \{ x \} } \times N \mid = \mid N^{M \backslash \{ x \} } \mid \mid N \mid = n^{m - 1}n = n^m

3. Für eine Teilmenge A von M existiert die sogenannte Indikatorfunktion:
I_A : M \rightarrow \{ 0, 1 \} , x \mapsto \{ {1 falls \ x \in A \atop 0 falls \ x \not\in A}
Für die Funktion, welche alle Teilmengen der Potenzmenge auf die Indikatorfunktion abbildet ergibt sich eine Bijektion:
F : \mathbb{P}(M) \rightarrow \{ 0, 1 \} ^M, A \mapsto I_A
\Rightarrow \mid \mathbb{P}(M) \mid = \mid \{ 0, 1 \} ^M \mid = 2^{ \mid M \mid } = 2^m

4. {n \choose k} beschreibt den sogenannten Binomialkoeffizienten. Dieser benutzt die Fakultät n!. Die Fakultät ist definiert durch 0! = 1, \ n! = 1 \cdot 2 \cdot 3 \cdots n. Daraus folgt offensichtlich, dass n! = (n - 1)!n. Der Binomialkoeffizient ist definiert für n \in \mathbb{N}_0, k \in \mathbb{N} durch:
{n \choose k} = \frac{n(n - 1)(n - 2)(n - 3) \cdots (n - (k - 2))(n - (k - 1))}{k!}
Per Definition gilt ausserdem {n \choose 0} = 1 \ \forall n \in \mathbb{N}_0. Offensichtlich ist {0 \choose k} = 0 \ \forall k \in \mathbb{N}.
Für n = 0 = \mid M \mid \Rightarrow M = \emptyset gilt:
Sei k \in \mathbb{N}, dann ist \mathbb{P}_k( \emptyset ) = \emptyset = 0 = {0 \choose k}, \mathbb{P}_0( \emptyset ) = \{ \emptyset \} = 1 = {n \choose 0}.
Für n \not= 0 = \mid M \mid \Rightarrow M \not= \emptyset gilt:
Sei x \in M, dann ist
\mathbb{P}_k(M) = \mathbb{P}_k(M \backslash \{ x \} ) \times \{ A \in \mathbb{P}_k(M) : x \in A \}
die Menge der Potenzmengen ohne das x vereinigt mit den Potenzmengen mit dem x.
\Rightarrow da \ A \mapsto A \backslash \{ x \} eine Bijektion mit \mathbb{P}_{k-1}(N \backslash \{ x \} ) ist, folgt induktiv:
\mid \mathbb{P}_k(N) \mid = \mid \mathbb{P}_k(N \backslash \{ x \} ) \mid + \mid \mathbb{P}_{k-1}(N \backslash \{ x \} ) (der zweite Summand entspricht genau der Anzahl an Teilmengen der Potenzmenge, die durch den Ausschluss von x im ersten Summanden nicht berücksichtigt werden)
Die vorangegangene Gleichung ist dasselbe wie:
{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}
Für n = n + 1 ergibt sich daraus:
{n+1 \choose k} = {n \choose k} + {n \choose k-1}
Dies ist die Formel für das Pascalsche Dreieck, die sich direkt aus dem Binomialkoeffizienten ergibt:
{n+1 \choose k} = \frac{n+1(n) \cdots (n-k+2)}{k!} = \frac{n(n-1) \cdots (n-k+2)}{k!} \cdot (n+1) =
= \frac{n(n-1) \cdots (n-k+2)}{k!} \cdot ((n-k+1)+k) =
= \frac{n(n-1) \cdots (n-k+1)}{k!} + \frac{nk(n-1) \cdots (n-k+2)}{k!} =
= \frac{n(n-1) \cdots (n-k+1)}{k!} + \frac{n(n-1) \cdots (n-k-1+1)}{(k-1)!} = {n \choose k} + {n \choose k-1}

Tags: , , , , , , , , ,
Posted in Analysis, Functions, Linear Algebra, Theory of Sets | No Comments »