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 △:=\{A,\mathrm{..},Z\}$.

Es gibt $26^2$ Namen der Form $X_1{X}_2$ mit $X_1,X_2\in △$. 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 △$. Davon ziehen wir $8\ast 26+1$ wieder ab (nämlich alle der Form $X_{1}OR$, $X_{1}OF$, $X_{1}GO$, $X_{1}TO$, $OR{X}_3$, $OF{X}_3$, $GO{X}_3$, $TO{X}_3$ für $X_1,X_3\in △$, 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 △$ Von diesen ziehen wir $2\ast 26+3\ast 4\ast 26^2+1$ wieder ab (nämlich alle der Form $X_{1}AND$, $AND{X}_4$, $X_1{X}_{2}OR$, $X_1{X}_{2}OF$, $X_1{X}_{2}GO$, $X_1{X}_{2}TO$, $X_{1}OR{X}_4$, $X_{1}OF{X}_4$, $X_{1}GO{X}_4$, $X_{1}TO{X}_4$, $OR{X}_3{X}_4$, $OF{X}_3{X}_4$, $GO{X}_3{X}_4$, $TO{X}_3{X}_4$, und natürlich THEN).

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

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