Suma elementów zbioru

[MrOmega]

Na ile różnych sposobów mogę zsumować elementy zbioru \(\displaystyle{ \left\{ 1,3,4\right\}}\) (nie musza być wszystkie; mogą się powtarzać), aby otrzymać w sumie \(\displaystyle{ 15}\)?

Przykład rozwiązań:
\(\displaystyle{ 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1}\),
\(\displaystyle{ 3+4+4+4}\),
\(\displaystyle{ 1+3+3+4+4}\).

Chodzi o znalezienie najszybszej metody liczenia tego typu zadań.

[nowheredense_man]

innymi słowy pytasz o to ile jest takich \(\displaystyle{ k,l,m}\) naturalnych, dla których zachodzi:
\(\displaystyle{ k+3l+4m=15}\), ta liczba jest współczynnikiem wielomianu:
\(\displaystyle{ (1+x+\ldots+x^{15})(1+x^3+x^6+\ldots+x^{15})(1+x^4+\ldots+x^{16})}\)
stojącym przy \(\displaystyle{ x^{15}}\)

[MrOmega]

Ojej, to strasznie dużo liczenia będzie... W szczególności, że ta suma może być liczbą nawet \(\displaystyle{ 10^{1000}}\)...

Dałoby się tutaj może zastosować jakiś rekurencyjny wzór?

[vpprof]

Poczytaj o funkcjach tworzących, tu jest dokładnie ten sam problem:

[MrOmega]

Chyba jednak za bardzo pospieszyłem się z odpowiedzią. Moglibyście mi pokazać jak dojść do rozwiązania dla trzech liczb z przykładu z mojego pierwszego posta? Byłbym bardzo wdzięczny, chciałbym to zrozumieć, potrzebuję napisać program, ale nie obejdzie się bez zrozumienia problemu matematycznego.

-- 9 lis 2012, o 22:17 --

OK, już rozumiem Dziękuję wszystkim za pomoc.

[nowheredense_man]

Ojej, to strasznie dużo liczenia będzie... W szczególności, że ta suma może być liczbą nawet \(\displaystyle{ 10^{1000}}\)...

Dałoby się tutaj może zastosować jakiś rekurencyjny wzór?

są darmowe programy do wyliczeń symbolicznych, które te obliczenia mogą zrobić za Ciebie... np. Maxima.