ustawianie ludzi, na ile sposobów
-
- Użytkownik
- Posty: 92
- Rejestracja: 7 paź 2014, o 18:44
- Płeć: Mężczyzna
- Lokalizacja: Ostrołęka
- Podziękował: 46 razy
ustawianie ludzi, na ile sposobów
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}}\)?
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
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
ustawianie ludzi, na ile sposobów
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!
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!
-
- Użytkownik
- Posty: 92
- Rejestracja: 7 paź 2014, o 18:44
- Płeć: Mężczyzna
- Lokalizacja: Ostrołęka
- Podziękował: 46 razy
ustawianie ludzi, na ile sposobów
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.
Nie wiem ile bym musiał siedzieć, żeby wpaść na taki wzór. :/ Zresztą i tak nie rozumiem co się z czego wzięło.
-
- Użytkownik
- Posty: 1674
- Rejestracja: 23 sty 2015, o 21:47
- Płeć: Mężczyzna
- Lokalizacja: lubelskie
- Podziękował: 6 razy
- Pomógł: 354 razy
ustawianie ludzi, na ile sposobów
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.
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.
-
- Użytkownik
- Posty: 92
- Rejestracja: 7 paź 2014, o 18:44
- Płeć: Mężczyzna
- Lokalizacja: Ostrołęka
- Podziękował: 46 razy
ustawianie ludzi, na ile sposobów
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.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
ustawianie ludzi, na ile sposobów
ł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}\)
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}\)
-
- Użytkownik
- Posty: 163
- Rejestracja: 29 lis 2011, o 20:33
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3 razy
- Pomógł: 20 razy
ustawianie ludzi, na ile sposobów
\(\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}}\)
\(\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}}\)