Binomialkoeffizient - kombinatorischer Beweis

Neue Frage »

donvito Auf diesen Beitrag antworten »
Binomialkoeffizient - kombinatorischer Beweis
Hallo, wir sollen folgende zwei Formeln "kombinatorisch" zeigen. Ich weiß nur, dass man dazu irgendwas mit Mengen machen muss... und die Eigenschaften des Binomialkoeffizienten darf man auch benutzen.


Den habe ich schon bewiesen, indem ich einfach die Formel mit den Fakultäten eingesetzt habe und dann mit Mathematica) ausgerechnet. Nur kombinatorisch ist das vermutlich nicht.

Dazu fällt mir bisher bloß ein, dass eine n-elementige Menge insgesamt 2^n Teilmengen hat. Soweit so gut, aber wie formt er den rechten Binomialkoeffizienten um?Ich finde keine Formel, welche das bewerkstelligen könnte...
AD Auf diesen Beitrag antworten »

"Kombinatorischer" Beweis heißt das deswegen, weil man eben nicht viel rechnen, sondern mehr überlegen und interpretieren sollte. Im vorliegenden Fall könnte das so aussehen:


Zunächst mal macht die Formel nur für Sinn. In diesem Fall ist

die Anzahl der Auswahlmöglichkeiten von aus Grundelementen; die übrigbleibenden Elemente bezeichne ich mal mit Typ A. Weiterhin ist die Anzahl der Auswahlmöglichkeiten von aus diesen in der 1.Stufe ausgewählten Elementen; diese Elemente bezeichne ich mit Typ B und die verbleibenden Elemente letztendlich mit Typ C.


Summa summarum ist dann die Anzahl der Aufteilungsmöglichkeiten von Elementen in Elemente vom Typ A, Elemente vom Typ B und schließlich Elemente vom Typ C.


Dieselbe Anzahl kann man aber auch auf eine andere Art erreichen:

Erst aus den Grundelementen die Elemente vom Typ B wählen (Auswahlanzahl ), und anschließend aus den verbleibenden Elementen die Elemente vom Typ C wählen (Auswahlanzahl ); der Rest ist vom Typ A. Macht dann Auswahlmöglichkeiten.


Viel, sehr viel Text - aber wenig Rechnung. Augenzwinkern
donvito Auf diesen Beitrag antworten »

Ok, danke schonmal... Beim 3. Durchlesen hat es "klick" gemacht Big Laugh

Funktioniert das so auch bei der 2. Aufgabe oder ist hier noch ein anderer Trick notwendig?
AD Auf diesen Beitrag antworten »

Bei dieser zweiten Formel wird ja die erste Formel über summiert. Gemäß dieser Kernaussage

Zitat:
Original von Arthur Dent
Summa summarum ist dann die Anzahl der Aufteilungsmöglichkeiten von Elementen in Elemente vom Typ A, Elemente vom Typ B und schließlich Elemente vom Typ C.

bedeutet das, dass es stets um Aufteilungsmöglichkeiten in Elemente vom Typ A geht, während die völlig freie Wahl von (innerhalb der sinnvollen Grenzen 0 bis r) bedeutet, dass die Aufteilung der restlichen Elemente auf B oder C beliebig ist! Also ergibt sich

(a) Auswahl der Elemente für B oder C (womit A dann automatisch feststeht): Anzahl

(b) Jedes der ausgewählten Elemente kann man B oder C zuordnen: Anzahl (Variationen mit Wiederholung)
Mr-Teddy Auf diesen Beitrag antworten »

Hallo, ich hatte auch die Aufgabe

Allerdings einmal mit der Aufgabenstellung: "Beweisen Sie folgende Gleichung..." und einmal mit "Zeigen Sie..."

Darum meine Frage, ob es sich auch anders herleiten lässt? Ich habe bisher folgenden Ansatz:

AD Auf diesen Beitrag antworten »

Zitat:
Original von Mr-Teddy

Eine blanke Katastrophe - das ist kein Einsetzen, sondern blindes Copy+Paste ohne jeden Sinn und Verstand: Was hat z.B. rechts dieses da zu suchen??? unglücklich

Richtig wird



eingesetzt.
 
 
Mr-Teddy Auf diesen Beitrag antworten »

Oh nein nein, meine Ausführungen waren schon richtig, ich war nur von



ausgegangen. Was ja im Prinzip das Gleiche ist nur andre Buchstaben smile War schon spät gestern ^^ Ja aber was mach ich nun damit?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mr-Teddy
Oh nein nein, meine Ausführungen waren schon richtig,

Das erzähl mal nach einer Klausur: "Oh nein, meine Ausführungen waren schon richtig, ich hab nur eine andere Aufgabe bearbeitet."
Mr-Teddy Auf diesen Beitrag antworten »

Wie dumm von mir, keine Maschine zu sein, die niemals kleine Fehler macht, ich werde daran arbeiten, gleich nachdem ich mich zu tote geschämt habe.

Ich wollte nur kurz alte Aufgaben durchgehen, die ich noch nicht ganz verstanden hatte. Und nicht gleich bei irgendwelchen virtuellen Klausuren durchfallen.
AD Auf diesen Beitrag antworten »

Na du kannst jetzt noch eine Weile rumzicken - oder aber die Binomialkoeffizienten-Definition auf den Ausdruck auf der anderen Seite der nachzuweisenden Gleichung anwenden - und dann vergleichen. Das zweite wäre deutlich konstruktiver.
Mr-Teddy Auf diesen Beitrag antworten »

Also mal davon abgesehen, dass ich nicht angefangen hab, mich an Kleinigkeiten aufzugeilen, war ich so schlau auch schon und würde nicht hier schreiben, wenn ich dabei auf die Lösung gekommen wäre.

Ich denke, ich werde mir die Aufgabe lieber noch einmal schnell von einem Kommilitonen erklären lassen, der antwortet weniger herablassend und dafür hilfreicher.

Schönen Dank auch.
AD Auf diesen Beitrag antworten »

Also rumzicken - wie du willst. Finger2

Zur Erklärung für andere:

Ich sehe Copy+Paste-Fehler der Größenordnung von oben nicht als kleine Fehler an. Derart Hingerotztes zeigt mir eine bedenkliche Acht- und Gedankenlosigkeit an, die umgekehrt von Helfern angeboten bestimmmt auch nicht lustig gefunden werden. Und nur darauf wollte ich deutlich hinweisen, was sogleich schmollend aufgenommen wurde.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »