cztery pary małżeńskie

[gacman]

Do zdjecia pozuja cztery pary małzenskie. Ile jest mozliwych ustawien takich, ze zadna zona nie stoi obok swojego meza, jezeli wszyscy stoja w jednym rzedzie?

Czy jest to \(\displaystyle{ 8! - {4 \choose 2}}\)?

[arek1357]

Raczej ten wzór chyba nie jest dobry
Ja tu widzę troszkę inaczej mianowicie niech \(\displaystyle{ a_{i}}\) oznacza ilość permutacji \(\displaystyle{ i}\) par
tak aby małżeństwa nie stały koło siebie.

łatwo zauważyć, że:

\(\displaystyle{ a_{1}=0, a_{2}=8}\)
i teraz najpierw bierzemy jedną parę na \(\displaystyle{ n}\) sposobów z \(\displaystyle{ a_{n}}\) par, pomiędzy tę parę dajemy nową parę i przekładamy na \(\displaystyle{ 8}\) sposobów ,

i żeby pary nie stały koło siebie jest \(\displaystyle{ 8na_{n-1}}\) możliwości a do tego dokładamy
jeszcze \(\displaystyle{ 2(1+2+...+2n)a_{n}}\) czyli ułożenie \(\displaystyle{ a_{n}}\) przekładamy jedną dołożoną parą którą też przestawiamy na \(\displaystyle{ 2}\) sposoby
Razem mamy:

\(\displaystyle{ a_{n+1}=8na_{n-1}+2n(2n+1)a_{n}}\)

[Dilectus]

Cztery pary mogą stać obok siebie na \(\displaystyle{ 4!\cdot 2!}\) sposobów i tyle jest możliwych ustawień takich, żeby żona stała obok męża. Interesują nas pozostałe sposoby, czyli

\(\displaystyle{ 8!-4!\cdot 2!=40272}\)

Żeby zrobić tyle zdjęć czterem parom małżeńskim fotograf musi się sporo napstrykać...

Chyba, że się gdzieś rąbnąłem...

[arek1357]

Ale nie uwzględniasz sytuacji gdy tylko jedna lub dwie lub trzy pary stoją koło siebie!!
Dlatego pojechałem rekurencją!

[Dilectus]

Masz rację...

[Gouranga]

Jeszcze prościej - metodą włączania i wyłączania:
Wszystkich możliwości mamy \(\displaystyle{ 8!}\)
Odejmujemy od tego wszystkie możliwości, gdzie conajmniej jedna żona stoi obok swojego męża
Takich możliwości będziemy mieli \(\displaystyle{ {4 \choose 1} \cdot 2 \cdot 7!}\) bo z 4 żon wybieramy jedną, 2 możliwe ustawienia w obrębie pary i 7! przestawień reszty
Teraz musimy włączyć do tego wszystkie, gdzie co najmniej dwie żony są obok swoich mężów (bo w poprzednim kroku odjęliśmy je dwukrotnie)
będzie ich \(\displaystyle{ {4 \choose 2}\cdot 4 \cdot 6!}\) wiadomo dlaczego - 2 żony z 4, 2 opcje w każdej z 2 par i 6! przestawień
dalej musimy odjąć te, gdzie są conajmniej 3 żony ze swoimi i dodać przypadek, gdzie wszystkie są dobrze, ostatecznie dostajemy:
\(\displaystyle{ \sum_{i=0}^{4} (-1)^{i}{4 \choose i} \cdot 2^{i} \cdot (8-i)!}\)

[arek1357]

Na piechotę liczę i zawsze wychodzi mi, że \(\displaystyle{ a_{3}=160}\)

Z Twego wzoru wychodzi \(\displaystyle{ a_{3}=240}\)

\(\displaystyle{ 1,2,1',2'}\)

\(\displaystyle{ 1',2,1,2'}\)

\(\displaystyle{ 1,2',1',2}\)

\(\displaystyle{ 1',2',1,2}\)

to samo jak jest dwójka z przodu co da nam \(\displaystyle{ 8}\) możliwości dla \(\displaystyle{ a_{2}}\)

I teraz do każdej możliwości z \(\displaystyle{ a_{2}}\) dokładamy \(\displaystyle{ 20}\) możliwości
przekładek trzeciej pary co da nam \(\displaystyle{ 20 \cdot 8=160}\)

Czy może coś przeoczyłem

[Gouranga]

\(\displaystyle{ a_3}\):
na \(\displaystyle{ {4 \choose 3}}\) sposobów wybieramy 3 żony, które będą miały swojego męża obok siebie (4 sposoby)
każda, która ma koło siebie swojego męża stanowi z nim parę, więc mamy 3 pary + 2 osoby luzem
w każdej z par możemy zamieniać małżonków (\(\displaystyle{ 2^3 = 8}\)) a 3 pary + 2 osoby luzem możemy mieszać na \(\displaystyle{ 5!}\) sposobów
\(\displaystyle{ 4 \cdot 8 \cdot 5! = 32 \cdot 120 = 3840}\)

