Bijektion von Monomen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| 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
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
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!!!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
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!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
|
