Na półce stoi \(\displaystyle{ 12}\) książek. Iloma sposobami można spośród nich wybrać \(\displaystyle{ 5}\) tak, aby nie brać żadnych dwóch stojących obok siebie?
Jak to zrobić? Może mi ktoś pomóc?
Na półce stoją książki
-
arek1357
- Użytkownik
- Posty: 5766
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 132 razy
- Pomógł: 528 razy
Re: Na półce stoją książki
Wydaje mi się, że problem ten można tak rozwiązać:
Załóżmy, że na półce jest w rzędzie \(\displaystyle{ n}\) książek, mamy wybrać \(\displaystyle{ k}\) z nich tak, żeby nie wybierać sąsiadów...
Oznaczmy ilość takich wyborów przez: \(\displaystyle{ f(n,k)}\)
Zauważmy, że:
\(\displaystyle{ f(n,1)=n}\)
\(\displaystyle{ f(2n-1,n)=1}\)
\(\displaystyle{ f(2n,n)=2}\)
\(\displaystyle{ f(2n-k,n)=0 , k \ge 2}\)
teraz do szeregu n książek na półce dostawmy jeną na początku, co jak widać rekurencyjnie możemy zapisać:
\(\displaystyle{ f(n+1,k)=f(n,k)+f(n-2,k-1)}\)
Drugi składnik bierze się stąd, że zakładając, że bierzemy pierwszą książkę z półki to pozostałe wybieranie \(\displaystyle{ k-1}\) książek musi pominąć drugą książkę na półce...w pierwszym wybieraniu nie wybieramy pierwszej książki z półki...
Załóżmy, że na półce jest w rzędzie \(\displaystyle{ n}\) książek, mamy wybrać \(\displaystyle{ k}\) z nich tak, żeby nie wybierać sąsiadów...
Oznaczmy ilość takich wyborów przez: \(\displaystyle{ f(n,k)}\)
Zauważmy, że:
\(\displaystyle{ f(n,1)=n}\)
\(\displaystyle{ f(2n-1,n)=1}\)
\(\displaystyle{ f(2n,n)=2}\)
\(\displaystyle{ f(2n-k,n)=0 , k \ge 2}\)
teraz do szeregu n książek na półce dostawmy jeną na początku, co jak widać rekurencyjnie możemy zapisać:
\(\displaystyle{ f(n+1,k)=f(n,k)+f(n-2,k-1)}\)
Drugi składnik bierze się stąd, że zakładając, że bierzemy pierwszą książkę z półki to pozostałe wybieranie \(\displaystyle{ k-1}\) książek musi pominąć drugą książkę na półce...w pierwszym wybieraniu nie wybieramy pierwszej książki z półki...