Wieder mal Inklusion-Exlusion

25.01.2022, 13:09	inkex	Auf diesen Beitrag antworten »
Wieder mal Inklusion-Exlusion Betrache folgende Wörter (Bem: Wörter ist hier etwas verwirrend) $\begin{eqnarray} \mathcal W_n=\{w=w_1w_2\ldots w_n: w_i \in \{0,1\},\mathrm{für}\ 1\leq i \leq n\} \end{eqnarray}$ $\begin{eqnarray} w\in \mathcal W_n \end{eqnarray}$ heißt zusammengesetzt wenn $\begin{eqnarray} w=u^k=\underbrace{uu\ldots u}_{\mathrm{k Mal}} \end{eqnarray}$ mit $\begin{eqnarray} k\|n,\ k>1,\ u\in \mathcal W_k \end{eqnarray}$ Gesucht: Anzahl der nicht-zusammengesetzten Wörter mit 12 Buchstaben. Wie löst man das? Ich hab mir mal überlegt: Primfaktorzerlegung von 12: $\begin{eqnarray} 12=2\cdot 2\cdot 3 \end{eqnarray}$ A=Menge der zusammengesetzten Wörter der Länge 2 B=Menge der zusammengesetzten Wörter der Länge 3 C=Menge der zusammengesetzten Wörter der Länge 23=6 Und dann $\begin{eqnarray} 2^{12}-\|A\|-\|B\|+\|C\| \end{eqnarray*}$ ?
25.01.2022, 13:38	HAL 9000	Auf diesen Beitrag antworten »
Die Idee ist richtig, die Wortwahl aber etwas missverständlich: $\begin{eqnarray} k \end{eqnarray}$ würde ich nicht als "Länge" bezeichnen, denn die eigentliche Bitlänge solcher Teilwörter $\begin{eqnarray} u \end{eqnarray}$ mit $\begin{eqnarray} u^k\in \mathcal{W}_n \end{eqnarray}$ ist ja dann $\begin{eqnarray} \frac{n}{k} \end{eqnarray}$ . Insofern bekommt man als Ergebnis die Anzahl $\begin{eqnarray} 2^{12}-2^6-2^4+2^2 = 4020 \end{eqnarray}$ heraus. Bei mehr als zwei Primfaktoren von $\begin{eqnarray} n \end{eqnarray}$ muss dann entsprechend die Siebformel ran.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »