Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Funkcje tworzące, wzór ogólny ciągu

Strona 1 z 1

[ Posty: 11 ]

Autor

Wiadomość

sarevok37 Offline

Tytuł: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 18:21

Posty: 24
Lokalizacja: Mińsk Mazoweicki

Mam taki mały problem i potrzebuję aby ktoś mi to wytłumaczył bo coś robię źle.
Muszę znaleźć jaki ciąg odpowiada funkcji tworzącej: $A(x) = \frac{ x^{2} }{ (1-x)^{3} }$
Myślałem że należy to zrobić w taki sposób:
Rozbić na 2 funkcje: $\frac{x}{(1-x)^{2} } \times \frac{x}{(1-x)}$
wtedy ciąg dla pierwszej funkcji to $a_{n}=(0,1,2,3,4...) => a_{n}=n$ (jeżeli pierwszy wyraz ciągu oznaczało się jako $a_{0}$ , bo nie pamiętam xd)
a co do drugiej funkcji to byłoby to $a_{n}=(0,1,1,1,1 ...)$ , ale że nie wiem jak zapisać to na wzór ogólny, oraz wiedząc że powinno wyjść $a _{n} = \frac{1}{2}n(n-1)$ domyślam się że jednak robię coś mocno źle

Będę wdzięczny za jakieś wytłumaczenie

Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018

Góra

Benny01 Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 18:43

Posty: 930
Lokalizacja: Górnicza Dolina

$\frac{x^2}{(1-x)^3}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}$
Jak znajdziesz $A,B,C$ to jeśli się nie mylę:
$\frac{1}{1-x}= \sum_{n=0}^{ \infty } x^n$
$\frac{1}{(1-x)^2}=\sum_{n=0}^{ \infty }(n+1) x^n$
$\frac{1}{(1-x)^3}=\frac{1}{2} \sum_{n=0}^{ \infty }(n+1)(n+2) x^n$

Góra

sarevok37 Offline

Tytuł: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 19:10

Posty: 24
Lokalizacja: Mińsk Mazoweicki

Dzięki za odpowiedź, ale nadal nie wiem jak dojść z tych obliczeń do wyniku

Góra

Premislav Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 19:37

Posty: 11872
Lokalizacja: Wrocław

Funkcja tworząca ciągu $(a_n)_{n \in \NN}$ ma postać
$G(x)= \sum_{n=0}^{ \infty }a_n \ x^n$
Przekształcenia i równości, które napisał Benny01 pozwalają (po obliczeniu współczynników $A, B, C$ ) przedstawić
$\frac{x^2}{(1-x)^3}$ w takiej formie, a następnie wystarczy spojrzeć na wyraz, który stoi przy $x^n$ , a to dlatego, że funkcja tworząca (wewnątrz przedziału zbieżności oczywiście) jednoznacznie wyznacza ciąg.
A żeby dokończyć te obliczenia, to po prostu trzeba rozwiązać równanie
$\frac{x^2}{(1-x)^3}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}$
ze względu na $A,B, C$ .
Po wymnożeniu stronami przez $(1-x)^3$ masz równość pewnych wielomianów, co daje Ci układ trzech równań na współczynniki $A,B, C$ , ponieważ dwa wielomiany są równe wtedy i tylko wtedy, gdy mają takie same współczynniki przy wszystkich potęgach.
Jeśli będziesz mieć jakiś problem z obliczeniami, to pokaż do czego doszedłeś i pomożemy dokończyć.

-- 4 sie 2017, o 19:41 --

Zobacz też tutaj:
298450.htm

Rozkład na ułamki proste często się może przydać przy takich zadaniach. Można też ordynarnie tu zgadnąć, że $A=1, B=-2, C=1$ , ale takie rozwiązanie nie jest kształcące, a poza tym nie zawsze tak łatwo zgadnąć.

Góra

sarevok37 Offline

Tytuł: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 20:12

Posty: 24
Lokalizacja: Mińsk Mazoweicki

Rozkład na ułamki proste mam opanowany, nie jest to zbyt trudne xd
problem mam jedynie z zamianą funkcji tworzącej na wzór ogólny ciągu

wyniki otrzymałem takie same jak ty $\frac{ x^{2} }{ (1-x)^{3} } = \frac{1}{1-x} + \frac{-2}{ (1-x)^{2} } + \frac{1}{ (1-x)^{3} }$

