Kombinatoryka - sposób ustawienia w szeregu

[Inkwizytor]

Wnoszę pod dyskusje moje rozwiązanie:

Ustawień dziewcząt względem siebie jest \(\displaystyle{ 9!}\)
Ustawień chłopców względem siebie jest \(\displaystyle{ 12!}\)

Mamy 4 klasy ciągów:
1) na pozycji pierwszej i ostatniej dziewczyna -> DC............CD
2) na pozycji pierwszej i ostatniej chłopak -> C................C
3) na pozycji pierwszej dziewczyna, na ostatniej chłopak -> DC.............C
4) odwrotnie w stosunku do 3) -> C.................CD

Przypadek 3 i 4 są symetryczne więc wystarczy rozpatrzeć jeden z nich i wynik pomnożyć "razy 2"

Jeśli jako D oznaczymy pozycję dziewczyny, a C ugrupowanie chłopców składające sie z przynajmniej jednego chłopca to klasa pierwsza wygląda tak:
Ad 1)
D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D
Mam 8 pozycji, gdzie chłopaki mogą stać. W każdym miejscu przynajmniej 1, więc mam 4 pozycje chłopięce które mogę rozdysponować w 8 miejsc stąd \(\displaystyle{ 8^4}\) typów kolejek należących do klasy 1
Ad 2)
C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C
Mam 10 pozycji, gdzie chłopaki mogą stać. W każdym miejscu przynajmniej 1, więc mam 2 pozycje chłopięce, które mogę rozdysponować w 10 miejsc stąd \(\displaystyle{ 10^2}\) typów kolejek należących do klasy 2
Ad 3) i 4)
D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C oraz C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D-C-D
Mam 9 pozycji, gdzie chłopaki mogą stać. W każdym miejscu przynajmniej 1, więc mam 3 pozycje chłopięce, które mogę rozdysponować w 9 miejsc stąd \(\displaystyle{ 2 \cdot 9^3}\) typów kolejek należących do klasy 3 lub 4

Zatem wszystkich typów kolejek jest \(\displaystyle{ 8^4 +10^2+2 \cdot 9^3=5654}\)
Końcowe rozwiązanie zatem \(\displaystyle{ 5654 \cdot 9! \cdot 12!}\)

[Konikov]

Inkwizytor, zdaje mi się, że błąd polega na tym, iż liczysz możliwe permutacje, a później, przy przydziale pozostałych miejsc, znów uwzględniasz kolejność, przez co trochę za dużo wychodzi.

Istnieje spore prawdopodobieństwo że się mylę, godzina późna ;]

[mat_61]

Przyjrzałem się temu co napisał Inkwizytor i rozumiem, że jego idea jego rozwiązania jest taka:
- porządkujemy dziewczynki (9!) i chłopców (12!)
- teraz staramy się zgodnie z przyjętymi zasadami upchać chłopców pomiędzy dziewczęta w podanych czterech klasach ciągów.

I teraz rozważmy klasę 1 czyli DCDC...D
Inkwizytor napisał tak:

Mam 8 pozycji, gdzie chłopaki mogą stać. W każdym miejscu przynajmniej 1, więc mam 4 pozycje chłopięce które mogę rozdysponować w 8 miejsc stąd \(\displaystyle{ 8^{4}}\)typów kolejek należących do klasy 1

Ale które to są pozycje, które możemy dowolnie rozmieszczać? Przecież ciąg chłopców jest już uporządkowany i nie możemy go zmieniać.

Dlatego mam wątpliwości co do ilości \(\displaystyle{ 8^{4}}\)typów kolejek. Wg mnie skoro chłopcy są już poszeregowani w ciąg (C1;C2;C2;...;C12) to możemy go tylko rozciąć w 7 dowolnych miejscach po to aby uzyskać 8 co najmniej 1-elementowych "zestawów" do rozmieszczenia w 8 miejscach pomiędzy dziewczynami. Takich możliwych rozcięć (czyli wyboru 7 miejsc rozcięcia spośród 11 możliwych) jest \(\displaystyle{ \frac{11!}{7! \cdot 4!}=330}\)

