Denkfehler - projecteuler 172
-
How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?
Ich habe mir das jetz so vorgestellt:
Jede Zahl darf maximal 3 mal vorkommen. Also nehme ich jede Zahl von 0-9
und lege sie 3 mal in einer Urne ab.Dort liegen jetzt 30 Zahlen. Wenn ich nun alle 18er-Variationen ohne Zurücklegen nehme
30!
---
18!sollte ich alle Möglichkeiten haben, die ich bilden kann.
Das Problem wäre nur dass manche mit 0 anfangen, was sie ja nicht dürften.Also müssten es ein paar weniger sein als 30!/18!.
Die Lösung ist aber etwa 5 mal so groß.
Was habe ich falsch gedacht?
-
Für 18 Zahlen aus 30 mit Berücksichtigung der Reihenfolge hast du 30! / (30 - 18)! = 30! / 12! Möglichkeiten.
-
Das macht das ganze auch nicht besser, jetzt liegt meine Anzahl Millionenfach über der Lösung.
Kann dieser erste Ansatz überhaupt zum Ziel führen?
( Ich hätte jetzt weitergemacht, dass bei einer Gleichverteilung der Zahlen 10%
mit einer führenden 0 beginnen und die schon mal abgezogen, bin aber immer noch meilenweit von der Lösung entfernt)
-
shisha schrieb:
Das macht das ganze auch nicht besser, jetzt liegt meine Anzahl Millionenfach über der Lösung.
Ist ja auch kein Wunder, denn du kannst je drei Kugeln der Urne nicht voneinander unterscheiden.
Kann dieser erste Ansatz überhaupt zum Ziel führen?
Mir fällt auf die Schnelle keine Lösung ohne Computer ein.
-
Ist ja auch kein Wunder, denn du kannst je drei Kugeln der Urne nicht voneinander unterscheiden.
Kannst du das etwas genauer ausführen? Ich weiß nicht wo daran das Problem ist.
Ich möchte ja zwischen 1 1 und 1 keine Unterscheidung treffen, weil zb
12 und 12 mit einer anderen 1 ja die selbe Zahl darstellen
-
Vielleicht könnte man erzeugende Funktionen benutzen.
-
shisha schrieb:
Ist ja auch kein Wunder, denn du kannst je drei Kugeln der Urne nicht voneinander unterscheiden.
Kannst du das etwas genauer ausführen? Ich weiß nicht wo daran das Problem ist.
Ich möchte ja zwischen 1 1 und 1 keine Unterscheidung treffen, weil zb
12 und 12 mit einer anderen 1 ja die selbe Zahl darstellenGenau ist ja das Problem. Du zählst im Moment neunmal die Zahl 12 (wenn du zweistellige Zahlen erzeugen willst): Für jede Kombination aus den drei Einsen und den drei Zweien einmal.