Na półce stoją książki

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1004 razy
Pomógł: 3 razy

Na półce stoją książki

Post autor: max123321 »

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?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5762
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

Post autor: arek1357 »

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...
ODPOWIEDZ