ustawianie ludzi, na ile sposobów

[Sachato]

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?

\(\displaystyle{ n! -1}\)?

Ad 1. \(\displaystyle{ {n\choose 2}}\)?
Ad 2. \(\displaystyle{ {n\choose 2}}\)?

[arek1357]

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

\(\displaystyle{ \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!

[Sachato]

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.

[szachimat]

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.

[Sachato]

no to dla \(\displaystyle{ n=2}\), są dwie możliwości. dla \(\displaystyle{ n=3}\) jest chyba 12. Ale jak przekształcić takie domysły w wzór podany przez arka, to nie mam pojęcia.

[szachimat]

Nie znam tego wzoru. I po prostu nie wiem czy działa.

[arek1357]

ł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 \(\displaystyle{ n=2}\)

wzór:

\(\displaystyle{ {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}\)

[Konradek]

\(\displaystyle{ Z=\left\{ 1, 2, 3, ..., n \right\}}\)
\(\displaystyle{ 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\}}\)
\(\displaystyle{ \# 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 \(\displaystyle{ x_{i}}\) (\(\displaystyle{ i \in Z}\)) liczby ze zbioru \(\displaystyle{ Z}\)(który podałem w poprzednim poście).
Sulcesem nazwiemy nieprzypisanie liczby \(\displaystyle{ i}\) miejscu \(\displaystyle{ x_{i}}\)
Liczba prób - \(\displaystyle{ n}\)
Prawdopodobieństwo sukcesu (\(\displaystyle{ p}\)) - \(\displaystyle{ \frac{n-1}{n}}\)
Prawdopodobieństwo porażki (\(\displaystyle{ q}\)) - \(\displaystyle{ \frac{1}{n}}\)
Żądana liczba sukcesów - \(\displaystyle{ n}\)
\(\displaystyle{ 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}}\)