Analogicznie mamy kolejno:

- dla klasy 2: 9 miejsc rozcięcia spośród 11 możliwych, czyli \(\displaystyle{ \frac{11!}{9! \cdot 2!}=55}\)
- dla klas 3 i 4: 8 miejsc rozcięcia spośród 11 możliwych, czyli \(\displaystyle{ 2 \cdot \frac{11!}{8! \cdot 3!}=330}\)

Razem mamy więc \(\displaystyle{ 330+55+330=715}\) wariantów

Teraz przedstawię swój nowy sposób rozwiązania:

- początek taki jak u Inkwizytora czyli uporządkowanie chłopców i dziewcząt
- teraz zamiast upychać tych chłopców między dziewczęta proponuję zrobić odwrotnie tzn. porozmieszczać pojedyncze dziewczyny (zachowując oczywiście kolejność uporządkowania) obok chłopców co jest znacznie prostsze. Wystarczy wybrać 9 dowolnych miejsc spośród 13 w których mogą stać dziewczęta (zarówno pomiędzy jak i na zewnątrz chłopców). Takich możliwości jest \(\displaystyle{ \frac{13!}{9! \cdot 4!}=715}\)

Jak widać mamy 2 takie same wyniki końcowe:

\(\displaystyle{ 9! \cdot 12! \cdot 715}\)

Jestem ciekaw opinii na temat takiego sposobu rozwiązania.

Oczywiście ten wynik jest różny od wyniku podanego przez Konikova z którym wcześniej się zgodziłem
Postaram się w wolnej chwili jeszcze raz przeanalizować tamto rozwiązanie i zastanowić się dlaczego tak jest.

-- 24 wrz 2010, o 07:28 --

Teraz przyszedł mi do głowy jeszcze prostszy sposób (myślę, że poprawny):

- porządkujemy zbiór chłopców (12!)
- i teraz mamy na 13 dostępnych miejscach (zarówno pomiędzy jak i na zewnątrz chłopców) umieścić w dowolny sposób 9 dziewcząt (czyli typowe wariacje bez powtórzeń)

Daje to rozwiązanie:

\(\displaystyle{ 12! \cdot \frac{13!}{(13-9)!}}\)

Oczywiście ten wynik jest taki sam jak ten powyżej czyli: \(\displaystyle{ 9! \cdot 12! \cdot 715}\)

[Inkwizytor]

mat_61 W pełni się zgadzam z Twoim rozumowaniem. Musze tylko podumać nad tym co nie tak poszło w moim -- 24 wrz 2010, o 10:19 --Znalazłem błędy w moim rozumowaniu Po poprawkach policzyłem moim sposobem i wyszło mi....715 Zatem ten wynik (pomnożony przez \(\displaystyle{ 9! \cdot 12!}\)) jest na pewno odpowiedzią poprawną. Nie będę zamieszczał mego rozwiązania, bo chodzi chyba o przedstawienie najprostszego sposobu a ten zaproponowany przez mat_61 jest zdecydowanie najlepszy.

[mat_61]

Przeanalizowałem też sposób rozwiązania podany przez Konikova.

- uważam, że dwa pierwsze kroki są OK. tzn. uporządkowanie dziewcząt i wybór 8 spośród 12 chłopców do ustawienia pomiędzy dziewczętami
- natomiast nie pasuje mi obliczona jako \(\displaystyle{ 10^{4}}\) ilość możliwości rozmieszczenia 4 pozostałych chłopców (P1;P2;P3;P4) na 10 dostępnych miejscach: M1; M2; ... ; M10.

Wg mnie ten sposób liczenia nie uwzględnia jako różnych tych przypadków gdy chłopcy zostaną "przydzieleni" do tego samego miejsca ale są w nim różnie ustawieni. Jeżeli np. wszystkim chłopcom zostanie przydzielone miejsce M1 (przed pierwszą dziewczyną), to ten przypadek jest policzony tylko jeden raz, ale przecież ci chłopcy mogą być tam ustawieni na 4! sposobów czego taki sposób liczenia nie uwzględnia.

