Mam prostokąt o wymiarach 3 x n. Muszę znaleźć funkcję tworzącą, określającą ilość pokryć tego prostokąta bloczkami o wymiarach 1 x 3.
Mam pewną wskazówkę, mianowicie skorzystanie z rekurencji:
\(\displaystyle{ a_{n+3} = a_{n} + a_{n+2}}\)
Ale jak to wykorzystać, i co potem zrobić?
Ilość prostokątów w większym prostokącie
-
sstanko
- Użytkownik
- Posty: 27
- Rejestracja: 10 lis 2012, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 5 razy
Ilość prostokątów w większym prostokącie
\(\displaystyle{ f(x)=a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 ...}\)
\(\displaystyle{ a_0 =1; a_1 =1; a_2 =1}\)
\(\displaystyle{ a_n=a_{n-1}+a_{n-3}}\)
\(\displaystyle{ f(x)=a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 ... = a_0 + a_1 x + a_2 x^2 + (a_0+a_2)x^3 + (a_1 + a_3) x^4 + (a_2 + a_4) x^5 + ... = a_0 + a_1 x + a_2 x^2 + (a_2 x^3 + a_3 x^4 + a_4 x^5 + ...) + (a_0 x^3 + a_1 x^4 + a_2 x^5 + ...) = a_0 + a_1 x + a_2 x^2 + x(a_2 x^2 + a_3 x^3 + a_4 x^4 + ...) + x^{3}(a_0 + a_1 x + a_2 x^2 + ...) = a_0 + a_1 x + a_2 x^2 + x[f(x)-a_1 x - a_0] + x^{3}f(x) = a_0 + (a_1-a_0) x + (a_2-a_1) x^2 + (x+x^3) f(x) = 1+ (x+x^3) f(x)}\)
A wiec \(\displaystyle{ f(x)= \frac{1}{1-x-x^3} = 1+x+x^2+2x^3+3x^4+4x^5+...}\)
\(\displaystyle{ a_0 =1; a_1 =1; a_2 =1}\)
\(\displaystyle{ a_n=a_{n-1}+a_{n-3}}\)
\(\displaystyle{ f(x)=a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 ... = a_0 + a_1 x + a_2 x^2 + (a_0+a_2)x^3 + (a_1 + a_3) x^4 + (a_2 + a_4) x^5 + ... = a_0 + a_1 x + a_2 x^2 + (a_2 x^3 + a_3 x^4 + a_4 x^5 + ...) + (a_0 x^3 + a_1 x^4 + a_2 x^5 + ...) = a_0 + a_1 x + a_2 x^2 + x(a_2 x^2 + a_3 x^3 + a_4 x^4 + ...) + x^{3}(a_0 + a_1 x + a_2 x^2 + ...) = a_0 + a_1 x + a_2 x^2 + x[f(x)-a_1 x - a_0] + x^{3}f(x) = a_0 + (a_1-a_0) x + (a_2-a_1) x^2 + (x+x^3) f(x) = 1+ (x+x^3) f(x)}\)
A wiec \(\displaystyle{ f(x)= \frac{1}{1-x-x^3} = 1+x+x^2+2x^3+3x^4+4x^5+...}\)