Kombinatorischer Beweis

Neue Frage »

Cara456 Auf diesen Beitrag antworten »
Kombinatorischer Beweis
Meine Frage:
Kann jemand mir bitte bei folgender Aufgabe helfen?

Es seien natürliche Zahlen. Finden Sie einen kombinatorischen Beweis für die Gleichung




Wäre super, super dankbar!!!! Bitte helft mir!!!!




Meine Ideen:
Ich weiß, dass "n über k" für die Auswahlmöglichkeiten von n Elementen aus einer m-elementigen Gesamtmemge steht ...

Leider komme ich nicht weiter
HAL 9000 Auf diesen Beitrag antworten »

Denk dir eine dichotome Grundgesamtheit (wie bei der hypergeometrischen Verteilung, mit der diese deine Summe übrigens eng verwandt ist) von Elementen eines Typs 1 sowie Elementen eines anderen Typs 2, davon abgesehen aber alle Elemente unterscheidbar.

Jetzt wählst du Elemente aus, dafür gibt es mögliche Auswahlanzahlen. In wie vielen dieser Auswahlen hast du dann genau Elemente vom Typ 2 ? Und für welche Werte macht die vorgenannte Frage überhaupt Sinn?


P.S.: Übrigens kann man die zu beweisende Summe auch zu



umschreiben, d.h., den Indexbereich für so einengen, dass keine Summanden mehr berücksichtigt werden, wo einer der beiden Faktoren oder sowieso zu Null wird. Davon bleibt unbenommen, dass die Formel generell nur für angewandt werden darf.
Leopold Auf diesen Beitrag antworten »

siehe auch hier
Cara456 Auf diesen Beitrag antworten »

Vielen Dank euch beiden! Habe die Aufgabe nun verstanden! Kann ich die neu gewonnene Erkenntnis auf die folgende Aufgabe anwenden, oder wird hier ein anderes Vorgehen verlangt?

Denn ich komme mit der Aufgabe nicht ganz zu recht, ich glaube, mir fehlt das letzte Puzzlestück. Könntet ihr mir einen Tipp geben?


"Es sei eine natürliche Zahl. Zeigen Sie, dass die Anzahl der -Tupel , für die
gilt, gleich

ist."
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Cara456
"Es sei eine natürliche Zahl. Zeigen Sie, dass die Anzahl der -Tupel , für die gilt, gleich ist.

Du bist ein wenig schludrig, was die Indizes betrifft. Ich nehme stark an, es muss eigentlich

Zitat:
Zeigen Sie, dass die Anzahl der -Tupel , für die gilt, gleich ist.

heißen. Zur Lösung siehe

Kombinationen mit Wiederholung (Mengendarstellung),

dazu führt man eine Schlupfvariable ein mit dann .
Cara456 Auf diesen Beitrag antworten »

Ja, stimmt, danke fürs Korrigieren! Krass, dass dir so etwas auffällt, du bist echt gut! Und danke für de Tipp!!!! smile

Wir haben es hier dann also mit einer Kombination mit Wiederholung zu tun ... Mal sehen, was sich daraus machen lässt
 
 
Cara456 Auf diesen Beitrag antworten »

Hm ... Aber wie beweist man denn nun die Identität? Soll ich eine bijektive Abbildung entwerfen?
Cara456 Auf diesen Beitrag antworten »

Leider bringt mich dein Tipp nicht weiter ... ich verstehe nicht ganz, wörauf du hinauswillst
HAL 9000 Auf diesen Beitrag antworten »

Vielleicht mal etwas länger als zwei Minuten drüber nachdenken. Mit dem Tipp "Schlupfvariable" sowie dem Link zur Mengendarstellung der Kombinationen mit Wiederholung sollte es machbar sein für jemanden, der sich ein wenig anstrengt.

EDIT: So kann man ggfs. auch zum Erfolg kommen https://www.mathelounge.de/663941/kombin...mialkoeffizient , viel Erfolg.
Cara456 Auf diesen Beitrag antworten »

Du hast recht, danke! Also ich habe es jetzt so gelöst:


Wir führen eine Schlupfvariable ein, so dass


Die Menge der -Tupel, die diese Gleichung erfüllen, lässt sich wie folgt darstellen


{ {} }


Dies ist zugleich die Menge aller Kombinationen mit Wiederholung von Dingen zur Klasse .


Die Menge der -Tupel mit ist somit gleich








