Strings und Teilstrings < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:48 So 07.11.2010 | | Autor: | Kato |
| Aufgabe | Bestimmen Sie die Anzahl binärer Strings der Länge n, in denen der Teilstring 01 genau einmal vorkommt.
Beispiel (n = 10):
1100001110 |
Guten Abend,
habe mir folgendes überlegt:
Ich zerlege den String in vier Teilstrings, sagen wir a1, a0, b1, b0, dabei besteht a1 nur aus Einsen, a0 nur aus Nullen, b1 nur aus Einsen und b0 nur aus Nullen. Addiert man ihre Längen zusammen kommt man auf n. a1, a0, b1, b0 müssen in dieser Reihenfolge im String vorkommen, wobei a1 und b0 auch Länge 0 haben können.
Schön und gut soweit nur weiß ich jetzt nicht, wie ich das in Relation zu der Anzahl der Möglichkeiten setzen soll. Was mich am meisten irritiert ist, dass ich die richtige Antwort [mm]{n+1 \choose 3}[/mm] zwar kenne, aber überhaupt nicht nachvollziehen kann. Wieso drei, wenn ich doch vier Teilmengen/strings habe und wieso n+1.
Ich bitte um eure Hilfe und habe diese Frage in keinem anderen Forum gestellt.
Liebe Grüße
Kato
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:58 So 07.11.2010 | | Autor: | Sax |
Hi,
> Bestimmen Sie die Anzahl binärer Strings der Länge n, in
> denen der Teilstring 01 genau einmal vorkommt.
> Beispiel (n = 10):
> 1100001110
> Guten Abend,
>
> habe mir folgendes überlegt:
>
> Ich zerlege den String in vier Teilstrings, sagen wir a1,
> a0, b1, b0, dabei besteht a1 nur aus Einsen, a0 nur aus
> Nullen, b1 nur aus Einsen und b0 nur aus Nullen. Addiert
> man ihre Längen zusammen kommt man auf n. a1, a0, b1, b0
> müssen in dieser Reihenfolge im String vorkommen, wobei a1
> und b0 auch Länge 0 haben können.
Die Idee ist sehr gut.
Beachte aber, dass beim Übergang a0b1 der String 01 vorkommen muss.
Zähle also nur die in deinem Beispiel nicht fett gedruckten Nullen und Einsen, d.h. du zerlegst in vier Teilstrings a1, a0', b1', b0, wobei a0' eben eine 0 weniger und b1' eine 1 weniger hat als dein a0 und b1.
a1, a0', b1', b0 haben zusammen eine Länge von n-2.
Außerdem gibt es drei Übergänge zwischen a1-a0', a0'-b1' und b1'-b0.
Das macht zusammen (n-2)+3 = n+1 Stellen, nämlich n-2 Ziffern z und drei Übergänge |, die den String eindeutig charakterisieren, dein Beispiel 1100001110 etwa in der Form zz|zzz|zz|z, wobei der mittlere Übergang die Position des 01-Teilstrings beschreibt.
Jede Auswahl der drei Übergangspositionen aus den n+1 Gesamtpositionen stellt einen String der geforderten Art dar und umgekehrt.
> Schön und gut soweit nur weiß ich jetzt nicht, wie ich
> das in Relation zu der Anzahl der Möglichkeiten setzen
> soll. Was mich am meisten irritiert ist, dass ich die
> richtige Antwort [mm]{n+1 \choose 3}[/mm] zwar kenne, aber
> überhaupt nicht nachvollziehen kann. Wieso drei, wenn ich
> doch vier Teilmengen/strings habe und wieso n+1.
>
> Ich bitte um eure Hilfe und habe diese Frage in keinem
> anderen Forum gestellt.
>
> Liebe Grüße
> Kato
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:32 So 07.11.2010 | | Autor: | Kato |
Ich möchte mich ganz herzlich für diese Antwort bedanken. Sie hat mir sehr geholfen. Vielen Dank.
Liebe Grüße
Kato
|
|
|
|
