Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Browning0
Użytkownik
Posty: 333 Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy
Post
autor: Browning0 » 3 cze 2012, o 18:25
Witajcie, mam takie zadanie i w sumie umiem je zrobić tylko do połowy, a w sumie nie wiem nawet czy tę połowę robię dobrze...
Treść zadania brzmi:
Rozwiązać równanie rekurencyjne przy pomocy funkcji tworzących
\(\displaystyle{ a_n = 4a_{n-1} - 4a_{n-2} - 3^{n-2} \quad a_0=a_1=1}\)
No to jazda!
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + x + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n = \\ \\ = 1 + x + 4 \sum_{n=2}^{\infty} a_{n-1}x^n - 4 \sum_{n=2}^{\infty} a_{n-2}x^n - \sum_{n=2}^{\infty}3^{n-2}x^n = \\ \\ = 1 + x + 4x \sum_{n=1}^{\infty}a_n x^n - 4x^2\sum_{n=0}^{\infty}a_n x^n - x^2\sum_{n=0}^{\infty}3^n x^n = \\ \\ = 1 + x + 4x (A(x) - 1) -4x^2 A(x) - \frac{x^2}{1-3x}}\)
Czyli:
\(\displaystyle{ A(x) = 1 + x + 4xA(x) - 4x -4x^2 A(x) - \frac{x^2}{1-3x} \\ \\ A(x)(1 - 4x + 4x^2) = 1 - 3x - \frac{x^2}{1-3x} \\ \\ A(x) = \frac{1-3x}{1-4x+4x^2} - \frac{x^2}{(1-3x)(1-4x+4x^2)}}\)
No właśnie... I co dalej trzeba z tym zrobić? ;/ Bardzo proszę o wskazówki!
Ostatnio zmieniony 3 cze 2012, o 18:50 przez
Browning0 , łącznie zmieniany 1 raz.
Qń
Użytkownik
Posty: 9833 Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy
Post
autor: Qń » 3 cze 2012, o 18:29
Browning0 pisze: Rozwiązać równanie rekurencyjne przy pomocy funkcji tworzących
\(\displaystyle{ a_n = 4a_{n-1} - 4a_{n-2} - 3^{n-2} \quad a_0=a_1=a}\)
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + 1 + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n}\) Nawet jeśli w treści zadania zrobiłeś literówkę i ma być
\(\displaystyle{ a_0=a_1=1}\) , to i tak powinno być:
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + x + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n}\)
A po prawidłowym wyznaczeniu funkcji tworzącej należy rozłożyć ją na ułamki proste.
Q.
Browning0
Użytkownik
Posty: 333 Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy
Post
autor: Browning0 » 3 cze 2012, o 19:16
Święta prawda! Już poprawiłem żeby nie mylić innych.
No to mamy:
\(\displaystyle{ A(x) = \frac{1-3x}{1-4x+4x^2} - \frac{x^2}{(1-3x)(1-4x+4x^2)} = \frac{1-3x}{(2x-1)^2} + \frac{x^2}{(3x-1)(2x-1)^2}}\)
\(\displaystyle{ \frac{1-3x}{(2x-1)^2} = \frac{-3}{2(2x-1)} - \frac{1}{2(2x-1)^2} \\ \\ \frac{x^2}{(3x-1)(2x-1)^2} = \frac{1}{3x-1} - \frac{1}{2(2x-1)} + \frac{1}{2(2x-1)^2}}\)
Z tego wynika, że:
\(\displaystyle{ A(x) =\frac{1}{3x-1} - \frac{2}{2x-1}}\)
Dobra, zaczyna wyglądać nawet ładnie, bo wcześniej wychodził "kartofel" ^^
Qń
Użytkownik
Posty: 9833 Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy
Post
autor: Qń » 3 cze 2012, o 20:22
Zgadza się, ale wygodniej zapisać to w postaci:
\(\displaystyle{ A(x)=\frac{2}{1-2x}-\frac{1}{1-3x}}\)
i teraz korzystając ze wzoru \(\displaystyle{ \sum_{n=0}^{\infty}q^n= \frac{1}{1-q}}\) rozwinąć w szereg. Z definicji funkcji tworzącej to co będzie stało przy \(\displaystyle{ x^n}\) to będzie właśnie \(\displaystyle{ a_n}\) .
Q.
Browning0
Użytkownik
Posty: 333 Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy
Post
autor: Browning0 » 4 cze 2012, o 16:53
\(\displaystyle{ \sum_{n=0}^{\infty} (2^{(n+1)} - 3^n)x^n}\)
Dziękuję bardzo za pomoc! Pozdrawiam
johanneskate
Użytkownik
Posty: 488 Rejestracja: 24 lut 2009, o 18:00
Płeć: Mężczyzna
Podziękował: 38 razy
Pomógł: 2 razy
Post
autor: johanneskate » 6 wrz 2012, o 21:11
Rozwiązywałem podobne zadanie i natrafiłem przy A(x) na następujący składnik:
\(\displaystyle{ \frac{1}{(1-2x)^{2}}}\) . Jak rozwinąć to w szereg?
adambak
Użytkownik
Posty: 1272 Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy
Post
autor: adambak » 6 wrz 2012, o 22:58
znane: \(\displaystyle{ \frac{1}{(1-ax)^k} = \sum_{n=0}^{+\infty} {n+k-1 \choose k-1} (ax)^n}\)
iridescent
Użytkownik
Posty: 19 Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa
Post
autor: iridescent » 21 lut 2016, o 15:14
Mocno odkopuję temat, ale w jaki sposób zostało rozłożone
\(\displaystyle{ \frac{1-3x}{(2x-1)^2}}\) oraz \(\displaystyle{ \frac{x^2}{(3x-1)(2x-1)^2}}\)
Dlaczego akurat takie mianowniki i jak zostały policzone liczniki?
Kartezjusz
Użytkownik
Posty: 7330 Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy
Post
autor: Kartezjusz » 21 lut 2016, o 15:20
Tak jak przy całkach. Mianowniki były czynnikami postaci iloczynowej
iridescent
Użytkownik
Posty: 19 Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa
Post
autor: iridescent » 21 lut 2016, o 15:59
A istnieje na to pytanie odpowiedź dla kogoś kogo jeszcze całki nie obowiązują, a funkcje tworzące tak?
arek1357
Użytkownik
Posty: 5762 Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 132 razy
Pomógł: 528 razy
Post
autor: arek1357 » 21 lut 2016, o 20:41
Istnieje odpowiedź
iridescent
Użytkownik
Posty: 19 Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa
Post
autor: iridescent » 21 lut 2016, o 22:10
Niesamowicie pomocne, dziękuję.
Mariusz M
Użytkownik
Posty: 6910 Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy
Post
autor: Mariusz M » 2 kwie 2016, o 12:41
iridescent , tutaj nie chodzi o całki tylko sumę szeregu geometrycznego i jego pochodnych
(pochodne chyba już wróciły na rozszerzoną, za moich czasów były w minimum programowym)
Jeżeli funkcję tworzącą przedstawisz w postaci sumy ułamków postaci
\(\displaystyle{ \frac{A_{km}}{\left( 1-\lambda_{m}x\right)^{k} }}\)
to łatwiej ci będzie zwinąć funkcję w szereg będący sumą szeregów geometrycznych i jego pochodnych
Pochodne i tak ci się przydadzą bo co jeśli funkcja tworząca nie będzie wymierna ?
Jak wtedy uzyskasz współczynniki ?