www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Bijektion von Monomen
Bijektion von Monomen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Bijektion von Monomen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:03 Mi 03.11.2010
Autor: mathecrack

Aufgabe
Sei M(n,d) := [mm] \{ \alpha \in \mathbb{N}^{n+1} | \sum_{i=1}^{n+1} \alpha_i =d \} [/mm]
die Menge der Monome vom Grad d in n+1 Variablen.

1. Geben Sie eine Bijektion zwischen M(n,d) und der Menge der (n+d)-Tupel über {0,1} mit genau n Einsen an.
2. Bestimmen Sie |M (n,d)| mithilfe von 1.)
3. Beweisen Sie die in Teil 2 gefundene Formel durch Induktion nach n. Hinweis: Zeigen Sie zuerst, dass |M(n,d)| = [mm] \sum_{k=0}^{d} [/mm] |M(n-1,d-k)|. Verwenden Sie für den Induktionsschritt die Formel
[mm] \binom{n}{d} [/mm] = [mm] \binom{n-1}{d-1} [/mm] + [mm] \binom{n-1}{d} [/mm]

# Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Hallo liebe Mathecracks!

Ich brauche gerade mal eure Hilfe, weil ich bei dieser Aufgabe total auf dem Schlauch stehe :(
Habe mir schon überlegt, dass z.B. die Menge M(1,2) {(1,1),(0,2),(2,0)} entspricht, die Menge der (3)-Tupel mit Nullen und Einsen dann {(1,0,0),(0,1,0),(0,0,1)}.
Aber wie sieht jetzt z.B. die Bijektion aus? Da die Aufgabe unter dem Thema Kombinatorik steht, vermute ich, dass irgendein Binomialkoeffizient dabei vorkommt.

Leider kann ich Teil 2 und 3 auch nicht machen, wenn ich 1 nicht geschafft habe :(

Ich wäre euch so dankbar, wenn ihr mir helfen könntet - brauch vielleicht auch nur einen Ansatz, um die Aufgabe zu lösen...
Ich hoffe, ihr habt eine Idee für mich ;)
Schonmal vielen Dank im Vorraus

        
Bezug
Bijektion von Monomen: Antwort
Status: (Antwort) fertig Status 
Datum: 09:39 Sa 06.11.2010
Autor: felixf

Moin!

> Sei M(n,d) := [mm]\{ \alpha \in \mathbb{N}^{n+1} | \sum_{i=1}^{n+1} \alpha_i =d \}[/mm]
>  
> die Menge der Monome vom Grad d in n+1 Variablen.
>  
> 1. Geben Sie eine Bijektion zwischen M(n,d) und der Menge
> der (n+d)-Tupel über {0,1} mit genau n Einsen an.
>  2. Bestimmen Sie |M (n,d)| mithilfe von 1.)
>  3. Beweisen Sie die in Teil 2 gefundene Formel durch
> Induktion nach n. Hinweis: Zeigen Sie zuerst, dass |M(n,d)|
> = [mm]\sum_{k=0}^{d}[/mm] |M(n-1,d-k)|. Verwenden Sie für den
> Induktionsschritt die Formel
>  [mm]\binom{n}{d}[/mm] = [mm]\binom{n-1}{d-1}[/mm] + [mm]\binom{n-1}{d}[/mm]
>  # Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>  
> Hallo liebe Mathecracks!
>  
> Ich brauche gerade mal eure Hilfe, weil ich bei dieser
> Aufgabe total auf dem Schlauch stehe :(
>  Habe mir schon überlegt, dass z.B. die Menge M(1,2)
> {(1,1),(0,2),(2,0)} entspricht, die Menge der (3)-Tupel mit
> Nullen und Einsen dann {(1,0,0),(0,1,0),(0,0,1)}.
>  Aber wie sieht jetzt z.B. die Bijektion aus? Da die
> Aufgabe unter dem Thema Kombinatorik steht, vermute ich,
> dass irgendein Binomialkoeffizient dabei vorkommt.

Fuer die Bijektion brauchst du keine Binomialkoeffizienten. Die brauchst du erst bei 2.

Ueberleg dir doch mal, wie du das Tupel $(2, 3, 1)$ darstellen kannts, wenn du 2+3+1 = 6 rote Kieselsteine hast und 2 weisse Kieselsteine, und du diese Kieselsteine neben ein cm-Mass legen kannst (so dass der erste bei 0 cm liegt, der zweite bei 1 cm, etc.).

Hast du eine Idee, wie du das machen kannst? Denk mal etwas darueber nach.

> Leider kann ich Teil 2 und 3 auch nicht machen, wenn ich 1
> nicht geschafft habe :(

Quark. Fuer 2 und 3 brauchst du nur zu wissen, dass es eine Bijektion gibt. Wie die aussieht ist voellig egal.

Versuch doch einfach mal 2 und 3 zu machen!

LG Felix


Bezug
                
Bezug
Bijektion von Monomen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:23 So 07.11.2010
Autor: mathecrack

Danke für die schnelle Antwort!

(2,3,1) kann man sich so vorstellen, dass man erstmal 2 rote
Kieselsteine hinlegt, dann einen weißen, dann wieder 3 rote, einen
weißen und einen roten.

also wenn man die roten Kieselsteine mit 0 verbindet und die weißen mit
1, sieht das so aus:

(0,0,1,0,0,0,1,0)

und über den Weg kommt man dann auf die andere Menge, oder? Das haben
wir uns jetzt zumindest überlegt..
Aber wie gibt man diese Bijektion jetzt am besten an? Einfach sprachlich?

Und davon ausgehend haben wir uns überlegt, dass die Kardinalität der Bijektion (n+d) über n sein muss - also in diesem Beispiel, die Möglichkeiten, die 2 Einsen auf 8 Feldern zu verteilen

Was meinst du? Ist das schon richtig so? Und wie geht das mit der Bijektion?

Vielen Dank nochmal!!!!!

Bezug
                        
Bezug
Bijektion von Monomen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:13 So 07.11.2010
Autor: felixf

Moin!

> Danke für die schnelle Antwort!
>  
> (2,3,1) kann man sich so vorstellen, dass man erstmal 2
> rote
>  Kieselsteine hinlegt, dann einen weißen, dann wieder 3
> rote, einen
>  weißen und einen roten.
>  
> also wenn man die roten Kieselsteine mit 0 verbindet und
> die weißen mit
>  1, sieht das so aus:
>  
> (0,0,1,0,0,0,1,0)
>  
> und über den Weg kommt man dann auf die andere Menge,
> oder? Das haben
>  wir uns jetzt zumindest überlegt..

Genau, so geht das :)

>  Aber wie gibt man diese Bijektion jetzt am besten an?
> Einfach sprachlich?

Man kann das schon explizit machen. Hsat du das Tupel [mm] $(a_1, \dots, a_{n+1})$, [/mm] und willst daraus [mm] $(b_1, \dots, b_{n+d}) \in \{ 0, 1 \}^{n+d}$ [/mm] machen, dann ist [mm] $b_{a_1 + 1} [/mm] = 1$, [mm] $b_{a_1 + a_2 + 2} [/mm] = 1$, usw. (kannst ja sagen wo die $i$-te 1 hinsoll), und alle anderen [mm] $b_i$ [/mm] sind gleich 0.

> Und davon ausgehend haben wir uns überlegt, dass die
> Kardinalität der Bijektion (n+d) über n sein muss - also
> in diesem Beispiel, die Möglichkeiten, die 2 Einsen auf 8
> Feldern zu verteilen

Genau.

> Was meinst du? Ist das schon richtig so? Und wie geht das
> mit der Bijektion?

Das ist richtig. Und bzgl. Bijektion siehe oben.

LG Felix


Bezug
                        
Bezug
Bijektion von Monomen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:00 Mo 08.11.2010
Autor: Matheproof

Hallo,

soll in der 3.Aufgabe das hier gezeigt werden

[mm] \vektor{n+d \\ n} [/mm] =  [mm] \summe_{k=0}^{d}\vektor{n-1+d- k \\ n-1} [/mm] ?


LG Matheproof




Bezug
                                
Bezug
Bijektion von Monomen: Antwort
Status: (Antwort) fertig Status 
Datum: 02:23 Mo 08.11.2010
Autor: felixf

Moin!

> soll in der 3.Aufgabe das hier gezeigt werden
>  
> [mm]\vektor{n+d \\ n}[/mm] =  [mm]\summe_{k=0}^{d}\vektor{n-1+d- k \\ n-1}[/mm]
> ?

Nicht direkt. Es soll $|M(n, d)| = [mm] \binom{n + d}{n}$ [/mm] gezeigt werden.

Dazu soll man erst $|M(n, d)|$ auf eine Kombination der $|M(n - 1, [mm] \bullet)|$ [/mm] zurueckgefuehrt werden und das ganze dann per Induktion gezeigt werden.

LG Felix


Bezug
                                        
Bezug
Bijektion von Monomen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:47 Mo 08.11.2010
Autor: mathecrack

Ach menno, da dachte ich mal, ich hätte es verstanden - und es ist schon wieder so verwirrend.

Also: Induktionsstart ist ja nicht schwierig. Danach geh ich wieder davon aus, dass es für P(n) stimmt und will daraus P(n+1) ableiten. Ich hab das jetzt alles aus der Binomialschreibweise in Brüche verwandelt und versuch jetzt, das irgendwie wieder auf ne Schreibweise zu bringen, die darauf schließen lässt, dass es für n+1 auch gilt.

Aber irgendwie komme ich da nicht weiter. Ich muss das d auch noch irgendwie anpassen, oder? Und was genau meintest du mit $|M(n - 1, [mm] \bullet)|$ [/mm] ? :( Ach mensch, manchmal ist Mathe echt kompliziert!!

Ich wäre dir ganz unglaublich dankbar, wenn du nochmal schnell einen Tipp für mich postest!

Bezug
                                                
Bezug
Bijektion von Monomen: Antwort
Status: (Antwort) fertig Status 
Datum: 09:29 Di 09.11.2010
Autor: felixf

Moin!

> Ach menno, da dachte ich mal, ich hätte es verstanden -
> und es ist schon wieder so verwirrend.
>  
> Also: Induktionsstart ist ja nicht schwierig.

Ja. $M(0, 0)$ besteht aus genau einem Element, und ebenso [mm] $\binom{0}{0} [/mm] = 1$.

Hast du die Formel aus dem Hinweis bewiesen?

> Danach geh
> ich wieder davon aus, dass es für P(n) stimmt und will
> daraus P(n+1) ableiten.

Hast du dir ueberlegt, was $P(n)$ eigentlich sein soll? Wenn ich das hier lese, scheinst du etwas anderes zu nehmen, als die Aufgabenstellung es moechte. Verrat uns es doch mal...

> Ich hab das jetzt alles aus der
> Binomialschreibweise in Brüche verwandelt und versuch
> jetzt, das irgendwie wieder auf ne Schreibweise zu bringen,
> die darauf schließen lässt, dass es für n+1 auch gilt.
>  
> Aber irgendwie komme ich da nicht weiter. Ich muss das d
> auch noch irgendwie anpassen, oder? Und was genau meintest
> du mit [mm]|M(n - 1, \bullet)|[/mm] ? :( Ach mensch, manchmal ist
> Mathe echt kompliziert!!

Mit $|M(n - 1, [mm] \bullet)|$ [/mm] meine ich die Kardinalitaet der Menge $M(n - 1, [mm] \bullet)$, [/mm] wobei [mm] $\bullet$ [/mm] ein Platzhalter ist, fuer den irgendetwas eingesetzt werden kann. Zum Beispiel $k$.

LG Felix


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


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]