Wie viele solche Zahlen gibt es?

Question

Aufgabe

(f) Wir betrachten siebenstellige Zahlen, bei welchen keine Ziffer grösser als irgend eine vorangehende Ziffer sein darf. Wie viele solche Zahlen gibt es?
Lösung:
Die Anzahl solcher Zahlen ist gleich der Anzahl positiver ganzzahligen Lösungen der Gleichung
\( x_{0}+x_{1}+\ldots+x_{9}=7 \)
minus 1. (Warum?)
Man kann sich die Gleichung als Menge von 7 Einsen vorstellen, welche wir in 10 Abschnitte unterteilen wollen, wobei jeder Abschnitt zu einem \( x_{i} \) korrespondiert.
Wir wollen also die Anzahl an Möglichkeiten bestimmen, 10-1=9 Teilende "Balken" auf die Menge der Einsen zu verteilen. Wir haben 10+7-1 Positionen, auf welche wir 9 Balken verteilen wollen, also
\( \left(\begin{array}{c} 16 \\ 9 \end{array}\right)=\frac{16 !}{9 ! \cdot 7 !}=11.440 \)

Möglichkeiten.
Die gesuchte Anzahl Zahlen ist 11.439.

Text erkannt:

(f) Wir betrachten siebenstellige Zahlen, bei welchen keine Ziffer grösser als irgend eine vorangehende Ziffer sein darf. Wie viele solche Zahlen gibt es?
Lösung:
Die Anzahl solcher Zahlen ist gleich der Anzahl positiver ganzzahligen Lösungen der Gleichung
\( x_{0}+x_{1}+\ldots+x_{9}=7 \)
minus 1. (Warum?)
Man kann sich die Gleichung als Menge von 7 Einsen vorstellen, welche wir in 10 Abschnitte unterteilen wollen, wobei jeder Abschnitt zu einem \( x_{i} \) korrespondiert.
Wir wollen also die Anzahl an Möglichkeiten bestimmen, 10-1=9 Teilende "Balken" auf die Menge der Einsen zu verteilen. Wir haben 10+7-1 Positionen, auf welche wir 9 Balken verteilen wollen, also
\( \left(\begin{array}{c} 16 \\ 9 \end{array}\right)=\frac{16 !}{9 ! \cdot 7 !}=11.440 \)

Möglichkeiten.
Die gesuchte Anzahl Zahlen ist 11.439.

Problem/Ansatz:

Kann mir jemand die Lösung etwas genauer erklären? Ich verstehe nicht warum man sieben Einsen nimmt und warum man dann 16 Positionen hat und nicht 7. Ausserdem ist mir unklar weshalb ich am ende noch minus 1 rechnen muss.

Comments

Ich wäre auch schon froh wenn ihr mir nur ein Teil der Aufgabe erklären könntet.

Answer 1

warum man sieben Einsen nimmt

Es ist

        \(1+1+1+1+1+1+1 = 7\).

Jede positive ganzzahlige Lösung der Gleichung

        \(x_0+x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8+x_9 = 7\)

kann mittels Assoziativgesetz und Einfügen von Nullen aus der Summe der sieben Einsen gewonnen werden. Die Lösung

        \(x_2=2, x_5=4, x_7=1, x_0=x_1=x_3=x_4=x_6=x_8=x_9=0\)

ergibt sich zum Beispiel aus

        \(0+0+(1+1)+0+0+(1+1+1+1)+0+1+0+0=7\).

Auf die Tatsache, dass der Autor der Lösung die \(0\) anscheinend als positive Zahl ansieht, möchte ich hier nicht näher eingehen.

und warum man dann 16 Positionen hat

Trennt man in obiger Gleichung die Summenden durch \(\vert\) und verwendet man \(\star\) anstatt \(1\) (der Übersichtlichkeit halber), dann sähe obige Lösung so aus:

        \(\vert\vert\vert\star\star\vert\vert\vert\star\star\star\star\vert\vert\star\vert\vert\vert\)

Steht zwischen zwei \(\vert\) kein \(\star\), so ist das der Summand \(0\), ansonsten ist das der Sumand entsprechend der Anzahl der \(\star\).

Bei dieser Kodierung steht am Anfang und am Ende immer ein \(\vert\). Diese können weggelassen werden und man bekommt

        \(\vert\vert\star\star\vert\vert\vert\star\star\star\star\vert\vert\star\vert\vert\).

Diese Kodierung besteht aus \(16\) Zeichen. Die Anzahl der Möglichkeiten bekommt man deshalb, indem man in den \(16\) verfügbaren Positionen an \(9\) Positionen ein \(\vert\) schreibt und an den restlichen \(7\) Positionen einen \(\star\).