TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 187

Wieviele verschiedene Variablennamen kann man in einer fiktiven Programmiersprache verwenden, wenn diese Namen aus mindestens einem, höchstens aber vier (nicht notwendig verschieden) Buchstaben {A,...,Z} bestehen müssen, und die Befehle AND, OR, IF, THEN und GOTO nicht als Teilwörter enthalten sein dürfen.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von W wallner

Das Beispiel kann mit dem Inklusions-Exklusions-Prinzip gelöst werden.

Gesucht ist die Menge M der Wörter mit Länge 1 bis 4 ohne die reservierten Teilwörter.

Wir betrachten das Universum E der Wörter mit einer Länge von 1 bis 4. E besteht aus den Mengen $E_{k}$ der Wörter mit Länge k, $k\in \{1,2,3,4\}$. Jede Menge $E_{k}$ enthält alle Variationen mit Wiederholung von k Buchstaben mit jeweils 26 Möglichkeiten, also gilt:

$\left|E_{1}\right|=26^{1}$
$\left|E_{2}\right|=26^{2}$
$\left|E_{3}\right|=26^{3}$
$\left|E_{4}\right|=26^{4}$

Die Gesamtgröße unseres Universums ist also:

$\left|E\right|=\left|E_{1}\right|+\left|E_{2}\right|+\left|E_{3}\right|+\left|E_{4}\right|=26^{1}+26^{2}+26^{3}+26^{4}$

Davon müssen wir jetzt die Vereinigung der Mengen mit den reservierten Teilwörter abziehen. Dabei müssen wir berücksichtigen, dass es Wörter gibt, die mehrere Teilwöter enthalten, und deshalb fälschlicherweise öfters abgezogen werden (z.B.: Das Wort IFOR enthält die beiden Teilwörter IF und OR, darf aber nur einmal abgezogen werden.)

Wir berechnen deshalb die Beträge der reservierten Teilmengen, sowie die Beträge der Vereinigungen mehrerer Teilmengen. Dabei bezeichnet z.B. xOR die Menge aller Wörter, die als erstes einen beliebigen Buchstaben, und als zweiten und dritten die Buchstaben OR enthalten ({AOR, BOR, COR, DOR, ..., ZOR)

Beträge der einzelnen Mengen

$\left|OR\right|=1$
$\left|ORx\right|=26$
$\left|xOR\right|=26$
$\left|ORxx\right|=26^{2}$
$\left|xORx\right|=26^{2}$
$\left|xxOR\right|=26^{2}$

$\left|IF\right|=1$
$\left|IFx\right|=26$
$\left|xIF\right|=26$
$\left|IFxx\right|=26^{2}$
$\left|xIFx\right|=26^{2}$
$\left|xxIF\right|=26^{2}$
 
$\left|AND\right|=1$
$\left|ANDx\right|=26$
$\left|xAND\right|=26$

$\left|THEN\right|=1$

$\left|GOTO\right|=1$

Beträge der Vereinigungen

Es gibt bei unsere Angabe nur 4 mögliche Wörter, die mehr als ein Teilwort enthalten können. Beim Test sollte man aber vorsichtig sein, falls z.B. in der Angabe die Teilwörter (GOTO, GO, TO), (FOR, OR), (TO, OR) oder ähnliches genannt werden (siehe Angabe und Lösung weiter unten von mnemetz).

$\left|ORxx\cap xxOR\right|=1$
$\left|ORxx\cap xxIF\right|=1$
$\left|IFxx\cap xxOR\right|=1$
$\left|IFxx\cap xxIF\right|=1$

Alle anderen Vereinigungen von zwei oder mehr Teilmengen sind leer.

Anmerkung mick:

Ist hier nicht geschnitten gemeint?

Anwenden des Inklusions-Exklusions-Prinzips

Einsetzen in die Formel des Inklusions-Exklusions-Prinzip bringt uns zu:

${\begin{aligned}\left|M\right|=&\left|E\right|\\&-\left|OR\right|-\left|IF\right|\\&-\left|ORx\right|-\left|xOR\right|-\left|IFx\right|-\left|xIF\right|-\left|AND\right|\\&-\left|ORxx\right|-\left|xORx\right|-\left|xxOR\right|\\&-\left|IFxx\right|-\left|xIFx\right|-\left|xxIF\right|\\&-\left|ANDx\right|-\left|xAND\right|\\&-\left|THEN\right|-\left|GOTO\right|\\&+\left|ORxx\cap xxOR\right|+\left|ORxx\cap xxIF\right|\\&+\left|IFxx\cap xxOR\right|+\left|IFxx\cap xxIF\right|\end{aligned}}$

Einsetzen der uns bereits bekannten Werte bringt uns zu:

${\begin{aligned}\left|M\right|=&26^{1}+26^{2}+26^{3}+26^{4}\\&-1-1\\&-26-26-26-26-1\\&-26^{2}-26^{2}-26^{2}\\&-26^{2}-26^{2}-26^{2}\\&-26-26\\&-1-1\\&+1+1\\&+1+1\end{aligned}}$

Zusammenfassen und ausrechnen ergibt:

${\begin{aligned}\left|M\right|&=26^{3}+26^{4}-5*26-5*26^{2}-1\\&=17576+456976-130-3380-1\\&=471041\end{aligned}}$

mfg, --W wallner

PS: Wolfgang, beim Zusammenfassen hast du 2*26 vergessen, habs schon ausgebessert :) --p.paulweber

