szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 lis 2014, o 23:50 
Użytkownik

Posty: 18
Lokalizacja: Polska
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 8! - {4 \choose 2}?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 10:09 
Użytkownik
Avatar użytkownika

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

łatwo zauważyć, że:

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

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

a_{n+1}=8na_{n-1}+2n(2n+1)a_{n}
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 14:13 
Użytkownik

Posty: 2244
Lokalizacja: Warszawa
Cztery pary mogą stać obok siebie na 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

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... :)
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 14:35 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Ale nie uwzględniasz sytuacji gdy tylko jedna lub dwie lub trzy pary stoją koło siebie!!
Dlatego pojechałem rekurencją!
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 15:13 
Użytkownik

Posty: 2244
Lokalizacja: Warszawa
Masz rację... :)
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 15:48 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
Jeszcze prościej - metodą włączania i wyłączania:
Wszystkich możliwości mamy 8!
Odejmujemy od tego wszystkie możliwości, gdzie conajmniej jedna żona stoi obok swojego męża
Takich możliwości będziemy mieli {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 {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:
\sum_{i=0}^{4} (-1)^{i}{4 \choose i} \cdot 2^{i} \cdot (8-i)!
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 16:31 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Na piechotę liczę i zawsze wychodzi mi, że a_{3}=160

Z Twego wzoru wychodzi a_{3}=240

1,2,1',2'

1',2,1,2'

1,2',1',2

1',2',1,2

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

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

Czy może coś przeoczyłem
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 16:51 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
a_3:
na {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 (2^3 = 8) a 3 pary + 2 osoby luzem możemy mieszać na 5! sposobów
4 \cdot 8 \cdot 5! = 32 \cdot 120 = 3840
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 16:54 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Zaraz zaraz trzy pary wyjdzie więcej niż 6!=720
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 17:04 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
No tak, przeanalizuj to dokładnie
4 sposoby na wybranie, które żony mają mieć swoich mężów
2^3 przestawień osób w obrębie 3 par
5! permutacji 3 par z 2 osobami
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2014, o 20:41 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
No dobrze ale ja tu czegoś nie kumam 3 pary to tylko 6 osób,
i jak może ilość wszystkich permutacji być mniejsza od sposobów ustawienia żon i mężów nie koło siebie.
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2014, o 01:19 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
bo w metodzie włączania i wyłączania przypadki się powtarzają
na prostym przykładzie, masz książki 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 a_1 czyli tych do wzoru będzie {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
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2014, o 11:18 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
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 a_{3}=160

a a_{2}=8
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2014, o 17:40 
Użytkownik

Posty: 1
Lokalizacja: Polska
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:
1
2
3
4
5
6
7
8
9
10
11
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:
1
2
3
4
5
6
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
arek1357 napisał(a):
Na piechotę liczę i zawsze wychodzi mi, że a_{3}=160
(...) do każdej możliwości z a_{2} dokładamy 20 możliwości
przekładek trzeciej pary co da nam 20 \cdot 8=160
Czy może coś przeoczyłem

Chyba widzę, co jest przeoczone:
Ciągów w stylu 1,1',2,2' w a_{2} nie było (i słusznie, bo błędne), ale przecież można je "naprawić" do 1,3,1',2,3',2' jeśli wstawiasz kolejną parę.
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2014, o 19:05 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Tak dokładnie tu je zgubiłem
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 cztery kule...  marcelinianka  1
 Relacje równości/ klasy abstrakcji (tym razem pary liczb).  Atais  4
 Pary spośród 16 osób.  kasiapuszka  1
 Z talii 52 kart losujemy cztery karty  flowers_evil  1
 zależność i pary A omega  smyda92  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl