Binomialkoeffizient - Teilmengen - Induktion?!

07.11.2010, 09:58

galois

Binomialkoeffizient - Teilmengen - Induktion?!

Hallo,

ich verstehe die Aufgabenstellung hier nicht.

Ich soll zeigen, dass für $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ und $\begin{eqnarray*} 0 \leq i \leq \end{eqnarray*}$ der Binomialkoeffizient $\begin{eqnarray*} \binom n i \end{eqnarray*}$ die Anzahl der $\begin{eqnarray*} i \end{eqnarray*}$ -elementigen Teilmengen einer $\begin{eqnarray*} n \end{eqnarray*}$ -elementigen Menge angibt:
$\begin{eqnarray*} \binom n i = |\{ X | X \subseteq {1,...,n}; |X|=i \} \end{eqnarray*}$

Als Hinweis ist folgendes gegeben:
Hinweis: verwenden Sie Vollständige Induktion über n, indem Sie im Induktionsschritt die k-elementigen Teilmengen X mit Hilfe der Fallunterscheidung $\begin{eqnarray*} n+1 \in X \end{eqnarray*}$ oder $\begin{eqnarray*} n+1 \notin X \end{eqnarray*}$ zählen.

Was muß ich hier tun? Ich möchte keinen Lösungsweg, sondern nur erklärt, was der Hinweis sein soll.
Eine vollständige Induktion für $\begin{eqnarray*} \binom n i \end{eqnarray*}$ etwa? Oder eine vollständige Induktion für die rechte (=Alles was im Betragsstrich steht) Seite?

07.11.2010, 12:11

René Gruber

Auf diesen Beitrag antworten »

Es steht genau da:

Zitat:

Original von galois
verwenden Sie Vollständige Induktion über n

Im Induktionsschritt also $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ , d.h. du musst die Teilmengen der $\begin{eqnarray*} (n+1) \end{eqnarray*}$ -elementigen Menge irgendwie auf Teilmengen einer $\begin{eqnarray*} n \end{eqnarray*}$ -elementigen Menge zurückführen. Genaueres zu diesem "irgendwie" liefert der Rest des Tipps.

07.11.2010, 12:34

galois

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Es steht genau da:

Zitat:

Original von galois
verwenden Sie Vollständige Induktion über n

Ich habe nicht die leiseste Ahnung, was du meinst. Ehrlich nicht.

07.11.2010, 13:01

René Gruber

Auf diesen Beitrag antworten »

Wenn ich noch mehr verrate, ist der Beweis schon fertig. Also lies dir alles nochmal durch und denke mal gründlich drüber nach.

07.11.2010, 18:33

galois

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Wenn ich noch mehr verrate, ist der Beweis schon fertig. Also lies dir alles nochmal durch und denke mal gründlich drüber nach.

Hallo,
ich habe darüber nachgedacht, aber ich habe nach wie vor keine Ahnung, was die Hinweise sein sollen und weiß auch gar nicht in welcher Art und Weise ich die vollständige Induktion verwenden soll...

07.11.2010, 18:39

René Gruber

Auf diesen Beitrag antworten »

Wenn man sich die k-elementigen Teilmengen von {1,2,...,n+1} anschaut, dann kann man die in zwei Bereiche gruppieren:

- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ enthalten, und
- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ nicht enthalten

In beiden Bereichen liegt eine Anzahl von Teilmengen. Beide Anzahlen kann man mit Hilfe der Induktionsvoraussetzung angeben. Die Summe beider Anzahlen ist dann die, für die man den Wert $\begin{eqnarray*} \binom{n+1}{k} \end{eqnarray*}$ nachweisen muss. Wie lauten denn nun die Anzahlen für die beiden von mir angegebenen Fälle?

07.11.2010, 19:04

galois

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Wenn man sich die k-elementigen Teilmengen von {1,2,...,n+1} anschaut, dann kann man die in zwei Bereiche gruppieren:

- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ enthalten, und
- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ nicht enthalten

In beiden Bereichen liegt eine Anzahl von Teilmengen. Beide Anzahlen kann man mit Hilfe der Induktionsvoraussetzung angeben. Die Summe beider Anzahlen ist dann die, für die man den Wert $\begin{eqnarray*} \binom{n+1}{k} \end{eqnarray*}$ nachweisen muss. Wie lauten denn nun die Anzahlen für die beiden von mir angegebenen Fälle?

Ich möchte dir nichts vorheucheln. Ich habe keine Ahnung und kann dir auch deine Frage nicht im Geringsten beantworten.

