Witam mam problem z dwoma rodzajami zadań z MD. Licze na zyczliwosc lepszych ode mnie :
Pierwszy problem:
Jak za pomoca metody wlaczen i wylaczen obliczyc ponizsze zadanie:
Ile jest calkowitoliczbowych rozwiazan rownania:
\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=30}\)
spelniajacego warunki:
\(\displaystyle{ (a) 0 qslant x_{i} qslant 10}\)
\(\displaystyle{ (b) -10 qslant x_{i} qslant 20}\)
I drugie zadanie:
Znalesc wzor jawny i funkcje tworzaca ciagu:
\(\displaystyle{ a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n , a_{0}=0 , a_{1}=0 , a_{2}=-1}\)
Samo znalezienie wzoru jawnego nie jest problemem, chodzi glownie o funkcje tworzaca.
Dwa zadania: metoda wlaczen i wylaczen oraz funkcja tworzaca
-
max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
Dwa zadania: metoda wlaczen i wylaczen oraz funkcja tworzaca
Drugie:
Z zależności rekurencyjnej:
\(\displaystyle{ a_{n+3} = 6a_{n+2} - 12a_{n+1} + 8a_{n} + n}\)
Funkcja tworząca ciągu to szereg potęgowy o współczynnikach przy kolejnych potęgach x równych kolejnym wyrazom ciągu:
\(\displaystyle{ G(x) = \sum_{n = 0}^{\infty}a_{n}x^{n} = \\
= a_{0}\cdot x^{0} + a_{1}\cdot x^{1} + a_{2}\cdot x^{2} + \sum_{n = 0}^{\infty}a_{n + 3}x^{n + 3}=\\
= -x^{2} + \sum_{n = 0}^{\infty}(6a_{n+2} - 12a_{n+1} + 8a_{n} + n)x^{n+3} =\\
= -x^{2} + \sum_{n = 0}^{\infty}6a_{n+2}x^{n+3} - \sum_{n = 0}^{\infty} 12a_{n+1}x^{n + 3} + \sum_{n = 0}^{\infty}8a_{n}x^{n + 3} + \sum_{n = 0}^{\infty}nx^{n + 3} = \\
=-x^{2} + 6x\sum_{n = 0}^{\infty}a_{n+2}x^{n+2} - 12x^{2}\sum_{n = 0}^{\infty} a_{n+1}x^{n + 1} + 8x^{3}\sum_{n = 0}^{\infty}8a_{n}x^{n} + x^{4}\sum_{n = 0}^{\infty}nx^{n - 1} =\\
= -x^{2} + 6x(G(x) - a_{0}x^{0} - a_{1}x) - 12x^{2}(G(x) - a_{0}x^{0}) + 8x^{3}G(x) + \frac{x^{4}}{(1 - x)^{2}}=\\
= \frac{x^{4} - x^{2}(1 - x)^{2}}{(1 - x)^{2}} + 6xG(x) -12x^{2}G(x) + 8x^{3}G(x)=\\
= \frac{x^{2}(2x - 1)}{(1 - x)^{2}} + G(x)(6x - 12x^{2} + 8x^{3})}\)
Po wyliczeniu \(\displaystyle{ G(x)}\):
\(\displaystyle{ G(x) = \frac{x^{2}(2x - 1)}{(1 - x)^{2}(1 - 6x + 12x^{2} - 8x^{3})} = -\frac{x^{2}(1 - 2x)}{(1 - x)^{2}(1 - 2x)^{3}} =\\
= -\left(\frac{x}{(1 - x)(1 - 2x)}\right)^{2} = -\left(\frac{1}{1 - 2x} - \frac{1}{1 - x}\right)^{2} = \\
= -\frac{1}{(1 - 2x)^{2}} + \frac{2}{(1 - 2x)(1 - x)} - \frac{1}{(1 - x)^{2}} = \\
= -\frac{1}{(1 - 2x)^{2}} + \frac{4}{1 - 2x} - \frac{2}{1 - x} - \frac{1}{(1 - x)^{2}}}\)
Po rozwinięciu funkcji tworzącej w szereg potęgowy otrzymujemy wzór jawny na wyraz ogólny ciągu:
\(\displaystyle{ a_{n} = 2^{n}(3 - n) - n - 3}\)
Z zależności rekurencyjnej:
\(\displaystyle{ a_{n+3} = 6a_{n+2} - 12a_{n+1} + 8a_{n} + n}\)
Funkcja tworząca ciągu to szereg potęgowy o współczynnikach przy kolejnych potęgach x równych kolejnym wyrazom ciągu:
\(\displaystyle{ G(x) = \sum_{n = 0}^{\infty}a_{n}x^{n} = \\
= a_{0}\cdot x^{0} + a_{1}\cdot x^{1} + a_{2}\cdot x^{2} + \sum_{n = 0}^{\infty}a_{n + 3}x^{n + 3}=\\
= -x^{2} + \sum_{n = 0}^{\infty}(6a_{n+2} - 12a_{n+1} + 8a_{n} + n)x^{n+3} =\\
= -x^{2} + \sum_{n = 0}^{\infty}6a_{n+2}x^{n+3} - \sum_{n = 0}^{\infty} 12a_{n+1}x^{n + 3} + \sum_{n = 0}^{\infty}8a_{n}x^{n + 3} + \sum_{n = 0}^{\infty}nx^{n + 3} = \\
=-x^{2} + 6x\sum_{n = 0}^{\infty}a_{n+2}x^{n+2} - 12x^{2}\sum_{n = 0}^{\infty} a_{n+1}x^{n + 1} + 8x^{3}\sum_{n = 0}^{\infty}8a_{n}x^{n} + x^{4}\sum_{n = 0}^{\infty}nx^{n - 1} =\\
= -x^{2} + 6x(G(x) - a_{0}x^{0} - a_{1}x) - 12x^{2}(G(x) - a_{0}x^{0}) + 8x^{3}G(x) + \frac{x^{4}}{(1 - x)^{2}}=\\
= \frac{x^{4} - x^{2}(1 - x)^{2}}{(1 - x)^{2}} + 6xG(x) -12x^{2}G(x) + 8x^{3}G(x)=\\
= \frac{x^{2}(2x - 1)}{(1 - x)^{2}} + G(x)(6x - 12x^{2} + 8x^{3})}\)
Po wyliczeniu \(\displaystyle{ G(x)}\):
\(\displaystyle{ G(x) = \frac{x^{2}(2x - 1)}{(1 - x)^{2}(1 - 6x + 12x^{2} - 8x^{3})} = -\frac{x^{2}(1 - 2x)}{(1 - x)^{2}(1 - 2x)^{3}} =\\
= -\left(\frac{x}{(1 - x)(1 - 2x)}\right)^{2} = -\left(\frac{1}{1 - 2x} - \frac{1}{1 - x}\right)^{2} = \\
= -\frac{1}{(1 - 2x)^{2}} + \frac{2}{(1 - 2x)(1 - x)} - \frac{1}{(1 - x)^{2}} = \\
= -\frac{1}{(1 - 2x)^{2}} + \frac{4}{1 - 2x} - \frac{2}{1 - x} - \frac{1}{(1 - x)^{2}}}\)
Po rozwinięciu funkcji tworzącej w szereg potęgowy otrzymujemy wzór jawny na wyraz ogólny ciągu:
\(\displaystyle{ a_{n} = 2^{n}(3 - n) - n - 3}\)