Zeichenfolge 11 in endlicher Folge aus 0en und 1en

25/05/2009 - 16:21 von Stephan Gerlach | Report spam
Vorhin las ich zufàllig irgendwo an einem Aushang eine Knobel(?)aufgabe
zur Wahrscheinlichkeitstheorie, die in verallgemeinerter Form auf
folgendes Problem hinauslàuft:

Wieviele mögliche Zeichenfolgen der Lànge n, wobei jedes der n Zeichen
nur 0 oder 1 sein kann, gibt es, in denen mindestens einmal eine Kette
aus k 1-en auftaucht?
(Es bezeichne a_{k,n} diese Anzahl.)

Also z.B. n = 5, k = 2; dann ist a_{2,5} = 19:
1. 00011
2. 00110
3. 00111
4. 01011
5. 01100
6. 01101
7. 01110
8. 01111
9. 10011
10. 10110
11. 10111
12. 11000
13. 11001
14. 11010
15. 11011
16. 11100
17. 11101
18. 11110
19. 11111

Selbst im Fall k = 2 ist es IMHO nicht trivial (OK, Ansichtssache...),
z.B. aus a_{2,2}, a_{2,3}, ... , a_{2,n} die Anzahl a_{2n+1} rekursiv
herzuleiten. Das "Gegenereignis" betrachten, also gewissermaßen
2^n-a{2,n} auszurechnen, klappt auch nicht so richtig. (Oder es ist
trivial, und ich sehe nur die triviale Lösung nicht.)



Eigentlich sollte Brain 1.0 laufen.


gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
 

Lesen sie die antworten

#1 Helmut Richter
25/05/2009 - 17:07 | Warnen spam
On Mon, 25 May 2009, Stephan Gerlach wrote:

Selbst im Fall k = 2 ist es IMHO nicht trivial (OK, Ansichtssache...), z.B.
aus a_{2,2}, a_{2,3}, ... , a_{2,n} die Anzahl a_{2n+1} rekursiv herzuleiten.
Das "Gegenereignis" betrachten, also gewissermaßen 2^n-a{2,n} auszurechnen,
klappt auch nicht so richtig. (Oder es ist trivial, und ich sehe nur die
triviale Lösung nicht.)



Der Fall k=2 ist relativ simpel. Sei b_n die Anzahl der Muster der Lànge n
ohne 11, die auf 0 enden und c_n die auf 1 enden. An beide (b und c) darf
man 0 anhàngen, ohne dass 11 neu entsteht und nur an die ersteren (b) darf
man auch 1 anhàngen, also:

b_n = b_n-1 + c_n-1
c_n = b_n-1

c in die erste Gleichung eingesetzt ergibt die Fibonacci-Folge. Die a_n
sind dann der Rest: a_n = 2^n - F(n+2). Für n=5 ergibt sich 32 - 13 = 19.

Helmut Richter

Ähnliche fragen