 |
 |
 |
 |
 |
 |
Startseite » Forum » Beweis von n über k
Beweis von n über k
Universität / Fachhochschule
Tags: Induktionsbeweis
 
|
  |
|---|
|
Hallo, ich habe mal wieder eine Aufgabe vor mir, wo ich nicht weiterkomme.. Die Aufgabe: Man zeige mittels vollständiger Induktion: ist die Anzahl der k-elementigen Teilmengen von Ich komme schon mit der Aufgabenstellung nicht klar, da ich nicht weiß, was "die Anzahl der k-elementigen Teilmengen" sein soll.. Es wäre toll, wenn mir jmd helfen könnte.. Danke, ebruse |
|
 |
|
Gemeint ist damit, dass man ausrechnen möchte wie viele Teilmenge es gibt, die k-elemente enthalten ein beispiel wäre die menge die menge enthält elemente jetzt frage ich mich wie viele teilmengen es mit elementen gibt die teilmengen sind und es sind 3 teilmengen. das kann man auch über den binomialkoeffizienten berechnen es ist nämlich 3 über jetzt nachdem du evt. die aufgabenstellung verstanden hast, könntest du es ganz allgemein beweisen, wie gesagt geht das üebr vollständige induktion. |
 |
|
hi.. danke erstmal für die erklärung.. aber jetzt habe ich das problem, dass ich nciht weiß, wie genau ich es allgemein mit vollständiger induktion beweisen kann.. ich bin jetzt so weit, dass ich gesagt habe, sei dann folgt oder . dann folgt ja oder dann sage ich ja, die Teilmenge von ist die leere menge und die teilmenge von ist die menge . wenn ich das jetzt aber für versuche weiterzumachen, klappt es nicht.. könntest du mir da weiterhelfen? |
|
|
|
ach so, noch eine ergänzung: sei mit und |
|
|
|
ach so, noch eine ergänzung: sei mit und |
|
|
|
Du möchtest die Teilmengen von untersuchen und kennst für bereits die Antwort. Beachte: Eine k-elementige Teilmenge A von ist - entweder bereits eine k-elementige Teilmenge von weil gilt - oder es gilt und es ist dann eine (k-1)-elementige Teilmenge von Wenn die Anzahl der k-elementigen Teilmengen ist, folgere aus obiger Überlegung, dass gilt. Da diese Rekursion entsprechend auch für gilt, foglt per Induktion sofern du auch den Induktionsanfang hast. |
|
|
|
ok den induktionsanfang hast du ja schonmal gemacht jetzt behauptet man einfach, dass diese aussage für eine n-elementige menge gilt nun betrachtest du eine menge mit elementen und betrachtest alle teilmengen, die nicht das erste element enthalten. Das ist dann sowas wie die anzahl k-elementiger teilmengen aus einer n-elementigen menge. das ist nach voraussetzung über jetzt betrachtest du alle teilmengen, die das erste element der menge beinhalten jede dieser teilmengen hat elemente, aber nur elemente werden "variiert", das erste element fixiert man ja, also ist das die anzahl von k-1-elementigen teilmengen einer n-elementigen menge. das ist nach voraussetzung über insgesamt ergibt sich über über über |
|
|
|
hi, was ich noch nicht verstehe ist der satz: "jetzt betrachtest du alle teilmengen, die das erste element der menge beinhalten jede dieser teilmengen hat elemente, aber nur elemente werden "variiert"..." was meinst du mit elemente werden variiert? |
|
|
|
es ist so, dass du ein element fixierst. Um andere teilmengen zu erhalten tauscht du halt irgendwelche elemente durch andere elemente aus, nur das eine fixierte element muss für den betrachteten fall immer in der menge enthalten sein. und wenn du k-elemente hast, aber eines davon fixiert ist, kannst du nur elemente davon durch andere ersetzen. |
 |
|
jetzt hab ich den beweis.. danke.. :-) |
685042
684865