kombinatorik hilfe zu Aufgabe

Question

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

die Elemente aus Xⁿ als 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 (kⁿ⁺¹ −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.

Comments

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

Answer 1

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 (kⁿ⁺¹ −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

Comments

i) also wie ich verstanden habe , was ist die Mächtigkeit von kⁿIA: |k¹ | = 1IV: für  kⁿ⁺¹IS: |kⁿ⁺¹ | = |kⁿ x k¹| Produktregel = |kⁿ |• |k¹ |   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}