Lösungsvorschlag von mnemetz (etwas komplexere u. andere Angabe!)

Wieviele verschiedene Variablennamen kann man in einer fiktiven Programmiersprache verwenden, wenn diese Namen aus mindestens einem, höchstens aber vier (nicht notwendig verschieden) Buchstaben {A,...,Z} bestehen müssen, und die Befehle AND, OR, OF, THEN, GO, TO und FOR nicht als Teilwörter enthalten sein dürfen.

Wie sehen, dass in allen Variablennamen, in denen FOR vorkommt, OR schon enthalten ist. Die Einschränkung, dass FOR nicht vorkommen darf, koennen wir uns also sparen!

Wir zählen:

Es gibt 26 Variablennamen der Form $x_{1}$ mit $x_{1}\in \bigtriangleup :=\{A,..,Z\}$.

Es gibt $26^{2}$ Namen der Form $X_{1}X_{2}$ mit $X_{1},X_{2}\in \bigtriangleup$. Von diesen ziehen wir 4 (nämlich OR, OF, GO und TO) wieder ab. Es gibt also $26^{2}-4$ Variablennamen der Länge 2.

Es gibt $26^{3}$ Namen der Form $X_{1}X_{2}X_{3}$ mit $X_{1},X_{2},X_{3}\in \bigtriangleup$. Davon ziehen wir $8*26+1$ wieder ab (nämlich alle der Form $X_{1}OR$, $X_{1}OF$, $X_{1}GO$, $X_{1}TO$, $ORX_{3}$, $OFX_{3}$, $GOX_{3}$, $TOX_{3}$ für $X_{1},X_{3}\in \bigtriangleup$, und natürlich AND). Weil das aber zu einfach wäre, müssen wir 4 wieder hinzuaddieren (nämlich GOR, GOF, TOR und TOF), die wir sonst doppelt subtrahiert hätten. Es gibt also $26^{3}-(8*26+1)+4$ Variablennamen der Länge 3.

Und jetzt wird es noch komplizierter ... :-/

Es gibt $26^{4}$ Namen der Form $X_{1}X_{2}X_{3}X_{4}$ mit $X_{1},X_{2},X_{3},X_{4}\in \bigtriangleup$ Von diesen ziehen wir $2*26+3*4*26^{2}+1$ wieder ab (nämlich alle der Form $X_{1}AND$, $ANDX_{4}$, $X_{1}X_{2}OR$, $X_{1}X_{2}OF$, $X_{1}X_{2}GO$, $X_{1}X_{2}TO$, $X_{1}ORX_{4}$, $X_{1}OFX_{4}$, $X_{1}GOX_{4}$, $X_{1}TOX_{4}$, $ORX_{3}X_{4}$, $OFX_{3}X_{4}$, $GOX_{3}X_{4}$, $TOX_{3}X_{4}$, und natürlich THEN).

Nun müssen wir wieder $2*4*26+4*4$ addieren, die wir sonst doppelt subtrahiert hätten (nämlich $X_{1}GOR$, $X_{1}TOR$, $X_{1}GOF$, $X_{1}TOF$, $GORX_{4}$, $TORX_{4}$, $GOFX_{4}$, $TOGX_{4}$, und OROR, OROF, ORGO, ORTO, OFOR, OFOF, OFGO, OFTO, GOOR, GOOF, GOGO, GOTO, TOOR, TOOF, TOGO, TOTO). Es gibt also $26^{4}-(2*26+3*4*26^{2}+1)+2*4*26+4*4$ Variablennamen der Länge 4.

Insgesamt haben wir nun: Es gibt $26+26^{2}-4+26^{3}-(8*26+1)+4+26^{4}-(2*26+3*4*26^{2}+1)+2*4*26+4*4$ Variablennamen der Länge höchstens 4. (Das sind: 467104)