Es geht ja schonmal da los.. Was ist denn überhaupt hier gegeben (Eine Menge X??) und was suche ich? Und warum schaue ich mir n+1 an? Und warum sollten Teilmengen einer Menge X mit n Elementen auf enmal n+1 enthalten?

Möchte zu meiner Verteidigung noch was sagen... Mag gut sein, daß ich in dieser Aufgabe und auch sonst ein hoffnungsloser Fall bin und meine Fragen furchtbar bescheuert klingen mögen, aber ich will das Ganze auch verstehen und selbst lösen können...

Danke!!!

07.11.2010, 19:10

René Gruber

Auf diesen Beitrag antworten »

Also gut:

- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ enthalten:

Die Zahl n+1 ist also drin, da haben wir bereits eins der k Elemente dieser Teilmenge jeweils festgelegt. Ergänzend stammen die anderen k-1 Elemente also aus {1,..,n}, davon gibt es laut Induktionsvoraussetzung genau $\begin{eqnarray*} \binom{n}{k-1} \end{eqnarray*}$ .

- diejenigen, die die Zahl $\begin{eqnarray*} n+1 \end{eqnarray*}$ nicht enthalten:

Das sind dann alles k-elementige Teilmengen von {1,...,n}, davon gibt es laut Induktionsvoraussetzung genau $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ .

Was also letztendlich im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ noch nachzuweisen ist, ist die Gleichung

$\begin{eqnarray*} \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} \end{eqnarray*}$ ,

das ist das Bildungsgesetz des Pascalschen Dreiecks. War das nun so schwer?

07.11.2010, 19:21

galois

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Ich hoffe nicht, dass in den Bachelor-Studiengängen jetzt das selbständige Denken abgeschafft wurde, oder doch?

Wurde es nicht, sonst würden sie uns nicht denselben Stoff wie für Diplomer zumuten. Was haben denn meine Fragen mit meinem Bachelor-Studiengang zu tun?

Außerdem habe ich mir wirklich Gedanken über diese Aufgabe auch gemacht. Fragen werde ich allerdings zukünftig keine mehr Stellen.

Was deine Ausführungen zur Aufgabe angehen: Danke dir dafür vielmals.

07.11.2010, 19:25

René Gruber

Auf diesen Beitrag antworten »

Ich hab's ja bereits zurückgenommen. Aber es macht mich schon wütend, dass eine nicht unbeträchtliche Anzahl von Fragestellern hier - selbst im Hochschulbereich - sich jeglicher Mitarbeit verweigert und sich von vorn bis hinten bedienen lassen will.

07.11.2010, 19:30

galois

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Ich hab's ja bereits zurückgenommen. Aber es macht mich schon wütend, dass eine nicht unbeträchtliche Anzahl von Fragestellern hier sich jeglicher Mitarbeit verweigert und sich von vorn bis hinten bedienen lassen will.

Ich bin der Letzte, der sich keine Gedanken über seine Aufgaben macht. Siehe meine anderen eröffneten Threads. Hier allerdings hatte ich überhaupt keinen Peil, deswegen schrieb ich auch entschuldigend folgenden Part in meinen vorherigen Beitrag:
"Möchte zu meiner Verteidigung noch was sagen... Mag gut sein, daß ich in dieser Aufgabe und auch sonst ein hoffnungsloser Fall bin und meine Fragen furchtbar bescheuert klingen mögen, aber ich will das Ganze auch verstehen und selbst lösen können..."

Wünsche dir mit anderen Fragestellern viel Spaß und weniger Ärger und möchte dir nochmals für deine Hilfe danken, auch wenn ich die Aufgabe immer noch nicht ganz verinnerlicht habe.

Das war jetzt aber wirklich mein letzter Beitrag. Au revoir. smile

08.11.2010, 20:13

MeliW84

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient - Teilmengen - Induktion?!
Hallo, ich habe zwar keine Frage, wollte hier nur mal anmerken, dass ich es super finde, wie hier einem geholfen wird.
Ich studiere auch Bachelor Mathe in Regensburg im ersten Semester und sitze gerade an der gleichen Aufgabe, die ich für Lineare Algebra I am Mittwoch abgeben muss und danke euch für eure Hilfe. Bin selbst am verzweifeln...

Also vielen Dank.

Neue Frage »

Antworten »

Binomialkoeffizient - Teilmengen - Induktion?!

Verwandte Themen