szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 5 lis 2006, o 16:53 
Użytkownik
Avatar użytkownika

Posty: 19
Lokalizacja: Kraków
Proszę o pomoc w rozwiązaniu 3 zadanek:

1) Ile podzbiorów zbioru {1,2,3,...} wliczając zbiór pusty nie zawiera sąsiednich liczb?
2) Na ile sposobów można wypełnić prostokąt o wymiarach 2 x n kostkami domino w wymiarach 2 x 1?
3) Ile jest słów długości n złożonych z liter a,b,c, w których nie ma dwóch kolejnych liter a?

Bardzo proszę o jakiś komentarz do zadań i w miarę możliwości o wzór rekurencyjny:)

Pozdrawiam :smile:
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 5 lis 2006, o 17:44 
Użytkownik

Posty: 5809
Lokalizacja: Kraków
ad1 Fibonacci Fn+2
Góra
Mężczyzna
PostNapisane: 7 lis 2006, o 20:03 
Użytkownik

Posty: 103
Lokalizacja: Warszawa
Ad.2 Nie jestem dobry w te klocki, więc jeśli się mylę, to poprawcie mnie.

Możemy postawić klocek pionowo, i wtedy pozostanie nam n-1 "miejsc" lub postawić dwa klocki poziomo i pozostanie nam n-2 miejsc. Zatem:

F_{n}=F_{n-1}+F_{n-2} , czyli Fibonacci.
Góra
Mężczyzna
PostNapisane: 29 sie 2012, o 11:05 
Użytkownik

Posty: 6
Lokalizacja: Wawa
3.

Alfabet zawiera dwie litery \Sigma ={a,b}

S_[n] - liczba słów długości słów n, gdzie nie występuje "aa".

1) a,b,c...\infty - S_{n-2}
2) b,c...\infty -S_{n-1}


\begin{cases} 
S_{n}= S_{n-2}+S_{n-1};  n \ge 2 \\
S_{0}= 1 \\
S_{1}= 2 \\
 \end{cases}
Góra
Mężczyzna
PostNapisane: 30 sie 2012, o 02:24 
Użytkownik

Posty: 26
@Hefajstos1
1. Mocny wykop, nie ma co :D
2. Dlaczego S_{1} to 2? Nie mamy 3 słów 1-literowych (a; b; c)? Trochę też nie rozumiem Twojego zapisu z nieskończonościami. Ja bym do tego podszedł trochę inaczej (tzn. zdefiniował A_{n}, B_{n}, C_{n} jako n-literowe ciągi kończące się na odpowiednio a, b, c, a później zapisał S_{n} jako odpowiednią sumę tychże ciągów tzn.:
\begin{cases}
S_{n} = 2A_{n-1} + 3B_{n-1} + 3C_{n-1}\\
A_{n}= B_{n-1} +  C_{n-1}\\
B_{n}= A_{n-1} + B_{n-1} +  C_{n-1}\\
C_{n}= A_{n-1} + B_{n-1} +  C_{n-1}\\
\end{cases},
ale w ten sposób zadanie robi się podejrzanie trudniejsze od 2 poprzednich (co prawda nie aż tak trudne, zwłaszcza jeśli zauważyć, że B_{n}=C_{n}, no ale i tak trudniejsze), co powoduje, że zaczynam się zastanawiać czy nie ma jakiegoś prostszego sposobu.

Pierwsze chyba z Fibonacciego. Jeśli S_{n} to liczba takich podzbiorów to mamy 2 sytuacje - ostatni element nie został wybrany (wtedy pozostaje S_{n-1} sposobów (dlaczego?)) albo został (co daje S_{n-2} sposobów (dlaczego?)). Zatem S_{n} = S_{n-1} + S_{n-2}. Jeszcze pozostaje określić S_{0} i S_{1}.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 Dwa SKOMPLIKOWANE zadania :)))  domel666  5
 :(:( jak rozwiazywac zadania z kombinatoryki :(:(  kuczek87  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl