Binomialkoeffizient < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei M eine Menge mit n Elementen und k [mm] \in \{0,...,n\}. [/mm] Beweisen Sie, dass (n über k) die Zahl der k-elementigen Teilmengen vom M ist. |
Hallo,
ich komme leider nicht so richtig mit der Aufgabe klar!
Ich weiss das (n über k) = (n-1 über k-1) + (n-1 über k)
Denke auch dass das ein brauchbarer Ansatz sein könnte.
In einem Beispiel könnte ich es mir so vorstellen:
wenn n=3
und wenn M = [mm] \{1,2,3\}
[/mm]
dann gibt es sechs Möglichkeiten (3*2*1=3 also 3!)
Sind das dann auch die Teilmengen (sechs Teilmengen??)
Wie zeige ich sowas generell bzw. allgemeingültig?
Ein Tipp wäre echt nett!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:17 Di 04.11.2008 | | Autor: | luis52 |
Moin,
da schau her.
vg Luis
|
|
|
| |
|
Hallo und vielen Dank für deine Hilfe, dass ist echt nett!
Also ich habe dem ganzen entnommen das ich die Aufgabe mit vollständiger Induktion beweisen kann.
Normalerweise setze ich ja beim IA n=1 muss ich hier k=1 setzen??
also (n über 1) = n ??
Meine Frage welche Formel nehme ich jetzt für (n über k): n!/1! (n-1)! oder
(n-1 über k-1) + (n-1 über k)
die richtige formel ist doch dann gleich meine Induktionsvoraussetzung oder?
Induktionsschritt ist dann k [mm] \to [/mm] k+1 oder n [mm] \to [/mm] n+1??
Was ist damit gemeint das sich alle k+1 elementigen TM merfach ergeben??
Vielen Dank für Eure Mühe und viele Grüße!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:04 Mi 05.11.2008 | | Autor: | luis52 |
Moin mathefragen0815,
Die zu beweisende Aussage lautet:
Fuer alle [mm] $n\in\IN$ [/mm] gilt [mm] $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, $k=0,1,2,\dots,n$.
[/mm]
IA: Es gilt [mm] $\binom{1}{0}=\frac{1!}{0!(1-0)!}=1$ [/mm] und
[mm] $\binom{1}{1}=\frac{1!}{1!(1-1)!}=1$. [/mm] Die $k=0$-elementige Teilmenge
der $n=1$-elementigen Menge [mm] $\{4711\}$ [/mm] ist
[mm] $\emptyset$ [/mm] und die $k=1$-elementige Teilmenge
der $n=1$-elementigen Menge [mm] $\{4711\}$ [/mm] ist [mm] $\{4711\}$.
[/mm]
IV: Es gilt [mm] $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ [/mm] fuer [mm] $k=0,1,2,\dots,n$.
[/mm]
IB: Es gilt [mm] $\binom{n+1}{k}=\frac{(n+1)!}{k!(n+1-k)!}$ [/mm] fuer [mm] $k=0,1,2,\dots,n,n+1$.
[/mm]
Jetzt du ....
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:26 Do 06.11.2008 | | Autor: | gigi |
> Moin mathefragen0815,
>
>
> Die zu beweisende Aussage lautet:
>
> Fuer alle [mm]n\in\IN[/mm] gilt [mm]\binom{n}{k}=\frac{n!}{k!(n-k)!}[/mm],
> [mm]k=0,1,2,\dots,n[/mm].
>
> IA: Es gilt [mm]\binom{1}{0}=\frac{1!}{0!(1-0)!}=1[/mm] und
> [mm]\binom{1}{1}=\frac{1!}{1!(1-1)!}=1[/mm]. Die [mm]k=0[/mm]-elementige
> Teilmenge
> der [mm]n=1[/mm]-elementigen Menge [mm]\{4711\}[/mm] ist
> [mm]\emptyset[/mm]
wieso leer? um eine wahre aussage zu erhalten, muss ich im ergebnis doch auf 1 kommen?!
und die [mm]k=1[/mm]-elementige Teilmenge
> der [mm]n=1[/mm]-elementigen Menge [mm]\{4711\}[/mm] ist [mm]\{4711\}[/mm].
>
>
> IV: Es gilt [mm]\binom{n}{k}=\frac{n!}{k!(n-k)!}[/mm] fuer
> [mm]k=0,1,2,\dots,n[/mm].
>
> IB: Es gilt [mm]\binom{n+1}{k}=\frac{(n+1)!}{k!(n+1-k)!}[/mm] fuer
> [mm]k=0,1,2,\dots,n,n+1[/mm].
>
> Jetzt du ....
>
>
> vg Luis
>
wie setze ich nun die definition mit der anzahl aller k-elementigen TM hier ein?? über einen weiteren anhaltspunkt wäre ich wirklich dankbar!
gruß und dank
|
|
|
| |
|
> > Die zu beweisende Aussage lautet:
> >
> > Fuer alle [mm]n\in\IN[/mm] gilt [mm]\binom{n}{k}=\frac{n!}{k!(n-k)!}[/mm],
> > [mm]k=0,1,2,\dots,n[/mm].
> >
> > IA: Es gilt [mm]\binom{1}{0}=\frac{1!}{0!(1-0)!}=1[/mm] und
> > [mm]\binom{1}{1}=\frac{1!}{1!(1-1)!}=1[/mm]. Die [mm]k=0[/mm]-elementige
> > Teilmenge
> > der [mm]n=1[/mm]-elementigen Menge [mm]\{4711\}[/mm] ist
> > [mm]\emptyset[/mm]
> wieso leer? um eine wahre aussage zu erhalten, muss ich im
> ergebnis doch auf 1 kommen?!
Hallo,
man betrachtet hier doch gerade die Teilmengen einer einelementigen Menge.
Also Beispiel hat luis die einelementige Menge [mm] \{4711\} [/mm] genommen. (Komisch- die 4711 verwende ich auch für alles mögliche...)
Welches sind ihre Teilmengen?
Da hätten wir als erstes die die Menge [mm] \emptyset, [/mm] welche kein Element enthält.
Dann noch [mm] \{4711\} [/mm] , welche ein element enthält.
Also: eine 0-elementige Teilmenge, nämlich [mm] \emptyset, [/mm] und eine 1-elementige, nämlich [mm] \{4711\}. [/mm]
>
> und die [mm]k=1[/mm]-elementige Teilmenge
> > der [mm]n=1[/mm]-elementigen Menge [mm]\{4711\}[/mm] ist [mm]\{4711\}[/mm].
> >
> >
> > IV: Es gilt [mm]\binom{n}{k}=\frac{n!}{k!(n-k)!}[/mm] fuer
> > [mm]k=0,1,2,\dots,n[/mm].
> >
> > IB: Es gilt [mm]\binom{n+1}{k}=\frac{(n+1)!}{k!(n+1-k)!}[/mm] fuer
> > [mm]k=0,1,2,\dots,n,n+1[/mm].
> >
> > Jetzt du ....
> >
> >
> > vg Luis
> >
> wie setze ich nun die definition mit der anzahl aller
> k-elementigen TM hier ein?? über einen weiteren
> anhaltspunkt wäre ich wirklich dankbar!
Da Du eine induktion machen möchtest, könnte es wohl lohnend sein, den Versuch zu machen, einen Zusammenhang herustellen zwischen der jetzt betrachteten Menge [mm] M_{n+1}:= \{e_1, ..., e_n, e_{n+1} \} [/mm] und [mm] M_n=\{e_1, ...,e_n\}.
[/mm]
Was haben die k-elementigen Teilmengen von [mm] M_{n+1} [/mm] mit denen von [mm] M_n [/mm] zu tun?
Ich finde, man kann sich selbst so gut auf gut Ideen bringen durchs Betrachten konkreter Beispiele.
Kannst ja mal die 3-elementigen Teilmengen von von [mm] \{1,2,3,4,5\} [/mm] aufstellen.
Schau Dir dann die an, die die 5 nicht enthalten und vergleiche mit denen von [mm] \{1,2,3,4\}
[/mm]
Als nächstes betrachte die, die 5 enthalten. Wieviele von 5 verschiedene Elemente sind drin? Stell einen Zusammenhang zu den Teilmengen von [mm] \{1,2,3,4\} [/mm] her.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:56 Do 06.11.2008 | | Autor: | luis52 |
Per definitionem kann man Antworten von Angela nicht perfekter formulieren. 
Aber vielleicht kannst du hier noch etwas Nektar saugen.
vg Luis
|
|
|
| |
|
> Aber vielleicht kannst du
> hier noch etwas
> Nektar saugen.
Gar mühselig ist das Leben der Bienchen sowie der friedlich das Pfeiflein schmauchenden Imkersleut.
Gruß v. Angela
|
|
|
|
