Vollst.Induktion zu "n über k" < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Seien k,n ∈ N und gelte k ≤ n . Es sei M eine n-elementige Menge. Zeigen Sie: Die Anzahl der k-elementigen Teilmengen Teilmengen von M ist [mm] \vektor{n \\ k} [/mm] |
Also ich weiß das Man das mit Vollständiger Induktion lösen kann/muss. Ein Induktionsanfang ist ja auch schnell gemacht, aber wie ich den Induktionsschritt mache hab ich irgendwie gar keinen Ansatz :( . Also wenn mir eine das vorrechnen könnte, oder wenigstens erklären könnte wie ich vorgehen muss wär ich demjenigen sehr dankbar. :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:43 Do 27.10.2011 | | Autor: | abakus |
> Seien k,n ∈ N und gelte k ≤ n . Es sei M eine
> n-elementige Menge. Zeigen Sie: Die Anzahl der
> k-elementigen Teilmengen Teilmengen von M ist [mm]\vektor{n \\ k}[/mm]
>
> Also ich weiß das Man das mit Vollständiger Induktion
> lösen kann/muss. Ein Induktionsanfang ist ja auch schnell
> gemacht, aber wie ich den Induktionsschritt mache hab ich
> irgendwie gar keinen Ansatz :( . Also wenn mir eine das
> vorrechnen könnte, oder wenigstens erklären könnte wie
> ich vorgehen muss wär ich demjenigen sehr dankbar. :)
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Hallo,
Man geht in der IV davon aus, dass es [mm]\vektor{n \\ k}[/mm] Möglichkeiten gibt, eine k-elementige Teilmenge aus n Elementen auszuwählen.
Wie viele Möglichkeiten gibt es dann, k-elementige Teilmengen auszuwählen, wenn ein neues Element in die Menge kommt (wenn man also jetzt (n+1) Elemente hat?
Nun, man kann zunächst die [mm]\vektor{n \\ k}[/mm] Teilmengen zählen, die man schon aus den ersten n Elementen auswählen konnte.
Neue, noch nicht gezählte Teilmengen entstehen, wenn man das neue
(n+1)-te Element zusammen mit (k-1) der n alten Elementen auswählt.
Die Gesamtzahl der k-elementigen Teilmengen ist somit
[mm]\vektor{n \\ k}[/mm]+[mm]\vektor{n \\ k-1}[/mm].
Gruß Abakus
|
|
|
| |
|
Hallo Abakus!
Danke für deine schnelle Antwort!
Ok also gehe ich im Induktionschritt davon aus das es für (n+1) [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1} [/mm] k-elementige Teilmengen gibt. Und muss dann beweisen, dass das das selbe ist wie [mm] \vektor{n+1 \\ k} [/mm] richtig? Weil das ist dann rum rechnerei das krieg ich hin und hab ich glaub ich auch schonmal so oder so ähnlich gemacht.
Aber eine frage hab ich noch: ich verstehe leider noch nicht ganz wie man darauf kommt das man für (n+1) [mm] \vektor{n \\ k-1} [/mm] dazu addiert. Ich mein ich könnte es einfach voraussetzen und hinschreiben, aber ich wills gerne nachvollziehen können ;)
Gruß
KingArthur
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:29 Do 27.10.2011 | | Autor: | abakus |
> Hallo Abakus!
>
> Danke für deine schnelle Antwort!
>
> Ok also gehe ich im Induktionschritt davon aus das es für
> (n+1) [mm]\vektor{n \\ k}[/mm] + [mm]\vektor{n \\ k-1}[/mm] k-elementige
> Teilmengen gibt. Und muss dann beweisen, dass das das
> selbe ist wie [mm]\vektor{n+1 \\ k}[/mm] richtig? Weil das ist dann
> rum rechnerei das krieg ich hin und hab ich glaub ich auch
> schonmal so oder so ähnlich gemacht.
>
> Aber eine frage hab ich noch: ich verstehe leider noch
> nicht ganz wie man darauf kommt das man für (n+1)
> [mm]\vektor{n \\ k-1}[/mm] dazu addiert. Ich mein ich könnte es
> einfach voraussetzen und hinschreiben, aber ich wills gerne
> nachvollziehen können ;)
>
> Gruß
> KingArthur
Hallo,
es geht um das Zählen derjenigen k-elementigen Teilmengen, die erst dadurch entstehen, dass ein bisher neues (n+1)-tes Element dazukommt.
Diese Teilmengen entstehen dadurch, dass man aus den n alten Elementen (k-1) Elemente auswählt (und noch das neue Element dazugibt). Laut Induktionsvoraussetzung gibt es dafür [mm]\vektor{n \\ k-1}[/mm] Möglichkeiten. (Da wir die Induktion nach n und nicht nach k vornehmen, kann hier durchaus statt vorhin k jetzt k-1 verwendet werden).
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:35 Do 27.10.2011 | | Autor: | KingArthur |
Ok ich glaub jetzt hab ichs kapiert ;)
Danke nochmal! wusste dass es grob so ablaufen muss aber der Ansatz wollte nicht so ganz bisher. Aber jetzt läufts.
Gruß
Arthur
|
|
|
|
