Współczynnik w wielomianie

[patryk007]

Na ile sposobów można kupić 50 litrów soku, jeśli dostępnych jest 33 butelek 1 litrowych, 25 butelek 2 litrowych i 12 butelek 4 litrowych?

Wiem, że trzeba teraz znaleźć współczynnik przy \(\displaystyle{ x^{50}}\) (nie do końca wiem dlaczego ale to inna kwestia).
\(\displaystyle{ (1+x+x^2+...+x^{33})\cdot (1+x^2+...+x^{48}+x^{50})\cdot (1+x^4+...+x^{48})}\)
Znaleźć współczynnik przy \(\displaystyle{ x^{50}}\).

Próbowałem to zliczać ręcznie po zastosowaniu wzorów i wyszło mi 227.
Sprawdzałem w programach, z których nie do końca umiem korzystać i mi wyszło 157, 224, 149.

Nie wiem, który jest dobry. ;P
Niech no ktoś sprawdzi.
TIA

[abc666]

patryk007, to jest metoda funkcji tworzących. Powiedzmy, że masz do dyspozycji monety jedno-, dwu- i pięciozłotowe i chcesz wiedzieć na ile sposobów możesz rozmienić np. 10zł przy ich użyciu. Mamy powiedzmy 2 pięciozłotówki, 5 dwuzłotówek i 10 złotówek. Możesz np. rozmienić tak
\(\displaystyle{ 5+5=2\cdot 5}\)
tzn. wziąłeś 0 monet jedno- i dwuzłotowych i 2 pięciozłotowe.
Możesz też np. tak
\(\displaystyle{ 1+1+1+2+5=3\cdot 1+1\cdot 2+1\cdot 5}\)
Tzn. że za każdym razem wybieramy ileś monet każdego rodzaju i w sumie dają one 10. No to teraz zapiszmy sobie szereg taki
\(\displaystyle{ x^0+x^1+x^2+...+x^{10}}\)
potęga przy \(\displaystyle{ x}\) oznacza ile monet jednozłotowych wybieramy. Zapiszmy sobie jeszcze teraz
\(\displaystyle{ x^0+x^2+x^4+x^6+x^8+x^{10}}\)
Teraz gdy je wymnożymy zliczymy wszystkie możliwe wybory dla każdej możliwej sumy. Dlaczego? Ponieważ mnożymy każdy wyraz z pierwszego nawiasu z każdym z drugiego. Np. kiedy wymnożymy
\(\displaystyle{ x^1}\) z pierwszego z \(\displaystyle{ x^4}\) z drugiego otrzymamy \(\displaystyle{ x^5}\) co przedstawia nam jedną z możliwości otrzymania 5 zł przy pomocy jednej złotówki i 2 dwuzłotówek \(\displaystyle{ (2\cdot 2=4)}\). Ale to tylko jedna z możliwości, kiedy wymnożymy wszystkie wyrazy i je uporządkujemy dostaniemy liczbę sposobów na jakie możemy rozmienić daną kwotę. Kwota ta to potęga iksa.

Wracając do przykładowego zadanka jeśli wymnożymy
\(\displaystyle{ (x^0+x^1+x^2+...+x^{10})\cdot ( x^0+x^2+x^4+x^6+x^8+x^{10})\cdot (x^0+x^5+x^{10})}\)
i odczytamy wsp. przy \(\displaystyle{ x^{10}}\) dostaniemy liczbę możliwych sposobów na jakie możemy rozmienić 10 zł przy pomocy w/w nominałów.

[patryk007]

No OK. Dzięki.
A jak jeszcze ten współczynnik liczyć, bo mi wyszło tyle ile napisałem i się chce upewnić ile powinno być.

[Xitami]

