Erzeugende Funktionen 2 - Kakuro

04/07/2008 - 14:08 von Jutta Gut | Report spam
Hallo!

Angenommen, ich will wissen, auf wie viele Arten man 25 als Summe von Zahlen
aus {1, 2, 3, ... 9} darstellen kann. Dabei darf jede Zahl höchstens einmal
auftreten (wie bei den Kakuro-Ràtseln). Da ist der Koeffizient von x^25 im
Polynom (1 + x)*(1 + x^2)*(1 + x^3)* ... *(1 + x^9).

Wie kann ich aber herausfinden, wie viele Möglichkeiten mit (z.B.) 4
Summanden es gibt?

Grüße
Jutta
 

Lesen sie die antworten

#1 Chris VoIk
04/07/2008 - 16:42 | Warnen spam
Jutta Gut wrote:
Hallo!

Angenommen, ich will wissen, auf wie viele Arten man 25 als Summe von
Zahlen aus {1, 2, 3, ... 9} darstellen kann. Dabei darf jede Zahl
höchstens einmal auftreten (wie bei den Kakuro-Ràtseln). Da ist der
Koeffizient von x^25 im Polynom (1 + x)*(1 + x^2)*(1 + x^3)* ... *(1
+ x^9).
Wie kann ich aber herausfinden, wie viele Möglichkeiten mit (z.B.) 4
Summanden es gibt?



Den Summanden x^3 statt des Summanden 1 zu wàhlen,
heißt ja, dass die Zahl 3 vorkommt. Den Summanden 1 zu wàhlen
heißt, dass die Zahl 3 nicht vorkommt (alle anderen Zahlen
aber vorkommen dürfen).

Wenn du jetzt das Polynom (y+x)*(y+x^2)*(y+x^3)*..*(y+x^9)
im Ring Z[X,Y] betrachtest, ist der Koeffizient von y^k*x^m
die Anzahl der Möglichkeiten, die Zahl "m" als Summe zu erhalten,
wobei k Zahlen nicht vorkommen, d.h. 9-k Zahlen vorkommen.

Du suchst also im Beispiel den Koeffizienten von y^(9-4)*x^25.

Viele Grüße!

Chr1stian

Ähnliche fragen