Kombinatorik + Induktionsbeweis

Neue Frage »

Tost1989 Auf diesen Beitrag antworten »
Kombinatorik + Induktionsbeweis
Meine Frage:
Hallo an Alle,

wir haben folgende Aufgabe gestellt bekommen und ich stehe noch ziemlich auf dem Schlauch:

Sei

die Menge der Monome vom Grad in Variablen.

1. Geben Sie eine Bijektion zwischen und der Menge der -Tupel über mit genau Einsen an.

2. Bestimmen Sie mit Hilfe von Teil 1. (Hier ist die Kardinalität gemeint)

3. Beweisen Sie die in Teil 2 gefundene Formel durch Induktion nach . Hinweis: Zeigen Sie zuerst, dass . Verwenden Sie für den Induktionsschritt die Formel
.

Frage: Mein eigentliches Problem liegt darin, dass die Aufgabenteile aufeinander aufbauen. Bei 2. und 3. weiß ich grob was ich zu tun habe. Allerdings bei der 1. Aufgabe weiß ich nichts genaues mit der Formulierung "Menge der -Tupel über mit genau Einsen" anzufangen. Klingt banal, aber was muss ich mir darunter vorstellen? Wahrscheinlich sehe ich nur den Wald vor lauter Bäumen nicht mehr.

Meine Ideen:
Ich habe ersteinmal versucht mir die Definition zu veranschaulichen:


zu 1: Problem wie oben beschrieben. Es ist klar, dass ich eine Bijektive Abbildung angeben soll.

zu 2 und 3: Würde ich gerne drauf eingehen, wenn ich 1. gelöst habe.

Ich danke schonmal im Voraus für Eure Hilfe!
René Gruber Auf diesen Beitrag antworten »
RE: Kombinatorik + Induktionsbeweis
Zitat:
Original von Tost1989
Ich habe ersteinmal versucht mir die Definition zu veranschaulichen:

Nein - richtig wäre



Zitat:
Original von Tost1989
Allerdings bei der 1. Aufgabe weiß ich nichts genaues mit der Formulierung "Menge der -Tupel über mit genau Einsen" anzufangen. Klingt banal, aber was muss ich mir darunter vorstellen?

Schauen wir uns das an dem von dir angefangenen Beispiel doch genauer an: Das ist die Menge aller 5-Tupel mit genau 3 Einsen, dazu zählen z.B. (1,1,0,1,0) oder (0,1,1,0,1).
Tost1989 Auf diesen Beitrag antworten »
RE: Kombinatorik + Induktionsbeweis
Hallo René,

vielen Dank für deine schnelle Antwort. Die Definition der Tupel war, wie ich es mir schon fast gedacht hatte, sehr simpel - aber ich bin nicht drauf gekommen.

Zum ersten Teil deiner Antwort: Mir leuchtet noch nicht ganz genau ein warum etc. auch Monome 2-ten Grades sind, so wie es die Aufgabenstellung von uns verlangt. Oder reichen da einfach nur zwei Variablen um vom 2-ten Grad zu sprechen?

Die weiteren Aufgaben ergeben dann zumindest einen Sinn: In unserem Beispiel haben wir gesetzt und dann insgesamt eine Menge von 10 Monomen erhalten. Wenn wir nun die 5-Tupel mit genau 3 Einsen betrachten, dann ergeben sich mögliche Tupelvariationen. Also für jedes Element aus meiner Menge gibt es eins aus der Tupelmenge. Die Mengen sind also gleichmächtig, wodurch eine Bijektion überhaupt erst möglich wird. Reicht es dann also, wenn ich einfach das Beispiel zu Aufgabenteil 1 aufschreibe oder müsste man das noch etwas formaler machen?

zu 2: Hier ergibt sich dann ja aufgrund des oben "entdeckten" Zusammenhangs, dass die Menge eine Kardinalität von haben muss.

zu 3: Hier liegt wohl die Hauptaufgabe drin. Muss erstmal gucken, was ich mit dem Hinweis anfagen kann.

Grüße
Tobias
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Tost1989
Mir leuchtet noch nicht ganz genau ein warum etc. auch Monome 2-ten Grades sind

Wie sind denn Monome d-ten Grades bei euch definiert? Doch nicht nur als d-te Potenzen einer Variable??? geschockt

Zitat:
Original von Tost1989
Reicht es dann also, wenn ich einfach das Beispiel zu Aufgabenteil 1 aufschreibe oder müsste man das noch etwas formaler machen?

Du musst überhaupt erstmal eine passende Bijektion angeben, d.h., die für alle möglichen passt, nicht nur dein n=3,d=2. Davon ist weit und breit noch nichts zu sehen, da musst du schon noch einiges an Überlegung investieren. Ich sehe jedenfalls im Finden dieser Bijektion die Hauptdenkleistung bei dieser Aufgabe! Augenzwinkern

Zitat:
Original von Tost1989
zu 2: Hier ergibt sich dann ja aufgrund des oben "entdeckten" Zusammenhangs, dass die Menge eine Kardinalität von haben muss.

