ustawienie w kolejce

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Downonmyluck
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 25 kwie 2015, o 12:24
Płeć: Mężczyzna
Podziękował: 11 razy
Pomógł: 3 razy

ustawienie w kolejce

Post autor: Downonmyluck »

Na ile sposobów można ustawić w kolejce \(\displaystyle{ k}\) rozróżnialnych kobiet i \(\displaystyle{ m}\) rozróżnialnych mężczyzn przy założeniu, że żadna z kobiet nie może stać obok siebie?

Mam problem z kombinatoryką, bo często nie jestem w stanie uzasadnić, czy czegoś nie policzyłem dwa razy, albo czy jakiś sposób w ogóle nie został wzięty pod uwagę.

Moje kalekie rozumowanie jest takie:

Grupujemy kobiety i mężczyzn w pary. Zauważmy, że mężczyźni mogą stać obok siebie, zatem skonstruujmy ciągi 2-elementowe postaci

\(\displaystyle{ (MK)^{i} (KM)^{k-i}}\), gdzie \(\displaystyle{ i\in \lbrace 0,1,...,k \rbrace}\)

Układ, gdzie będziemy mieć daną ilość powyższych ciągów, możemy wybrać na \(\displaystyle{ k+1}\) sposobów. Teraz powstaje pytanie, czy którykolwiek z układów można ustawić na różne sposoby?
Np. wiadomo, że gdy \(\displaystyle{ i=k, i=0}\), można to ustawić tylko na jeden sposób, wystarczy tylko potem "spermutować" kobiety i mężczyzn, co można uczynić na \(\displaystyle{ k! * m!}\) sposobów.
Wracając do pierwszego pytania w tym akapicie, to chyba nie ma innej możliwości. Jeśli pierwszym wyrazem będzie \(\displaystyle{ MK}\), to następnym nie może być \(\displaystyle{ KM}\), bo kobiety stałyby obok siebie, a więc najpierw musimy "zużyć" ciągi \(\displaystyle{ KM}\), jeśli jakieś mamy, następnie dopiero ustawiać ciągi \(\displaystyle{ MK}\). Zatem wszystkich sposobów będzie \(\displaystyle{ (k+1)*m!*k!}\).

Czy to rozumowanie jest poprawne? Ktoś mógłby podać może inne rozwiązanie, ale z wyjaśnieniem?

Dzięki z góry za pomoc.
mostostalek
Użytkownik
Użytkownik
Posty: 1384
Rejestracja: 26 lis 2006, o 21:34
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 33 razy
Pomógł: 268 razy

ustawienie w kolejce

Post autor: mostostalek »

Nie wziąłeś pod uwagę, że liczba mężczyzn może różnić się od liczby kobiet o więcej niż 1?

Zauważ, że jeśli \(\displaystyle{ m<k-1}\) to nie da się tak ustawić tej zgrai, żeby nam pasowało, bo zawsze jakieś dwie kobiety będą stały obok siebie..

Jeśli \(\displaystyle{ m=k-1}\) to jest dokładnie jeden sposób, żeby ustawić ciąg "mężczyzna", "kobieta" tak, aby "kobieta" nie stała obok "kobieta" i zadanie polega jedynie na permutacji mężczyzn i kobiet między sobą na \(\displaystyle{ k! \cdot m!}\) sposobów.

Jeśli \(\displaystyle{ m>k-1}\) to przypadek jest już znacznie bardziej ciekawy..
Ustawmy kobiety w rzędzie i zużyjmy dokładnie \(\displaystyle{ k-1}\) mężczyzn aby je rozdzielić..
Teraz pozostałą liczbę \(\displaystyle{ m-(k-1)=m-k+1}\) mężczyzn muszę wstawić gdzieś między tych ludzi.. Nie ma dla mnie jednak znaczenia czy wstawię gościa między i-tą kobietę a i-tego mężczyznę czy między i-tego mężczyznę a i+1-szą kobietę bo w obu przypadkach mój ciąg "m" "k" będzie wyglądał tak samo.. Mam więc niejako \(\displaystyle{ k+1}\) pudełek i teraz tych \(\displaystyle{ m-k+1}\) rozrzucam między nie.. Robię to dokładnie na \(\displaystyle{ (k+1)^{m-k+1}}\) sposobów.. Pozostała mi tylko faza permutacji mężczyzn i kobiet między sobą..