Moim zdaniem żeby policzyć ilość możliwości rozmieszczenia tych 4 chłopców trzeba rozpatrzyć rozmieszczenie wszystkich możliwych podzbiorów utworzonych z elementów {P1:P2;P3;P4}:

1) wszyscy chłopcy są razem:
Mogą wówczas zająć jedno z 10 miejsc i w każdym być uporządkowani na 4! sposobów. Możliwości jest więc:

\(\displaystyle{ 10 \cdot 4!=240}\)

2) podzieleni są na 2 grupy: {dwie osoby} {dwie osoby}. Możliwości podziału na takie grupy są 3, możliwości uporządkowania w każdej grupie po 2, możliwości wyboru miejsc wśród dziewczyn \(\displaystyle{ \frac{10!}{8!}=90.}\) Daje to razem:

\(\displaystyle{ 3 \cdot 2 \cdot 2 \cdot 90=1080}\)

3) podzieleni są na 2 grupy: {jedna osoba} {trzy osoby}. Możliwości podziału na takie grupy są 4, możliwości uporządkowania w grupe 3-osobowej 6, możliwości wyboru miejsc wśród dziewczyn tak jak w punkcie 2) \(\displaystyle{ \frac{10!}{8!}=90.}\) Daje to razem:

\(\displaystyle{ 4 \cdot 6 \cdot 90=2160}\)

4) podzieleni są na 3 grupy: {jedna osoba} {jedna osoba} {dwie osoby}. Możliwości podziału na takie grupy jest 6, możliwości uporządkowania w grupe 2-osobowej 2, możliwości wyboru miejsc wśród dziewczyn \(\displaystyle{ \frac{10!}{7!}=720.}\) Daje to razem:

\(\displaystyle{ 6 \cdot 2 \cdot 720=8640}\)

5) podzieleni są na 4 grupy: {jedna osoba} {jedna osoba} {jedna osoba} {jedna osoba}. Możliwość podziału na takie grupy jest oczywiście 1, możliwości wyboru miejsc wśród dziewczyn \(\displaystyle{ \frac{10!}{6!}=5040.}\) Daje to razem:

\(\displaystyle{ 1 \cdot 5040=5040}\)

Po zsumowaniu tych wszystkich przypadków mamy:

\(\displaystyle{ 240+1080+2160+8640+5040=17160}\)

Co daje ostateczne rozwiązanie:

\(\displaystyle{ 9! \cdot \frac{12!}{4!} \cdot 17160}\)

Ten wynik jest oczywiście zgodny z wynikami uzyskanymi pozostałymi sposobami podanymi przeze mnie poprzednio.

[Konikov]

Teraz przyszedł mi do głowy jeszcze prostszy sposób (myślę, że poprawny):

- porządkujemy zbiór chłopców (12!)
- i teraz mamy na 13 dostępnych miejscach (zarówno pomiędzy jak i na zewnątrz chłopców) umieścić w dowolny sposób 9 dziewcząt (czyli typowe wariacje bez powtórzeń)

Daje to rozwiązanie:

\(\displaystyle{ 12! \cdot \frac{13!}{(13-9)!}}\)

Oczywiście ten wynik jest taki sam jak ten powyżej czyli: \(\displaystyle{ 9! \cdot 12! \cdot 715}\)

Właśnie na to wpadłem już leżąc w łóżku ;]

ale przecież ci chłopcy mogą być tam ustawieni na 4! sposobów czego taki sposób liczenia nie uwzględnia.

Dokładnie ;] Błędem u mnie było rozdzielenie raz ze zbioru w ciąg, a drugi raz z ciągu w ciąg.

Wpadłem jeszcze na coś takiego, że można permutować i chłopców i dziewczyny, a następnie wziąć pierwszych 8 w otrzymanej permutacji i wrzucić między kobiety, a pozostałych dalej rozmieszczać, w kolejności jaka się utworzyła.