szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 22:01 
Użytkownik

Posty: 88
Lokalizacja: Ostrołęka
Witam!

Mam takie dwa zadanka, które nie wiem jak ruszyć (zresztą ciężko mi przychodzi kombinatoryka), właściwie, one są chyba identyczne.

1) Na ile sposobów można posadzić n par wrogów wokół ogrągłego stołu tak, aby wrogowie nie siedzieli obok siebie?
2) Na ile sposobów można posadzić na ławie n małżeństw, tak, aby żaden mąż nie siedział obok swojej żony?

I jeszcze jedno zadanko, które wydaje mi się być trochę za łatwe:

Na ile sposobów można spermutować ciąg liczb 1,2,3,...,n tak aby, żadna z tych liczb nie pozostała na swoim miejscu?

n! -1?

Ad 1. {n\choose 2}?
Ad 2. {n\choose 2}?
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 22:20 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Wszystko źle!
zadanie pierwsze i drugie na zasadzie włączeń i wyłączeń zadanie trzecie nieporządki!
Zresztą zadania nie są identyczne do końca bo siedzenie na ławie a przy okrągłym stole to ciut co innego!

zad.1

\sum_{i=0}^{n}(-1)^i {n \choose i}(2n-i-1)! \cdot 2^i

W zadaniu drugim będzie tak samo tylko pewnie bez odejmowania jedynki w nawiasie,
Bo przy okrągłym stole wszystko się zmniejsza!

Wzór na nieporządki masz piętro niżej!
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 23:13 
Użytkownik

Posty: 88
Lokalizacja: Ostrołęka
co to jest? O.o

Nie wiem ile bym musiał siedzieć, żeby wpaść na taki wzór. :/ Zresztą i tak nie rozumiem co się z czego wzięło. :P
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 23:16 
Użytkownik

Posty: 1717
Lokalizacja: lubelskie
Ad 1
A jak to zadziała dla dwóch par? (n=2). Np. A i B - jedna para, C i D - druga. Bo ja widzę dwa rozmieszczenia:
1) Po lewej stronie osoby A siedzi C, po prawej D, a naprzeciwko B
2) Po lewej stronie osoby A siedzi D, po prawej C, a naprzeciwko B
I chyba to obejmuje wszystkie możliwości.
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 23:37 
Użytkownik

Posty: 88
Lokalizacja: Ostrołęka
no to dla n=2, są dwie możliwości. dla n=3 jest chyba 12. Ale jak przekształcić takie domysły w wzór podany przez arka, to nie mam pojęcia.
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2015, o 23:44 
Użytkownik

Posty: 1717
Lokalizacja: lubelskie
Nie znam tego wzoru. I po prostu nie wiem czy działa.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2015, o 00:31 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
łatwo sprawdzić działa!


Wybieram i par odrzucam resztę, i mnożę przez dwa do potęgi i ponieważ pary mogą się między sobą permutować (przestawiać)!
I wstawiam na wrór włączeń i wyłączeń proste...


masz dla n=2

wzór:

{2 \choose 0}(4-1)! \cdot 2^0- {2 \choose 1}(4-2)! \cdot 2^1+ {2 \choose 2}(4-3)! \cdot 2^2=2
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2015, o 11:46 
Użytkownik

Posty: 170
Lokalizacja: Kraków
Z=\left\{ 1, 2, 3, ..., n \right\}
A=\left\{ \left( x_{1}, x_{2},x_{3},...,x_{n}\right): x_{i} \in Z-\left\{ i\right\}   \wedge x_{j} \in Z-\left\{ j\right\}   \wedge i,j \in Z  \wedge  (i \neq j \Rightarrow x_{i} \neq x_{j})   \right\}
\# A=(n-1)(n-1)(n-2)(n-3)... \cdot 2 \cdot 1=(n-1)!(n-1)
---
Po chwili namysłu dochodzę do wniosku, że moje rozwiązanie nie jest poprawne.

-- 10 kwi 2015, o 08:39 --

Chyba już doszedłem do rozwiązania trzeciego.
Wykorzystamy schemat Bernoulliego.
Pojedyncza próba polega na przypisaniu do miejsca x_{i} (i \in Z) liczby ze zbioru Z(który podałem w poprzednim poście).
Sulcesem nazwiemy nieprzypisanie liczby i miejscu x_{i}
Liczba prób - n
Prawdopodobieństwo sukcesu (p) - \frac{n-1}{n}
Prawdopodobieństwo porażki (q) - \frac{1}{n}
Żądana liczba sukcesów - n
P(S_{n}=n)={n \choose n} \left(  \frac{n-1}{n}  \right)^{n}  \left(  \frac{1}{n}  \right)^{0}= \left(  \frac{n-1}{n}  \right)^{n}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na ile sposobów możemy rozdzielić prezenty  s147698  4
 Na ile sposobów można rozdzielić......  siQboY  4
 Na ile sposobów można rozmieścić wiersze  mmigi  3
 Na ile sposobów... - zadanie 16  Miralem  3
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl