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: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 29 kwie 2020, o 13:53

Moją funkcją tworzącą w postaci zwartej jest \(\displaystyle{ \frac{1}{z} }\) , w jaki sposób przedstawić ją w postaci szeregu?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

a4karo
Użytkownik
Użytkownik
Posty: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 29 kwie 2020, o 17:17

A w jakim punkcie chcesz ten szereg?
I o jakim szeregu mowa?

wixy0
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 29 kwie 2020, o 17:41

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: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 29 kwie 2020, o 19:20

Napisz tę rekurencję poprawnie, bo ciężko zgadnąć o co chodzi

wixy0
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 29 kwie 2020, o 21:08

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: 14859
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 120 razy
Pomógł: 4921 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: Premislav » 29 kwie 2020, o 21:53

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: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 29 kwie 2020, o 22:17

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: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 1 maja 2020, o 15:58

\(\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: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 1 maja 2020, o 16:26

Przeciez co to Premislav policzył

wixy0
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 1 maja 2020, o 16:43

No jak widać nie, poza tym wielomian \(\displaystyle{ 1 - z + 2 \cdot z ^{2} }\) nie jest rozkładalny.

a4karo
Użytkownik
Użytkownik
Posty: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 1 maja 2020, o 16:50

A w twoim rachunku czym jest `a_{-1}` i `a_{-2}`?

wixy0
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 1 maja 2020, o 16:56

\(\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: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 1 maja 2020, o 17:19

Rozkłada się, tylko w zespolonych. Jakaś przeszkoda?

wixy0
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 16 kwie 2020, o 09:52
Płeć: Mężczyzna
wiek: 15
Podziękował: 5 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: wixy0 » 1 maja 2020, o 17:22

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: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Postać rozwinięta funkcji tworzącej

Post autor: a4karo » 1 maja 2020, o 17:27

dokładnie tak samo jak w rzeczywistych.

ODPOWIEDZ