Ilość rosnących ciągów 4-elementowych spełniających warunek
-
abc666
Ilość rosnących ciągów 4-elementowych spełniających warunek
Oj literówka :-p
Nie męcz mnie już dzisiaj
-- 29 maja 2009, 17:15 --
No dobra napisze to rozwiązanie ale nie pytaj mnie qer, o szczegóły bo sam do końca niektórych kwestii nie rozumiem, wszystko w oparciu o rozdział Funkcje tworzące w zliczaniu
Najpierw sprowadzamy naszą sytuację do prostszej, ponieważ \(\displaystyle{ a,b,c,d>0}\) więc możemy podstawić \(\displaystyle{ p,q,r,s}\) gdzie \(\displaystyle{ a=p-1, b=q-1}\) itd
Dostajemy równanie \(\displaystyle{ 4p+3q+2r+s=41}\) gdzie \(\displaystyle{ p,q,r,s \ge 0}\) więc już mamy sytuację jak w artykule, teraz podstępując analogicznie (nie będę przepisywał tego wszystkiego) dostajemy zależności rekurencyjne
\(\displaystyle{ a_n=1\\
b_n=a_n+b_{n-2}\\
c_n=b_n+c_{n-3}\\
d_n=c_n+d_{n-4}}\)
I tak jak w artykule tworząc tabelkę dostajemy nasze 672
W sumie można by się też pokusi o rozwiązanie tych rekurencji-- 29 maja 2009, 19:27 --No, dobrze jest czasem zajrzeć do następnego wykładu, jest tam cały rozdział o twoim problemie i jest on bardzo dokładnie wyjaśniony ... by_na_sumy
Nie męcz mnie już dzisiaj
-- 29 maja 2009, 17:15 --
No dobra napisze to rozwiązanie ale nie pytaj mnie qer, o szczegóły bo sam do końca niektórych kwestii nie rozumiem, wszystko w oparciu o rozdział Funkcje tworzące w zliczaniu
Najpierw sprowadzamy naszą sytuację do prostszej, ponieważ \(\displaystyle{ a,b,c,d>0}\) więc możemy podstawić \(\displaystyle{ p,q,r,s}\) gdzie \(\displaystyle{ a=p-1, b=q-1}\) itd
Dostajemy równanie \(\displaystyle{ 4p+3q+2r+s=41}\) gdzie \(\displaystyle{ p,q,r,s \ge 0}\) więc już mamy sytuację jak w artykule, teraz podstępując analogicznie (nie będę przepisywał tego wszystkiego) dostajemy zależności rekurencyjne
\(\displaystyle{ a_n=1\\
b_n=a_n+b_{n-2}\\
c_n=b_n+c_{n-3}\\
d_n=c_n+d_{n-4}}\)
I tak jak w artykule tworząc tabelkę dostajemy nasze 672
Kod: Zaznacz cały
N 0 1 2 3 4 5 6 7 8 ... 36 37 38 39 40 41
a 1 1 1 1 1 1 1 1 1 ... 1 1 1 1 1 1
b 1 1 2 2 3 3 4 4 5 ... 19 19 20 20 21 21
c 1 1 2 3 4 5 7 8 10 ... 127 133 140 147 154 161
d 1 1 2 3 5 6 9 11 15 ... 478 511 551 588 632 672
Ilość rosnących ciągów 4-elementowych spełniających warunek
czy mógłby mi ktoś w punktach wypisać jak od postaci początkowej tej podanej przeze mnie po kolei wyprowadza sie kolejne wzory?? niestety ciezko mi zrozumieć te funkcje tworzące
bardzo bym prosił o jakies punktowe zestawienie najlepiej z krótkim komentarzem... wtedy może zrozumiem na jakiej zasadzie to dziala
bardzo bym prosił o jakies punktowe zestawienie najlepiej z krótkim komentarzem... wtedy może zrozumiem na jakiej zasadzie to dziala
-
abc666
Ilość rosnących ciągów 4-elementowych spełniających warunek
Ok, spróbuje jeszcze raz to wszystko zebrać, ale fajnie jakby ktoś się jeszcze wypowiedział kto przerabiał funkcje tworzące.
Mamy nasze równanie
\(\displaystyle{ x_1+x_2+x_3+x_4=51}\) gdzie \(\displaystyle{ x_1, x_2, x_3, x_4 \in \mathbb{C}_+ \wedge x_1>x_2>x_3>x_4}\)
Teraz stosujemy podstawienie
\(\displaystyle{ x_1=a+b+c+d \\
x_2=a+b+c\\
x_3=a+b\\
x_4=a}\)
gdzie \(\displaystyle{ a,b,c,d \in \mathbb{C}_+}\) . W ten sposób pozbyliśmy się relacji pomiędzy zmiennymi. A nasze równanie ma postać \(\displaystyle{ 4a+3b+2c+d=51}\)
Teraz stosujemy kolejne podstawienie
\(\displaystyle{ a=p+1 \\
b=q+1\\
c=r+1\\
d=s+1}\)
gdzie \(\displaystyle{ p,q,r,s \in \mathbb{C}_+ \cup \{0\}}\). Dzięki temu podstawieniu dostaliśmy równanie które ma tyle samo rozwiązań, ale rozwiązujemy je już w liczbach całkowitych nieujemnych.
\(\displaystyle{ 4(p+1)+3(q+1)+2(r+1)+s+1=51\\
4p+3q+2r+s=41 \quad (*)}\)
Liczba rozwiązań równania \(\displaystyle{ (*)}\) to liczba sposobów na które możemy rozmienić \(\displaystyle{ 41}\) przy użyciu monet \(\displaystyle{ 1,2,3,4}\).
Teraz oznaczmy przez \(\displaystyle{ A_k(x)}\) funkcje tworzącą \(\displaystyle{ A_k(x)=1+x^k+x^{2k}+x^{3k}+...}\). Wiemy też że \(\displaystyle{ 1+x^k+x^{2k}+x^{3k}+...= \frac{1}{1-x^k} \quad ( \star)}\).
Z linkowanego artykułu wiemy też, że funkcja \(\displaystyle{ A_k(x)}\) przedstawia suma wszystkich możliwych kwot jakie możemy uzyskać przy pomocy monet o nominale \(\displaystyle{ k}\).
Liczba możliwości rozmienienia kwoty \(\displaystyle{ n}\) przy pomocy monet \(\displaystyle{ 1,2,3,4}\) jest więc współczynnikiem przy wyrazie \(\displaystyle{ x^n}\) wyrażenia \(\displaystyle{ A_1(x) \cdot A_2(x) \cdot A_3(x) \cdot A_4(x)}\)
Wprowadzamy teraz dodatkowo
\(\displaystyle{ A(x)}\) - liczba sposobów rozmiany przy pomocy monet 1
\(\displaystyle{ B(x)}\) - ------ // ---------- pomocy monet 1 i 2
\(\displaystyle{ C(x)}\) - ------ // ---------- pomocy monet 1,2 i 3
\(\displaystyle{ D(x)}\) - ------ // ---------- pomocy monet 1,2,3 i 4
Korzystając z równości \(\displaystyle{ ( \star)}\) możemy więc napisać
\(\displaystyle{ A(x)=A_1(x)= \frac{1}{1-x} \\
B(x)=A(x) \cdot A_2(x)= \frac{A(x)}{1-x^2} \\
C(x)=B(x) \cdot A_3(x)= \frac{B(x)}{1-x^3}\\
D(x)=C(x) \cdot A_4(x)= \frac{C(x)}{1-x^4}}\)
Stąd dostajemy
\(\displaystyle{ A(x)=1+xA(x) \\
B(x)=A(x)+x^2B(x) \\
C(x)=B(x)+x^3C(x) \\
D(x)=C(x)+x^4D(x)}\)
Teraz przez \(\displaystyle{ a_n}\) oznaczmy n-ty współczynnik \(\displaystyle{ A(x)}\), zaczynając od zera. Analogicznie definiujemy \(\displaystyle{ b_n,c_n,d_n}\)
Teraz kiedy rozwiniemy pierwszą równość dostajemy
\(\displaystyle{ a_0+a_1x+a_2x^2+...=1+x(a_0+a_1x+a_2x^2+...) \\
a_0+a_1x+a_2x^2+...=1+a_0x+a_1x^2+a_2x^3...}\)
Z równości wielomianów dostajemy że \(\displaystyle{ 1=a_0=a_1=a_2=...}\) a więc w konsekwencji mamy \(\displaystyle{ a_n=1}\). Teraz zajmijmy się \(\displaystyle{ B(x)}\), mamy
\(\displaystyle{ b_0+b_1x+b_2x^2...=a_0+a_1x+a_2x^2+...+x^2(b_0+b_1x+b_2x^2...)\\
b_0+b_1x+b_2x^2...=a_0+a_1x+a_2x^2+...+b_0x^2+b_1x^3+b_2x^4...\\
b_0+b_1x+b_2x^2...=a_0+a_1x+(a_2+b_0)x^2+(a_3+b_1)x^3+...}\)
Ponownie z równości wielomianów dostajemy że
\(\displaystyle{ b_n=a_n+b_{n-2}}\)
Teraz już przez analogię zauważamy że
\(\displaystyle{ c_n=b_n+c_{n-3}\\
d_n=c_n+d_{n-4}}\)
Więc mamy już cel naszych poszukiwań, mianowicie \(\displaystyle{ d_n}\), jeśli obliczymy \(\displaystyle{ d_{41}}\) to mamy odpowiedź. Możemy to zrobić na dwa sposoby. Albo policzyć po prostu wszystkie ciągi do 41 wyrazu włącznie lub rozwiązać te rekurencje w celu uzyskania wzoru ogólnego. Jest to raczej proste ale żmudne (wyjdą straszne krzaki), więc przy stosunkowo małej liczbie jaka jest 41 możemy obliczyć wartość na kartce. Jednak przy większej liczbie musimy wyznaczyć już wzór jawny. Jak to się robi można przeczytać w kompendium mat.pl.
Uff.., jakbyś miał jeszcze jakieś pytania to pisz
Mamy nasze równanie
\(\displaystyle{ x_1+x_2+x_3+x_4=51}\) gdzie \(\displaystyle{ x_1, x_2, x_3, x_4 \in \mathbb{C}_+ \wedge x_1>x_2>x_3>x_4}\)
Teraz stosujemy podstawienie
\(\displaystyle{ x_1=a+b+c+d \\
x_2=a+b+c\\
x_3=a+b\\
x_4=a}\)
gdzie \(\displaystyle{ a,b,c,d \in \mathbb{C}_+}\) . W ten sposób pozbyliśmy się relacji pomiędzy zmiennymi. A nasze równanie ma postać \(\displaystyle{ 4a+3b+2c+d=51}\)
Teraz stosujemy kolejne podstawienie
\(\displaystyle{ a=p+1 \\
b=q+1\\
c=r+1\\
d=s+1}\)
gdzie \(\displaystyle{ p,q,r,s \in \mathbb{C}_+ \cup \{0\}}\). Dzięki temu podstawieniu dostaliśmy równanie które ma tyle samo rozwiązań, ale rozwiązujemy je już w liczbach całkowitych nieujemnych.
\(\displaystyle{ 4(p+1)+3(q+1)+2(r+1)+s+1=51\\
4p+3q+2r+s=41 \quad (*)}\)
Liczba rozwiązań równania \(\displaystyle{ (*)}\) to liczba sposobów na które możemy rozmienić \(\displaystyle{ 41}\) przy użyciu monet \(\displaystyle{ 1,2,3,4}\).
Teraz oznaczmy przez \(\displaystyle{ A_k(x)}\) funkcje tworzącą \(\displaystyle{ A_k(x)=1+x^k+x^{2k}+x^{3k}+...}\). Wiemy też że \(\displaystyle{ 1+x^k+x^{2k}+x^{3k}+...= \frac{1}{1-x^k} \quad ( \star)}\).
Z linkowanego artykułu wiemy też, że funkcja \(\displaystyle{ A_k(x)}\) przedstawia suma wszystkich możliwych kwot jakie możemy uzyskać przy pomocy monet o nominale \(\displaystyle{ k}\).
Liczba możliwości rozmienienia kwoty \(\displaystyle{ n}\) przy pomocy monet \(\displaystyle{ 1,2,3,4}\) jest więc współczynnikiem przy wyrazie \(\displaystyle{ x^n}\) wyrażenia \(\displaystyle{ A_1(x) \cdot A_2(x) \cdot A_3(x) \cdot A_4(x)}\)
Wprowadzamy teraz dodatkowo
\(\displaystyle{ A(x)}\) - liczba sposobów rozmiany przy pomocy monet 1
\(\displaystyle{ B(x)}\) - ------ // ---------- pomocy monet 1 i 2
\(\displaystyle{ C(x)}\) - ------ // ---------- pomocy monet 1,2 i 3
\(\displaystyle{ D(x)}\) - ------ // ---------- pomocy monet 1,2,3 i 4
Korzystając z równości \(\displaystyle{ ( \star)}\) możemy więc napisać
\(\displaystyle{ A(x)=A_1(x)= \frac{1}{1-x} \\
B(x)=A(x) \cdot A_2(x)= \frac{A(x)}{1-x^2} \\
C(x)=B(x) \cdot A_3(x)= \frac{B(x)}{1-x^3}\\
D(x)=C(x) \cdot A_4(x)= \frac{C(x)}{1-x^4}}\)
Stąd dostajemy
\(\displaystyle{ A(x)=1+xA(x) \\
B(x)=A(x)+x^2B(x) \\
C(x)=B(x)+x^3C(x) \\
D(x)=C(x)+x^4D(x)}\)
Teraz przez \(\displaystyle{ a_n}\) oznaczmy n-ty współczynnik \(\displaystyle{ A(x)}\), zaczynając od zera. Analogicznie definiujemy \(\displaystyle{ b_n,c_n,d_n}\)
Teraz kiedy rozwiniemy pierwszą równość dostajemy
\(\displaystyle{ a_0+a_1x+a_2x^2+...=1+x(a_0+a_1x+a_2x^2+...) \\
a_0+a_1x+a_2x^2+...=1+a_0x+a_1x^2+a_2x^3...}\)
Z równości wielomianów dostajemy że \(\displaystyle{ 1=a_0=a_1=a_2=...}\) a więc w konsekwencji mamy \(\displaystyle{ a_n=1}\). Teraz zajmijmy się \(\displaystyle{ B(x)}\), mamy
\(\displaystyle{ b_0+b_1x+b_2x^2...=a_0+a_1x+a_2x^2+...+x^2(b_0+b_1x+b_2x^2...)\\
b_0+b_1x+b_2x^2...=a_0+a_1x+a_2x^2+...+b_0x^2+b_1x^3+b_2x^4...\\
b_0+b_1x+b_2x^2...=a_0+a_1x+(a_2+b_0)x^2+(a_3+b_1)x^3+...}\)
Ponownie z równości wielomianów dostajemy że
\(\displaystyle{ b_n=a_n+b_{n-2}}\)
Teraz już przez analogię zauważamy że
\(\displaystyle{ c_n=b_n+c_{n-3}\\
d_n=c_n+d_{n-4}}\)
Więc mamy już cel naszych poszukiwań, mianowicie \(\displaystyle{ d_n}\), jeśli obliczymy \(\displaystyle{ d_{41}}\) to mamy odpowiedź. Możemy to zrobić na dwa sposoby. Albo policzyć po prostu wszystkie ciągi do 41 wyrazu włącznie lub rozwiązać te rekurencje w celu uzyskania wzoru ogólnego. Jest to raczej proste ale żmudne (wyjdą straszne krzaki), więc przy stosunkowo małej liczbie jaka jest 41 możemy obliczyć wartość na kartce. Jednak przy większej liczbie musimy wyznaczyć już wzór jawny. Jak to się robi można przeczytać w kompendium mat.pl.
Uff.., jakbyś miał jeszcze jakieś pytania to pisz