Zliczanie rozkładów grupy 9-osobowej
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Dana jest grupa złożona z \(\displaystyle{ 3}\) Chińczyków, \(\displaystyle{ 3}\) Polaków i \(\displaystyle{ 3}\) Rosjan. Na ile sposobów można ustawić te osoby tak, żeby nikt nie miał za sąsiada swojego rodaka?
Próbowałem "od tyłu", licząc wszystkie ustawienia, w których trafią się obok siebie krajanie, ale wyszło dużo skomplikowanych przypadków i kilkakrotne użycie zasady włączeń i wyłączeń. Zresztą nie wiem, jak sobie poradzić ze zliczaniem cząstkowym w niektórych miejscach. Można jakoś prościej?
Próbowałem "od tyłu", licząc wszystkie ustawienia, w których trafią się obok siebie krajanie, ale wyszło dużo skomplikowanych przypadków i kilkakrotne użycie zasady włączeń i wyłączeń. Zresztą nie wiem, jak sobie poradzić ze zliczaniem cząstkowym w niektórych miejscach. Można jakoś prościej?
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Można ustawiać w szeregu, w kółeczku, albo w jakiś bardziej wymyślny sposób. Czy chcesz zliczać to wszystko?
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Tak przypuszczałem, ale wolałem się upewnić.
Jeśli chcesz to zliczać ręcznie, to można się ograniczyć do ustawień z ustalonymi pierwszymi dwiema osobami, a na końcu wynik pomnożyć przez \(\displaystyle{ 6.}\) Możliwości nie jest bardzo dużo, ale i tak ręczna metoda nie jest szczególnie zachęcająca. Jeszcze pomyślę nad tym.
Jeśli chcesz to zliczać ręcznie, to można się ograniczyć do ustawień z ustalonymi pierwszymi dwiema osobami, a na końcu wynik pomnożyć przez \(\displaystyle{ 6.}\) Możliwości nie jest bardzo dużo, ale i tak ręczna metoda nie jest szczególnie zachęcająca. Jeszcze pomyślę nad tym.
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Nie wiem, co masz na myśli, pisząc: "jeśli chcesz to zliczać ręcznie". Chcę to po prostu zliczyć. Oczywiście im szybszą metodą, tym lepiej. Nie mam innego pomysłu na rozwiązanie niż taki:
Niech \(\displaystyle{ S}\) oznacza zbiór wszystkich możliwych ustawień tych ludzi, \(\displaystyle{ P}\) to te ustawienia, w których znajdzie się koło siebie dwóch Polaków, \(\displaystyle{ R}\) - Rosjan, \(\displaystyle{ C}\) - Chińczyków.
Wówczas \(\displaystyle{ |S|=9!}\) i szukamy \(\displaystyle{ |S\setminus(P\cup R\cup C)|=|S|-|P\cup R\cup C|}\). Do znalezienia \(\displaystyle{ |P\cup R\cup C|}\) zastosujemy zasadę włączeń i wyłączeń.
Zacznijmy od znalezienia \(\displaystyle{ |P|}\). Ustawienia, w których znajdzie się obok siebie dwóch Polaków, możemy rozdzielić na takie, w których stoją obok siebie wszyscy trzej, i takie, w których stoi obok siebie dokładnie dwóch. W pierwszym przypadku wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 7}\) miejsc dla tej trójki, następnie permutujemy ją oraz permutujemy pozostałą szóstkę. W drugim wypadku ustalmy najpierw ustawienie nie-Polaków. Między nimi i na skrajach mamy \(\displaystyle{ 7}\) miejsc, które możemy zaproponować dwójce Polaków. Po usadzeniu tej dwójki mamy \(\displaystyle{ 6}\) miejsc dla pojedynczego Polaka. Pozostaje spermutować Polaków na wybranych dla nich miejscach i spermutować pozostałych. Stąd
\(\displaystyle{ |P|=7\cdot3!\cdot6!+7\cdot6\cdot3!\cdot6!=7!\cdot42}\)
Obliczamy \(\displaystyle{ |P\cap R|}\). Możemy tutaj rozróżnić następujące przypadki:
1) obie nacje wystąpią trójkami;
2) jedna nacja wystąpi trójką, druga dwójką i pojedynczo;
3) obie nacje wystąpią w dwójce i pojedynczo.
W każdym z tych przypadków ważny jest odpowiedni wybór miejsc dla poszczególnych narodowości, natomiast niezależnie od konfiguracji trzeba będzie spermutować każdą z tych trójek ludzi. Dlatego dla wygody wystarczy liczyć jedynie sposoby wyboru miejsc, a sumę pomnożyć na końcu przez \(\displaystyle{ (3!)^3}\).
1) Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 5}\) miejsc dla trójki Polaków, następnie \(\displaystyle{ 1}\) z \(\displaystyle{ 4}\) dla trójki Rosjan.
2) Wybieramy na \(\displaystyle{ 2}\) sposoby, która nacja ma wystąpić w trójce. Mamy \(\displaystyle{ 4}\) możliwości ustawienia tej trójki z trzema Chińczykami. W tym momencie w rzędzie znajduje się \(\displaystyle{ 6}\) miejsc dla dwójki Polaków, a w kolejnym kroku \(\displaystyle{ 5}\) miejsc dla pojedynczego.
3) Niech \(\displaystyle{ X}\) oznacza dwójkę lub pojedynczą osobę z jednej nacji, \(\displaystyle{ Y}\) z drugiej. Mamy trzy podprzypadki rozmieszczenia iksów i igreków, zanim dołożymy do rzędu Chińczyków.
a) \(\displaystyle{ XXYY}\)
b) \(\displaystyle{ XYYX}\)
c) \(\displaystyle{ XYXY}\)
W każdym z podprzypadków możemy wybrać na \(\displaystyle{ 2}\) sposoby, która nacja jest iksem, na \(\displaystyle{ 2}\) sposoby, który iks oznacza dwójkę ludzi, na \(\displaystyle{ 2}\), który igrek oznacza dwójkę.
a) Należy rozdzielić stojące obok siebie iksy i igreki. Zatem wstawiamy po jednym Chińczyku między iksy i między igreki. Trzeci ma do dyspozycji \(\displaystyle{ 5}\) miejsc.
b) Iksy są rozdzielone, więc jeden Chińczyk musi rozdzielić igreki, a pozostali dwaj mają do wyboru dowolne \(\displaystyle{ 2}\) miejsca z \(\displaystyle{ 6}\).
c) Wszyscy są rozdzieleni, więc wybieramy dla Chińczyków dowolne \(\displaystyle{ 3}\) miejsca z \(\displaystyle{ 7}\).
\(\displaystyle{ |P\cap R|=(3!)^3\left(5\cdot4+2\cdot4\cdot6\cdot5+2^3\left( 5+ {6 \choose 2}+{7\choose3} \right)\right)=6^3\cdot676}\)
Obliczamy \(\displaystyle{ |P\cap R\cap C|}\). Przypadki:
1) wszystkie trzy nacje w trójkach;
2) dwie nacje w trójce, trzecia w dwójce i pojedynczo
3) jedna nacja w trójce, pozostałe w dwójkach i pojedynczo
4) wszystkie nacje w dwójce i pojedynczo
1) Ustalamy na \(\displaystyle{ 3!}\) sposobów kolejność trójek.
2) Wybieramy na \(\displaystyle{ 3}\) sposoby, która nacja ma być rozdzielona. Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 3}\) miejsc dla dwójki, \(\displaystyle{ 1}\) z \(\displaystyle{ 2}\) dla pojedynczej osoby. Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 2}\) kolejności dla trójek.
3) Niech \(\displaystyle{ Z}\) oznacza trójkę. Na podstawie wcześniejszych rozważań wiemy, że taki układ może być albo postaci \(\displaystyle{ XYZYX}\) albo \(\displaystyle{ XYXY}\) z trójką \(\displaystyle{ Z}\) dołączoną w dowolne z \(\displaystyle{ 5}\) miejsc. Mamy zatem \(\displaystyle{ 3!}\) sposobów przypisania literom nacji, \(\displaystyle{ 2}\) na zdecydowanie, który iks jest dwójką, \(\displaystyle{ 2}\) na to, który igrek jest dwójką, i łącznie \(\displaystyle{ 6}\) możliwości dołączenia trójki \(\displaystyle{ Z}\).
4) Przyjmijmy oznaczenia: \(\displaystyle{ p}\) - dwójka Polaków lub jeden Polak, \(\displaystyle{ r}\) - dwójka Rosjan lub jeden Rosjanin, \(\displaystyle{ c}\) - dwójka Chińczyków lub jeden Chińczyk. Wówczas szukane przypadki można sprowadzić do pytania o to, ile jest słów powstałych z liter \(\displaystyle{ p,p,r,r,c,c}\), w których żadne dwie litery nie stoją obok siebie. Odejmę od wszystkich możliwych słów te, w których jakiekolwiek dwie litery się powtarzają. Skorzystam w tym celu z gotowego wzoru na liczbę permutacji z powtórzeniami i zasady włączeń wyłączeń. Szczegóły pominę, prezentując same rachunki.
\(\displaystyle{ \frac{6!}{2^3}-3\cdot5\cdot\frac{4!}{2^2}+3\cdot4\cdot3-3!=30}\)
Pozostaje teraz zdecydować na \(\displaystyle{ 2^3}\) sposobów, która litera oznacza w danym ustawieniu dwójkę Polaków, dwójkę Rosjan i dwójkę Chińczyków.
\(\displaystyle{ |P\cap R\cap C|=(3!)^3\left(3!+3^2\cdot2^2+3!\cdot2^2\cdot6+2^3\cdot30\right)=6^3\cdot426}\)
Ostatecznie
\(\displaystyle{ |S|-|P\cup R\cup C|=9!-3\cdot7!\cdot42+3\cdot6^3\cdot676-6^3\cdot426=73872}\)
Rozwiązanie jest długie i niezachęcające. Nie potrafię wymyślić krótszego, ponieważ nie umiem obejść jednego problemu, który odpowiada za to zamieszanie i który było widać już przy obliczaniu \(\displaystyle{ |P|}\), a złożoność obliczeń w kolejnych krokach była właśnie jego następstwem.
Kiedy np. liczymy sytuacje, w których trafi się obok siebie dwóch Polaków, to musimy wziąć pod uwagę zarówno dwóch, jak i trzech. Gdybyśmy zaczęli liczyć to w taki sposób, że ustawiamy dwóch, bo tyle nam do szczęścia wystarczy, a resztą się nie przejmujemy, wtedy ustawienia z trójką Polaków policzylibyśmy kilkakrotnie. I o ile w tym wypadku dałoby się to jakoś skontrolować, tzn. stwierdzić, ile razy za dużo wystąpiła każda z trójek i odjąć to od liczby wszystkich możliwych dwójek, to kiedy rozważamy już wystąpienia choćby dwóch nacji, sytuacja staje się dla mnie zbyt skomplikowana, żeby można ją było w ten sposób skontrolować. Dlatego nie widzę innej możliwości niż takie babranie się w przypadkach i bardzo jestem ciekaw, czy da się to zrobić mądrzej.
Niech \(\displaystyle{ S}\) oznacza zbiór wszystkich możliwych ustawień tych ludzi, \(\displaystyle{ P}\) to te ustawienia, w których znajdzie się koło siebie dwóch Polaków, \(\displaystyle{ R}\) - Rosjan, \(\displaystyle{ C}\) - Chińczyków.
Wówczas \(\displaystyle{ |S|=9!}\) i szukamy \(\displaystyle{ |S\setminus(P\cup R\cup C)|=|S|-|P\cup R\cup C|}\). Do znalezienia \(\displaystyle{ |P\cup R\cup C|}\) zastosujemy zasadę włączeń i wyłączeń.
Zacznijmy od znalezienia \(\displaystyle{ |P|}\). Ustawienia, w których znajdzie się obok siebie dwóch Polaków, możemy rozdzielić na takie, w których stoją obok siebie wszyscy trzej, i takie, w których stoi obok siebie dokładnie dwóch. W pierwszym przypadku wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 7}\) miejsc dla tej trójki, następnie permutujemy ją oraz permutujemy pozostałą szóstkę. W drugim wypadku ustalmy najpierw ustawienie nie-Polaków. Między nimi i na skrajach mamy \(\displaystyle{ 7}\) miejsc, które możemy zaproponować dwójce Polaków. Po usadzeniu tej dwójki mamy \(\displaystyle{ 6}\) miejsc dla pojedynczego Polaka. Pozostaje spermutować Polaków na wybranych dla nich miejscach i spermutować pozostałych. Stąd
\(\displaystyle{ |P|=7\cdot3!\cdot6!+7\cdot6\cdot3!\cdot6!=7!\cdot42}\)
Obliczamy \(\displaystyle{ |P\cap R|}\). Możemy tutaj rozróżnić następujące przypadki:
1) obie nacje wystąpią trójkami;
2) jedna nacja wystąpi trójką, druga dwójką i pojedynczo;
3) obie nacje wystąpią w dwójce i pojedynczo.
W każdym z tych przypadków ważny jest odpowiedni wybór miejsc dla poszczególnych narodowości, natomiast niezależnie od konfiguracji trzeba będzie spermutować każdą z tych trójek ludzi. Dlatego dla wygody wystarczy liczyć jedynie sposoby wyboru miejsc, a sumę pomnożyć na końcu przez \(\displaystyle{ (3!)^3}\).
1) Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 5}\) miejsc dla trójki Polaków, następnie \(\displaystyle{ 1}\) z \(\displaystyle{ 4}\) dla trójki Rosjan.
2) Wybieramy na \(\displaystyle{ 2}\) sposoby, która nacja ma wystąpić w trójce. Mamy \(\displaystyle{ 4}\) możliwości ustawienia tej trójki z trzema Chińczykami. W tym momencie w rzędzie znajduje się \(\displaystyle{ 6}\) miejsc dla dwójki Polaków, a w kolejnym kroku \(\displaystyle{ 5}\) miejsc dla pojedynczego.
3) Niech \(\displaystyle{ X}\) oznacza dwójkę lub pojedynczą osobę z jednej nacji, \(\displaystyle{ Y}\) z drugiej. Mamy trzy podprzypadki rozmieszczenia iksów i igreków, zanim dołożymy do rzędu Chińczyków.
a) \(\displaystyle{ XXYY}\)
b) \(\displaystyle{ XYYX}\)
c) \(\displaystyle{ XYXY}\)
W każdym z podprzypadków możemy wybrać na \(\displaystyle{ 2}\) sposoby, która nacja jest iksem, na \(\displaystyle{ 2}\) sposoby, który iks oznacza dwójkę ludzi, na \(\displaystyle{ 2}\), który igrek oznacza dwójkę.
a) Należy rozdzielić stojące obok siebie iksy i igreki. Zatem wstawiamy po jednym Chińczyku między iksy i między igreki. Trzeci ma do dyspozycji \(\displaystyle{ 5}\) miejsc.
b) Iksy są rozdzielone, więc jeden Chińczyk musi rozdzielić igreki, a pozostali dwaj mają do wyboru dowolne \(\displaystyle{ 2}\) miejsca z \(\displaystyle{ 6}\).
c) Wszyscy są rozdzieleni, więc wybieramy dla Chińczyków dowolne \(\displaystyle{ 3}\) miejsca z \(\displaystyle{ 7}\).
\(\displaystyle{ |P\cap R|=(3!)^3\left(5\cdot4+2\cdot4\cdot6\cdot5+2^3\left( 5+ {6 \choose 2}+{7\choose3} \right)\right)=6^3\cdot676}\)
Obliczamy \(\displaystyle{ |P\cap R\cap C|}\). Przypadki:
1) wszystkie trzy nacje w trójkach;
2) dwie nacje w trójce, trzecia w dwójce i pojedynczo
3) jedna nacja w trójce, pozostałe w dwójkach i pojedynczo
4) wszystkie nacje w dwójce i pojedynczo
1) Ustalamy na \(\displaystyle{ 3!}\) sposobów kolejność trójek.
2) Wybieramy na \(\displaystyle{ 3}\) sposoby, która nacja ma być rozdzielona. Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 3}\) miejsc dla dwójki, \(\displaystyle{ 1}\) z \(\displaystyle{ 2}\) dla pojedynczej osoby. Wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 2}\) kolejności dla trójek.
3) Niech \(\displaystyle{ Z}\) oznacza trójkę. Na podstawie wcześniejszych rozważań wiemy, że taki układ może być albo postaci \(\displaystyle{ XYZYX}\) albo \(\displaystyle{ XYXY}\) z trójką \(\displaystyle{ Z}\) dołączoną w dowolne z \(\displaystyle{ 5}\) miejsc. Mamy zatem \(\displaystyle{ 3!}\) sposobów przypisania literom nacji, \(\displaystyle{ 2}\) na zdecydowanie, który iks jest dwójką, \(\displaystyle{ 2}\) na to, który igrek jest dwójką, i łącznie \(\displaystyle{ 6}\) możliwości dołączenia trójki \(\displaystyle{ Z}\).
4) Przyjmijmy oznaczenia: \(\displaystyle{ p}\) - dwójka Polaków lub jeden Polak, \(\displaystyle{ r}\) - dwójka Rosjan lub jeden Rosjanin, \(\displaystyle{ c}\) - dwójka Chińczyków lub jeden Chińczyk. Wówczas szukane przypadki można sprowadzić do pytania o to, ile jest słów powstałych z liter \(\displaystyle{ p,p,r,r,c,c}\), w których żadne dwie litery nie stoją obok siebie. Odejmę od wszystkich możliwych słów te, w których jakiekolwiek dwie litery się powtarzają. Skorzystam w tym celu z gotowego wzoru na liczbę permutacji z powtórzeniami i zasady włączeń wyłączeń. Szczegóły pominę, prezentując same rachunki.
\(\displaystyle{ \frac{6!}{2^3}-3\cdot5\cdot\frac{4!}{2^2}+3\cdot4\cdot3-3!=30}\)
Pozostaje teraz zdecydować na \(\displaystyle{ 2^3}\) sposobów, która litera oznacza w danym ustawieniu dwójkę Polaków, dwójkę Rosjan i dwójkę Chińczyków.
\(\displaystyle{ |P\cap R\cap C|=(3!)^3\left(3!+3^2\cdot2^2+3!\cdot2^2\cdot6+2^3\cdot30\right)=6^3\cdot426}\)
Ostatecznie
\(\displaystyle{ |S|-|P\cup R\cup C|=9!-3\cdot7!\cdot42+3\cdot6^3\cdot676-6^3\cdot426=73872}\)
Rozwiązanie jest długie i niezachęcające. Nie potrafię wymyślić krótszego, ponieważ nie umiem obejść jednego problemu, który odpowiada za to zamieszanie i który było widać już przy obliczaniu \(\displaystyle{ |P|}\), a złożoność obliczeń w kolejnych krokach była właśnie jego następstwem.
Kiedy np. liczymy sytuacje, w których trafi się obok siebie dwóch Polaków, to musimy wziąć pod uwagę zarówno dwóch, jak i trzech. Gdybyśmy zaczęli liczyć to w taki sposób, że ustawiamy dwóch, bo tyle nam do szczęścia wystarczy, a resztą się nie przejmujemy, wtedy ustawienia z trójką Polaków policzylibyśmy kilkakrotnie. I o ile w tym wypadku dałoby się to jakoś skontrolować, tzn. stwierdzić, ile razy za dużo wystąpiła każda z trójek i odjąć to od liczby wszystkich możliwych dwójek, to kiedy rozważamy już wystąpienia choćby dwóch nacji, sytuacja staje się dla mnie zbyt skomplikowana, żeby można ją było w ten sposób skontrolować. Dlatego nie widzę innej możliwości niż takie babranie się w przypadkach i bardzo jestem ciekaw, czy da się to zrobić mądrzej.
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Chodziło mi o coś takiego:
\(\displaystyle{ PRPRCPCRC\\
PRPRCRCPC\\
PRPCPRCRC\\
PRPCPCRCR\\
PRPCRPCRC\\
PRPCRCPRC\\
PRPCRCPCR\\
PRPCRCRPC\\
PRPCRCRCP\\
PRCPRPCRC\\
PRCPRCPRC\\
PRCPRCPCR\\
PRCPRCRPC\\
PRCPRCRCP\\
PRCPCPRCR\\
PRCPCRPRC\\
PRCPCRPCR\\
PRCPCRCPR\\
PRCPCRCRP\\
PRCRPRCPC\\
PRCRPCPRC\\
PRCRPCPCR\\
PRCRPCRPC\\
PRCRPCRCP\\
PRCRCPRPC\\
PRCRCPRCP\\
PRCRCPCPR\\
PRCRCPCRP\\
PRCRCRPCP.}\)
Następnie mnożymy wynik (\(\displaystyle{ 29}\)) przez \(\displaystyle{ 6}\) (o czym wcześniej pisałem) i przez \(\displaystyle{ (3!)^3}\) (o czym poprzednio zapomniałem).
\(\displaystyle{ PRPRCPCRC\\
PRPRCRCPC\\
PRPCPRCRC\\
PRPCPCRCR\\
PRPCRPCRC\\
PRPCRCPRC\\
PRPCRCPCR\\
PRPCRCRPC\\
PRPCRCRCP\\
PRCPRPCRC\\
PRCPRCPRC\\
PRCPRCPCR\\
PRCPRCRPC\\
PRCPRCRCP\\
PRCPCPRCR\\
PRCPCRPRC\\
PRCPCRPCR\\
PRCPCRCPR\\
PRCPCRCRP\\
PRCRPRCPC\\
PRCRPCPRC\\
PRCRPCPCR\\
PRCRPCRPC\\
PRCRPCRCP\\
PRCRCPRPC\\
PRCRCPRCP\\
PRCRCPCPR\\
PRCRCPCRP\\
PRCRCRPCP.}\)
Następnie mnożymy wynik (\(\displaystyle{ 29}\)) przez \(\displaystyle{ 6}\) (o czym wcześniej pisałem) i przez \(\displaystyle{ (3!)^3}\) (o czym poprzednio zapomniałem).
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Majeskas pisze:wybieramy \(\displaystyle{ 1}\) z \(\displaystyle{ 7}\) miejsc dla tej trójki, następnie permutujemy ją oraz permutujemy pozostałą szóstkę. W drugim wypadku ustalmy najpierw ustawienie nie-Polaków. Między nimi i na skrajach mamy \(\displaystyle{ 7}\) miejsc, które możemy zaproponować dwójce Polaków. Po usadzeniu tej dwójki mamy \(\displaystyle{ 6}\) miejsc dla pojedynczego Polaka. Pozostaje spermutować Polaków na wybranych dla nich miejscach i spermutować pozostałych
W każdym z tych przypadków ważny jest odpowiedni wybór miejsc dla poszczególnych narodowości, natomiast niezależnie od konfiguracji trzeba będzie spermutować każdą z tych trójek ludzi. Dlatego dla wygody wystarczy liczyć jedynie sposoby wyboru miejsc, a sumę pomnożyć na końcu przez \(\displaystyle{ (3!)^3}\).
norwimaj pisze: Następnie mnożymy wynik (\(\displaystyle{ 29}\)) przez \(\displaystyle{ 6}\) (o czym wcześniej pisałem) i przez \(\displaystyle{ (3!)^3}\) (o czym poprzednio zapomniałem).
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Zliczanie rozkładów grupy 9-osobowej
Ja to tak widzę:
\(\displaystyle{ 3 \cdot {3 \choose 2} \cdot (2!)^1 \cdot 8!-3 \cdot {3 \choose 2} \cdot {3 \choose 2}(2!)^2 \cdot 7!+{3 \choose 2} \cdot {3 \choose 2}\cdot {3 \choose 2} \cdot (2!)^3 \cdot 6!}\)
Najpierw wybieramy tylko jedną parę z trzech narodowości możliwości jest trzy po dwa, w każdej grupe narodowości, mnożymy przez trzy bo jedną parę można wybrać z trzech narodowości!
potem wybieramy już dwie pary na trzy możliwości(zawsze z dwcóh narodowości) i permutujemy,
na końcu wybieramy aż trzy pary z trzech narodowości i też permutujemy!
W rozpisce Norwimaja przestawienie np dwóch Chińczyków nie zmienia sytuacji a ja uważam, że powinno być:
\(\displaystyle{ p1,p2,p3,r1,r2,r3,c1,c2,c3}\)
a nie:
\(\displaystyle{ p,p,p,r,r,r,c,c,c}\)
w tym ostatnim pomyśle różnice by były między:
\(\displaystyle{ p,p,r,p,r,r,c,c,c}\)
a:
\(\displaystyle{ p,r,p,p,r,r,c,c,c}\)
Sytuacja by się bardziej skomplikowała bo np para polaków i jeden polak to np dla rosjan dwa różne obiektu a dla polaków między sobą takie same!-- 15 lutego 2015, 15:54 --Jeżeli nie rozróżniamy ludzi jednej narodowości to wtedy wynik wychodzi:
\(\displaystyle{ 107}\)
\(\displaystyle{ 3 \cdot {3 \choose 2} \cdot (2!)^1 \cdot 8!-3 \cdot {3 \choose 2} \cdot {3 \choose 2}(2!)^2 \cdot 7!+{3 \choose 2} \cdot {3 \choose 2}\cdot {3 \choose 2} \cdot (2!)^3 \cdot 6!}\)
Najpierw wybieramy tylko jedną parę z trzech narodowości możliwości jest trzy po dwa, w każdej grupe narodowości, mnożymy przez trzy bo jedną parę można wybrać z trzech narodowości!
potem wybieramy już dwie pary na trzy możliwości(zawsze z dwcóh narodowości) i permutujemy,
na końcu wybieramy aż trzy pary z trzech narodowości i też permutujemy!
W rozpisce Norwimaja przestawienie np dwóch Chińczyków nie zmienia sytuacji a ja uważam, że powinno być:
\(\displaystyle{ p1,p2,p3,r1,r2,r3,c1,c2,c3}\)
a nie:
\(\displaystyle{ p,p,p,r,r,r,c,c,c}\)
w tym ostatnim pomyśle różnice by były między:
\(\displaystyle{ p,p,r,p,r,r,c,c,c}\)
a:
\(\displaystyle{ p,r,p,p,r,r,c,c,c}\)
Sytuacja by się bardziej skomplikowała bo np para polaków i jeden polak to np dla rosjan dwa różne obiektu a dla polaków między sobą takie same!-- 15 lutego 2015, 15:54 --Jeżeli nie rozróżniamy ludzi jednej narodowości to wtedy wynik wychodzi:
\(\displaystyle{ 107}\)
-
- 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
Zliczanie rozkładów grupy 9-osobowej
Zrozumiałem z tego tylko tyle (czego też nie jestem pewien), że podobnie jak ja, zliczasz wszystkie te ustawienia, w których pewna para tej samej narodowości wystąpi koło siebie. Ale nie wiem, co te skrótowe opisy mają wspólnego z problemem.arek1357 pisze:Ja to tak widzę:
\(\displaystyle{ 3 \cdot {3 \choose 2} \cdot (2!)^1 \cdot 8!-3 \cdot {3 \choose 2} \cdot {3 \choose 2}(2!)^2 \cdot 7!+{3 \choose 2} \cdot {3 \choose 2}\cdot {3 \choose 2} \cdot (2!)^3 \cdot 6!}\)
Najpierw wybieramy tylko jedną parę z trzech narodowości możliwości jest trzy po dwa, w każdej grupe narodowości, mnożymy przez trzy bo jedną parę można wybrać z trzech narodowości!
potem wybieramy już dwie pary na trzy możliwości(zawsze z dwcóh narodowości) i permutujemy,
na końcu wybieramy aż trzy pary z trzech narodowości i też permutujemy!
arek1357 pisze:
W rozpisce Norwimaja przestawienie np dwóch Chińczyków nie zmienia sytuacji a ja uważam, że powinno być:
\(\displaystyle{ p1,p2,p3,r1,r2,r3,c1,c2,c3}\)
a nie:
\(\displaystyle{ p,p,p,r,r,r,c,c,c}\)
Owszem, Norwimaj wypisał po prostu wszystkie możliwe ustawienia trzech grup trzyosobowych bez przypisywania im narodowości i osób, a następnie uwzględnił te różnice. Mnożenie przez \(\displaystyle{ (3!)^3}\) odpowiada właśnie za to, na co zwróciłeś uwagę, tj. przypisanie konkretnych osób w grupach.norwimaj pisze:
Następnie mnożymy wynik (\(\displaystyle{ 29}\)) przez \(\displaystyle{ 6}\) (o czym wcześniej pisałem) i przez \(\displaystyle{ (3!)^3}\) (o czym poprzednio zapomniałem).
Nie rozumiem.w tym ostatnim pomyśle różnice by były między:
\(\displaystyle{ p,p,r,p,r,r,c,c,c}\)
a:
\(\displaystyle{ p,r,p,p,r,r,c,c,c}\)
Sytuacja by się bardziej skomplikowała bo np para polaków i jeden polak to np dla rosjan dwa różne obiektu a dla polaków między sobą takie same!
Moim zdaniem przy takiej treści powinniśmy wszystkich rozróżniać. Gdybyśmy mieli nie rozróżniać ludzi, pytanie powinno raczej brzmieć: "Na ile sposobów możemy wybrać miejsca w rzędzie dla Polaków, Rosjan i Chińczyków, tak aby…?".Jeżeli nie rozróżniamy ludzi jednej narodowości to wtedy wynik wychodzi:
\(\displaystyle{ 107}\)
Nawiasem mówiąc, nie ma to jakiegoś szczególnego znaczenia dla trudności zadania, bo ona leży właśnie w zliczeniu wyborów tych miejsc, a rozróżnialność czy nierozróżnialność ludzi to tylko kwestia pomnożenia albo niepomnożenia tej liczby przez \(\displaystyle{ 6^3}\). Tak jak to było u Norwimaja.
Co do wyniku \(\displaystyle{ 107}\), to nie wiem, skąd się wziął i co może mieć wspólnego z tym, który podałeś na początku posta. Jeśli chodzi o wyniki moje i Norwimaja, to ciężka sprawa. Wyszło mi niemal dwukrotnie więcej. Metoda Norwimaja jest na pewno poprawna, tylko niełatwo sprawdzić, czy faktycznie wypisał wszystkie możliwości. Chyba jeszcze gorzej znaleźć błąd w moim długim, zawiłym rozumowaniu, choć jeśli ktoś go widzi, to będę wdzięczny.
Najlepszy byłby komputer, który wypisałby wszystko i policzył.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Zliczanie rozkładów grupy 9-osobowej
107 liczyłem przypadek gdy nie rozróżniamy ludzi tej samej narodowości!
A pierwszy wzór dla przypadków gdy rozróżniamy ludzi jednakowej narodowości.
A pierwszy wzór dla przypadków gdy rozróżniamy ludzi jednakowej narodowości.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Zliczanie rozkładów grupy 9-osobowej
Zastosuj ten mój wzór poprzez analogię na przypadek dwóch Polaków i dwóch Rosjan , mamy:
\(\displaystyle{ p_{1},p_{2},r_{1},r_{2}}\)
łatwo zauważyć ustawiając ich na piechotę, że możliwości , że nie stoją obok siebie dwóch z jednej narodowości jest osiem , a teraz zastosujmy moje rozumowanie poprzez analogię do mojego wzoru i otrzymamy (na to że stoją koło siebie):
\(\displaystyle{ 2 \cdot {2 \choose 2} \cdot 2! \cdot 3!- {2 \choose 2} \cdot {2 \choose 2} \cdot (2!)^2 \cdot 2!=16}\)
Czyli wychodzi osiem!
Pierwsza kombinacja to wybór dwóch Polaków z grupy dwóch Polaków lub dwóch Rosjan z grupy dwóch Rosjan(na dwa sposoby) i masz jedną parę i dwóch ludzi do permutowania między sobą razem trzy!
Potem wybierasz już dwóch Polaków z grupy dwóch Polaków i dwóch Rosjan z grupy Dwóch Rosjan (już tylko jeden sposób)
co daje dwie pary , które permutujesz również.
A na koniec stosujesz zasadą włączeń i wyłączeń czyli odejmujesz!
Sprawdza się to też przy dwóch Polakach, dwóch Rosjanach i dwóch Chińczykach!
To zadanie i to drugie z liczbami stojącymi koło siebie to bardzo podobne zadania do obu zastosowałem ten sam tok postępowania!
A teraz jak nie rozróżniasz ludzi tej samej narodowości otrzymujesz:
\(\displaystyle{ p,r,p,r}\)
lub:
\(\displaystyle{ r,p,r,p}\)
czyli dwie możliwości odpowiednik tego \(\displaystyle{ 107}\) możliwości dla dziewięciu ludzi o trzech narodowościach (przy nierozróżnianiu tej samej narodowości)!
\(\displaystyle{ p_{1},p_{2},r_{1},r_{2}}\)
łatwo zauważyć ustawiając ich na piechotę, że możliwości , że nie stoją obok siebie dwóch z jednej narodowości jest osiem , a teraz zastosujmy moje rozumowanie poprzez analogię do mojego wzoru i otrzymamy (na to że stoją koło siebie):
\(\displaystyle{ 2 \cdot {2 \choose 2} \cdot 2! \cdot 3!- {2 \choose 2} \cdot {2 \choose 2} \cdot (2!)^2 \cdot 2!=16}\)
Czyli wychodzi osiem!
Pierwsza kombinacja to wybór dwóch Polaków z grupy dwóch Polaków lub dwóch Rosjan z grupy dwóch Rosjan(na dwa sposoby) i masz jedną parę i dwóch ludzi do permutowania między sobą razem trzy!
Potem wybierasz już dwóch Polaków z grupy dwóch Polaków i dwóch Rosjan z grupy Dwóch Rosjan (już tylko jeden sposób)
co daje dwie pary , które permutujesz również.
A na koniec stosujesz zasadą włączeń i wyłączeń czyli odejmujesz!
Sprawdza się to też przy dwóch Polakach, dwóch Rosjanach i dwóch Chińczykach!
To zadanie i to drugie z liczbami stojącymi koło siebie to bardzo podobne zadania do obu zastosowałem ten sam tok postępowania!
A teraz jak nie rozróżniasz ludzi tej samej narodowości otrzymujesz:
\(\displaystyle{ p,r,p,r}\)
lub:
\(\displaystyle{ r,p,r,p}\)
czyli dwie możliwości odpowiednik tego \(\displaystyle{ 107}\) możliwości dla dziewięciu ludzi o trzech narodowościach (przy nierozróżnianiu tej samej narodowości)!