[arek1357]

Zaraz zaraz trzy pary wyjdzie więcej niż \(\displaystyle{ 6!=720}\)

[Gouranga]

No tak, przeanalizuj to dokładnie
\(\displaystyle{ 4}\) sposoby na wybranie, które żony mają mieć swoich mężów
\(\displaystyle{ 2^3}\) przestawień osób w obrębie 3 par
\(\displaystyle{ 5!}\) permutacji 3 par z 2 osobami

[arek1357]

No dobrze ale ja tu czegoś nie kumam \(\displaystyle{ 3}\) pary to tylko \(\displaystyle{ 6}\) osób,
i jak może ilość wszystkich permutacji być mniejsza od sposobów ustawienia żon i mężów nie koło siebie.

[Gouranga]

bo w metodzie włączania i wyłączania przypadki się powtarzają
na prostym przykładzie, masz książki \(\displaystyle{ A,B,C,D}\), na ile sposobów możesz je ustawić tak, żeby conajmniej jedna była na swoim miejscu? zgodnie z tą metodą takie \(\displaystyle{ a_1}\) czyli tych do wzoru będzie \(\displaystyle{ {4 \choose 1} \cdot 3!}\) ale to liczy że np. A na swoim miejscu a pozostałe B D C a potem ten sam układ A B D C liczy dla B na swoim miejscu i permutacji reszty dlatego gdybyśmy chcieli policzyć faktycznie ile jest takich ustawieńto trzeba by od wszystkich odjąć wszystkie gdzie żadna nie jest na swoim, wszystkie gdzie conajmniej 2 są na swoim miejscu, dodać wszystklie gdzie 3 sąna swoim itd. to się tak na zmianę dodaje i odejmuje i te wielokrotne przypadki się wtedy dopełniają na równo

[arek1357]

Znam metodę wyłączania i włączania i wiem że to co się z nadwyżką doda trzeba potem odjąć jest to konsekwencją wzoru Sylwestra.
Ale w naszym przypadku i będę tego na razie bronił wychodzi \(\displaystyle{ a_{3}=160}\)

a \(\displaystyle{ a_{2}=8}\)

[pio95]

Spróbowałem całkowicie odmiennego podejścia - rozwiązać to intuicyjną (przynajmniej dla informatyka) rekurencją. Mam nadzieję, że nie obrazicie się za użycie składni javascriptu zamiast zapisu matematycznego - tak szybciej było testować:
p - liczba par do wstawienia w rząd
s - liczba "singli" do wstawienia, tzn. osób których druga połówka już stoi w rzędzie
c - korekta: 1, jeśli druga połówka pary osoby ostatnio wstawionej jeszcze jest do wstawienia, 0 jeśli ostatnio wstawiona była osoba dopełniająca parę wśród ustawionych.

Kod: Zaznacz cały

t = function(p,s,c) {
var sum = 0;
if(p==0 && s==1 && c==0) return 1; // ostatnie miejsce bez kolizji
if(p>0) sum+=2*p*t(p-1,s+1,1); // ilość sposobów wstawienia jednej osoby spośród p par razy ilość możliwych ustawień dla reszty miejsc c=1

if(s>c) sum+=(s-c)*t(p,s-1,0);  // ilość sposobów wstawienia jednej osoby spośród s "singli" razy ilość możliwych ustawień dla reszty miejsc przy c=0
// z uwzględnieniem możliwości, że jeden z "singli" może być 
// "zablokowany" przez poprzednią osobę - uwzględnione przez c
return sum;
}

Wyniki:

Kod: Zaznacz cały

t(1,0,0) = 0
t(2,0,0) = 8
t(3,0,0) = 240
t(4,0,0) = 13824
t(5,0,0) = 1263360

To skłania mnie do uznania rozwiązania Gouranga (metoda włączania i wyłączania) za prawidłowe, bo wyniki dostaję identyczne.

Co do

Na piechotę liczę i zawsze wychodzi mi, że \(\displaystyle{ a_{3}=160}\)
(...) do każdej możliwości z \(\displaystyle{ a_{2}}\) dokładamy \(\displaystyle{ 20}\) możliwości
przekładek trzeciej pary co da nam \(\displaystyle{ 20 \cdot 8=160}\)
Czy może coś przeoczyłem

Chyba widzę, co jest przeoczone:
Ciągów w stylu \(\displaystyle{ 1,1',2,2'}\) w \(\displaystyle{ a_{2}}\) nie było (i słusznie, bo błędne), ale przecież można je "naprawić" do \(\displaystyle{ 1,3,1',2,3',2'}\) jeśli wstawiasz kolejną parę.

[arek1357]

Tak dokładnie tu je zgubiłem