Siema mam problem z tymi zadaniami jest mi wstanie ktoś pomóc
1. Tworzymy sznury korali majac do dyspozycji koraliki typu a długosci 1, oraz koraliki typów
b; c; d; e; f; g, kazde długosci 2. Ile jest róznych sznurów długosci n? Napisz wzór rekurencyjny i warunki poczatkowe.
Wyznacz dowolna metoda wzór ogólny ciagu.
2.a) Mamy po dwadziescia owoców z kazdego z nastepujacych pieciu gatunków: sliwki, jabłka,
banany, gruszki, pomarancze. Wybieramy losowo 50 owoców i wkładamy do koszyka. Ile jest takich wyborów, w których
kazdy owoc wystepuje przynajmniej raz. Uzyj funkcji tworzacych.
b) Mamy owoce kazdego z nastepujacych pieciu gatunków: sliwki, jabłka, banany, gruszki, pomarancze. Wybieramy
losowo 50 owoców i wkładamy do koszyka. Ile jest takich wyborów, w których kazdy owoc wystepuje przynajmniej raz.
Uzyj funkcji tworzacych.
c) b) Mamy owoce kazdego z nastepujacych pieciu gatunków: sliwki, jabłka, banany, gruszki, pomarancze. Wybieramy
losowo 50 owoców i wkładamy do koszyka. Ile jest takich wyborów, w których kazdy owoc wystepuje przynajmniej raz.
To jest to samo zadanie, co w podpunkcie b), ale tym razem uzyj zasady właczania-wyłaczania.
Funkcje tworzace
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Funkcje tworzace
Zadanie 1.
Jak znaleźć rekurencję? To nie jest zbytnio skomplikowane, ale należy troszeczkę pomyśleć.
Niech \(\displaystyle{ s_{n}}\) oznacza liczbę różnych sznurów długości \(\displaystyle{ n}\). Mamy oczywiście \(\displaystyle{ s_{1}=1}\), bo jest tylko jeden koralik długości jeden. Ponadto mamy \(\displaystyle{ s_{2} = 7}\), bo sznur o długości \(\displaystyle{ 2}\) można ułożyć biorąc jeden dowolny spośród koralików b-g (jest ich \(\displaystyle{ 6}\)) albo biorąc \(\displaystyle{ 2}\) koraliki typu a (zakładam, że koraliki dwa koraliki tego samego typu są identyczne i ich nie odróżniam), to daje dodatkowy 1 sposób, a więc w sumie mamy \(\displaystyle{ 7}\). To był jeden z kroków - wyznaczenie początkowych wyrazów ciągu - to podstawa do rekurencji. Dlaczego tutaj wyznaczamy akurat dwa warunki początkowe, a nie na przykład 3 lub 1, wyjaśni się w dalszej części.
Teraz przechodzimy do trudniejszej części. Po pierwsze załóżmy sobie, że mamy już sznur o długości \(\displaystyle{ k}\). Jakie możemy otrzymać sznury dodając na końcu tego sznura jeden dodatkowy koralik? Odpowiedź jest natychmiastowa - te długości mogą wynosić \(\displaystyle{ k+1}\) albo \(\displaystyle{ k+2}\). Wobec tego będziemy chcieli znaleźć rekurencyjny wzór pozwalający wyznaczyć \(\displaystyle{ s_{k+2}}\) w zależności od \(\displaystyle{ s_{k+1}}\) i \(\displaystyle{ s_{k}}\).
Zastanówmy się w jaki sposób można otrzymać sznur o długości \(\displaystyle{ k+2}\). No można to uczynić dodając do sznura o długości \(\displaystyle{ k}\) jeden koralik o długości 2 (typu b-g). Zatem w tym przypadku można to uczynić na \(\displaystyle{ 6s_{k}}\) sposobów (wszystkich sznurów o długości \(\displaystyle{ k}\) było \(\displaystyle{ s_{k}}\), a na końcu dodajemy jeden z sześciu koralików b-g. Innym sposobem można sobie pomyśleć jest dodanie na końcu sznura o długości \(\displaystyle{ k+1}\) jednego koralika o długości \(\displaystyle{ 1}\). Można to zrobić na \(\displaystyle{ s_{k+1}}\) sposobów (rozumując analogicznie jak powyżej). Czy są to już wszystkie możliwe sposoby? Okazuje się że tak. Oczywiście jest tak dlatego, że sznur o długości \(\displaystyle{ k+2}\) może powstać bezpośrednio poprzez dodanie jednego koralika tylko ze sznurów o długościach \(\displaystyle{ k}\) i \(\displaystyle{ k+1}\). Konstruowanie takiego sznura właśnie w ten sposób należy sobie wyobrażać - do małych sznurów dodajemy kolejne koraliki i w ten sposób otrzymujemy dłuższe sznury. Podsumowując dostajemy, że z jednej strony liczba sznurów o długości \(\displaystyle{ k+2}\) wynosi oczywiście \(\displaystyle{ s_{k+2}}\) (bo tak jest zdefiniowana ta wielkość, a z drugiej strony jest to równe \(\displaystyle{ s_{k+1}+6s_{k}}\). W ten sposób dostajemy naszą rekurencję:
\(\displaystyle{ s_{k+2}=s_{k+1}+6s_{k}}\).
Teraz trzeba się zastanowić nad \(\displaystyle{ k}\) w tej rekurencji. Oczywiście to działa od \(\displaystyle{ k \ge 1}\) (na upartego można brać też pusty sznur pod uwagę, ale wyjdzie to samo). Żeby rekurencja "ruszyła z miejsca" potrzeba nam pewnych wartości początkowych dla małych \(\displaystyle{ k}\), tutaj akurat dwóch pierwszych, bo po prawej stronie mamy zależność od dwóch indeksów. Ogólniej, dla innych rekurencji, trzeba znać wszystkie wyrazy o indeksach większych lub równych od najmniejszego indeksu w rekurencji aż do wyrazów o indeksach mniejszych niż wyraz o największym indeksie (oczywiście to nie zawsze się stosuje dla zagmatwanych rekurencji, ale nie przewiduję byś miał z takimi do czynienia). Czyli przykładowo dla rekurencji \(\displaystyle{ s_{k+4} = 3s_{k+3} + s_{k}}\) trzeba znać \(\displaystyle{ 4}\) wyrazy początkowe. To jest nieco skomplikowane do opisania, ale jak się załapie to widać dość szybko.
Dorzucamy do naszej rekurencji warunki początkowe:
\(\displaystyle{ \begin{cases} s_{1}=1 \\ s_{2} = 7 \\ s_{k+2}=s_{k+1}+6s_{k} \end{cases}}\)
Mamy już pełny opis na nasz ciąg.
Przystępujmy do wyznaczenia wzoru jawnego na ciąg \(\displaystyle{ s_{n}}\) (to znaczy wzoru w postaci:
\(\displaystyle{ s_{n} = \dots}\) i w miejscu kropek stoją rzeczy zależne tylko od zmiennej \(\displaystyle{ n}\).
To czynimy metodą funkcji tworzących. Napiszę o tym nieco później, bo niestety muszę właśnie wychodzić W razie wątpliwości lub pytań pisz śmiało
Jak znaleźć rekurencję? To nie jest zbytnio skomplikowane, ale należy troszeczkę pomyśleć.
Niech \(\displaystyle{ s_{n}}\) oznacza liczbę różnych sznurów długości \(\displaystyle{ n}\). Mamy oczywiście \(\displaystyle{ s_{1}=1}\), bo jest tylko jeden koralik długości jeden. Ponadto mamy \(\displaystyle{ s_{2} = 7}\), bo sznur o długości \(\displaystyle{ 2}\) można ułożyć biorąc jeden dowolny spośród koralików b-g (jest ich \(\displaystyle{ 6}\)) albo biorąc \(\displaystyle{ 2}\) koraliki typu a (zakładam, że koraliki dwa koraliki tego samego typu są identyczne i ich nie odróżniam), to daje dodatkowy 1 sposób, a więc w sumie mamy \(\displaystyle{ 7}\). To był jeden z kroków - wyznaczenie początkowych wyrazów ciągu - to podstawa do rekurencji. Dlaczego tutaj wyznaczamy akurat dwa warunki początkowe, a nie na przykład 3 lub 1, wyjaśni się w dalszej części.
Teraz przechodzimy do trudniejszej części. Po pierwsze załóżmy sobie, że mamy już sznur o długości \(\displaystyle{ k}\). Jakie możemy otrzymać sznury dodając na końcu tego sznura jeden dodatkowy koralik? Odpowiedź jest natychmiastowa - te długości mogą wynosić \(\displaystyle{ k+1}\) albo \(\displaystyle{ k+2}\). Wobec tego będziemy chcieli znaleźć rekurencyjny wzór pozwalający wyznaczyć \(\displaystyle{ s_{k+2}}\) w zależności od \(\displaystyle{ s_{k+1}}\) i \(\displaystyle{ s_{k}}\).
Zastanówmy się w jaki sposób można otrzymać sznur o długości \(\displaystyle{ k+2}\). No można to uczynić dodając do sznura o długości \(\displaystyle{ k}\) jeden koralik o długości 2 (typu b-g). Zatem w tym przypadku można to uczynić na \(\displaystyle{ 6s_{k}}\) sposobów (wszystkich sznurów o długości \(\displaystyle{ k}\) było \(\displaystyle{ s_{k}}\), a na końcu dodajemy jeden z sześciu koralików b-g. Innym sposobem można sobie pomyśleć jest dodanie na końcu sznura o długości \(\displaystyle{ k+1}\) jednego koralika o długości \(\displaystyle{ 1}\). Można to zrobić na \(\displaystyle{ s_{k+1}}\) sposobów (rozumując analogicznie jak powyżej). Czy są to już wszystkie możliwe sposoby? Okazuje się że tak. Oczywiście jest tak dlatego, że sznur o długości \(\displaystyle{ k+2}\) może powstać bezpośrednio poprzez dodanie jednego koralika tylko ze sznurów o długościach \(\displaystyle{ k}\) i \(\displaystyle{ k+1}\). Konstruowanie takiego sznura właśnie w ten sposób należy sobie wyobrażać - do małych sznurów dodajemy kolejne koraliki i w ten sposób otrzymujemy dłuższe sznury. Podsumowując dostajemy, że z jednej strony liczba sznurów o długości \(\displaystyle{ k+2}\) wynosi oczywiście \(\displaystyle{ s_{k+2}}\) (bo tak jest zdefiniowana ta wielkość, a z drugiej strony jest to równe \(\displaystyle{ s_{k+1}+6s_{k}}\). W ten sposób dostajemy naszą rekurencję:
\(\displaystyle{ s_{k+2}=s_{k+1}+6s_{k}}\).
Teraz trzeba się zastanowić nad \(\displaystyle{ k}\) w tej rekurencji. Oczywiście to działa od \(\displaystyle{ k \ge 1}\) (na upartego można brać też pusty sznur pod uwagę, ale wyjdzie to samo). Żeby rekurencja "ruszyła z miejsca" potrzeba nam pewnych wartości początkowych dla małych \(\displaystyle{ k}\), tutaj akurat dwóch pierwszych, bo po prawej stronie mamy zależność od dwóch indeksów. Ogólniej, dla innych rekurencji, trzeba znać wszystkie wyrazy o indeksach większych lub równych od najmniejszego indeksu w rekurencji aż do wyrazów o indeksach mniejszych niż wyraz o największym indeksie (oczywiście to nie zawsze się stosuje dla zagmatwanych rekurencji, ale nie przewiduję byś miał z takimi do czynienia). Czyli przykładowo dla rekurencji \(\displaystyle{ s_{k+4} = 3s_{k+3} + s_{k}}\) trzeba znać \(\displaystyle{ 4}\) wyrazy początkowe. To jest nieco skomplikowane do opisania, ale jak się załapie to widać dość szybko.
Dorzucamy do naszej rekurencji warunki początkowe:
\(\displaystyle{ \begin{cases} s_{1}=1 \\ s_{2} = 7 \\ s_{k+2}=s_{k+1}+6s_{k} \end{cases}}\)
Mamy już pełny opis na nasz ciąg.
Przystępujmy do wyznaczenia wzoru jawnego na ciąg \(\displaystyle{ s_{n}}\) (to znaczy wzoru w postaci:
\(\displaystyle{ s_{n} = \dots}\) i w miejscu kropek stoją rzeczy zależne tylko od zmiennej \(\displaystyle{ n}\).
To czynimy metodą funkcji tworzących. Napiszę o tym nieco później, bo niestety muszę właśnie wychodzić W razie wątpliwości lub pytań pisz śmiało
-
kinia7
- Użytkownik
- Posty: 704
- Rejestracja: 28 lis 2012, o 11:58
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Podziękował: 89 razy
- Pomógł: 94 razy
Funkcje tworzace
Czy a-b-a i a-c-a to są dwa różne sznury o długości 4?jawor92 pisze:1. Tworzymy sznury korali majac do dyspozycji koraliki typu a długosci 1, oraz koraliki typów
b; c; d; e; f; g, kazde długosci 2. Ile jest róznych sznurów długosci n?