www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - Binomialkoeffizienten
Binomialkoeffizienten < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Binomialkoeffizienten: Herleitung
Status: (Frage) beantwortet Status 
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! :-)


        
Bezug
Binomialkoeffizienten: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

Bezug
                
Bezug
Binomialkoeffizienten: Antwort
Status: (Antwort) fertig Status 
Datum: 10:32 Di 07.02.2012
Autor: Schadowmaster


> 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

Bezug
        
Bezug
Binomialkoeffizienten: Antwort
Status: (Antwort) fertig Status 
Datum: 10:30 Di 07.02.2012
Autor: Schadowmaster

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

Bezug
                
Bezug
Binomialkoeffizienten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:42 Di 07.02.2012
Autor: clemenum

Hallo Schadow!

Vielen Dank für deine Erklärungen - es ist um vieles klarer geworden!! :-)

Wenn noch im laufe meines heutigen Lerntages Fragen auftauchen werden,  schreibe ich sie wieder hinein!

Nochmals, dankeschön! :-)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de