Rozsadzanie osób przy okrągłym stole - 2 zadania.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
krazen
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 27 wrz 2009, o 12:37
Płeć: Mężczyzna
Lokalizacja: Warszawa

Rozsadzanie osób przy okrągłym stole - 2 zadania.

Post autor: krazen »

Mam dwa następujące zadania do rozwiązania:

1. Na ile sposobów można posadzić n par przy okrągłym stole tak, żeby żadna para nie siedziała obok siebie?

Tutaj nie mam rozwiązania i nie wiem za bardzo jak się za to zabrać. Podejrzewam że trzeba skorzystać z zasady włączeń i wyłączeń tak jak niżej.

2. Przy okrągłym stole sadzamy n małżeństw, na przemian kobietę i mężczyznę. Jakie jest prawdopodobieństwo, że żadne małżeństwo nie będzie siedziało obok siebie?

Do drugiego mam rozwiązanie, w którym jest napisane, że przyjmując że miejsca są numerowane i że kobiety siedzą na miejscach nieparzystych, to ilość rozsadzeń takich, żeby k małżeństw siedziało obok siebie wynosi:

\(\displaystyle{ 2n {2n - k - 1 \choose k -1} \left( k - 1\right)! \left(n -k \right)! \left(n -k \right)!}\)

Resztę już łatwo dokończyć z zasady włączeń i wyłączeń. Czego nie rozumiem to czy przyjęcie że kobiety siedzą na nieparzystych miejscach jest ok? I skąd bierze się część \(\displaystyle{ 2n {2n - k - 1 \choose k -1} \left( k - 1\right)!}\), bo reszta to jak sądzę rozsadzenie pozostałych osób.
Awatar użytkownika
Konikov
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 13 mar 2008, o 18:56
Płeć: Mężczyzna
Lokalizacja: z całki tego świata
Podziękował: 66 razy
Pomógł: 44 razy

Rozsadzanie osób przy okrągłym stole - 2 zadania.

Post autor: Konikov »

2. Założenie, że na nieparzystych siedzą kobiety nie zmniejsza ogólności (dlaczego miałoby? Siedzeń jest parzysta liczba, a mamy okrągły stół). Rozwiązanie krok po kroku masz w 6. rozdziale skryptu B. Chlebusa:
ODPOWIEDZ