Binomialkoeffizienten < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:03 Mo 06.02.2012 | | Autor: | clemenum |
| Aufgabe | | Man leite den Binomialkoeffizienten mittels der charakteristischen Funktion her. |
Es geht hier im wesentlichen um eine Musterbespiel aus meinem Skript.
Wenn man also das Produkt [mm] $(x+y)^n =(x+y)\cdot [/mm] (x+y) [mm] \cdot \ldots \cdot [/mm] (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.
es scheint "klar" , dass die Codierung eindeutig ist. Ist das so zu verstehen, dass etwa die Codierung 011 eindeutig auf das Monom [mm] $x^2y^0$ [/mm] 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$. Habe ich Richtig verstanden?
Danach wird (in für mich verständliche Weise) geschlossen, dass [mm] $x^ky^{n-k}$ [/mm] 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] := [mm] \{1,2, \ldots,n\}$ [/mm] gibt es eine "offensichtliche" Bijektion: Wir deuten die n-stellige Binärzahl als charakteristische Funktion Funktion [mm] $\chi_A:[n] \rightarrow \{0,1\} [/mm] $ einer gewissen Teilmenge [mm] $A\subseteq [/mm] [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 [mm] \rightarrow [/mm] B $ ohne etwa zu schreiben $x [mm] \mapsto x^2 [/mm] $. 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 [mm] $(x+y)^3 [/mm] $ das Monom $x^2y$ 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 große Hilfe! 
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:13 Di 07.02.2012 | | Autor: | clemenum |
Ist meine Frage echt so trivial, dass jeder denkt, ich müsste sie selbst beantworten können? Oder habe ich damit selbst ein paar von Euch verunsichert, wie die Abbildung genau aussieht?
Über eine kurze Meldung wäre ich Euch dankbar!
|
|
|
| |
|
> Ist meine Frage echt so trivial, dass jeder denkt, ich
> müsste sie selbst beantworten können? Oder habe ich damit
> selbst ein paar von Euch verunsichert, wie die Abbildung
> genau aussieht?
Nene, die Frage ist schon nicht ganz so trivial, aber auch nicht zu schwer.
Ich glaube das Hauptproblem ist, dass man diese Aufgabe "anschaulich" einsehen muss, das ist immer etwas komplizierter zu erklären als wenn man einfach sagen könnte "nimm Formel 14 auf Seite 37 und rechne nach".
MfG
Schadow
|
|
|
| |
|
moin clenum,
> Man leite den Binomialkoeffizienten mittels der
> charakteristischen Funktion her.
> Es geht hier im wesentlichen um eine Musterbespiel aus
> meinem Skript.
>
> Wenn man also das Produkt [mm](x+y)^n =(x+y)\cdot (x+y) \cdot \ldots \cdot (x+y)[/mm]
> formal ausmultiplizieren will, muss man aus einen der [mm]n[/mm]
> Faktoren immer entweder [mm]x[/mm] oder [mm]y[/mm] auswählen.
Soweit ja.
> Jede solche Auswahl lässt sich durch eine Binärzahl mit [mm]n[/mm] Bits
> codieren. Wird aus dem [mm]j[/mm]-ten Faktor [mm]x[/mm] ausgewählt, so setze
> man auf 1, bei [mm]y[/mm] auf 0.
>
> es scheint "klar" , dass die Codierung eindeutig ist. Ist
> das so zu verstehen, dass etwa die Codierung 011 eindeutig
> auf das Monom [mm]x^2y^0[/mm] 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 [mm]k[/mm]. Habe
> ich Richtig verstanden?
Du musst hier auch noch die Reihenfolge beachten.
Also 011 bedeutet: "aus der ersten Klammer das y, aus der zweiten und dritten das x".
Das heißt es geht hier um das Monom [mm] $x^2y^1$.
[/mm]
Dieses würdest du aber auch etwa durch $101$ oder durch $110$ erhalten.
Eindeutig ist das ganze, weil es anschaulich das selbe ist.
Anstatt zu schreiben "erste Klammer: x, zweite Klammer: x, dritte Klammer y,... schreibst du 110...
Das heißt das ist (erstmal) nur eine andere Schreibweise für das Vorgehen und [mm] $\textb{danach}$ [/mm] stellt sich heraus, dass man damit gerade Binärzahlen gebastelt hat.
> Danach wird (in für mich verständliche Weise)
> geschlossen, dass [mm]x^ky^{n-k}[/mm] gleich der Anzahl der
> n-stelligen Binärzahlen, die genau [mm]k[/mm] Einser enthalten,
> ist.
>
> So, und jetzt kommt das für mich unverständliche:
> Zwischen den Mengen aller [mm]n[/mm]-stelligen Binärzahlen, die
> genau [mm]k[/mm] Einser enthalten, und der Familie [mm]k-[/mm]elementigen
> Teilmengen von [mm][n] := \{1,2, \ldots,n\}[/mm] gibt es eine
> "offensichtliche" Bijektion: Wir deuten die n-stellige
> Binärzahl als charakteristische Funktion Funktion
> [mm]\chi_A:[n] \rightarrow \{0,1\}[/mm] einer gewissen Teilmenge
> [mm]A\subseteq [n][/mm].
Das ist so zu verstehen:
Nehmen wir uns als Menge mal die Menge [mm] $\{1,2,3,4,5\}$ [/mm] und als Teilmenge die Menge [mm] $\{1,2,4\}$.
[/mm]
Nun wollen wir diese Teilmenge eindeutig mit einer fünfstelligen Binärzahl identifizieren.
Dazu sagen wir einfach: Wir nehmen uns die Zahlen 1-5 und wenn die jeweilige Zahl in der Teilmenge vorkommt so schreiben wir eine 1, sonst eine 0.
Das heißt obige Teilmenge wäre als Binärzahl: 11010.
Das diese Abbildung oder vielleicht besser Identifikation bijektiv ist siehst du daran, dass sie eben eindeutig umkehrbar ist.
Gebe ich dir etwa die Binärzahl 01100 so weißt du sofort, dass damit die Teilmenge [mm] $\{2,3\}$ [/mm] gemeint ist.
> 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 [mm]f: A \rightarrow B[/mm]
> ohne etwa zu schreiben [mm]x \mapsto x^2 [/mm]. Ich vermisse also
> die konkrete Abbildungsvorschrift, was die Funktion genau
> macht.
Das versteckt sich wahrscheinlich in der "charakteristischen" Funktion.
Ich kenne den Begriff zwar auch nicht, aber guck mal bei dir im Skript nach, vielleicht hattet ihr die irgendwo schonmal.
So, ich hoffe ich konnte dir helfen, wenn noch Fragen offen sind immer her damit.
lg
Schadow
|
|
|
|
