Na ile różnych sposobów można wybrać wyprawę k spośród n rycerzy okrągłego stołu, jeśli nie wolno wybrać żadnych dwóch sąsiadów?
Niestety nie jestem w stanie sam tego rozwiązać...
Wyprawa rycerzy okrągłego stołu
-
pproc
- Użytkownik
- Posty: 5
- Rejestracja: 19 mar 2012, o 12:52
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 3 razy
Wyprawa rycerzy okrągłego stołu
Po pierwsze przeanalizuj sobie rozwiązanie bardzo podobnego zadania (choć na pierwszy rzut oka tego nie widać): 290545.htm#p4905853
Teraz tak: bierzemy sobie jakiś punkt odniesienia. Załóżmy, że 1 z rycerzy okrągłego stołu to Lancelot.
Rozpatrujemy 2 przypadki:
1. Lancelot jedzie:
czyli osoby będące po jego lewej stronie i prawej nie mogą jechać, zatem zostaje nam:
n-3 osób, z których trzeba wybrać k-1, więc osób, których nie wybierzemy jest: n-k-2
(analogia do powyższego zadania: k-1 czarnych kul i n-k-2 białych)
jeśli osoby które nie pojadą ustawią się teraz w szereg to między nimi będzie n-k-3 miejsc oraz 1 z lewej i 1 z prawej strony, razem n-k-1 miejsce, gdzie mogłyby siedzieć osoby wybrane
zatem w tym przypadku ilość możliwych wyborów delegacji to \(\displaystyle{ \binom{n-k-1}{k-1}}\)
2.Lancelot nie jedzie:
pozostaje nam n-1 osób, z których trzeba wybrać k, osób, których nie wybierzemy jest: n-k-1
(analogia do powyższego zadania: k czarnych kul i n-k-1 białych)
jeśli osoby które nie pojadą ustawią się teraz w szereg to między nimi będzie n-k-2 miejsc oraz 1 z lewej i 1 z prawej strony, razem n-k miejsce, gdzie mogłyby siedzieć osoby wybrane
zatem w tym przypadku ilość możliwych wyborów delegacji to \(\displaystyle{ \binom{n-k}{k}}\)
Rozw. jest: \(\displaystyle{ \binom{n-k-1}{k-1} + \binom{n-k}{k}}\)
Teraz tak: bierzemy sobie jakiś punkt odniesienia. Załóżmy, że 1 z rycerzy okrągłego stołu to Lancelot.
Rozpatrujemy 2 przypadki:
1. Lancelot jedzie:
czyli osoby będące po jego lewej stronie i prawej nie mogą jechać, zatem zostaje nam:
n-3 osób, z których trzeba wybrać k-1, więc osób, których nie wybierzemy jest: n-k-2
(analogia do powyższego zadania: k-1 czarnych kul i n-k-2 białych)
jeśli osoby które nie pojadą ustawią się teraz w szereg to między nimi będzie n-k-3 miejsc oraz 1 z lewej i 1 z prawej strony, razem n-k-1 miejsce, gdzie mogłyby siedzieć osoby wybrane
zatem w tym przypadku ilość możliwych wyborów delegacji to \(\displaystyle{ \binom{n-k-1}{k-1}}\)
2.Lancelot nie jedzie:
pozostaje nam n-1 osób, z których trzeba wybrać k, osób, których nie wybierzemy jest: n-k-1
(analogia do powyższego zadania: k czarnych kul i n-k-1 białych)
jeśli osoby które nie pojadą ustawią się teraz w szereg to między nimi będzie n-k-2 miejsc oraz 1 z lewej i 1 z prawej strony, razem n-k miejsce, gdzie mogłyby siedzieć osoby wybrane
zatem w tym przypadku ilość możliwych wyborów delegacji to \(\displaystyle{ \binom{n-k}{k}}\)
Rozw. jest: \(\displaystyle{ \binom{n-k-1}{k-1} + \binom{n-k}{k}}\)