0 Daumen
151 Aufrufe

Aufgabe:

Gegeben sei das Alphabet ∑={a, b}. Für jede natürliche Zahl n ist die Menge ∑n definiert
als ∑n={x1,...,xn | x1,...,xn ∈ ∑ }.

Finden Sie eine natürliche Zahl n, sodass |∑n| = 16 und geben Sie die Elemente von
n in quasi-lexikographischer Reihenfolge an.

Beweisen Sie, dass für jede natürliche Zahl n die Formel |Uni=0|=2n+1−1 gilt.


Problem/Ansatz:

Ich hab leider keine Ahnung, wie ich diese Aufgabe lösen kann, deshalb würde ich mich sehr freuen, wenn mir jemand dabei helfen kann^^

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Jedes Element aus \( \Sigma^{n} \) ist ein \( n \) Tupel bestehend aus einer Sequenz von a's und b's. Für jede der \( n \) Positionen im Tupel kann man entweder a oder \( b \) wählen, also gibt es insgesamt \( 2^{n} \) Elemente in \( \Sigma^{n} \).
Nun sind die verschiedenen \( \Sigma^{i} \) disjunkt, also ist

\(\begin{aligned} \left|\bigcup_{i=1}^{n} \Sigma^{n}\right|=\sum \limits_{i=1}^{n} 2^{i}=2^{n+1}-1\end{aligned} \)

wobei die geometrische Reihe verwendet wurde.

Avatar von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community