EDIT: Nein, ist falsch - denk nochmal nach.

Zitat:
Original von Tost1989
zu 3: Hier liegt wohl die Hauptaufgabe drin. Muss erstmal gucken, was ich mit dem Hinweis anfagen kann.

Ich weiß gar nicht so sehr, was 3. soll: Eigentlich ist 2. doch bereits mit kombinatorischen Grundkenntnissen bewiesen. Kann sein, dass man diese Grundkenntnisse hier bewusst "vergessen" soll. verwirrt
Tost1989 Auf diesen Beitrag antworten »

Hallo René,

Respekt. Du antwortest wirklich flott.

Um ehrlich zu sein. Ich höre momentan Mathe I aus dem Grundstudium. Habe also momentan mehr oder weniger nur mein mathematisches Schulwissen und wir haben Monome nicht explizit in der Vorlesung definiert. Habe also wieder etwas dazugelernt :-).

Zum Auffinden der Bijektion vielleicht ein kleiner Tipp oder Hinweis von deiner Seite: Diese Tupel mit 0 und 1 sind ja sicherlich nicht ohne Grund gewählt. Könnte es sich um eine Abbildung ins Dualsystem handeln? Oder läuft das in eine vollkommen falsche Richtung?

Grüße
Tobias
René Gruber Auf diesen Beitrag antworten »

Ich geb mal für einige deiner Monome des Beispiels n=3,d=2 eine passende Zuordnung an, vielleicht erkennst du das Bildungsprinzip:

 
 
Tost1989 Auf diesen Beitrag antworten »

Hallo René,

ich glaube, dass ich auf dein Bildungsprinzip gekommen bin: Du betrachtest die Buchstabenvariablen als Stellengeber. a steht beispielsweise für die 1. Stelle im Tupel. Wenn wir jetzt eine weitere Buchstabenvariable betrachten, dann rechnen wir die Stelle der ersten hinzu. An die berechneten Stellen schreiben wir Nullen und den Rest des Tupels füllen wir mit Einsen auf. So kann jedem Monom aus M ein eindeutiges (n+d)-Tupel zugewiesen werden.

Ich definiere erstmal die Mengen:

gegeben ist:


Die Menge der (n+d)-Tupel ließen sich dann wie folgt definieren:


zu 1: Suche bijektive Abbildung:
Sei

mit n Einsen und d Nullen. Jetzt werden 's nach oben genannten Prinzip eindeutig die Nullen oder Einsen zugewiesen, wodurch für jedes ein einzigartiges Tupel existiert und umgekehrt. Die Abbildung ist also injektiv und surjektiv also auch bijektiv. Daraus kann man folgern:


zu 2: Da

Jetzt noch meinen vorschnellen Schluss verbessern:


zu 3:
Hier muss ich nun zeigen:

Da sitze ich jetzt grad noch dran.

Gruß
Tobias
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Tost1989
Du betrachtest die Buchstabenvariablen als Stellengeber. a steht beispielsweise für die 1. Stelle im Tupel. Wenn wir jetzt eine weitere Buchstabenvariable betrachten, dann rechnen wir die Stelle der ersten hinzu. An die berechneten Stellen schreiben wir Nullen und den Rest des Tupels füllen wir mit Einsen auf.

Tut mir leid, so geschrieben verstehe ich nicht, wie die Bijektion aussehen soll. Mal ein Test, ob es nur die Ausdrucksweise ist und du das Prinzip trotzdem verstanden hast:

Welches Monom (mit Variablen ) wird nach dem obigen Prinzip in auf das Tupel (0,0,1,0,1,1,1,0,0,0,1,0) abgebildet?
Tost1989 Auf diesen Beitrag antworten »

Hallo René,

das müsste dann:
bzw.
sein!?

Gruß
Tobias
Tost1989 Auf diesen Beitrag antworten »

Hallo René,

das müsste dann:
bzw.
sein!?

Gruß
Tobias
René Gruber Auf diesen Beitrag antworten »

Richtig, so hab ich es gemeint, dann war es nur die Formulierung.

Ich würde es so beschreiben: Jede 0 im Tupel steht für ein Vorkommen einer Variable, während eine 1 für das Fortrücken zur nächsten Variable steht. In dem Sinne sind die Einsen als Trennstriche zwischen den Variablenexponenten zu verstehen, und die Exponenten selbst sind durch die Anzahl fortlaufender Nullen zwischen den Einsen (oder am Anfang bzw. Ende) gegeben.

Ist aber womöglich Geschmackssache, was besser verständlich ist, das kann ich wie wohl jeder nicht objektiv genug einschätzen. Augenzwinkern
Tost1989 Auf diesen Beitrag antworten »

Hallo René,

mir fehlt sicher noch ein wenig der "mathematische Blick" und die entsprechend genaue Formulierung - aber bin optimistisch, dass das noch wird. Danke nochmal für deine Hilfe :-).

Grüße
Tobias
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »