Wieviele Möglichkeiten gibt es, einen 100-Euro-Schein zu wechseln?

Es sind etwa 7 Billiarden (genau 7089628318292844) Möglichkeiten. Um ohne allzu viel Schreibarbeit zu erklären, wie man das ausrechnet, möchte ich es zunächst am Beispiel von 10 Cent vorrechnen:

Man betrachte zunächst das Polynom
(x⁰ + x + x² + x³ + ... + x⁹ + x¹⁰) (x⁰ + x²+ x⁴ + x⁶ + x⁸ + x¹⁰) (x⁰ + x⁵ + x¹⁰)

Dabei steht der erste Faktor für null bis zehn 1-Cent-Stücke, der zweite für null bis fünf 2-Cent-Stücke und der dritte Faktor für null bis zwei 5-Cent-Stücke.

Multipliziert man das aus, kommt in der Summe jede Kombination aus max. zehn 1-Cent-Stücken, max. fünf 2-Cent-Stücken und max. zwei 5-Cent-Stücken genau einmal vor. Darüber hinaus ist jeder Summand genau eine Potenz xⁿ, wobei n gerade den dargestellten Geldbetrag angibt. Ordnet man die Summe nach Potenzen von x, kann man jetzt am Koeffizient von x¹⁰ ablesen, wieviele Möglichkeiten es gibt, 10 Cent mit 1, 2 und 5-Cent-Münzen auszubezahlen. In unserem Beispiel ergibt Ausmultiplizieren:

1 + x + 2x² + 2x³ + 3x⁴ + 4x⁵ + 5x⁶ + 6x⁷ + 7x⁸ + 8x⁹ + 10x¹⁰ + 10x¹¹ + 11x¹² + 11x¹³ + ... + 2x²⁸ + x²⁹ + x³⁰

Der Koeffizient von x¹⁰ ist 10. Also gibt es 10 Möglichkeiten.

Die Frage ist jetzt natürlich, wie man sowas mit vernünftigem Aufwand bis 10000 Cent = 100 Euro macht.
Nun, dazu benutzt man ein Computeralgebrasystem. Ich bevorzuge Mathematica. Der entsprechende Befehl für 1 Euro lautet:

Expand [Sum[x^n, {n, 0, 100}]*Sum[x^(2*n), {n, 0, 50}]*Sum[x^(5*n), {n, 0, 20}]*Sum[x^(10*n), {n, 0, 10}]*Sum[x^(20*n), {n, 0, 5}]*Sum[x^(50*n), {n, 0, 2}]]

Man erhält augenblicklich ein Polynom der Ordnung 600. Der Koeffizient von x¹⁰⁰ ist 4562. Es gibt also 4562 Möglichkeiten, eine Euro-Münze klein zu machen. Dabei ist der einfache Tausch Euro-Münze gegen Euro-Münze nicht mitgerechnet.
Erweitert man das Ganze auf 100 Euro, braucht allerdings auch Mathematica sehr lange, um das entstehende Polynom auszumultiplizieren. Hier bedient man sich eines genialen Tricks:
Man benutzt die Tatsache, dass 1+p+p²+p³+p⁴+... für Betrag p kleiner 1 gegen 1/(1-p) konvergiert (geometrische Reihe) und multipliziert nun einfach die entsprechenden Grenzwerte miteinander. Man erhält die sog. Erzeugende Funktion:

1/(1-x) * 1/(1-x²) * 1/(1-x⁵) * 1/(1-x¹⁰) * 1/(1-x²⁰) * 1/(1-x⁵⁰) * 1/(1-x¹⁰⁰) * 1/(1-x²⁰⁰) * 1/(1-x⁵⁰⁰) * 1/(1-x¹⁰⁰⁰) * 1/(1-x²⁰⁰⁰) * 1/(1-x⁵⁰⁰⁰)

Von dieser ganzrationalen Funktion ist nun eine Taylorreihenentwicklung in 10000. Ordnung durchzuführen. Dabei ist eine letzte Hürde zu nehmen. Die Berechnung nach der üblichen McLaurin-Formel

f(x) = f(0) + x* f '(0) + x²/2! f ''(0) + x³/3! f'''(0) + ...

ist kaum durchführbar, da in 10000. Ordnung Fakultäten großer Zahlen zu berechnen wären. (10000! ist eine 35660-stellige Zahl.) Das ist aber auch gar nicht notwendig. Schließlich ist unsere Erzeugende Funktion nur der Kehrwert 1/P(x) eines Polynoms. Wir haben also:

P(x) T(x) = 1

wobei T(x) das zu bestimmende Taylorpolynom ist. Schreiben wir das etwas aus:

 (p₀ + p₁x + p₂x² + p₃x³ + ... ) ( t₀ + t₁x + t₂x² + t₃x³ + ... ) = 1

Die noch unbekannten Koeffizienten t_i erhält man nun nach Ausmultiplizieren und Zusammenfassen gleicher Potenzen von x sukzessive durch Koeffizientenvergleich:

x⁰ : p₀t₀ = 1     =>      t₀ = 1/p₀
x¹ : p₁t₀ + t₁p₀ = 0    

...

Und so erhält man nach Eingabe von:

Series [1/(1 - x)*1/(1 - x^2)*1/(1 - x^5)*1/(1 - x^10)*1/(1 - x^20)*1/(1 - x^50)*1/(1 - x^100)*1/(1 - x^200)*1/(1 - x^500)*1/(1 - x^1000)*1/(1 - x^2000)*1/(1 - x^5000),{x, 0, 10000}]

nach etwa zwei Minuten die Reihenentwicklung:

1 + x + 2x² + 2x³ + ... + 7089628318292844x¹⁰⁰⁰⁰ + O[x]¹⁰⁰⁰¹

Der Koeffizient vor x¹⁰⁰⁰⁰ ist die gesuchte Lösung.

Zurück zu gewetz' Homepage