Witam,
mam problem z następującym zadaniem:
Są trzy rodzaje kostek:
- o długości 1
- o długości 2
- o długości 3
Niech t(n) - liczba ciągów łącznej długości n, które można ułożyć z tych kostek
Wyznacz asymptotyke ciągu t(n).
Póki mam doszedłem do czegoś takiego:
trywialne przypadki:
\(\displaystyle{ t_{0}=1}\) (pusty ciąg)
\(\displaystyle{ t_{1}=1}\) (kostka długości 1)
\(\displaystyle{ t_{2}=2}\) (1 + 1, 2)
Tworząc funkcje rekurencyjną otrzymujemy:
\(\displaystyle{ t_{n}=t_{n-3}+t_{n-2}+t_{n-1}}\)
Liczymy funkcje tworzącą:
\(\displaystyle{ T(x)= \sum_{n=0}^{\infty}t_nx^n=t_0+t_1x+t_2x^2+\sum_{n=3}^{\infty}t_nx^n =}\)
\(\displaystyle{ =1+x+2x^2+\sum_{n=3}^{\infty}(t_{n-3}+t_{n-2}+t_{n-1})x^n =}\)
\(\displaystyle{ =1+x+2x^2+\sum_{n=3}^{\infty}t_{n-1}x^n+\sum_{n=3}^{\infty}t_{n-2}x^n+\sum_{n=3}^{\infty}t_{n-3}x^n=}\)
\(\displaystyle{ =1+x+2x^2+x\sum_{n=3}^{\infty}t_{n-1}x^{n-1}+x^2\sum_{n=3}^{\infty}t_{n-2}x^{n-2}+x^3\sum_{n=3}^{\infty}t_{n-3}x^{n-3}=}\)
\(\displaystyle{ =1+x+2x^2+x\sum_{n=2}^{\infty}t_{n}x^{n}+x^2\sum_{n=1}^{\infty}t_{n}x^{n}+x^3\sum_{n=0}^{\infty}t_{n}x^{n}=}\)
\(\displaystyle{ =1+x+2x^2+x(T(x)-(t_0+t_1x))+x^2(T(x)-t_0)+x^3T(x)}\)
\(\displaystyle{ T(x)=1+x+2x^2+xT(x)-x-x^2+x^2T(x)-x^2+x^3T(x)}\)
\(\displaystyle{ T(x)-xT(x)-x^2T(x)-x^3T(x)= 1}\)
\(\displaystyle{ T(x)(1-x-x^2-x^3)= 1}\)
\(\displaystyle{ T(x)= \frac{1}{1-x-x^2-x^3}}\)
i tutaj mi się komplikuje. Gdyby\(\displaystyle{ 1-x-x^2-x^3}\) miało 3 pierwiastki to nie miałbym żadnego problemu - rozbijam na 3 ułamki i znajduję dominujący składnik, lecz w tym przypadku mam problem.
Bardzo proszę o pomoc co mam dalej zrobić. A może popełniłem błąd gdzieś wcześniej?
pozdrawiam,
Antek
asymptotyka ciągu
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
asymptotyka ciągu
Ten wielomian ma trzy różne pierwiastki zespolone.
\(\displaystyle{ t_n=t_{n-1}+t_{n-2}+t_{n-3}+[n=0]}\) dla dowolnych \(\displaystyle{ n}\), niekoniecznie \(\displaystyle{ n>3}\).
\(\displaystyle{ \sum_{n=0}^{\infty}t_nx^n=
\sum_{n=0}^{\infty}t_{n-1}x^n+\sum_{n=0}^{\infty}t_{n-2}x^n+\sum_{n=0}^{\infty}t_{n-3}x^n+1=\\\\
=x\sum_{n=-1}^{\infty}t_nx^n+x^2\sum_{n=-2}^{\infty}t_{n}x^n+x^3\sum_{n=-3}^{\infty}t_{n}x^n+1}\)
\(\displaystyle{ T(x)=xT(x)+x^2T(x)+x^3T(x)+1}\).
Tu brakuje \(\displaystyle{ x}\) przy \(\displaystyle{ t_1}\), a później też są błędy. Łatwiej jest zastosować tzw. nawias Iversona: \(\displaystyle{ [\mathrm{warunek}]}\) jest równy \(\displaystyle{ 0}\), gdy warunek jest fałszywy, \(\displaystyle{ 1}\), gdy prawdziwy.antek11 pisze: \(\displaystyle{ =1+x+2x^2+x(T(x)-(t_0+t_1))+x^2(T(x)-t_0)+x^3T(x)}\)
\(\displaystyle{ t_n=t_{n-1}+t_{n-2}+t_{n-3}+[n=0]}\) dla dowolnych \(\displaystyle{ n}\), niekoniecznie \(\displaystyle{ n>3}\).
\(\displaystyle{ \sum_{n=0}^{\infty}t_nx^n=
\sum_{n=0}^{\infty}t_{n-1}x^n+\sum_{n=0}^{\infty}t_{n-2}x^n+\sum_{n=0}^{\infty}t_{n-3}x^n+1=\\\\
=x\sum_{n=-1}^{\infty}t_nx^n+x^2\sum_{n=-2}^{\infty}t_{n}x^n+x^3\sum_{n=-3}^{\infty}t_{n}x^n+1}\)
\(\displaystyle{ T(x)=xT(x)+x^2T(x)+x^3T(x)+1}\).
-
antek11
- Użytkownik
- Posty: 80
- Rejestracja: 29 paź 2006, o 11:18
- Płeć: Mężczyzna
- Lokalizacja: Wałbrzych
- Podziękował: 30 razy
asymptotyka ciągu
Dziękuję bardzo za wskazówki - poprawiłem już obliczenia na górze.
A mógłbyś mi dać wskazówkę jak się do tego zabrać w przypadku pierwiastków urojonych?
A mógłbyś mi dać wskazówkę jak się do tego zabrać w przypadku pierwiastków urojonych?