\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}
