Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Herleitung des Binomialkoeffizienten

Herleitung des Binomialkoeffizienten

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Clemensum

Clemensum aktiv_icon

18:21 Uhr, 06.02.2012

Antworten
Es geht aus einem Beispiel aus meinem Skriptum zu zeigen, dass das Monom xkyn-k genau nk mal auftritt. Dabei darf die kombinatorische Bedeutung vom Binomialkoeffizienten vorausgesetzt werden.

Wenn man also das Produkt (x+y)n=(x+y)⋅(x+y)⋅…⋅(x+y) formal ausmultiplizieren will, muss man aus einen der n Faktoren immer entweder x oder y auswählen. Jede solche Auswahl lässt sich durch eine Binärzahl mit n Bits codieren. Wird aus dem j-ten Faktor x ausgewählt, so setze man auf 1, bei y auf 0.

So, und jetzt steht im Skriptum, dass es "klar" ist, dass die Codierung eindeutig ist. Ist das so zu verstehen, dass etwa die Codierung 011 eindeutig auf das Monom x2y0 zurückzuführen ist? Das wäre mal die Injektivität. Die Surjektivität der Abbildung besteht (meiner Ansicht nach) dadurch, dass dadurch jedes einzelne Monom eine Codierung erfährt, das heißt für alle k. Richtig verstanden?

Danach wird (in für mich verständliche Weise) geschlossen, dass xkyn-k gleich der Anzahl der n-stelligen Binärzahlen, die genau k Einser enthalten, ist.

So, und jetzt kommt das für mich unverständliche:
Zwischen den Mengen aller n-stelligen Binärzahlen, die genau k Einser enthalten, und der Familie k-elementigen Teilmengen von [n]:={1,2,…,n} gibt es eine "offensichtliche" Bijektion: Wir deuten die n-stellige Binärzahl als charakteristische Funktion Funktion χA:[n]→{0,1} einer gewissen Teilmenge A⊆[n].

Ich verstehe im letzten Absatz nicht:
Was wird denn genau auf was abgebildet? Es sind ja nur ganz allgemein die Mengen angegeben, die aufeinander abgebildet werden, aber keine konkrete Abbildungsvorschrift. Es ist etwa so, als würde ich bloß sagen: Wir definieren eine Funktion f:A→B ohne etwa zu schreiben x↦x2. Ich vermisse also die konkrete Abbildungsvorschrift, was die Funktion genau macht.

Nehmen wir der Veranschaulichung halber die Menge [3] her. Wie kann ich hier zeigen, dass in der Entwicklung (x+y)3 das Monom x2y genau 3 mal vorkommt, ohne es ausmultiplizieren zu müssen? Wie kann ich also beweisen, dass die Codierung 110 genau 3-mal vorkommt? Was genau wird hier auf wen (bijektiv) genau 3mal abgebildet? Dies ist mir unklar.

Kann mir jemand dies anhand meines konkreten Veranschaulichungsbeispiel klar machen? Ihr wärd mir jedenfalls eine riesige Hilfe! :-)


Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Online-Nachhilfe in Mathematik
Antwort
hagman

hagman aktiv_icon

22:47 Uhr, 07.02.2012

Antworten
Es wird eine Bijektion zwischen der Menge der n-stelligen Binärzahlen mit genau k Einsern einerseits und der Menge der k-elementigen Teilmengen von [n] andererseits behauptet.
Im von dir gegebenen konkreten Beispiel also eine Bijektion zwischen der Menge {110,101,011} und der Menge {{1,2},{1,3},{2,3}}.
Eine n-stellige Binärzahl ist bei euch offenbar eine Abbildung a:[n]→{0,1}
Jeder solchen Binärzahl a kann man eine Teilmenge von [n] zuordnen, nämlich {x∈[n]:a(x)=1}
und umgekehrt ist für jede Teilmenge A⊆[n] die charakteristische Funktion χA:[n]→{0,1} eine Binärzahl. Diese Zuordnungen sind zueinander invers, also bijektiv.
Zusammengefasst:
Φ:{a|a ist n-stellige Binärzahlt mit k Einsern} →{A|A⊆[n] mit |A|=k}
ist gegeben durch Φ(a)={x∈[n]|a(x)=1} und es ist Φ-1(A)=χA
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.