Na ile sposobów można rozsadzić trzy małżeństwa przy okrągłym stole tak, aby nikt nie siedział obok swojego małżonka?
Ustaliłem proste własności:
\(\displaystyle{ P_{1}}\) - pierwsze małżeństwo obok siebie.
\(\displaystyle{ P_{2}}\) - drugie małżeństwo obok siebie.
\(\displaystyle{ P_{3}}\) - trzecie małżeństwo obok siebie.
I problem mam z samym wyznaczeniem liczności zbiorów \(\displaystyle{ P_{1}}\), \(\displaystyle{ P_{2}}\), \(\displaystyle{ P_{3}}\).
Czy powinienem zdeterminować sobie jakieś miejsce? Np. przypisać mu mężczyznę z pierwszego małżeństwa i potem względem niego wyznaczać liczność wszystkich zbiorów?
Czy każde małżeństwo rozpatrywać osobno i wtedy miejsca traktować jak ponumerowane?
Okrągły stół, zasada włączeń i wyłączeń.
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Okrągły stół, zasada włączeń i wyłączeń.
Niech \(\displaystyle{ X_{i}}\) będzie zbiorem tych rozmieszczeń, w których \(\displaystyle{ i}\)-ta para małżeństw siedzi koło siebie.
Wtedy:
\(\displaystyle{ N= \sum_{i=0}^{n}(-1)^iS_{i}^{(n)}}\)
Gdzie nasze S to części wspólne.
I teraz nasze pary wybierasz tak, żeby siedziały koło siebie:
\(\displaystyle{ S_{i}^{(n)}= {n \choose i}(2n-i)! \cdot 2^i}\)- sposobów
ostatecznie masz stosując zasadę włączeń i wyłączeń:
sposobów-\(\displaystyle{ N= \sum_{i=0}^{n}(-1)^i{n \choose i}(2n-i)! \cdot 2^i}\)
U ciebie natomiast: \(\displaystyle{ n=3}\)
Bardziej elegancko by było przedstawić to rekurencyjnie.Rekurencja ma w sobie dużo więcej prostoty i elegancji oraz jest bardziej czytelna.
Guzik jedynki nie będzie...
Jak wyniki będziemy dzielić przez moc grupy izometrii \(\displaystyle{ 2n}\) - kąta to otrzymamy możliwości dla okrągłego stołu o nieponumerowanych miejscach , czyli wtedy każda symetria i obrót nie zmieni sytuacji!
Wtedy:
\(\displaystyle{ N= \sum_{i=0}^{n}(-1)^iS_{i}^{(n)}}\)
Gdzie nasze S to części wspólne.
I teraz nasze pary wybierasz tak, żeby siedziały koło siebie:
\(\displaystyle{ S_{i}^{(n)}= {n \choose i}(2n-i)! \cdot 2^i}\)- sposobów
ostatecznie masz stosując zasadę włączeń i wyłączeń:
sposobów-\(\displaystyle{ N= \sum_{i=0}^{n}(-1)^i{n \choose i}(2n-i)! \cdot 2^i}\)
U ciebie natomiast: \(\displaystyle{ n=3}\)
Bardziej elegancko by było przedstawić to rekurencyjnie.Rekurencja ma w sobie dużo więcej prostoty i elegancji oraz jest bardziej czytelna.
Guzik jedynki nie będzie...
Jak wyniki będziemy dzielić przez moc grupy izometrii \(\displaystyle{ 2n}\) - kąta to otrzymamy możliwości dla okrągłego stołu o nieponumerowanych miejscach , czyli wtedy każda symetria i obrót nie zmieni sytuacji!