Polacy, Niemcy i Rosjanie [kombinatoryka]

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Robert2k9
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 9 paź 2013, o 19:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 1 raz

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Robert2k9 »

Witajcie! Zadanie brzmi:

W poczekalni siedzi 3 Polaków, 3 Niemców oraz 3 Rosjan. Na ile sposobów można ich posadzić na 9 krzesłach tak, żeby żadne dwie pary jednej narodowości nie siedziały obok siebie?

Uznałem, że wszystkich możliwych kombinacji usadzeń jest:
\(\displaystyle{ \frac{9!}{3!3!3!}}\)

Natomiast sytuacji, których musimy odrzucić, jest:

\(\displaystyle{ {3 \choose 2} \cdot {9 \choose 4} \cdot \frac{5!}{3!}}\)
Ponieważ z trzech nacji wybieramy dwie, z których bierzemy pary siedzące obok siebie, wybieramy im 4 z 9 miejsc, a resztę ustawiamy na 5! sposobów, co dzielimy przez 3! ponieważ nie odróżniamy członków jednej, pozostałej w pełni nacji.

Wynik ostateczny jest różnicą przytoczonych powyżej wyrażeń.

Czy ktoś mógłby sprawdzić poprawność rozwiązania?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: norwimaj »

Robert2k9 pisze: W poczekalni siedzi 3 Polaków, 3 Niemców oraz 3 Rosjan. Na ile sposobów można ich posadzić na 9 krzesłach tak, żeby żadne dwie pary jednej narodowości nie siedziały obok siebie?
A te krzesła jak są ustawione. W jednym rządku czy w trzech rządkach po trzy krzesła, czy w kółeczku, czy po prostu trzeba uwzględnić wszystkie sposoby?
Robert2k9
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 9 paź 2013, o 19:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 1 raz

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Robert2k9 »

Mamy jeden rządek krzeseł żadnych kółek, dwurzędów ani innych komplikacji.
Awatar użytkownika
Mathix
Użytkownik
Użytkownik
Posty: 357
Rejestracja: 18 mar 2012, o 13:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 9 razy
Pomógł: 73 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Mathix »

Jak wybierasz 4 spośród 9 miejsc to te miejsca nie muszą być koniecznie obok siebie, mogą to być na przykład miejsca pierwsze, trzecie, szóste i ósme.
Robert2k9
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 9 paź 2013, o 19:44
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 1 raz

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Robert2k9 »

A czy ktoś może zasugerować poprawne rozwiązanie tego zadania?
Awatar użytkownika
Mathix
Użytkownik
Użytkownik
Posty: 357
Rejestracja: 18 mar 2012, o 13:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 9 razy
Pomógł: 73 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Mathix »

Nie jestem pewien czy to jest dobrze:
Związujemy ze sobą czterech ludzi. Mamy ciąg postaci \(\displaystyle{ (aabb)acbc}\). Litery to narodowości, to jest ciąg przykładowy. Dla ciągu \(\displaystyle{ (aabb)}\) możemy wybrać \(\displaystyle{ 6}\) miejsc, natomiast \(\displaystyle{ bb}\) i \(\displaystyle{ aa}\) można wybrać spośród \(\displaystyle{ bbb}\) i \(\displaystyle{ aaa}\) i mogą się oni zamieniać miejscami, \(\displaystyle{ a}\) z \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\) z \(\displaystyle{ b}\).
Dodatkowo mamy trzy narodowości. Zatem od wszystkich możliwych ustawień, jest ich \(\displaystyle{ 9!}\) (przecież nawet ludzie tej samej narodowości są inni) należy odjąć:
\(\displaystyle{ 6\cdot(2!)^{2}\cdot{3\choose2}^{3}\cdot4!}\)

Byłbym wdzięczny jakby ktoś skomentował to rozwiązanie.
Ostatnio zmieniony 24 kwie 2014, o 22:11 przez Mathix, łącznie zmieniany 1 raz.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: norwimaj »

Chciałeś chyba napisać \(\displaystyle{ {3\choose2}^{2}}\) zamiast \(\displaystyle{ {3\choose2}^{3}}\).

Nie widzę, gdzie literom przyporządkowujesz narodowości. Można to zrobić na \(\displaystyle{ 3!}\) sposobów.

Wyniki \(\displaystyle{ (aabb)ccabc}\) oraz \(\displaystyle{ cc(aabb)cab}\) są takie same, a liczysz je jako różne.
Awatar użytkownika
Mathix
Użytkownik
Użytkownik
Posty: 357
Rejestracja: 18 mar 2012, o 13:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 9 razy
Pomógł: 73 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Mathix »

Wyniki (aabb)ccabc oraz cc(aabb)cab są takie same, a liczysz je jako różne.
a - Rosjanie
b - Polacy
c - Niemcy

Czemu takie same? Przecież jak posadzimy na ostatnim krzesełku Niemca to nie to samo jak posadzimy Polaka.

A z tym:
Chciałeś chyba napisać \(\displaystyle{ {3\choose2}^{2}}\) zamiast \(\displaystyle{ {3\choose2}^{3}}\).

Nie widzę, gdzie literom przyporządkowujesz narodowości. Można to zrobić na 3! sposobów.
się zgadzam dopiero teraz zauważyłem. Czyli wg ciebie w moim wyniku trzeba zmienić tylko \(\displaystyle{ {3\choose2}}\) na \(\displaystyle{ 3!}\)?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: norwimaj »

Czyli jeśli dobrze rozumiem, to rozwiązanie wygląda teraz następująco: litery są na stałe przyporządkowane poszczególnym narodowościom, na \(\displaystyle{ 3}\) sposoby wybieramy narodowość pierwszej pary (na przykład \(\displaystyle{ a}\)), na \(\displaystyle{ 2}\) sposoby wybieramy narodowość drugiej pary (na przykład \(\displaystyle{ b}\)), wybieramy osoby do pierwszej i drugiej pary na \(\displaystyle{ \binom32^2}\) sposobów, ustalamy kolejność osób w parach na \(\displaystyle{ (2!)^2}\) sposobów, ustalamy miejsce dla wybranych par na \(\displaystyle{ 6}\) sposobów, ustawiamy osoby spoza par na \(\displaystyle{ 5!}\) sposobów (bo jest ich \(\displaystyle{ 5}\), a nie \(\displaystyle{ 4}\)). Razem \(\displaystyle{ 3\cdot2\cdot\binom32^2\cdot(2!)^2\cdot6\cdot5!=(3!)^3\cdot6!}\).

Ale problemem jest to, że wyniki \(\displaystyle{ (aabb)ccabc}\) i \(\displaystyle{ aa(bbcc)abc}\) są takie same, a tym sposobem liczymy je jako różne.
Awatar użytkownika
Mathix
Użytkownik
Użytkownik
Posty: 357
Rejestracja: 18 mar 2012, o 13:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 9 razy
Pomógł: 73 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Mathix »

O to mi chodziło . W taki razie podwójnie będziemy liczyć ciągi, w których występują trzy pary po kolei ludzi tych samych narodowości. Więc od tego co policzyliśmy trzeba odjąć ciągi typu \(\displaystyle{ (aabbcc)abc}\), będzie ich:
\(\displaystyle{ {3\choose2}^{3}\cdot(2!)^{3}\cdot(3!)^{2}}\)
Bo do ciągu \(\displaystyle{ (aabbcc)}\) wybieramy trzy razy po dwie liczby z trzech, możemy je zamienić miejscami, narodowości możemy zmieniać miejscami i te liczby co są poza ciągiem trzeba spermutować.
Teraz będzie w porządku
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: norwimaj »

Jeszcze trzeba pomnożyć przez \(\displaystyle{ 4}\), bo grupa trzech par nie musi być na początku.

Ale to jeszcze nie koniec. Również dwukrotnie zostały policzone ustawienia typu \(\displaystyle{ (aabb)bccac=aab(bbcc)ac}\).
Awatar użytkownika
Mathix
Użytkownik
Użytkownik
Posty: 357
Rejestracja: 18 mar 2012, o 13:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 9 razy
Pomógł: 73 razy

Polacy, Niemcy i Rosjanie [kombinatoryka]

Post autor: Mathix »

Nie da się tego zadania rozwiązać bardziej trywialnie? Czy trzeba robić wszystko tak jak tu wyżej pisaliśmy? Może ma ktoś pomysł na jakieś prostsze rozwiązanie, bo ten sposób wymaga dużo liczenia i łatwo w nim o pomyłkę ze względu na dużą liczbę obliczeń, a także i błąd logiczny.
ODPOWIEDZ