kombinatorisches Zählen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Betrachtet strikt positive natürliche Zahlen mit streng monoton aufsteigender Folge von positiven Dezimalziffern, z.B. 235789. Führende Nullen sind nicht erlaubt. Wieviele solcher Zahlen gibt es? |
Ich habe diese Frage in keinem anderen Forum gestellt.
Hallo ,
leider habe ich noch absolut keine Idee, wie man das machen kann, außer natürliche alle Möglichkeiten aufzuschreiben, was hier aber wohl weder Sinn noch Zweck der Sache ist.
Also A:= [mm] \{ 1; 2; 3; 4; 5; 6; 7; 8; 9 \}.
[/mm]
P(A) = [mm] 2^{9} [/mm] = 512. Nun ich kann wohl kaum alle 512, bzw. 511, weil die leere Menge ja wegfällt, Möglichkeiten aufschreiben.
Ich bitte um Hilfe !!!
Danke schon mal im Voraus =)
Milchschelle
|
|
| |
|
Es ist eine streng monoton aufsteigende Folge von Dezimalziffern ohne führende Nullen gesucht. Das bedeutet, die längste mögliche Folge ist
123456789
hat also 9 Stellen. Dafür gibt es aber nur eine Möglichkeit, denn sobald man versucht Ziffern zu vertauschen, ist die Monotonie verletzt.
Die nächstlängste Folge hat 8 Stellen, zB
12346789, hier habe ich einfach eine Ziffer der 9 stelligen Folge weggelassen, nämlich die 5. Insgesamt kann ich mir von den 9 Ziffern der 9 stellige Folge eine beliebige Ziffer aussuchen und die weglassen, so erhalte ich jede mögliche 8 stellige Folge. Es gibt also für die 8 stellige Folge [mm] \binom{9}{1} [/mm] Möglichkeiten.
Bei der 7 stelligen Folge kann ich dann 2 beliebige Ziffern der 9 stelligen Folge auslassen usw, bis ich bei der 1 stelligen Folge 8 Ziffern weglassen muss.
|
|
|
| |
|
also muss ich ja bloß Folgendes berechnen:
[mm] \vektor{9 \\ 1} [/mm] = 9
[mm] \vektor{9 \\ 2} [/mm] = 36
[mm] \vektor{9 \\ 3} [/mm] = 84
[mm] \vektor{9 \\ 4} [/mm] = 126
[mm] \vektor{9 \\ 5} [/mm] = 126
[mm] \vektor{9 \\ 6} [/mm] = 84
[mm] \vektor{9 \\ 7} [/mm] = 36
[mm] \vektor{9 \\ 8} [/mm] = 9
[mm] \vektor{9 \\ 9} [/mm] = 1
Dann summiere ich diese alle: 9+36+84+126+126+84+36+9+1= 511. Also gibt es 511 Möglichkeiten, stimmt das?
|
|
|
| |
|
Hallo Milchschelle,
das ist korrekt, aber zu aufwändig.
> also muss ich ja bloß Folgendes berechnen:
>
> [mm]\vektor{9 \\
1}[/mm] = 9
> [mm]\vektor{9 \\
2}[/mm] = 36
> [mm]\vektor{9 \\
3}[/mm] = 84
> [mm]\vektor{9 \\
4}[/mm] = 126
> [mm]\vektor{9 \\
5}[/mm] = 126
> [mm]\vektor{9 \\
6}[/mm] = 84
> [mm]\vektor{9 \\
7}[/mm] = 36
> [mm]\vektor{9 \\
8}[/mm] = 9
> [mm]\vektor{9 \\
9}[/mm] = 1
>
> Dann summiere ich diese alle: 9+36+84+126+126+84+36+9+1=
> 511. Also gibt es 511 Möglichkeiten, stimmt das?
Ja, das stimmt so.
Es ist aber generell [mm] \summe_{k=0}^{n}\vektor{n\\k}=2^n
[/mm]
Da hier keine Zahl mit 0 Ziffern erlaubt ist, fällt [mm] \vektor{9\\0}=1 [/mm] heraus, es bleiben also [mm] 2^9-1=511 [/mm] Möglichkeiten.
Das kann man sich auch noch leichter und ohne Binomialkoeffizienten überlegen:
Stell Dir ein Scrabble-"Bänkchen" vor, auf dem die Plättchen 1 bis 9 in aufsteigender Reihenfolge auf festen Plätzen liegen. Für jedes Plättchen gibt es nun nur die beiden Möglichkeiten: 0) es wird nicht verwendet, oder 1) es wird verwendet.
Also insgesamt [mm] 2^9 [/mm] Möglichkeiten, wieder abzüglich der Zahl ohne Ziffern, also [mm] 2^9-1 [/mm] Möglichkeiten.
Grüße
reverend
|
|
|
|
