Problem par małżeńskich

[Matiks21]

Hej,

znalazłem takie zadanie, nie wiem jak sobie z nim poradzić.

Na ile sposób można ustawić \(\displaystyle{ 2n}\) małżonków (\(\displaystyle{ n}\) par) tak by istniała przynajmniej jedna para małżeńska która stoi koło siebie?

Proszę o pomoc

[piasek101]

A wiesz na ile sposobów można ich ustawić aby nie było żadnej pary ?

[Matiks21]

niestety nie

[kerajs]

To podpowiem:
Załóżmy że chodzi o ustawienie 2n osób w rzędzie.
Wpierw ustawiają się Panowie, na \(\displaystyle{ n!}\) sposobów. Pierwsza z dam ma do wyboru \(\displaystyle{ n+1}\) miejsc, z czego dwa obok małżonka. Skoro pary nie mogą stać obok siebie to pierwsza z Pań może zająć dowolne z \(\displaystyle{ n+1-2}\) miejsc, druga dowolne z \(\displaystyle{ n+2-2}\) miejsc, ... , a ostatnia dowolne z \(\displaystyle{ 2n-2}\) miejsc.
Ilość tych ustawień to \(\displaystyle{ (2n-2)! \cdot (n-1) \cdot n}\)


EDIT
Sorry za wprowadzenie w błąd.

[Wuja Exul]

Kerajs, to rozwiązanie jest nieprawidłowe. Choćby dla \(\displaystyle{ n=2}\) nie otrzymasz swoją metodą kolejności \(\displaystyle{ M_1,Z_2,Z_1,M_2}\).

Właściwe podejście do tego zadania to wykorzystanie zasady włączeń i wyłączeń. Domyślam się, że chodzi o ustawienie w rzędzie (w oryginalnym sformułowaniu był okrągły stół, a problem pochodzi od Lucasa).
Ponumerujmy pary od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Przez \(\displaystyle{ A_{i_1,i_2,\ldots,i_k}}\) oznaczmy zbiór ustawień, w których pary o numerach \(\displaystyle{ i_1<i_2<\ldots<i_k}\) stoją razem (a pozostałe razem lub osobno). Mamy

\(\displaystyle{ |A_{i_1,i_2,\ldots,i_k}| = 2^k(2n-k)!.}\)

Uzasadnienie tej równości jest następujące. Każdą z par \(\displaystyle{ i_1,\ldots,i_k}\) traktujemy jako jedną osobę. Wobec tego mamy \(\displaystyle{ 2n-k}\) ,,osób', które można ustawić na \(\displaystyle{ (2n-k)!}\) sposobów. Czynnik \(\displaystyle{ 2^k}\) bierze się stąd, że w każdej z par \(\displaystyle{ i_1,\ldots,i_k}\) możemy ustawić żonę po prawej stronie męża lub na odwrót.

Ponieważ liczba elementów zbioru \(\displaystyle{ A_{i_1,i_2,\ldots,i_k}}\) zależy tylko od \(\displaystyle{ n}\) i \(\displaystyle{ k}\), możemy się posłużyć uproszczoną wersją zasady włączeń i wyłączeń. Szukana liczba ustawień, w których co najmniej jedna para stoi razem, wynosi zatem

\(\displaystyle{ \sum_{k=1}^n (-1)^{k+1}{n \choose k}2^k(2n-k)!.}\)

Tego wzoru niestety się nie da uprościć.