0 Daumen
537 Aufrufe

Sei X eine endliche Menge mit |X| = k ≥ 1. Wir bezeichnen die Elemente aus X als Buchstaben und

die Elemente aus Xals Wörter über X der Länge n.

Beispiel: Es gilt (S,O,M,M,E,R) ∈ X, falls {S, O,M,E,R} ⊆ X.

i) Sei n ≥ 1. Wie viele Wörter über X der Länge genau n gibt es ? Beweis mit vollständiger Induktion

ii) Sei n ∈ N . Beweisen Sie, dass es (kn+1 −1/k−1) − 1 Wörter über X der Länge höchstens n gibt.

mit geometrische Reihe.

iii) Wir nehmen an, dass {H, F} ⊆ X. Sei A die Menge aller Wörter über X, die mit H beginnen,

an der 8ten Stelle ein F haben und eine Länge zwischen 8 und 13 haben. Sei B die Menge aller

Wörter über X, die die Länge 13 haben.

Bestimmen Sie die Mächtigkeit der Menge A ∪ B.

Avatar von

Es ist immer schöner wenn ihr euch eventuell vorher schonmal gedanken macht und schreibt worin genau die Schwierigkeiten bestehen.

1 Antwort

0 Daumen

i) Sei n ≥ 1. Wie viele Wörter über X der Länge genau n gibt es ? Beweis mit vollständiger Induktion 

Ich könnte mir vorstellen das gibt k^n möglichkeiten. Was kannst du dir vorstellen und was kannst du beweisen?

ii) Sei n ∈ N . Beweisen Sie, dass es (kn+1 −1/k−1) − 1 Wörter über X der Länge höchstens n gibt.

∑ (i = 1 bis n) (k^i) = (k^{n + 1} - 1)/(k - 1) - 1

iii) Wir nehmen an, dass {H, F} ⊆ X. Sei A die Menge aller Wörter über X, die mit H beginnen, an der 8ten Stelle ein F haben und eine Länge zwischen 8 und 13 haben. Sei B die Menge aller Wörter über X, die die Länge 13 haben. Bestimmen Sie die Mächtigkeit der Menge A ∪ B.

|A| = k^6 + k^7 + k^8 + k^9 + k^10 + k^11

|B| = k^13

|A ∪ B| = |A| + |B| - |A ∩ B| = k^6 + k^7 + k^8 + k^9 + k^10 + k^13

Avatar von 488 k 🚀
i) also wie ich verstanden habe , was ist die Mächtigkeit von knIA: |k| = 1IV: für  kn+1IS: |kn+1 | = |kn x k1| Produktregel = |kn |• |k1 |   wie kann man hier die IV anwenden?

Du solltest mal X^n benutzen

Also

IA:

k^n

n = 1

|X^1| = |X| = k

IS: n --> n + 1

|X^{n + 1}| = |X^1| * |X^n| = |X| * k^n = k * k^n = n^{n + 1}

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community