Was stört, ist das im unteren Teil des Binomialkoeffizienten. Habe ich irgendwo einen Fehler gemacht?
HAL 9000 Auf diesen Beitrag antworten »

Du hast ja auch die falsche Formel genommen! Richtig für " aus mit Wiederholung" ist Anzahl .
Cara456 Auf diesen Beitrag antworten »

Ah! Vielen, vielen Dank!
Cara456 Auf diesen Beitrag antworten »

Aber woher wissen wir, dass ?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Cara456
Aber woher wissen wir, dass ?

Das wissen wir nicht, weil es auch nicht wahr ist. Was soll denn dieser Unfug? unglücklich

Die Gleichheit, die ich da angegeben habe, rührt von der bekannten Symmetrie des Binomialkoeffizienten her.
Leopold Auf diesen Beitrag antworten »

Zitat:
Original von Cara456
Ja, stimmt, danke fürs Korrigieren! Krass, dass dir so etwas auffällt, du bist echt gut! Und danke für de Tipp!!!! smile


Ich weiß jetzt nicht, ob ich ob dieser Aussage lachen oder weinen soll. Man freut sich ja über jedes echte Lob, sicher auch unser HAL. Aber dieses Lob? Echt krass, daß einem Mathematiker der Unterschied zwischen m,n,0 und 1 auffällt! Wow! Waaaaahnsinnig … Prost
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Leopold
Man freut sich ja über jedes echte Lob, sicher auch unser HAL.

Na sicher freu ich mich darüber. Es bedeutet z.B., dass mein nächster Optikerbesuch vielleicht doch noch etwas Zeit hat, obwohl es letzthin andere Anzeichen gab. smile
Cara456 Auf diesen Beitrag antworten »

Okay, mein Fehler, sorry; mir als Anfängerin kam es zumindest beeindruckend vor Big Laugh

Und HAL 9000 hat es ja auch drauf, daran besteht kein Zweifel


Noch einmal eine Frage zur Mengendarstellung: Wie kommt man eigentlich von


{}


auf die Formel für Kombinationen mit Wiederholung?

Bzw.: Wie kommt man darauf mittels doppeltem Abzählen? Könntet ihr mir bitte, bitte noch bei dieser letzten Frage helfen?
Ulrich Ruhnau Auf diesen Beitrag antworten »
RE: Kombinatorischer Beweis
Zitat:
Es seien l,m,n natürliche Zahlen. Finden Sie einen kombinatorischen Beweis für die Gleichung

Was HAL 9000 darstellt in Ehren! Aber geht es nicht auch einfacher?

Wie viele Möglichkeiten gibt es, aus verschiedenen Kugeln genau auszuwählen? Dazu teilen wir die Kugel auf und legen die ersten n Kugeln in die erste Urne und die nächsten m Kugeln in die zweite. Dann ist Zahl der Möglichkeiten aus Kugeln genau auszuwählen die Summe der Möglichkeiten einen Teil der Kugeln (hier ) aus der ersten Urne zu beziehen und den Rest (hier ) aus der zweiten.

Leopold Auf diesen Beitrag antworten »
RE: Kombinatorischer Beweis
Zitat:
Original von Ulrich Ruhnau
Was HAL 9000 darstellt in Ehren! Aber geht es nicht auch einfacher?


Und wo ist jetzt der prinzipielle Unterschied zu HALs Lösung? Gut, du hast seinen Ansatz in einem bekannten Modell realisiert, das mag didaktisch hilfreich sein, weil es die "Angstschwelle" beim Fragesteller herabsetzt (das habe ich aber auch schon getan). Aber das war es dann auch. Einen irgendwie neuartigen Gedanken kann ich hier nicht entdecken. In allen Ehren!
HAL 9000 Auf diesen Beitrag antworten »

Naja, der Ulrich Ruhnau ist gerade dabei, die Threads der letzten Monate abzuklappern und gibt dort seine Kommentare ab, wo seiner Meinung nach die Erklärungen nicht gut genug sind. Auch wenn diese Kommentare die meisten der Fragesteller nicht mehr erreicht, ist es natürlich sein gutes Recht das zu tun.


Aber eine Nachfrage sei noch gestattet:

Zitat:
Original von Ulrich Ruhnau
Dazu teilen wir die Kugel auf

In zwei Halbkugeln? verwirrt
Neue Frage »
Antworten »



Verwandte Themen

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