0 Daumen
404 Aufrufe

Aufgabe:

n ∈ ℕ für die Menge

                Mn := {(a1,...,an ∈{0,1}n : außerdem gibt es kein i ∈ {1,...,n-1}, so dass ai = ai+1 = 0},

0-1-Folgen der Länge n, in denen das Vorkommen von 00 verboten ist.

(a) Angeben der Mengen M2, M3 und M4 (Elemente auflisten). Dazu noch die Kardinalitäten der Mengen bestimmen.
(b) Für n ∈ ℕ liegt die Menge Mn durch Auflistung der Elemente vor. Geben Sie eine Vorschrift
an, wie Sie mit dieser Auflistung die Elemente aus Mn+1 finden können.
(c) Finden Sie mit Ihren Ideen aus Aufgabenteil (b) eine Rekursionsvorschrift1 für |Mn+1|.


Problem/Ansatz:

ich weiß bei der Aufgabe nicht wie ich da vorgehen muss und wo ich anzufangen habe. Es wäre nett, wenn mir jemand erklären könnte was zu tun ist. Ich verlange nicht die Lösung zu den Aufgaben, lediglich worauf ich zu achten habe und was ich bei einer derartigen Aufgabe zu tun habe.

Danke

Avatar von

1 Antwort

0 Daumen

Wenn Du die Anzahl \(|M_n|\) der möglichen Folgen der Länge \(n\) betrachtest, so kannst Du diese aufteilen nach$$|M_n| = k_{n(0)} + k_{n(1)}$$wobei \(k_{n(0)}\) die Anzahl der Folgen sein soll, die auf \(0\) enden und \(k_{n(1)}\) die Anzahl der Folgen, die auf \(1\) enden.

Wenn man nun den Übergang nach \(n+1\) macht, so kann man an jede der \(k_{n(0)}\)-Folgen nur eine \(1\) hängen, die \(0\) wäre ja eine Doppel-\(0\) und nicht erlaubt. Wohingegen man hinter alle der \(k_{n(1)}\)-Folgen sowohl eine \(0\) als auch eine \(1\) hängen kann. Man kann diese Anzahl also verdoppeln. Also ist:$$|M_{n+1}| = k_{n(0)} + 2 k_{n(1)}$$und natürlich lässt sich auch diese Menge in die mit \(0\) und die mit \(1\) endenden aufteilen$$|M_{n+1}| = k_{n+1(0)} + k_{n+1(1)}$$und es ist$$k_{n+1(0)} = k_{n(1)} \\ k_{n+1(1)} = k_{n(0)} + k_{n(1)}$$... mit dem Hinweis sollte alle Unterpunkte kein Problem mehr sein. Falls doch, so frage bitte nach.

Gruß Werner

Avatar von 48 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community