szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 sie 2017, o 21:58 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Hej,

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

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

Proszę o pomoc
Góra
Mężczyzna Offline
PostNapisane: 8 sie 2017, o 22:02 
Użytkownik

Posty: 22725
Lokalizacja: piaski
A wiesz na ile sposobów można ich ustawić aby nie było żadnej pary ?
Góra
Mężczyzna Offline
PostNapisane: 8 sie 2017, o 22:37 
Użytkownik

Posty: 541
Lokalizacja: Kielce
niestety nie
Góra
Mężczyzna Offline
PostNapisane: 9 sie 2017, o 10:21 
Użytkownik
Avatar użytkownika

Posty: 6507
To podpowiem:
Załóżmy że chodzi o ustawienie 2n osób w rzędzie.
Wpierw ustawiają się Panowie, na n! sposobów. Pierwsza z dam ma do wyboru 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 n+1-2 miejsc, druga dowolne z n+2-2 miejsc, ... , a ostatnia dowolne z 2n-2 miejsc.
Ilość tych ustawień to (2n-2)! \cdot (n-1) \cdot n


EDIT
:oops: Sorry za wprowadzenie w błąd. :oops:
Góra
Mężczyzna Offline
PostNapisane: 9 sie 2017, o 15:30 
Użytkownik
Avatar użytkownika

Posty: 53
Lokalizacja: Poznań
Kerajs, to rozwiązanie jest nieprawidłowe. Choćby dla n=2 nie otrzymasz swoją metodą kolejności 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 1 do n. Przez A_{i_1,i_2,\ldots,i_k} oznaczmy zbiór ustawień, w których pary o numerach i_1<i_2<\ldots<i_k stoją razem (a pozostałe razem lub osobno). Mamy
|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 i_1,\ldots,i_k traktujemy jako jedną osobę. Wobec tego mamy 2n-k ,,osób'', które można ustawić na (2n-k)! sposobów. Czynnik 2^k bierze się stąd, że w każdej z par i_1,\ldots,i_k możemy ustawić żonę po prawej stronie męża lub na odwrót.

Ponieważ liczba elementów zbioru A_{i_1,i_2,\ldots,i_k} zależy tylko od n i 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
\sum_{k=1}^n (-1)^{k+1}{n \choose k}2^k(2n-k)!.

Tego wzoru niestety się nie da uprościć.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem szklanych kul  mol_ksiazkowy  0
 Kolejny problem z ilością liczb.  NogaWeza  3
 Problem związany z permutacją  myszka9  0
 Problem z ułożeniem dziewczynek i chłopców w szereg  KcR  7
 Problem rozmienienia n-kwoty bez funkcji tworzących  guziaster  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl