szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 lip 2016, o 09:19 
Użytkownik

Posty: 1
Lokalizacja: Jaworzno
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2016, o 17:05 
Gość Specjalny

Posty: 3047
Lokalizacja: Gołąb
Zadanie 1.
Jak znaleźć rekurencję? To nie jest zbytnio skomplikowane, ale należy troszeczkę pomyśleć.
Niech s_{n} oznacza liczbę różnych sznurów długości n. Mamy oczywiście s_{1}=1, bo jest tylko jeden koralik długości jeden. Ponadto mamy s_{2} = 7, bo sznur o długości 2 można ułożyć biorąc jeden dowolny spośród koralików b-g (jest ich 6) albo biorąc 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 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 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ć k+1 albo k+2. Wobec tego będziemy chcieli znaleźć rekurencyjny wzór pozwalający wyznaczyć s_{k+2} w zależności od s_{k+1} i s_{k}.
Zastanówmy się w jaki sposób można otrzymać sznur o długości k+2. No można to uczynić dodając do sznura o długości k jeden koralik o długości 2 (typu b-g). Zatem w tym przypadku można to uczynić na 6s_{k} sposobów (wszystkich sznurów o długości k było 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 k+1 jednego koralika o długości 1. Można to zrobić na 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 k+2 może powstać bezpośrednio poprzez dodanie jednego koralika tylko ze sznurów o długościach k i 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 k+2 wynosi oczywiście s_{k+2} (bo tak jest zdefiniowana ta wielkość, a z drugiej strony jest to równe s_{k+1}+6s_{k}. W ten sposób dostajemy naszą rekurencję:
s_{k+2}=s_{k+1}+6s_{k}.
Teraz trzeba się zastanowić nad k w tej rekurencji. Oczywiście to działa od 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 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 s_{k+4} = 3s_{k+3} + s_{k} trzeba znać 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:
\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 s_{n} (to znaczy wzoru w postaci:
s_{n} = \dots i w miejscu kropek stoją rzeczy zależne tylko od zmiennej 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 :)
Góra
Kobieta Offline
PostNapisane: 5 lip 2016, o 22:48 
Użytkownik
Avatar użytkownika

Posty: 661
Lokalizacja: Wrocław
jawor92 napisał(a):
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?

Czy a-b-a i a-c-a to są dwa różne sznury o długości 4?
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2016, o 23:51 
Gość Specjalny

Posty: 3047
Lokalizacja: Gołąb
Moim zdaniem jak najbardziej. Popatrz na to tak, jakby różnym literkom odpowiadały różne kolory koralików.
Góra
Kobieta Offline
PostNapisane: 6 lip 2016, o 08:31 
Użytkownik
Avatar użytkownika

Posty: 661
Lokalizacja: Wrocław
jawor92 napisał(a):
1. Tworzymy sznury korali ...

Jeśli mowa o sznurach to a-a-b-c i c-b-a-a to jest chyba jeden sznur?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 funkcje tworzace - zadanie 5  dafra  1
 Funkcje tworzące - zadanie 6  fala21  2
 Funkcje tworzące - zadanie 29  studciak123  3
 Funkcje tworzace  P@wel  0
 Funkcje tworzące - zadanie 21  squared  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl