ustawienie w kolejce
: 4 lip 2016, o 16:37
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.
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.