Zliczanie rozkładów grupy 9-osobowej

[szachimat]

Ciężko się wczytać w to wszystko co napisaliście, a naprawdę ciekawi mnie ile naprawdę powinno wyjść przy założeniu, że ludzie tej samej narodowości są:
a) nierozróżnialni
b) rozróżnialni (to właściwie powinno być brane pod uwagę, jeżeli nie ma żadnych założeń)

Może jakiś programik komputerowy pomógłby w podaniu właściwej odpowiedzi.

[Majeskas]

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

Wszystko to się zgadza i dlatego problem będzie prosty, dopóki wszystkie grupy, niezależnie od ich liczby, są \(\displaystyle{ 2}\)-elementowe. Wtedy jest to klasyczne zadanie na zasadę włączeń i wyłączeń i nie ma problemu, rozwiązuje się je tak, jak to zrobiłeś wyżej. Ale w momencie, w którym pojawiają się grupy \(\displaystyle{ 3}\)-elementowe, a nas interesują takie ustawienia, w których wystąpi jakakolwiek grupa \(\displaystyle{ 2}\)-elementowa, pojawia się problem. Dlatego wynik

\(\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!

jest z pewnością błędny. Weźmy ustawienie \(\displaystyle{ r_1,c_1,p_1,p_2,p_3,c_2,r_3,c_3}\). Zalicza się ono do tych, w których jedna para stoi obok siebie, zatem powinno być policzone w ramach ustawień pierwszego rodzaju, których wyszło \(\displaystyle{ 3 \cdot {3 \choose 2} \cdot (2!)^1 \cdot 8!}\). Przyjmując ten sposób liczenia, można je otrzymać w następujących krokach
- decydujemy, że Polacy mają się znaleźć obok siebie;
- decydujemy, że obok siebie staną Polacy \(\displaystyle{ p_1}\) i \(\displaystyle{ p_2}\);
- decydujemy, że staną w kolejności \(\displaystyle{ p_1,p_2}\);
- elementy \(\displaystyle{ (p_1,p_2),p_3,r_1,r_2,r_3,c_1,c_2,c_3}\) ustawiamy w kolejności \(\displaystyle{ r_1,c_1,p_1,p_2,p_3,c_2,r_3,c_3}\).

A oto inne kroki, które możemy wykonać w ramach takiego podejścia, otrzymując to samo ustawienie
- decydujemy, że Polacy mają się znaleźć obok siebie;
- decydujemy, że obok siebie staną Polacy \(\displaystyle{ p_2}\) i \(\displaystyle{ p_3}\);
- decydujemy, że staną w kolejności \(\displaystyle{ p_2,p_3}\);
- elementy \(\displaystyle{ (p_2,p_3),p_1,r_1,r_2,r_3,c_1,c_2,c_3}\) ustawiamy w kolejności \(\displaystyle{ r_1,c_1,p_1,p_2,p_3,c_2,r_3,c_3}\).

Przy takim sposobie liczenia ustawienia, w których będą się pojawiały trójki osób z tej samej grupy, zostaną policzone wielokrotnie. I dlatego właśnie moje rozwiązanie z początku tematu, również oparte na zasadzie włączeń i wyłączeń, jest długie i żmudne, a nie krótkie i eleganckie. Taki jest koszt obejścia tego problemu. Zresztą napisałem o tym na końcu.

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.

Co do tego, co napisał Szachimat, powtórzę się: Nie ma istotnego w sensie trudności znaczenia, czy rozróżniamy ludzi na swoich miejscach, czy nie. Weźmy dowolne ustawienie narodowości, np. \(\displaystyle{ p,r,r,p,c,c,r,p,c}\). Polakom odpowiada zbiór miejsc \(\displaystyle{ \left\{ 1,4,8\right\}}\), Rosjanom \(\displaystyle{ \left\{2,3,7 \right\}}\), Chińczykom \(\displaystyle{ \left\{5,6,9 \right\}}\). Każdej permutacji któregokolwiek z tych zbiorów miejsc odpowiada przypisanie miejsc konkretnym osobom, dlatego zależność jest prosta:

liczba ustawień, w których rozróżniamy ludzi=\(\displaystyle{ (3!)^3\cdot}\) liczba ustawień, w których ich nie rozróżniamy.

[arek1357]

Czyli nie wziąłem pod uwagę trójek tych samych narodowości stojących koło siebie!

[szachimat]

Nic nie wnoszę zmieniając litery, ale nie chcę się pomylić przepisując moje warianty.
Na początek zajmuję się przykładowo nierozróżnialnymi "klockami" AAABBBCCC.

Przypadek 1
Trzy pierwsze miejsca zajmują klocki wg schematu: ABA, ACA, BAB, BCB, CAC, CBC (6 takich układów)
Dla dowolnej z w/w trójki (np. ABA) kolejne układy na pozostałych sześciu miejscach są następujące:
1) _ _ _ BCACBC
2) _ _ _ BCBCAC
3) _ _ _ CABCBC
4) _ _ _ CACBCB
5) _ _ _ CBACBC
6) _ _ _ CBCABC
7) _ _ _ CBCACB
8) _ _ _ CBCBAC
9) _ _ _ CBCBCA
Czyli dołożyłem na wszystkie możliwe sposoby jedną literę A, dwie B i trzy C.
A zatem ilość wszystkich możliwości przypadku 1 wynosi \(\displaystyle{ 6 \cdot 9=54}\)

