Kombinatorik Aufgabe Wortzerlegung?
Ich habe n und k, die Elemente der natürlichen Zahlen sind:
Dazu habe ich ein Alphabet, das aber nicht angegeben ist. Es gibt ein Wort der Länge n und eine Zerlegung z = u1 u2 ... uk, wobei ui natürlich Element des Alphabets ist. Jetzt soll ich die Anzahl der möglichen Zerlegungen angeben, also alle Möglichkeiten ein Wort in k Abschnitte zu unterteilen, wobei jeder Abschnitt mindestens ein Element enthalten sollte (denke ich zumindest mal, macht sonst ja wenig Sinn).
Beispiel: Das Wort Tier ließe sich unterteilen mit n=4 und k=2
Ti er
T ier
Tie r
hoffe ich habe nichts vergessen. Finde die allgemeine Regel aber nicht. Die Reihenfolge also Tier muss natürlich erhalten bleiben. Danke für Eure Hilfe!
Um die Frage zu verstehen:
1) Tier
2) T ier
3) Tie r
4) Ti er
5) T ie r
6) T i e r
gehen da nicht mehr als k=2 Möglichkeiten ??
Nene k ist die Anzahl der Blöcke, in die du zerlegen darfst: und bei Tier sind das halt die 3 von mir angegeben. Du hast jetzt ja auch 4er Blöcke und 3er gemacht
1 Antwort
Das ist das klassische "Nikolaus verteilt Kekse auf Kinder, jedes Kind bekommt mindestens einen Keksproblem".
Der Nikolaus hat einen Sack mit n Keksen und er fliegt zu k Kindern. Beim ersten Kind lässt er mindestens 1 Keks, beim 2. auch usw.
Das kann man auch formulieren: Er hat einen Sack mit n-k Keksen und fliegt zu k Kindern, aber es muss nicht jeder einen Keks bekommen.
Und das lässt sich so überlegen: Sei n = 8 und k=4
Ich lege die n-k Kekse (also 4) (hier Nullen) in eine Reihe, jetzt mach ich zwischen die Keksportionen für jedes Kind immer einen Strich, ich habe ich brauch k-1 Striche:
0 | 0 0 | | 0
Jetzt bekommt also das erste Kind einen Keks, das zweite zwei, das dritte keinen und das letzte wieder einen (klar?).
Da ich keine Einschränkungen habe, wie viele Kekse jedes Kind haben kann (daher mein Umswitchen von "jeder eins" zu "egal"), repäsentiert jede Kombination aus 4 Nullen und 3 Strichen gerade eine zulässige Keksverteilung.
D. h. ich habe 3 aus 7 (oder 4 aus 7) mögliche Kombinationen.
Allgemein:
Die Anzahl der möglichen Zerlegungen ist
(in deinem Fall 1 aus drei, und das hast du auch richtig berechnet).
Das ist nur ein Trick. Ich weiß, jedes Kind soll mindestens einen Keks bekommen, d. h. k Kekse werden sowieso verteilt. Wenn ich diese rausnehme, dann kann ich hinterher diese Nebenbedingung auch weglassen.
ja hab's gerade auch gemerkt, vielen Dank für deine Hilfe!!
ok ich habe mich verlesen, du hast es ja mit n-k umformuliert. Danke
Nur eine Frage habe ich noch: Wo kommt das n-1 her, also wieso dieser Satz: D. h. ich habe 3 aus 7 (oder 4 aus 7) mögliche Kombinationen.
Ganz genau. Ich habe (weil ja jedes Kind schon einen Keks hat) n-k Kekse und k-1 Striche (weil ich nur k-1 Trenner brauche, um k Portionen zu erhalten). Also sind das n-k + k-1 = n-1 zu belegende Plätze.
Der ganze Kekskram rundherum ist natürlich der Adventszeit geschuldet. Letztlich geht es ja genau da drum: Ich zähle Buchstaben ab und mache einen Strich.
T | ier
Ti | er
Tie | r
Wichtig ist halt der Trick mit dem "einen Keks bekommt jeder, also kann ich n-k Kekse ignorieren".
Wenn ich also wie bei dem Beispiel vier Buchstaben habe und zwei Abschnitte bilden soll, habe ich die Kombinationen
|00
0|0
00|
Jetzt bekommt jeder Abschnitt seinen Grund"keks", d. h. die obigen Kombinationen werden zu
0|000
00|00
000|0
Und jetzt kannst du diese Plätze (also die 0) mit deinen Buchstaben belegen.
0|000 wird zu T | ier usw.
Erstmal vielen Dank aber für mich ist es nicht logisch, dass ein Kind gar keinen Keks bekommt, weil dann k für den Fall k-1 wäre oder nicht, also zu der Zerlegung mit k-1 und n gehört