TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 147

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, IF, THEN und GOTO nicht als Teilwörter enthalten sein dürfen.

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 denn 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^{2}$ 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\cdot 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}TOG$, $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)