\documentclass{uebungsblatt} \author{Marek Kubica, kubica@in.tum.de} \fach{Diskrete Strukturen} \blatt{10} \gruppe{11} \begin{document} \aufgabe \teilaufgabe Zwischen 999.999 und 1.000.010 gibt es keine Zahlen, deren Quersumme 16 beträgt, somit muss nur der bereich von 1 bis 999.999 betrachtet werden. Um die Anzahl der Quersummen zu bestimmen, kann man die Zahlpartition der Zahl 16 bilden. Da aber die zu untersuchenden Zahlen auch Nullen enthalten, muss man eine Kodierung hernehmen bei der die Zahlen von 0 $\cdots$ 9 auf die Zahlen 1 $\cdots$ 10 abgebildet werden. Somit muss 6 auf die Zahl deren Zahlpartition gebildet wird aufaddiert werden; es werden also die Zahlpartitionen von 22 gesucht. Die geordneten 6-Zahlpartitionen der Zahl 22 sind ${22 - 1 \choose 6 - 1} = 20349$. Dabei kommen dort noch die Zahlen 11 $\cdots$ 17 vor (17 ist die höchste Zahl, da $1+1+1+1+1+17=22$), diese müssen abgezogen werden: \begin{itemize} \item Partitionen die 11 enthalten: $6 \cdot {22 - 11 - 1 \choose 5 - 1} = 6 \cdot 210$ \item Partitionen die 12 enthalten: $6 \cdot {22 - 12 - 1 \choose 5 - 1} = 6 \cdot 126$ \item Partitionen die 13 enthalten: $6 \cdot {22 - 13 - 1 \choose 5 - 1} = 6 \cdot 70$ \item Partitionen die 14 enthalten: $6 \cdot {22 - 14 - 1 \choose 5 - 1} = 6 \cdot 35$ \item Partitionen die 15 enthalten: $6 \cdot {22 - 15 - 1 \choose 5 - 1} = 6 \cdot 15$ \item Partitionen die 16 enthalten: $6 \cdot {22 - 16 - 1 \choose 5 - 1} = 6 \cdot 5$ \item Partitionen die 17 enthalten: $6 \cdot {22 - 17 - 1 \choose 5 - 1} = 6 \cdot 1$ \end{itemize} Das Ergebnis ist also $20349 - 6(210+126+70+35+15+5+1) = 17577$. \teilaufgabe Für $n < 6$ ist die Anzahl der passenden Binärwörter immer 0, da dreimal 01 mindestens $n = 6$ benötigt. Für $n = 6$ ist die Anzahl 1, da das einzige passende Binärwort 010101 ist. Wenn man jetzt ein $n > 6$ betrachtet, ist die Anzahl der freien Stellen $n - 6$. In diese freien Stellen kann man nun keine, eine oder mehrere 0 oder 1 reinschreiben. Dabei hat das Binärwort die Form $x01x01x01x$, wobei $x$ die freie Stelle darstellt. Jedoch ist nicht jede Möglichkeit 0 und 1 in x einzusetzen gültig, es muss sichergestellt werden, dass die Sequenz $01$ nicht vorkommen darf. Dazu gibt es folgende Beobachtung dass wenn in ein x eine Zahl eingesetzt werden kann es zwei Möglichkeiten dafür gibt: $0$ und $1$. Wenn aber zwei Zahlen eingesetzt hat man drei Möglichkeiten: $11$, $10$, $11$. Die Möglichkeit $01$ fällt weg. Bei höheren Zahlen geht der Trend weiter: k Plätze, k+1 Möglichkeiten. Eine weitere Beobachtung ist wie man die freien Stellen im Binärwort verteilt. Wenn man annimmt, dass ``|'' eine freie Stelle repräsentiert, kann man etwa bei $n = 8$, also mit $8 - 6 = 2$ freien Stellen folgende Verteilung auf die vier $x$ herstellen: \begin{tabular}{ccccccc|c|c} $x$ & 01 & $x$ & 01 & $x$ & 01 & $x$ & Möglichkeiten & Darstellung\\ \hline & & & & & & || & 3 & (0, 0, 0, 2)\\ & & & & | & & | & 4 & (0, 0, 1, 1)\\ & & | & & & & | & 4 & (0, 1, 0, 1)\\ | & & & & & & | & 4 & (1, 0, 0, 1)\\ & & & & ||& & & 3 & (0, 0, 2, 0)\\ & & | & & | & & & 4 & (0, 1, 1, 0)\\ | & & & & | & & & 4 & (1, 0, 1, 0)\\ & & ||& & & & & 3 & (0, 2, 0, 0)\\ | & & | & & & & & 4 & (1, 1, 0, 0)\\ ||& & & & & & & 3 & (2, 0, 0, 0)\\ \hline \end{tabular} Dies ähnelt den Zahlpartitionen, jedoch muss man auch hier wieder zum Trick greifen und die Zahlpartitionen nicht von $n - 6$ bilden, sondern 4 aufaddieren also von $n - 6 + 4 = n - 2$ bilden, im Beispiel entspricht das den Zahlpartitionen von $2 + 4 = 6$: \begin{tabular}{|ccc|} \hline (0, 0, 0, 2) & $\equiv$ & (1, 1, 1, 3)\\ (0, 0, 1, 1) & $\equiv$ & (1, 1, 2, 2)\\ (0, 1, 0, 1) & $\equiv$ & (1, 2, 1, 2)\\ (1, 0, 0, 1) & $\equiv$ & (2, 1, 1, 2)\\ (0, 0, 2, 0) & $\equiv$ & (1, 1, 3, 1)\\ (0, 1, 1, 0) & $\equiv$ & (1, 2, 2, 1)\\ (1, 0, 1, 0) & $\equiv$ & (2, 1, 2, 1)\\ (0, 2, 0, 0) & $\equiv$ & (1, 3, 1, 1)\\ (1, 1, 0, 0) & $\equiv$ & (2, 2, 1, 1)\\ (2, 0, 0, 0) & $\equiv$ & (3, 1, 1, 1)\\ \hline \end{tabular} Somit stellt jedes Element der Tupel die Anzahl der Möglichkeiten für die eine Bestimmte Stelle dar. Wenn man nun die Elemente der Tupel jeweils zusammenmultipliziert, bekommt man die Anzahl der Möglichkeiten für eine bestimmte Verteilung der ``|'' auf die freien Stellen $x$. Also multipliziert man alle Elemente der Tupel und addiert dann alle Ergebnise und bekommt dann die Antwort (in diesem Fall für $n = 8$, bei den Zahlpartitionen von 8, aber selbiges Verfahren gilt auch algemein für $n$ mit den Zahlpartitionen von $n - 2$: $4 \cdot 3 + 6 \cdot 4 = 36$ \aufgabe \teilaufgabe $ { 4 + 9 - 1 \choose 9 - 1 } = 495 $ \teilaufgabe $ \sum^3_{k=1} P_{5,k} = P_{5,1} = P_{5,2} + P_{5,3} = 1 + 2 + 2 = 5 $ \teilaufgabe $ \frac{{12 \choose 2}{10 \choose 2}{8 \choose 2}{6 \choose 2}{4 \choose 2}{2 \choose 2}}{6!} = \frac{66 \cdot 45 \cdot 28 \cdot 15 \cdot 6 \cdot 1}{720} = \frac{7484400}{720} = 10395 $ \aufgabe \teilaufgabe Es existieren 11 verschiedene Spielsteine: RRR, GGG, BBB, BRR, GRR, GBB, RBB, BGG, RGG, RGB, RBG. \teilaufgabe Es existieren 10 verschiedene Spielsteine, weil in diesem Fall RGB $\equiv$ RBG ist und somit eine Möglichkeit wegfällt. Die allgemeine Form ist ${3 + n - 1 \choose 3}$. \aufgabe Die Reihenfolge der von den Stapeln gekauft wird ist wichtig, sowohl die $m$ möglichen Stapel als auch die $k$ Stapel von denen gekauft wurde sind unterscheidbar, somit ist die Anzahl der Möglichkeiten $m^{\underline{k}}$. $n$ unterscheidbare Kunden kaufen von $k$ in diesem Kontext nicht unterscheidbaren Stapeln: $S_{n,k}$. Somit ist die Anzahl der Möglichkeiten zusammen $m^{\underline{k}} \cdot S_{n,k}$. \end{document}