Poszukuję zadań z funkcji tworzących. Przekopałem już kilkanaście stron googla pod hasłami typu "znaleźć funkcję tworzącą", "funkcja tworząca" itd. Znalazłem głównie tematy z tego forum. Na Ważniaku też znalazłem klika przykładów do samodzielnego rozwiązania. Niestety, to mało. Jeżeli ktoś ma zadania z tego zagadnienia (np. z ćwiczeń) to bardzo proszę o wrzucenie ich tu. Oczywiście bez rozwiązania
Interesowałyby mnie polecenia "Znajdź funkcję tworzącą mając ciąg" lub "Mając f. tworzącą, znajdź odpowiadający jej ciąg".
Zadania z funkcji tworzących
-
bartek118
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Zadania z funkcji tworzących
Fajne zadania znajdziesz w literaturze, m. in.
- "Aspekty kombinatoryki", Victor Bryant,
- "Matematyka dyskretna dla informatyków 1", Jerzy Jaworski i inni
Trochę później przepiszę parę zadanek z tych książeczek, jeśli bardzo Ci na tym zależy, ale warto jednak po nie sięgnąć, bo bardzo fajnie jest w nich wytłumaczona teoria-- 6 sie 2011, o 15:54 --Możesz spróbować także wygooglować Zbiór zadań z Matematyki Dyskretnej, autorstwa dr hab. Grzegorza Bobińskiego - wśród tych zadań są także takie na funkcje generujące
- "Aspekty kombinatoryki", Victor Bryant,
- "Matematyka dyskretna dla informatyków 1", Jerzy Jaworski i inni
Trochę później przepiszę parę zadanek z tych książeczek, jeśli bardzo Ci na tym zależy, ale warto jednak po nie sięgnąć, bo bardzo fajnie jest w nich wytłumaczona teoria-- 6 sie 2011, o 15:54 --Możesz spróbować także wygooglować Zbiór zadań z Matematyki Dyskretnej, autorstwa dr hab. Grzegorza Bobińskiego - wśród tych zadań są także takie na funkcje generujące
-
bartek118
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Zadania z funkcji tworzących
Zadanie. Niech \(\displaystyle{ F_{0}}\), \(\displaystyle{ F_{1}}\), ... będą liczbami Fibonacciego i niech \(\displaystyle{ f}\) będzie funkcją zdefiniowaną w następujący sposób:
\(\displaystyle{ f(x)=F_{0}+F_{1}x+F_{2}x^{2}+...}\)
Pokazać, że
\(\displaystyle{ f(x)=\frac{x}{1-x(1+x)}}\),
a następnie wyrazić \(\displaystyle{ F_{n}}\) jako sumę współczynników dwumianowych.
Zadanie. Niech \(\displaystyle{ N}\) będzie ustaloną, dodatnią liczbą całkowitą i niech dla \(\displaystyle{ 0 \le n \le N}\)
\(\displaystyle{ a_{n}={n\choose n}+{n+1 \choose n}+{n+2 \choose n}+...+{N\choose n}}\).
Stosując metodę funkcji tworzących, wyrazić \(\displaystyle{ a_{n}}\) jako pojedynczy współczynnik dwumianowy.
Zadanie. Stosując aparat funkcji tworzących, rozwiązać równanie rekurencyjne
\(\displaystyle{ a_{n}=a_{n-1}+6a_{n-2}}\)
z warunkami początkowymi \(\displaystyle{ a_{0}=3}\) i \(\displaystyle{ a_{1}=4}\).
Zadanie. Znaleźć funkcję tworzącą ciągu \(\displaystyle{ \left( a_{n}\right)_{n \in \mathbb{N}}}\), gdzie \(\displaystyle{ a_{n}}\) oznacza liczbę całkowitoliczbowych rozwiązań równania
\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}=n}\), jeżeli
\(\displaystyle{ 0 \le x_{1} \le 5}\), \(\displaystyle{ 0 \le x_{2} \le 3}\), \(\displaystyle{ 2 \le x_{3} \le 8}\), \(\displaystyle{ 0\le x_{4} \le 4}\).
Zadanie. Znaleźć funkcję generującą, prostszą rekurencję i wzór jawny podanych ciągów:
a) \(\displaystyle{ a_{n}= \sum_{i=0}^{n-1}a_{i} + 1}\)
b) \(\displaystyle{ b_{n}= \sum_{i=0}^{n-1}\left( n-i\right) b_{i} + 1}\)
c) \(\displaystyle{ c_{n}= \sum_{i=0}^{n-1}2^{n-i-1}c_{i} + 1}\)
Zadanie. Znaleźć związek pomiędzy funkcjami generującymi ciągów \(\displaystyle{ (a_{n})}\) i \(\displaystyle{ (b_{n})}\):
a) \(\displaystyle{ a_{n+1}=b_{n}}\),
b) \(\displaystyle{ a_{n}=nb_{n}}\),
c) \(\displaystyle{ a_{n}=\sum_{i=0}^{n}b_{i}}\).
Jakby jeszcze był potrzebne jakieś zadania lub wskazówki - pisz
\(\displaystyle{ f(x)=F_{0}+F_{1}x+F_{2}x^{2}+...}\)
Pokazać, że
\(\displaystyle{ f(x)=\frac{x}{1-x(1+x)}}\),
a następnie wyrazić \(\displaystyle{ F_{n}}\) jako sumę współczynników dwumianowych.
Zadanie. Niech \(\displaystyle{ N}\) będzie ustaloną, dodatnią liczbą całkowitą i niech dla \(\displaystyle{ 0 \le n \le N}\)
\(\displaystyle{ a_{n}={n\choose n}+{n+1 \choose n}+{n+2 \choose n}+...+{N\choose n}}\).
Stosując metodę funkcji tworzących, wyrazić \(\displaystyle{ a_{n}}\) jako pojedynczy współczynnik dwumianowy.
Zadanie. Stosując aparat funkcji tworzących, rozwiązać równanie rekurencyjne
\(\displaystyle{ a_{n}=a_{n-1}+6a_{n-2}}\)
z warunkami początkowymi \(\displaystyle{ a_{0}=3}\) i \(\displaystyle{ a_{1}=4}\).
Zadanie. Znaleźć funkcję tworzącą ciągu \(\displaystyle{ \left( a_{n}\right)_{n \in \mathbb{N}}}\), gdzie \(\displaystyle{ a_{n}}\) oznacza liczbę całkowitoliczbowych rozwiązań równania
\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}=n}\), jeżeli
\(\displaystyle{ 0 \le x_{1} \le 5}\), \(\displaystyle{ 0 \le x_{2} \le 3}\), \(\displaystyle{ 2 \le x_{3} \le 8}\), \(\displaystyle{ 0\le x_{4} \le 4}\).
Zadanie. Znaleźć funkcję generującą, prostszą rekurencję i wzór jawny podanych ciągów:
a) \(\displaystyle{ a_{n}= \sum_{i=0}^{n-1}a_{i} + 1}\)
b) \(\displaystyle{ b_{n}= \sum_{i=0}^{n-1}\left( n-i\right) b_{i} + 1}\)
c) \(\displaystyle{ c_{n}= \sum_{i=0}^{n-1}2^{n-i-1}c_{i} + 1}\)
Zadanie. Znaleźć związek pomiędzy funkcjami generującymi ciągów \(\displaystyle{ (a_{n})}\) i \(\displaystyle{ (b_{n})}\):
a) \(\displaystyle{ a_{n+1}=b_{n}}\),
b) \(\displaystyle{ a_{n}=nb_{n}}\),
c) \(\displaystyle{ a_{n}=\sum_{i=0}^{n}b_{i}}\).
Jakby jeszcze był potrzebne jakieś zadania lub wskazówki - pisz
-
PAV38
- Użytkownik
- Posty: 149
- Rejestracja: 24 paź 2010, o 09:50
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 18 razy
- Pomógł: 2 razy
Zadania z funkcji tworzących
Dzięki Właśnie chodziło mi głównie o zadania podobne do trzeciego Masz, więcej tego typu? I czy są takie, że mam przykładowo jakiś tam ciąg:
\(\displaystyle{ \sum_{n=0}^{+ \infty } 8^{n-1} x^{n} =...}\)
I trzeba po prostu znaleźć funkcję tworzącą do tego. Bo głównie coś takiego, właśnie chciałem po prostu przećwiczyć, tylko na jakiś bardziej ambitnych przykładach
p.s jak zabrać się za czwarte?
\(\displaystyle{ \sum_{n=0}^{+ \infty } 8^{n-1} x^{n} =...}\)
I trzeba po prostu znaleźć funkcję tworzącą do tego. Bo głównie coś takiego, właśnie chciałem po prostu przećwiczyć, tylko na jakiś bardziej ambitnych przykładach
p.s jak zabrać się za czwarte?
-
bartek118
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Zadania z funkcji tworzących
W 5 są takie ambitniejsze przykłady. Teraz nie za bardzo mam czas, ale później wieczorkiem napiszę jeszcze parę takich przykładów.
A propos 4:
Wyjaśnię na troszkę prostszym przykładzie.
Szukamy rozwiązań całkowitoliczbowych równania \(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}=n}\) takich, że \(\displaystyle{ 0\le x_{i} \le 3}\). Liczba rozwiązań dla danego \(\displaystyle{ n}\) jest równa współczynnikowi przy \(\displaystyle{ x^{n}}\) w wyrażeniu:
\(\displaystyle{ (t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})}\)
Czyli funkcja tworząca jest postaci:
\(\displaystyle{ f(t)=(t^{0}+t^{1}+t^{2}+t^{3})^{4}}\)
No to zagadka do wytłumaczenia dla Ciebie - czemu liczba rozwiązań to współczynnik przy odpowiedniej potędze takiego wyrażenia?
Spróbuj analogicznie zrobić to zadanie czwarte, to jest fajne ćwiczenie
A propos 4:
Wyjaśnię na troszkę prostszym przykładzie.
Szukamy rozwiązań całkowitoliczbowych równania \(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}=n}\) takich, że \(\displaystyle{ 0\le x_{i} \le 3}\). Liczba rozwiązań dla danego \(\displaystyle{ n}\) jest równa współczynnikowi przy \(\displaystyle{ x^{n}}\) w wyrażeniu:
\(\displaystyle{ (t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})(t^{0}+t^{1}+t^{2}+t^{3})}\)
Czyli funkcja tworząca jest postaci:
\(\displaystyle{ f(t)=(t^{0}+t^{1}+t^{2}+t^{3})^{4}}\)
No to zagadka do wytłumaczenia dla Ciebie - czemu liczba rozwiązań to współczynnik przy odpowiedniej potędze takiego wyrażenia?
Spróbuj analogicznie zrobić to zadanie czwarte, to jest fajne ćwiczenie