Postać rozwinięta funkcji tworzącej

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

Moją funkcją tworzącą w postaci zwartej jest \(\displaystyle{ \frac{1}{z} }\) , w jaki sposób przedstawić ją w postaci szeregu?
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

A w jakim punkcie chcesz ten szereg?
I o jakim szeregu mowa?
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

Jestem w trakcie rozwiązywania takiej rekurencji \(\displaystyle{ a_{n} = a_{n-1} - 2a_{n-2} - 1 + 2\left[n=0 \right] }\). Wyznaczyłem już funkcję tworzącą tej rekurencji, czyli \(\displaystyle{ A(z) = \frac{1}{z} - \frac{1}{3} \frac{1}{1-z} - \frac{8}{3} \frac{1}{1+2z}}\). Teraz muszę przedstawić funkcję A(z) w postaci rozwiniętej, gdzie np dla \(\displaystyle{ \frac{1}{1-z}}\) jest to \(\displaystyle{ \sum_{n = 0}^{ \infty } z^{n}}\), a dla \(\displaystyle{ \frac{1}{1+2z}}\) jest to \(\displaystyle{ \sum_{n=0}^{ \infty } (-2)^{n} z^{n} }\).
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

Napisz tę rekurencję poprawnie, bo ciężko zgadnąć o co chodzi
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

Jest napisana poprawnie, za pomocą jednego równania. Składnik w kwadratowym nawiasie to symbol Iversona, gdy n = 0 przyjmuje wartość 1 a dla innych n przyjmuje wartość 0.

\(\displaystyle{ a_{n} = \begin{cases} 1, n = 0 \\ 0, n = 1 \\ a_{n-1} - 2a_{n-2} - 1, n \ge 2 \end{cases} }\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: Premislav »

Obawiam się, że źle wyznaczyłeś funkcję tworzącą.
\(\displaystyle{ a_{n}=a_{n-1}-2a_{n-2}-1, \ n\ge 2\\\sum_{n=2}^{\infty}a_{n}z^{n}=\sum_{n=2}^{\infty}a_{n-1}z^{n}-2\sum_{n=2}^{\infty}a_{n-2}z^{n}-\sum_{n=2}^{\infty}z^{n}\\ G(z)-a_{1}z-a_{0}=z\left(G(z)-a_{0}\right)-2z^{2}G(z)-\frac{z^{2}}{1-z}\\G(z)-1=z(G(z)-1)-2z^{2}G(z)-\frac{z^{2}}{1-z}\\G(z)\left(1-z+2z^{2}\right)=\frac{(1-z)^{2}-z^{2}}{1-z}\\ G(z)=\frac{1-2z}{(1-z)\left(1-z+2z^{2}\right)}}\)
Change my mind…
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

Coś nie za bardzo poprawnie wygląda to rozwinięcie: wyraz `1/z` wygląda podejrzanie, bo przecież `A(0)=a_0`. Sprawdź rachunki.

Ja zdecydowanie wolę rekurencję jednorodną: znajdź takie `u,` że ciąg `b_n=a_n+u` spełnia jednorodną rekurencję (tzn bez `-1`)
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

\(\displaystyle{ a _{n} = a _{n-1} - 2 \cdot a _{n-2} - 1 + 2 \cdot \left[ n=0\right] }\)
\(\displaystyle{ a _{n} \cdot z^{n} = \left( a _{n-1} - 2 \cdot a _{n-2} - 1 + 2 \cdot \left[ n=0\right]\right) \cdot z^{n} }\)
\(\displaystyle{ \sum_{n=0}^{ \infty } a _{n} \cdot z^{n} = \sum_{n=0}^{ \infty } \left( a _{n-1} - 2 \cdot a _{n-2} - 1 + 2 \cdot \left[ n=0\right]\right) \cdot z^{n}}\)

\(\displaystyle{ L = A(z)}\)
\(\displaystyle{ P = \sum_{n=0}^{ \infty } a _{n-1} \cdot z^{n} - \sum_{n=0}^{ \infty } 2 \cdot a _{n-2} \cdot z^{n} - \sum_{n=0}^{ \infty } z^{n} + \sum_{n=0}^{ \infty } 2 \cdot \left[ n=0\right] \cdot z^{n} }\)
\(\displaystyle{ P = z \cdot \sum_{n=0}^{ \infty } a _{n} \cdot z^{n} - 2 \cdot z^{2} \cdot \sum_{n=0}^{ \infty } a _{n} \cdot z^{n} - \frac{1}{1-z} + 2 \cdot 1 }\)
\(\displaystyle{ P = z \cdot A(z) - 2 \cdot z^{2} \cdot A(z) - \frac{1}{1-z} + 2 }\)
\(\displaystyle{ L = P \Leftrightarrow A(z) = z \cdot A(z) - 2 \cdot z^{2} \cdot A(z) - \frac{1}{1-z} + 2}\)
\(\displaystyle{ A(z) = \frac{1-2 \cdot z}{z \cdot \left( 1-z\right) \cdot \left( 1+2 \cdot z\right) } }\)

I po rozkładzie na ułamki proste:
\(\displaystyle{ A(z) = \frac{1}{z} - \frac{1}{3} \cdot \frac{1}{1-z} - \frac{8}{3} \cdot \frac{1}{1+2 \cdot z} }\)

Według mnie nie ma błędu i w dalszym ciągu nie wiem co zrobić z \(\displaystyle{ \frac{1}{z} }\).
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

Przeciez co to Premislav policzył
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

No jak widać nie, poza tym wielomian \(\displaystyle{ 1 - z + 2 \cdot z ^{2} }\) nie jest rozkładalny.
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

A w twoim rachunku czym jest `a_{-1}` i `a_{-2}`?
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

\(\displaystyle{ a_{n} = 0 }\) dla \(\displaystyle{ n < 0}\).

Dodano po 18 minutach 9 sekundach:
Już widzę gdzie popełniłem błąd, rzeczywiście Premislav podał dobrą odpowiedź, tylko teraz co zrobić ze składnikiem którego mianownikiem będzie ten wielomian nierozkładalny?
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

Rozkłada się, tylko w zespolonych. Jakaś przeszkoda?
wixy0
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 6 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 »

Znaczy wiem, że się rozkłada w zespolony tylko szczerze mówiąc nie pokazali nam co w tej sytuacji zrobić.
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo »

dokładnie tak samo jak w rzeczywistych.
ODPOWIEDZ