Przypadek 2
Trzy pierwsze miejsca zajmują klocki wg schematu: ABC, ACB, BAC, BCA, CAB, CBA (6 układów)
Dla dowolnej z w/w trójki (np. ABC) kolejne układy na pozostałych sześciu miejscach są następujące:
a) jako czwarta litera A i piąta B
_ _ _ ABACBC
_ _ _ ABCABC
_ _ _ ABCACB
_ _ _ ABCBAC
_ _ _ ABCBCA
b) czwarta A, piąta C (5 analogicznych układów)
c) czwarta B, piąta A (jw)
d) czwarta B, piąta C (jw)
Czyli dołożyłem na wszystkie możliwe sposoby dwie litery A, dwie B i dwie C.
A zatem ilość wszystkich możliwości przypadku 2 wynosi \(\displaystyle{ 6 \cdot 20=120}\)

Tak więc wszystkich układów, w których klocki są nierozróżnialne jest 174.

Ponieważ każdy z tych układów, w przypadku klocków rozróżnialnych, można przestawić na
\(\displaystyle{ {3\choose 1} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot {3\choose 1} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot {3\choose 1} \cdot {2 \choose 1} \cdot {1 \choose 1}=216}\) sposobów, więc ilość wszystkich możliwych wyników jest równa \(\displaystyle{ 174 \cdot 216=37584}\)

[Majeskas]

Wynik jest zgodny z rozważaniami Norwimaja, który wypisał układy liter bez przypisania im nacji. Każdemu układowi możemy przypisać nacje na \(\displaystyle{ 6}\) sposobów.
\(\displaystyle{ 174:6=29}\) - tak jak u Norwimaja.
Skoro dwie osoby doszły niezależnie od siebie do takiego samego wyniku, to to już coś - pewnie jest dobry. Ciekawe, gdzie są w takim razie błędy w moim rozumowaniu. Dzięki za wkład.

[arek1357]

Nie zauważyłem w układzie szachimata może ze względu na późną porę takich układów jak:

\(\displaystyle{ ABCBCBACA}\)

oraz:

\(\displaystyle{ ACABCBCBA}\)

[szachimat]

Nie zauważyłem w układzie szachimata może ze względu na późną porę takich układów jak:

\(\displaystyle{ ABCBCBACA}\)

oraz:

\(\displaystyle{ ACABCBCBA}\)

Ad 1
Przypadek 2d

Ad 2
Przypadek 1 (jedna z sześciu możliwości wymienionych na początku)

[arek1357]

Mam jeszcze jedno pytanie do przypadku nierozróżnialnych czy symetria osiowa zmniejsza o połowę ilość rozwiązań!

[szachimat]

Mam jeszcze jedno pytanie do przypadku nierozróżnialnych czy symetria osiowa zmniejsza o połowę ilość rozwiązań!

Nie bardzo rozumiem pytania. Czy chodzi o układy z elementów typu AABB (jest ich 6) na taką symetrię ABBA i BAAB (2 możliwości).

[arek1357]

właśnie nie wiem jak widzicie symetrię typu:

\(\displaystyle{ ABCBACA}\)

\(\displaystyle{ ACABCBA}\)

To jest np symetryczne jak ja liczyłem nierozróżnialne to pomijałem tego typu układy!

[szachimat]

właśnie nie wiem jak widzicie symetrię typu:

\(\displaystyle{ ABCBACA}\)

\(\displaystyle{ ACABCBA}\)

To jest np symetryczne jak ja liczyłem nierozróżnialne to pomijałem tego typu układy!

Nie możemy pomijać, bo istotne czy element stoi na pierwszym, czy na ostatnim miejscu.
Nie wiem, czy cię dobrze rozumiem, ale z tego przykładu dałbym kontrprzykład rzutu dwiema monetami:
OR
RO
To też jest wg twojego rozumowania symetryczne.