Binomialkoeffizient < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:08 Do 23.10.2008 | | Autor: | Shelli |
| Aufgabe | | Zeige (n über k) Element N. Ist A eine n-elementige Menge, so ist (n über k) die Anzahl der k-elementigen Teilmengen. |
Hallo!
Wie beweise ich, dass [mm] \vektor{n \\ k} [/mm] Element von N ist??
Kann ich außerdem die Aufgabe beweisen, in dem ich [mm] \summe_{i=1}^{n} \vektor{n \\ k} [/mm] = [mm] 2^n [/mm] setze, da [mm] 2^n [/mm] die Anzahl der Teilmengen ist? Kann ich das so machen und dann mit vollständiger Induktion beweisen?
Wäre echt dankbar über ein paar Tipps. Weiß leider überhaupt nicht wie ich an Beweise rangehen soll.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:44 Fr 24.10.2008 | | Autor: | koepper |
Hallo,
Daß ${n [mm] \choose [/mm] k}$ die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge ist, zeigst du über vollständige Induktion:
Zeige zuerst, daß ${n [mm] \choose [/mm] 1} = n$ die Anzahl der 1-elementigen Teilmengen ist (trivial).
Konstruiere dann die Anzahl der k+1-elementigen Teilmengen aus der Anzahl der k-elementigen, indem du zu jeder k-elementigen Teilmenge ein weiteres Element hinzunimmst. Dabei ergeben sich aber alle k+1-elementigen TM mehrfach (wie oft?)
${n [mm] \choose [/mm] k} [mm] \in \IN$ [/mm] für $n, k [mm] \in \IN$ [/mm] folgt dann daraus.
LG
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:02 Fr 24.10.2008 | | Autor: | Shelli |
Vielen Dank!
Habs jetzt doch hingekriegt, aber gut zu wissen, dass du denselben Lösungsweg hast... :)
|
|
|
|
