Funkcje tworzące - matematyka dyskretna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
likas
Użytkownik
Użytkownik
Posty: 51
Rejestracja: 6 lut 2010, o 15:54
Płeć: Mężczyzna
Lokalizacja: Skierniewice
Podziękował: 2 razy
Pomógł: 8 razy

Funkcje tworzące - matematyka dyskretna

Post autor: likas »

Witam, potrzebuję pomocy w rozwiązaniu następujących zadań:
1.
Podać postać zwartą ciągu \(\displaystyle{ a_{n}=\left \( 0, 1, \frac{3}{2},2,\frac{5}{2},... \right \)}\)
Niestety nie mam pomysłu, jedynie co mi przychodzi na myśli, to wzór \(\displaystyle{ \frac{G(x)}{1-x} = g _{0} + (g_{0} + g_{1}x) + (g_{0} + g_{1} + g_{2}) x^{2} + .....}\) ale nie wiem czy to w ogóle dobry kierunek.

Dwóch następnych, nawet nie wiem jak ruszyć
2.
Podać ilość rozwiązań \(\displaystyle{ a_{1}+a_{2}+a_{3}+a_{4}=12}\), gdzie:
\(\displaystyle{ a_{1}\leq 10 \wedge a_{1}\in N}\)
\(\displaystyle{ a_{2}\leq 10 \wedge a_{2}\in N}\)
\(\displaystyle{ a_{3}\leq 3 \wedge a_{3}\in N}\)
\(\displaystyle{ a_{4}\leq 3 \wedge a_{4}\in N}\)

3.
Podać postać zwartą ciągu określonego w sposób rekurencyjny przy wykorzystaniu funkcji tworzących: \(\displaystyle{ \begin{cases} &b_{0}=2 \\ &b_{1}=3 \\ &b_{n}=2b_{n-1}+3b_{n-2} \end{cases}}\)
abc666

Funkcje tworzące - matematyka dyskretna

Post autor: abc666 »

2.
\(\displaystyle{ a_1, a_2\in \{0,1,2,3,4,5,6,7,8,9,10\} \\
a_3, a_4 \in \{0,1,2,3\}}\)


Mówiąc kolokwialnie zamieniasz sobie liczby z tych zbiorów na potęgi iksa tworząc wielomiany

\(\displaystyle{ \underbrace{(1+x+x^2+...+x^{10})}_{a_1}\underbrace{(1+x+x^2+...+x^{10})}_{a_2}\underbrace{(1+x+x^2+x^{3})}_{a_3}\underbrace{(1+x+x^2+x^{3})}_{a_4}}\)

Teraz to wszystko wymarzasz, a twoją odpowiedzią jest współczynnik stojący przy \(\displaystyle{ x^{12}}\). Oczywiście nie musisz wszystkiego wymnażać dosłownie bo interesuje cię tylko wsp. przy \(\displaystyle{ x^{12}}\). Bez f. tworzących to zadanie można zrobić dużo szybciej. Chyba po prostu słabo dobrany przykład.
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Funkcje tworzące - matematyka dyskretna

Post autor: M4ksiu »

Osobiscie uzylbym tu zasady wlaczen i wylaczen. Zakladasz \(\displaystyle{ A_i}\) takie, ze dla danego i \(\displaystyle{ x_i}\) nie spelnia zalozenia. Czyli np. jesli \(\displaystyle{ x_1 < 10}\), to bierzesz przypadek, ze \(\displaystyle{ x_1 = 10 + \{ 0, 1, 2, ... n \}}\), gdzie \(\displaystyle{ n}\) stanowi kres danego zbioru liczbowego, ktorego wartosc dodana do 10 daje maksymalna wartosc dla danego zbioru szukanego ( np. dla szukanej sumy = 15, n bedzie rowne 5 ). Teraz ustalasz sobie funkcje \(\displaystyle{ D( n, k ) =}\)\(\displaystyle{ n + k - 1 \choose k - 1}\) i to jest Twoja funkcja wybierajaca wszystkie liczby takie, ze \(\displaystyle{ x_i}\) nie spelnia Twojego zalozenia. Dziala ona w taki sposob, ze masz dane \(\displaystyle{ x_i}\), ktorego wartosc ustawiasz na pierwsza niespelniajaca zalozenia ( np. dla \(\displaystyle{ x_1 < 10}\) i sumy wszystkich x na 15 ) i sumujesz po pozostalych kombinacjach podzialu pozostalego zbioru na wszystkie x'y, przy czym dany x bedzie >= 10.

Dla \(\displaystyle{ x_1 < 10}\) i sumy \(\displaystyle{ Sum_{i \in I} x_i = 15}\) masz \(\displaystyle{ D( 5, 4 )}\), co stanowi podzial pozostalego zbioru wartosci 5 pomiedzy 4 x'y, z czego pierwszy jest zawsze niewlasciwy.
Z zasady wlaczen i wylaczen sumujesz wszystkie takie sytuacje, odejmujesz te, ktore sie powtarzaja i odejmujesz wszystkie te przypadki od wiekszej calosci ( czyli wszystkich przypadkow ), ktore stanowia po prostu \(\displaystyle{ D( maxsum, count_x )}\). Pewnie wyszlo to tlumaczenie mocno chaotycznie, ale mysle, ze takie "cos" i dodatkowo teoria wlasciwa z "wlaczen i wylaczen" pomoga Ci latwo rozwiazac 2 zadanie.

Ponadto mozesz rozwiazac z enumeratorow - jak sugeruje kolega wyzej, natomiast nawet wymnazanie konkretnego przypadku moze byc dosc uciagliwe.


Z powazaniem, M4ksiu.
Ostatnio zmieniony 29 sie 2010, o 16:50 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Nie cytuj całego, poprzedniego posta.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Funkcje tworzące - matematyka dyskretna

Post autor: Mariusz M »

1.
Podać postać zwartą ciągu \(\displaystyle{ a_{n}=\left \( 0, 1, \frac{3}{2},2,\frac{5}{2},... \right \)}\)

Rozważmy ciąg \(\displaystyle{ b_{n}=\left \( \frac{1}{2}, 1, \frac{3}{2},2,\frac{5}{2},... \right \)}\)
który jest arytmetyczny
Przesunięty ciąg \(\displaystyle{ a_{n}}\)też jest arytmetyczny

Ciąg arytmetyczny można zapisać w postaci rekurencyjnej

\(\displaystyle{ \begin{cases} a_{n}=a_{n-1}+r \\ a_{0}=c \end{cases} \\}\)

\(\displaystyle{ b_{n}=\frac{1}{2}+ \frac{1}{2}n\\
b_{n} =\frac{1}{2}\left( n+1\right) \\
\sum_{n=0}^{ \infty }{b_{n}x^n}= \frac{1}{2}\left( \sum_{n=0}^{ \infty }{\left( n+1\right)x^{n} } \right)\\
B\left( x\right)= \frac{1}{2} \frac{ \mbox{d}}{ \mbox{d}x }\left( \sum_{n=0}^{ \infty }x^{n+1} \right) \\
=\frac{1}{2} \frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{x}{1-x} \right)\\
B\left( x\right) =\frac{1}{2}\frac{1}{\left( 1-x\right)^2 } \\
A\left( x\right)=\frac{1}{2}\left( \frac{1}{\left( 1-x\right)^2 }-1 \right)\\
A\left( x\right)=\frac{1}{2} \frac{2x-x^2}{\left( 1-x\right)^2 }\\}\)
ODPOWIEDZ