Na ile sposobów można rozsadzić przy okrągłym stole n par wrogów tak, by żadna z tych par nie siedziała
obok siebie?
n par wrogów
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
n par wrogów
Ustawmy naszych ludzi w ciągi \(\displaystyle{ P_{n} i Q_{n}}\) takie że \(\displaystyle{ P_{i} jest wrogiem Q_{i}}\)
Rozstawiamy na stole:
\(\displaystyle{ P_{1}}\)Koło niego usiąść może każdy tylko nie \(\displaystyle{ Q_{1}}\)
Liczba sposobów: 2(2n-2)(2n-3).
Dalej tak sadzamy aby ludzie o tych samych indeksach nie siadali koło siebie
Czyli liczba kombinacji
2(2n-2)(2n-3)(2n-5)(2n-7)...3*1.
Rozstawiamy na stole:
\(\displaystyle{ P_{1}}\)Koło niego usiąść może każdy tylko nie \(\displaystyle{ Q_{1}}\)
Liczba sposobów: 2(2n-2)(2n-3).
Dalej tak sadzamy aby ludzie o tych samych indeksach nie siadali koło siebie
Czyli liczba kombinacji
2(2n-2)(2n-3)(2n-5)(2n-7)...3*1.