zapisując to znaczkami matematycznymi zrobiłbym to w ten sposób:
$\frac{1}{1-x} => \sum_{n=0}^{ \infty }1 \times x^{n}$
$\frac{-2}{ (1-x)^{2} } => -2 \sum_{n=1}^{ \infty }n \times x^{n-1}$
$\frac{1}{ (1-x)^{3} } => \sum_{n=1}^{ \infty }n \times x^{n-1} \times \sum_{n=0}^{ \infty } x^{n}$

jeżeli nie mam błędu to muszę teraz to lekko uprościć a następnie pododawać do siebie, tak?
przypomnę że wynik tego zadania to: $a _{n} = \frac{1}{2}n(n-1)$

Góra

Takahashi Offline

Tytuł: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 20:47

Posty: 187
Lokalizacja: brak

Lemat. $\sum_{n = 0}^\infty a^n {n + k \choose k} x^n = \frac{1}{(1-ax)^{k+1}}$

(to jest twierdzenie o dwumianie dla ujemnego wykładnika)

Wniosek 1. $\sum_{n = 0}^\infty {n + 2 \choose 2} x^n = \frac{1}{(1-x)^{3}}$

Wniosek 2. $\sum_{n = 0}^\infty \frac 12 (n+1)(n+2) x^{n+2} = \frac{x^2}{(1-x)^{3}}$

Góra

sarevok37 Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 21:09

Posty: 24
Lokalizacja: Mińsk Mazoweicki

dzięki Takahashi, to dość znaczące ułatwienie, jednak wybaczcie ale nadal nie wiem tego samego, jak to zamienić na wzór ogólny ciągu ...
było już pisane że jest to po prostu wyraz przy $x^{n}$ , jednak co gdy mamy tutaj $x^{n+2}$ , należy wyciągnąć $x^{2}$ przed znak sumy a potem coś z nim zrobić?

Góra

Takahashi Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 21:14

Posty: 187
Lokalizacja: brak

Jest mi smutno, bo w postach wyżej niepotrzebnie zachęcano Cię do szukania rozwinięć dla niższych potęg...

sarevok37, wystarczy podstawienie:

$\sum_{n = 2}^\infty \frac 12 (n-1)(n) x^{n} = \frac{x^2}{(1-x)^{3}}$ .

Szukanym ciągiem jest więc

$a_n = \begin{cases} 0 & n = 1, 2 \\ \frac{n^2-n}{2} & n > 3\end{cases}$ ,

ale tak się cudownie zgadza, że dla $n = 1, 2$ dolny wzór też działa. Dlatego można zapisać w jednolity sposób

$a_n = \frac{n^2-n}{2}$ .

Góra

sarevok37 Offline

Tytuł: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 21:27

Posty: 24
Lokalizacja: Mińsk Mazoweicki

Wielkie dzięki, znacznie mi to rozjaśniło, i tak muszę porobić jeszcze sporo zadań tego typu by się dobrze czuć w tym dziale.

Jednak liczę i liczę i doliczyć się nie mogę tutaj jednego.
$a_n = \begin{cases} 0 & n = 1, 2 \\ \frac{n^2-n}{2} & n > 3\end{cases},$
pomijając że powinno być $n \ge 3$ , to przecież jak podstawimy do dolnego wzoru $n=2$ to mamy $\frac{ 2^{2}-2 }{2} = 1$ a nie $0$

Góra

Takahashi Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 21:33

Posty: 187
Lokalizacja: brak

Powinno być:

$a_n = \begin{cases} 0 & n = 0, 1 \\ \frac{n^2-n}{2} & n \ge 2\end{cases}$ ,

ponieważ pracujemy z szeregiem potęgowym $a_0 x^0 + a_1x^1 + a_2 x^2 + \ldots$ - to znak, że pora odstawić matematykę na rzecz snu.

Góra

sarevok37 Offline

Tytuł: Re: Funkcje tworzące, wzór ogólny ciągu

Napisane: 4 sie 2017, o 21:37

Posty: 24
Lokalizacja: Mińsk Mazoweicki

Jeszcze raz wielkie dzieki

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 11 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Wariacje z powtorzeniami : wzor	hipero	3
Ile monitorów można wybrać ?? jaki wzor?	Anonymous	1
zamiana ciagu rekurencyjnego na ogolny	eoor	1
Funkcje niemalejące	author	6
wyprowadzenie wzoru na funkcję Eulera	nykus	2

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]