Bit-Sequenzen / Wahrscheinlichkeitsrechnung

Neue Frage »

Susi2016 Auf diesen Beitrag antworten »
Bit-Sequenzen / Wahrscheinlichkeitsrechnung
Meine Frage:
Wie viele verschiedene n-Bit-Sequenzen gibt es, in denen die Bitfolge ?01?

a) nicht auftritt,
b) genau einmal auftritt,
c) genau zweimal auftritt?

Hinweis zu b): Eine solche n-Bit-Sequenz muss folgendes Aussehen haben: a Einsen, b Nullen, 0, 1, c Einsen, d Nullen. Die gesuchte Zahl ist also die Anzahl der Lösungen der Gleichung a + b + c + d = n?2 mit a, b, c, d ? N = {0, 1, 2, ?}.

Meine Ideen:
Bisher leider keine Idee.
Leopold Auf diesen Beitrag antworten »

Schreibe bei a) die einzelnen Möglichkeiten an:

1111...1111
1111...1110
...

Und bei b) ist ja ein Hinweis gegeben: ist in nichtnegativen ganzen Zahlen zu lösen. Tip: Die Anzahl der Lösungen ist ein spezieller Binomialkoeffizient.
HAL 9000 Auf diesen Beitrag antworten »

In Hinblick auf eine Analogie der Lösungen a),b),c) kann man a) natürlich auch als die Anzahl der Lösungen der Gleichung mit nichtnegativen ganzen Zahlen auffassen.
Susi2016_ Auf diesen Beitrag antworten »

zu a) habe ich nun folgendes:

- 01 entspricht Teilmenge der Mächtigkeit 2
- Variation Reihenfolge ist wichtig / erste Grundaufgabe der Kombinatorik
- mit Zurücklegen (0,1 stehen auf jedem Platz zur Verfügung)


(n / 2) = 0 ?
Leopold Auf diesen Beitrag antworten »

Das ist ziemlich sinnlos.
Susi2016__ Auf diesen Beitrag antworten »

n hoch 2 = 0 ?
 
 
Susi2016___ Auf diesen Beitrag antworten »

durch einfaches Aufzählen komme ich bei a) auf


1. 1111...1111
2. 1110...1111
3. 1111...1110
4. 0000...0000

4 Sequenzen - gibt es hier keine allgemeine Formel ? Es handelt sich doch um eine Variation mit Zurücklegen ...
Leopold Auf diesen Beitrag antworten »

Zitat:
Original von Susi2016___
durch einfaches Aufzählen komme ich bei a) auf


1. 1111...1111
2. 1110...1111
3. 1111...1110
4. 0000...0000

4 Sequenzen - gibt es hier keine allgemeine Formel ? Es handelt sich doch um eine Variation mit Zurücklegen ...


Ich kann nicht erkennen, wo hier der Zusammenhang mit der Lösung ist.

Vergiß die Formeln. Das geht in der Kombinatorik fast immer schief. Überlege dir lieber, wie Bitfolgen aussehen, die keinen Übergang 01 besitzen:

11111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111110
11111111111111111111111111111111111111111111111111111111111111111111111100
11111111111111111111111111111111111111111111111111111111111111111111111000
...

Wie viele sind das, wenn die Folge insgesamt n Bits besitzt?
susi20166 Auf diesen Beitrag antworten »

Bitfolgen die keinen Übergang 01 besitzen:

Beispiel: 6-Bit-Sequenz

111111
111110
111100
111000
110000
100000.

Lösung: n-Bit-Seqenzen
Leopold Auf diesen Beitrag antworten »

Da fehlt noch eine.
Susi2017 Auf diesen Beitrag antworten »

000000

also n+1 Bit-Sequenzen
Susi2018 Auf diesen Beitrag antworten »

bei b sind es dann

Bitfolge mit einer 01
Beispiel: 6-Bit-Sequenz

010000
001000
000100
000010
000001

Lösung: n-1 Bit-Sequenzen ?
Leopold Auf diesen Beitrag antworten »

Jetzt stimmt es (bezieht sich auf deinen vorletzten Beitrag).

Und in b) mußt du alle Summen bestimmen. Warum das so ist, darüber solltest du später noch einmal genau nachdenken. Jetzt kümmern wir uns erst einmal um diese Anzahl. Hier mal das Beispiel , also :





















Und es sind 10 Möglichkeiten.

Die allgemeine Lösung benutzt einen alten kombinatorischen Trick. Ich nehme einmal das Beispiel . Wir stellen uns vor, wir haben 18 Kugeln, tun davon 2 in die erste, 7 in die zweite, 8 in die dritte und 1 in die vierte Schublade:

oo|ooooooo|oooooooo|o

Und bei würde das so aussehen:

ooo||ooooooooo|oooooo

Statt nun die möglichen Summen zu zählen, kann man auch diese Symbolfolgen aus o und | zählen.
Susi2015 Auf diesen Beitrag antworten »

Bitfolge mit zwei 01

6-Bit-Sequenz:
010100
010001
001010
000101
010100
000101
→ 6

7-Bit-Sequenz
0101000
0010100
0001010
0000101
0100001
0010001
0001001

Lösung: n-Bit-Sequenzen
Susi2018 Auf diesen Beitrag antworten »

Und es sind 10 Möglichkeiten.

woher weiss ich dass a b c d jeweils 0 1 oder 2 annehmen können ?
Susi01 Auf diesen Beitrag antworten »

zu b)

Beispiel: 4-Bit-Sequenz

0100
0010
0001


Das sind doch nur 3 nicht 10 ?
Susi2020 Auf diesen Beitrag antworten »

Statt nun die möglichen Summen zu zählen, kann man auch diese Symbolfolgen aus o und | zählen.

das sind dann aber mehr als 10
Leopold Auf diesen Beitrag antworten »

|||oo -> 0+0+0+2 = 2 -> 0100
||oo| -> 0+0+2+0 = 2 -> 0111
|oo|| -> 0+2+0+0 = 2 -> 0001
oo||| -> 2+0+0+0 = 2 -> 1101
||o|o -> 0+0+1+1 = 2 -> 0110
|o||o -> 0+1+0+1 = 2 -> 0010
o|||o -> 1+0+0+1 = 2 -> 1010
|o|o| -> 0+1+1+0 = 2 -> 0011
o||o| -> 1+0+1+0 = 2 -> 1011
o|o|| -> 1+1+0+0 = 2 -> 1001

Das sind zehn.
Susi20000 Auf diesen Beitrag antworten »

ok, jetzt ist es klar . Ist c richtig ?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Susi20000
Ist c richtig ?

Sprichst du von Aufgabenstellung c) ? Zu der hast du dich bisher ja noch gar nicht geäußert - und vielleicht sollte man auch erstmal b) beenden, d.h., für allgemeines die Anzahlformel aufstellen.
maius_xx1997 Auf diesen Beitrag antworten »

Was bringt mir es, die Symbolfolgen zu zählen bzw. wie komme ich dadurch weiter? Für mich ändert sich dadurch irgendwie nichts...
Neue Frage »
Antworten »



Verwandte Themen

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