Wszystkie kombinacje miejsc z wyłączeniem miejsc początkowych

Question

Witam, czy mógłby ktoś mi wytłumaczyć jak zrobić takie zadanie?

Cztery osoby siedzą na ławce. W pewnym momencie wstają z ławki, zaś po jakimś czasie siadają ponownie. Na ile sposobów mogą usiąść tak, aby żadna z nich nie usiadła na miejscu poprzednio zajmowanym.

Coś ktoś pisał o zasadzie włączeń i wyłączeń, ale nie ma na to logicznego prostszego sposobu?

Comments

Trochę dziwne to zadanie, jakby ułożyła je jakaś niedojda matematyczna. To nie mogą siąść tylko na miejscach początkowych, czy w ogóle nie mogą siąść na miejscach, które już wcześniej zajmowali?

---

na początkowym, bo raz siadają

---

Zadanie jest czytelne. Mamy ustalone miejsca na ławce(zakładam, że więcej jak 4 osoby nie usiądą), które zajmują cztery osoby. Potem wstają, ale po jakimś czasie znowu siadają. Teraz chodzi o to, że żaden nie może usiąść na miejscu, na którym siedział wcześniej.

mvxxx Jeśli chodzi o zasadą włączeń i wyłączeń, to chyba nie ma tutaj zastosowania(jeśli jest, chętnie zobaczę).

Spróbuj w ten sposób: narysuj sobie schemat, ławkę na której umieszczasz w 4 miejscach 4 osoby - oznacz sobie np. tak: A, B, C, D. Potem zobacz, na ile sposobów możesz ponownie posadzić pierwszą z nich(może ona zająć 3 miejsca, to wiadomo). Jak posadzisz osobę A, na miejscu, które poprzednio zajmowała osoba B, to na ile sposobów możesz posadzić teraz osobę B? A pozostałe? Jak zrobisz, to spróbuj może z 5 osobami?

Answer 1

Coś ktoś pisał o zasadzie włączeń i wyłączeń, ale nie ma na to logicznego prostszego sposobu?

Według mnie jest, choć z zasady włączeń i wyłączeń też się podobno da. Najprostszy sposób polega na wypisaniu sobie wszystkich możliwości, ponieważ n=4 to nie jest jakiś skomplikowany przypadek. Spróbujmy jednak choć częściowo wyprowadzić wzór, zakładając że początkowo osoby siedzą w porządku ABCD:

A B C D # początkowy porządek
-------
A . . . # ten przypadek odrzucamy,
.       # bo A jest na 1. pozycji
.
.
A . . .


B A D C # przesuwamy A w prawo i wypisujemy
C A D B # wszystkie dopuszczalne kombinacje
D A B C
.
.
. . . .

B D A C # przesuwamy A w prawo i wypisujemy
C D A B # wszystkie dopuszczalne kombinacje
D C A B
.
.
. . . .

B C D A # przesuwamy A na ostatnią pozycję,
C D B A # wypisujemy wszystkie dopuszczalne
D C B A # kombinacje
.
.
. . . .

Gdybyśmy nie ograniczali w żaden sposób porządku, to wszystkich możliwych przypadków byłoby 4!  = 24. Z powyższej tabelki widzimy, że A na pierwszej pozycji odejmuje nam aż 6 przypadków, czyli rozważając TYLKO pierwszą warstwę mielibyśmy:

3 x 3!
(n-1) x (n-1)!

sposobów. Jednak widzimy, że w każdym bloku nie mamy po 6 = 3! kombinacji, tylko po 3, co daje nam całościowy wynik równy 9. Jak sobie z tym poradzić? Oznaczmy liczbę ciągów dla danego n przez S(n). Musimy policzyć S(4). Pierwszy poziom już rozważyliśmy, mamy więc:

S(4) = (4-1)*lvl2

Sednem sprawy jest wytypowanie liczby lvl2, odpowiadającej za drugi poziom.

1. Załóżmy, że A zajmuje pozycję B. Wtedy pozostałe trzy elementy mogą zająć trzy pozycje. Nie będzie to jednak permutacja z 3 elementów (3!), bo część elementów zajęłaby poprzednie miejsca. Na przykład D ponownie zajęłoby tę samą pozycję. Jest to więc ponownie problem taki sam jak w przypadku pierwszego poziomu, przy czym rozważamy już poziom drugi. Przyczynek do lvl2 będzie więc zawierał S(3) = S(n-1).
2. Drugi przypadek to taki, że A zajmuje pozycję inną niż B, a to oznacza że B nie może zająć pozycji zajętej przez A oraz dodatkowo swojej pierwotnej B. Liczba elementów (wolnych parametrów) zmniejsza się więc o 2, toteż musimy policzyć S(2) = S(n-2).

Ponieważ mamy dwa przypadki, to lvl2 będzie składał się z sumy:

S(n) = (n-1)[S(n-1) + S(n-2)]

I jest to wzór rekurencyjny. W rzeczywistości funkcję S(n) nazywamy nieporządkiem i oznaczamy symbolem !n. Więcej można przeczytać na Wikipedii.