Induktion Teilmengen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:58 So 21.11.2004 | | Autor: | Reaper |
Seien n,k [mm] \in \IN [/mm] mit k <= n, und sei A = {1,....,n}. Zeigen Sie mit Induktion, dass A genau [mm] \vektor{n \\ k} [/mm] Teilmengen mit genau k Elementen hat.
[ [mm] \vektor{n \\ k}= [/mm] n!/(k!(n-k)!) und n! = n.(n-1) ... 3.2.1]
Hab auch nicht den entferntesten Schimmer wie das gehen könnte
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:28 So 21.11.2004 | | Autor: | Hanno |
Hiho!
Sei [mm] $A:=\{1,2,...,n\}$ [/mm] eine Menge der Kardinalität n. Dann gibt es (Induktionsverankerung) genau eine Teilmenge der Kardinalität Null, nämlich die leere Menge.
Dies stimmt mit dem Binomialkoeffizieten [mm] $\vektor{n\\ 0}=\frac{n!}{(n-0)!0!}=1$ [/mm] überein und ist somit unsere Induktionsverankerung. Sei uns für den Induktionsschritt nun die Anzahl an Teilmengen mit k Elementen gegeben, nämlich [mm] $\vektor{n\\ k}$. [/mm] Mit Hilfe dieser Zahl soll nun die Anzahl der k+1-elementigen Teilmengen bestimmt werden Jede der [mm] $vektor{n\\ k}$ [/mm] Teilmengen hat nun n-k Möglichkeiten, sich um ein Element zu erweitern. Jedoch muss hier beachtet werden, dass keine Teilmenge doppelt gezählt wird. Sei nämlich X eine beliebige k-elementige Teilmenge und soll nun X um das Element x erweitert werden, so gibt es genau k weitere k-elementige Teilmengen, die das Element x und k-1 der Elemente von X beinhalten. Diese k Mengen stellen nach Erweiterung mit dem fehlenden Element aus A die gleiche Menge wie X mit x dar. Somit kommt die Menge X mit x genau k+1 Mal vor, einmal wegen der Erweiterung von X, und k mal wegen den anderen k angesprochenen Teilmengen. Somit muss man die errechnete Zahl [mm] $\vektor{n\\ k}\cdot [/mm] (n-k)$ noch mit [mm] $\frac{1}{k+1}$ [/mm] multiplizieren, damit man das richtige Ergebnis erhält. Es ergibt sich also:
[mm] $A_{k+1}=A_{k}\cdot\frac{n-k}{k+1}=\frac{n!}{(n-k)!\cdot k!}\cdot\frac{n-k}{k+1}=\frac{n!}{(n-k-1)!\cdot (k+1)!}=\vektor{n\\ k+1}$, [/mm] q.e.d.
Ich hoffe, ich konnte dir helfen.
Liebe Grüße,
Hanno
|
|
|
|
