kombinatoryka, kolejka

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
prawyakapit
Użytkownik
Użytkownik
Posty: 650
Rejestracja: 9 paź 2011, o 19:18
Płeć: Kobieta
Lokalizacja: łódź
Podziękował: 2 razy

kombinatoryka, kolejka

Post autor: prawyakapit »

18. Na ile sposobów można ustawić n ludzi w kolejce tak, aby ustalone a) dwie, b) trzy osoby nie
stały jedna za drugą (w dowolnym porządku)?

moje rozwiązanie:

Ad.A wydaje mi się , że te dwie osoby mogą zajmować n-2 miejsc, trzeba to pomnożyć przez dwa bo w dowolnej kolejności oraz przez (n-2)! bo na tyle sposobów mogą się ustawić pozostałe osoby zatem:

\(\displaystyle{ (n-2) \cdot 2 \cdot (n-2)!}\)

Ad.B sposób myślenia jest podobny:
\(\displaystyle{ (n-4) \cdot 3! \cdot (n-3)!}\)

czy to jest dobrze ?
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

kombinatoryka, kolejka

Post autor: mat_61 »

Wg mnie nie jest to poprawne rozwiązanie. Jeżeli dwie osoby nie mają stać koło siebie, to jeżeli jedna osoba zajmie miejsce na końcu lub początku kolejki to ta druga może zająć \(\displaystyle{ (n-2)}\) miejsc, ale jeżeli ta osoba zajmie inne miejsce to ta druga może zająć \(\displaystyle{ (n-3)}\) miejsc.

Jest znacznie prostsze rozumowanie. Od wszystkich możliwości ustawień osób w kolejce, czyli \(\displaystyle{ n!}\) odejmiemy te w których wybrane osoby są razem. Proponuję związać te dwie osoby sznurkiem (\(\displaystyle{ 2!}\) możliwości) i teraz mamy do ustawienia w kolejce \(\displaystyle{ (n-1)}\) elementów co możemy zrobić na \(\displaystyle{ (n-1)!}\) sposobów. Wszystkich możliwych ustawień wg punktu a) mamy więc:

\(\displaystyle{ n!-2!(n-1)!}\) sposobów.

Analogicznie możemy zrobić dla dowolnej liczby osób (wiązanie jest w tym przypadku niezawodne )
prawyakapit
Użytkownik
Użytkownik
Posty: 650
Rejestracja: 9 paź 2011, o 19:18
Płeć: Kobieta
Lokalizacja: łódź
Podziękował: 2 razy

kombinatoryka, kolejka

Post autor: prawyakapit »

zastosowałam twoje rozwiązanie dla n=6
wtedy:\(\displaystyle{ 6!-2 \cdot 5!=480}\)

a postępując logicznie powinno być \(\displaystyle{ 4 \cdot 2 \cdot 4!=192}\)
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

kombinatoryka, kolejka

Post autor: mat_61 »

Postępując logicznie są takie możliwości ustawienia osób A i B (na 6 miejsc) zakładając, że A jest po lewej stronie B i nie stoją obok siebie:

AxBxxx
AxxBxx
AxxxBx
AxxxxB
xAxBxx
xAxxBx
xAxxxB
xxAxBx
xxAxxB
xxxAxB

Jak widzisz takich możliwości jest \(\displaystyle{ 10}\). Teraz mnożymy przez \(\displaystyle{ 2}\) (zamiana miejscami A i B, czyli warianty w których B jest po lewej stronie A) no i oczywiście \(\displaystyle{ 4!}\) możliwych ustawień dla x-ów, czyli:

\(\displaystyle{ 10 \cdot 2 \cdot 4!=480}\)

Zgadza się?-- 3 kwi 2012, o 18:27 --Jeżeli chciałabyś koniecznie policzyć bezpośrednio wg Twojej propozycji to mamy tak:

Jeżeli A będzie na którymś z końców (\(\displaystyle{ 2}\) możliwości wyboru) to dla B mamy \(\displaystyle{ 4}\) możliwości wyboru i oczywiście \(\displaystyle{ 4!}\) możliwych ustawień dla pozostałych osób.

Jeżeli A będzie na innym miejscu niż końce (\(\displaystyle{ 4}\) możliwości wyboru) to dla B mamy \(\displaystyle{ 3}\) możliwości wyboru i oczywiście \(\displaystyle{ 4!}\) możliwych ustawień dla pozostałych osób.

Razem będzie:

\(\displaystyle{ 2 \cdot 4 \cdot 4!+4 \cdot 3 \cdot 4!=4 \cdot 4! \cdot (2+3)=20 \cdot 4!=480}\)
prawyakapit
Użytkownik
Użytkownik
Posty: 650
Rejestracja: 9 paź 2011, o 19:18
Płeć: Kobieta
Lokalizacja: łódź
Podziękował: 2 razy

kombinatoryka, kolejka

Post autor: prawyakapit »

Rzeczywiście nie wiem czemu założyłam że osoby A i B ma dzielić tylko jedno miejsce.
ODPOWIEDZ