\(\displaystyle{ \sum_{i=0}^{33}x^i\sum_{i=0}^{25}x^{2i}\sum_{i=0}^{12}x^{4i}=
\\\\x^{131}
+ x^{130}
+ 2 x^{129}
+ 2 x^{128}
+ 4 x^{127}
+ 4 x^{126}
+ 6 x^{125}
+ 6 x^{124}
+ 9 x^{123}
+ 9 x^{122}
+ 12 x^{121}
+ 12 x^{120}
+ 16 x^{119}
+ 16 x^{118}
+ 20 x^{117}
+ 20 x^{116}
+ 25 x^{115}
+ 25 x^{114}
+ 30 x^{113}
+ 30 x^{112}
+ 36 x^{111}
+ 36 x^{110}
+ 42 x^{109}
+ 42 x^{108}
+ 49 x^{107}
+ 49 x^{106}
+ 56 x^{105}
+ 56 x^{104}
+ 64 x^{103}
+ 64 x^{102}
+ 72 x^{101}
+ 72 x^{100}
+ 81 x^{99}
+ 81 x^{98}
+ 89 x^{97}
+ 89 x^{96}
+ 98 x^{95}
+ 98 x^{94}
+ 106 x^{93}
+ 106 x^{92}
+ 115 x^{91}
+ 115 x^{90}
+ 123 x^{89}
+ 123 x^{88}
+ 132 x^{87}
+ 132 x^{86}
+ 140 x^{85}
+ 140 x^{84}
+ 149 x^{83}
+ 149 x^{82}
+ 157 x^{81}
+ 157 x^{80}
+ 164 x^{79}
+ 164 x^{78}
+ 170 x^{77}
+ 170 x^{76}
+ 175 x^{75}
+ 175 x^{74}
+ 179 x^{73}
+ 179 x^{72}
+ 182 x^{71}
+ 182 x^{70}
+ 184 x^{69}
+ 184 x^{68}
+ 185 x^{67}
+ 185 x^{66}
+ 185 x^{65}
+ 185 x^{64}
+ 184 x^{63}
+ 184 x^{62}
+ 182 x^{61}
+ 182 x^{60}
+ 179 x^{59}
+ 179 x^{58}
+ 175 x^{57}
+ 175 x^{56}
+ 170 x^{55}
+ 170 x^{54}
+ 164 x^{53}
+ 164 x^{52}
+ 157 x^{51}
+ 157 x^{50}
+ 149 x^{49}
+ 149 x^{48}
+ 140 x^{47}
+ 140 x^{46}
+ 132 x^{45}
+ 132 x^{44}
+ 123 x^{43}
+ 123 x^{42}
+ 115 x^{41}
+ 115 x^{40}
+ 106 x^{39}
+ 106 x^{38}
+ 98 x^{37}
+ 98 x^{36}
+ 89 x^{35}
+ 89 x^{34}
+ 81 x^{33}
+ 81 x^{32}
+ 72 x^{31}
+ 72 x^{30}
+ 64 x^{29}
+ 64 x^{28}
+ 56 x^{27}
+ 56 x^{26}
+ 49 x^{25}
+ 49 x^{24}
+ 42 x^{23}
+ 42 x^{22}
+ 36 x^{21}
+ 36 x^{20}
+ 30 x^{19}
+ 30 x^{18}
+ 25 x^{17}
+ 25 x^{16}
+ 20 x^{15}
+ 20 x^{14}
+ 16 x^{13}
+ 16 x^{12}
+ 12 x^{11}
+ 12 x^{10}
+ 9 x^9
+ 9 x^8
+ 6 x^7
+ 6 x^6
+ 4 x^5
+ 4 x^4
+ 2 x^3
+ 2 x^2
+ x
+ 1}\)

[pyzol]

Matlab:

Kod: Zaznacz cały

clear all
a(1:34)=1; % wartość ai=1 dla i=1,2,3 resztę uzupełnia zerami, średnik nie wyświetla wyniku,
b(1:2:51)=1; % wartość bi=1 dla i=1,3,5,...,51 , 
c(1:4:49)=1; 
d=conv(a,b); %współczynniki iloczynu wielomianów
e=conv(d,c); %kolejny iloczyn, kolejne współczynniki
e(51)

Xitami, (tak z ciekawości) pisałeś to ręcznie?

[Xitami]

Pewnie, że tak
ręcznie napisałem:
printtex(sum(i=0,33,x^i)*sum(i=0,25,x^(2*i))*sum(i=0,12,x^(4*i)))