Podsumujmy:
\(\displaystyle{ k}\) rozróżnialnych kobiet i \(\displaystyle{ m}\) rozróżnialnych mężczyzn mogę ustawić w ten sposób, aby żadne dwie kobiety nie stały obok siebie na:

0 sposobów jeśli \(\displaystyle{ m<k-1}\)

\(\displaystyle{ (k+1)^{m-k+1} \cdot k! \cdot m!}\) sposobów jeśli \(\displaystyle{ m \ge k-1}\)
Downonmyluck
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 25 kwie 2015, o 12:24
Płeć: Mężczyzna
Podziękował: 11 razy
Pomógł: 3 razy

ustawienie w kolejce

Post autor: Downonmyluck »

Dzięki, zrozumiałem swoje błędne rozumowanie, ale wydaje mi się, że twoje również ma lukę. Sprostuj, jeśli się mylę.

Liczysz ilość funkcji ze zbioru \(\displaystyle{ m-k+1}\)-elementowego w zbiór \(\displaystyle{ k+1}\)-elementowy. Tu kolejność oczywiście nie ma znaczenia, więc musimy spermutować wyrazy należące do tego samego "pudełka", a my permutujemy cały zbiór mężczyzn, czyli np. mamy dwie funkcje, gdzie \(\displaystyle{ f(M) = K, f(M') = K'; g(M') = K, g(M) = K'}\), czyli odpowiednio układy \(\displaystyle{ (MKM'K'...), (M'KMK'...)}\), ale potem to permutujemy, więc policzymy jeden układ dwukrotnie (akurat w tym przypadku dwukrotnie) i otrzymamy policzony więcej niż jeden raz np. pierwszy z tych dwóch powyższych.
mostostalek
Użytkownik
Użytkownik
Posty: 1384
Rejestracja: 26 lis 2006, o 21:34
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 33 razy
Pomógł: 268 razy

ustawienie w kolejce

Post autor: mostostalek »

Oczywiście masz rację.. Mój wzór jest ok jeśli kolejność miałaby znaczenie.. W naszym przypadku nie ma bo później permutujemy zbiory mężczyzn i kobiet.. Należałoby więc zastosować wzór na kombinacje z powtórzeniami i dopiero później permutować..

\(\displaystyle{ {(m-k+1)+(k+1)-1 \choose m-k+1} \cdot k! \cdot m!={m+1 \choose m-k+1} \cdot k! \cdot m!}\)

Tak będzie dobrze?
Majeskas
Użytkownik
Użytkownik
Posty: 1456
Rejestracja: 14 gru 2007, o 14:36
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 49 razy
Pomógł: 198 razy

ustawienie w kolejce

Post autor: Majeskas »

Będzie dobrze, a żeby to uzasadnić, nie trzeba nawet hasła "kombinacje z powtórzeniami". Chcemy ustawić ciąg \(\displaystyle{ k}\) kobiet i \(\displaystyle{ m}\) mężczyzn, zgodny z warunkami zadaniami. Ustawmy jakkolwiek naszą \(\displaystyle{ m}\)-tkę mężczyzn. Następnie rozsuńmy ich, stwarzając \(\displaystyle{ m+1}\) miejsc między nimi i na skrajach, które mogą wybrać kobiety. Pozostaje wybrać kobietom te miejsca i spermutować je. Stąd:

\(\displaystyle{ {m+1\choose k}\cdot m!\cdot k!}\), co oczywiście jest równe wynikowi wyżej.
ODPOWIEDZ