funkcja tworzaca splotu ciagow

marcyk00 · Post autor: **marcyk00** » 17 lut 2011, o 16:45

witam . mam problem z tym zadaniem :
1 . niech \(\displaystyle{ a_n}\) oznacza liczbe sposobow rozmieszczenia n nierozroznialnych kul w 6 roznych pudelkach a \(\displaystyle{ b_n}\) niech oznacza liczbe sposobow rozmieszczenia n rozroznialnych kul w 5 roznych pudelkach . spleść te ciągi . nastepnie wyprowadzic wzor na funkcje tworzaca tego splotu.

A w ogóle wie ktoś czego w tym użyć czy kombinacji czy czego innego ?

Crizz · Post autor: **Crizz** » 17 lut 2011, o 21:09

Zacznij od zapisania wzorów ogólnych tych ciągów.

W przypadku ciągu \(\displaystyle{ a_n}\) to będą kombinacje z powtórzeniami (ze zbioru 6 pudełek wybieramy multizbiór tych, do których włożymy po kuli). W przypadku ciagu \(\displaystyle{ b_n}\) to będzie wariacja z powtórzeniami (każdej kuli przyporządkowujemy pudełko, do którego ją włożymy). Potem podpowiem, co dalej.

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 00:22

czyli w tym przypadku za n te z definicji kombinacji by bylo k z tresci zadania czyli 6 . wiec (przy C i V nie

ma () nawiasow ) \(\displaystyle{ a_n=C {n\choose k} = C {n\choose 6} = {{n+6-1}\choose n} = \frac{(n+6-1)!}{(n!(6-1)!} = \frac{(n+5)!}{n!5!}}\) czyli \(\displaystyle{ a_0=\frac{(0+5)!}{0!5!}=\frac{5!}{5!}=1}\)
\(\displaystyle{ a_1=6}\) \(\displaystyle{ a_2=21}\) \(\displaystyle{ a_3=56}\) \(\displaystyle{ a_4=126}\) \(\displaystyle{ a_5=252}\) itd .
\(\displaystyle{ b_n= V^{n}_{k} = V^{n}_{ 5} = 5^n}\) czyli \(\displaystyle{ b_0=1}\) \(\displaystyle{ b_1=5}\) \(\displaystyle{ b_2=25}\) \(\displaystyle{ b_3=125}\) itd.
i
\(\displaystyle{ \left\{\begin{array}{l} a_0=1\\a_1=6\\a_n=\frac{(n+5)!}{n!5!} \end{array}}\)
i drugi ciag

\(\displaystyle{ \left\{\begin{array}{l} b_0=1\\b_1=5\\b_n=5^n \end{array}}\) ale chyba \(\displaystyle{ b_n i a_n}\) nie moze byc funkcja tworzaca bo nie odwoluje sie do wczesniejszych wyrazow.
potem to jak spleść te dwa ciągi ?? ktos podpowie ??

Crizz · Post autor: **Crizz** » 18 lut 2011, o 11:32

Definicja splotu dwóch ciągów: \(\displaystyle{ c_n=a_n \circ b_n= \sum_{k=0}^{n}a_{n-k}b_k}\).

\(\displaystyle{ a_n}\) można jeszcze uprościć, bo mamy:

\(\displaystyle{ \frac{(n+5)!}{n! \cdot 5!}=\frac{(n+5)(n+4)(n+3)(n+2)(n+1) \cdot n!}{1\cdot 2\cdot 3\cdot 4\cdot 5 \cdot n!}=\frac{(n+5)(n+4)(n+3)(n+2)(n+1)}{120}= \\ =\frac{n^5}{120}+\frac{n^4}{8}+\frac{17n^3}{24}+\frac{15n^2}{8}+\frac{n}{120}+1}\)

Ta postać może przydać się do wyznaczenia funkcji tworzącej.

Może zapytam tak: wiesz mniej więcej, co to jest funkcja tworząca i jak się ją wyznacza? Twoje pytanie w poprzednim poście sugeruje, że nie, a bez tego to raczej nie ruszysz.

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 13:10

rownanie typu
\(\displaystyle{ \left\{\begin{array}{l} a_0=1\\a_1=6\\a_n=3a_{n-1}+5a_{n-2} \end{array}}\) potrafie rozwiazac i z tego sie dochodzi do funkcji tworzacej . mnie zmylilo to ze zawsze funkcje tworzaca rozwiazywalismy od tych warunkow poczatkowych i sie dochodzilo do tej funkcji tworzacej a w tym zadaniu juz jestesmy na koncu tych krokow ktore pisze i juz mamy funkcje tworzaca wyznaczona. wiec pozostaje splesc te funkcje i po sprawie tak? a bn dobrze rozpisalem ? a jak by wygladal wynik tego splecienia tych ciagow i jak bym chcial pojsc wstecz czyli do tych warunkow poczatkowych to da sie je ustalic jakos ??

Crizz · Post autor: **Crizz** » 18 lut 2011, o 13:23

Funkcja tworząca ciągu a wzór jawny ciągu to dwie różne rzeczy. Porównaj: i .

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 13:32

no ale z wzoru jawnego mozna wyznaczyc funkcje tworzaca

a co do zadania to wystarczy bn pomnozyc przez an z pomoca tego wzoru co napisales i to by byl koniec zadania?

Crizz · Post autor: **Crizz** » 18 lut 2011, o 14:06

marcyk00 pisze:no ale z wzoru jawnego mozna wyznaczyc funkcje tworzaca

No tak, ale jeszcze jej nie wyznaczyłeś więc to nie koniec zadania.

marcyk00 pisze:wystarczy bn pomnozyc przez an z pomoca tego wzoru co napisales i to by byl koniec zadania?

To będzie koniec wyznaczania splotu funkcji.

Oczywiście w zadaniu nie chodzi o to, żeby wyznaczyć splot, a potem korzystając z wyniku, wyznaczyć funkcję tworzącą. To byłoby koszmarne. Zamiast tego, trzeba skorzystać z następującej własności: \(\displaystyle{ Z(a_n \circ b_n)=Z(a_n) \cdot Z(b_n)}\).

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 14:15

nie czaje. co to jest to Z ? mozesz bardziej na przykladach wytlumaczyc ?

Crizz · Post autor: **Crizz** » 18 lut 2011, o 14:17

Przez \(\displaystyle{ Z}\) oznaczyłem transformatę, która przyporządkowuje danemu ciągowi funkcję tworzącą tego ciągu, na przykład \(\displaystyle{ Z(2^n)=F(s)=\frac{1}{1-2s}}\).

Chodziło o to, że funkcja tworząca splotu ciągów jest równa iloczynowi funkcji tworzących tych ciągów.

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 14:38

czyli spelcienie by wygladalo \(\displaystyle{ {1}/{{1-5^n}}*
\frac{(n+5)!}{n!5!}}\) ??

Crizz · Post autor: **Crizz** » 18 lut 2011, o 15:48

Crizz pisze:Definicja splotu dwóch ciągów: \(\displaystyle{ c_n=a_n \circ b_n= \sum_{k=0}^{n}a_{n-k}b_k}\).

\(\displaystyle{ a_n={n+5 \choose 5}\\
b_n=5^{n}}\)

\(\displaystyle{ c_n=\sum_{k=0}^{n}{n-k+5 \choose 5}5^{k}}\)

Z tym Twoim zapisem, skoro już tak się na niego upierasz:
\(\displaystyle{ c_n=\sum_{k=0}^{n}\frac{(n-k+5)! \cdot 5^{k}}{5! \cdot (n-k)!}}\)

Splot jest działaniem przemiennym, czyli mogłoby być też tak:
\(\displaystyle{ c_n=\sum_{k=0}^{n}{k+5 \choose 5}5^{n-k}}\)

Nie wiem, czy taka odpowiedź Ci wystarczy, czy musisz znaleźć wzór na tę sumę. Zależy od Twojego wykładowcy.

Wskazówka do znalezienia funkcji tworzącej ciągu \(\displaystyle{ b_n}\): skorzystaj z następującej własności:

Jeśli \(\displaystyle{ Z(a_n)=F(s)}\), to \(\displaystyle{ Z(n \cdot a_n)=s \cdot F^\prime (s)}\).

Możesz też skorzystać od razu z własności:

Jeśli \(\displaystyle{ Z(a_n)=F(s)}\), to \(\displaystyle{ Z(n^k \cdot a_n)= \sum_{i=1}^{k} s^i \cdot F^{(i)} (s)}\) (gdzie \(\displaystyle{ F^{(i)}(s)}\) oznacza i-tą pochodną \(\displaystyle{ F}\)). Tak czy inaczej, będziesz musiał policzyć \(\displaystyle{ Z(n),Z(n^2),Z(n^3),Z(n^4),Z(n^5)}\) (mówię oczywiście o tej postaci \(\displaystyle{ b_n}\), którą podałem parę postów wcześniej).

Obliczenia są koszmarne, być może jest jakaś prostsza metoda, ale nic nie przychodzi mi do głowy.

marcyk00 · Post autor: **marcyk00** » 18 lut 2011, o 21:12

dzieki wielkie . jeszcze troszke posiedze przy podobnych zadaniach i postaram sie w pelni zrozymiec te funkcje tworzace .