mnożenie załatwia się splotem, a splot liczy się mnożąc
ale tu nie potrzeba mnożyć, szybciej jest dodawać

Kod: Zaznacz cały

#include <stdio.h>

#define N 50
 
void zero(int * w){int i;  for(i=0;i<=N;i++) w[i]=0;}
   
void conv(int * w, int * a, int s, int e, int h){
   int i,j,jj;
   zero(w); if(e>N/h) e=N/h;
   for(j=s*h,jj=s; jj++<=e; j+=h)
      for(i=0; i+j<=N; i++)  
         w[i+j] +=a[i];
}
int main(){
   int i, w[N+1], a[N+1];
   zero(a);  
   for(i=0;i<=33;i++) a[i]=1;
   conv(w, a, 0, 25, 2);
   conv(a, w, 0, 12, 4);
   printf("%llu
",a[N]);
   for(i=50>N?N:50;i>=0;i--)      printf("%llu ",a[i]);
}

Ostatni krok (wiersz 19) można uprościć, potrzebujemy tylko jednej wartości
zostanie jedna pętelka, skorzysta się też tylko z wybranych liczb,
czyli już wcześniej część obliczeń poszła na marne
obadam to jeszcze kiedyś

[patryk007]

Te, programiści. Też nim jestem ale muszę to zrobić na kartce ładnie i sprytnie.

Rozpisałem to ze wzorów tak:
\(\displaystyle{ F(X) \; = \; (1+x+x^2+...+x^{33})\cdot (1+x^2+...+x^{48}+x^{50})\cdot (1+x^4+...+x^{48}) = \\=\frac{1-x^{33}}{1-x}\cdot \frac{1-x^{50}}{1-x^2}\cdot \frac{1-x^{48}}{1-x^4}=\frac{(1-x^{33})(1-x^{50})(1-x^{48})(1+x)}{(1-x^2)(1-x^2)(1-x^4)}=\frac{(1-x^{33})(1-x^{50})(1-x^{48})(1+x)(1+x^2)^2}{(1-x^4)^3}}\)


Korzystając ze wzoru \(\displaystyle{ \frac{1}{(1-x)^k}=\sum_{n=0}^{ \infty } {n+k-1 \choose n}\cdot x^n }}\)


\(\displaystyle{ F(X)=(1-x^{33})(1-x^{50})(1-x^{48})(1+x)(1+x^2)^2 \cdot \sum_{n=0}^{ \infty } {n+3-1 \choose n}\cdot x^n }=\\=(1-x^{33})(1-x^{50})(1-x^{48})(1+x)(1+2\cdot x^2+x^4) \cdot \sum_{n=0}^{ \infty } {n+2 \choose n}\cdot x^n }=\\=(1-x^{50})(1-x^{48})(1-x^{33})(1+x+2x^2+2x^3+x^4+x^5) \cdot \sum_{n=0}^{ \infty } \frac{(n+1)(n+2)}{2} \cdot x^n }}\)

Teraz szukam współczynnika przy \(\displaystyle{ x^{50}}\)

No to mamy takie opcje (kolejno: pierwszy nawias, drugi, trzeci, czwarty i piąte to to co jest po znaku sumy):
n = 0 || 50 + 0 + 0 + 0 + 0
n = 0 || 0 + 48 + 0 + 2 +0
n = 3 || 0 + 0 + 33 + 5 + 12
n = 4 || 0 + 0 + 33 + 1 + 16
n = 5 || 0 + 0 + 0 + 2 + 48

Z tego mi wychodzi ten współczynnik 154 a powinno być 157.
Jakiej opcji jeszcze nie policzyłem?-- 24 maja 2011, 23:17 --Ktoś pomoże?

[MatizMac]

printtex(sum(i=0,35,x^i)*sum(i=0,24,x^(2*i))*sum(i=0,12,x^(4*i)))

Mógłbym spytać jak z tego korzystać? tzn. gdzie się to wpisuje itd.?

... ok już wiem, program PARI/GP

[johanneskate]

Pomoże ktoś zrozumieć jak liczyć ten współczynnik przy danej potędze?