Nieszablonowy problem (ustawianie elementów w ciąg)

[loonatic]

Mamy 19 elementów: 4 el. typu A, 4 el. typu B, 4 el. typu C, 3 el. typu D, 3 el. typu E oraz 1 el. typu F (czyli takie elementy: AAAABBBBCCCCDDDEEEF). Na ile sposobów można ustawić wszystkie te elementy (19) w ciąg (należy pamiętać, że mamy po kilka elementów każdego typu)?

Proszę o sugestie i porady dotyczące sposobu rozwiązania. Nie potrzebuję gotowego wyniku, gdyż chcę przy okazji rozw. tego zadania nauczyć się czegoś (rozw. zadania w wakacje z innego powodu nie miałoby sensu ).

[Dasio11]

Podpowiedź: najpierw ustaw wszystkie elementy typu A, na pozostałych miejscach - elementy typu B itd.

[loonatic]

tzn. 4A w 4 elementowy ciag? to bedzie bez sensu, bo przeciez w wypadku samych 4A jedyny poprawny ciag to AAAA...
chyba czegos nie rozumiem, albo cos zle rozumiem...

[Dasio11]

1. Rozmieść 4 A na 4 spośród 19 miejsc (zapisz ilość możliwości).
2. Rozmieść 4 B na 4 spośród pozostałych 15 miejsc (zapisz ilość możliwości)
3. Rozmieść 4 C na 4 spośród pozostałych 11 miejsc (zapisz ilość możliwości)
4. Rozmieść 3 D na 3 spośród pozostałych 7 miejsc (zapisz ilość możliwości)
5. Rozmieść 3 E na 3 spośród pozostałych 4 miejsc (zapisz ilość możliwości)
6. Rozmieść 1 F na ostatnim miejscu (ilość możliwości = 1)

I pomnóż to wszystko.

[loonatic]

Jejku... Ale ze mnie geniusz :/...
Dzięki za pomoc .

\(\displaystyle{ \frac{19!}{15!} \cdot \frac{15!}{11!} \cdot \frac{11!}{7!} \cdot \frac{7!}{4!} \cdot \frac{4!}{1!} = 19!}\)
Dobrze?

[Dasio11]

\(\displaystyle{ 19!}\) byłoby wtedy, gdyby każdy z elementów był rozróżnialny, a przecież mamy grupy identycznych elementów

Powinno być:

\(\displaystyle{ {19 \choose 4} \cdot {15 \choose 4} \cdot {11 \choose 4} \cdot {7 \choose 3} \cdot {4 \choose 3} \cdot {1 \choose 1}}\)

[alchemik]

Lub co jest konsekwencją co Dasio11 napisał:

\(\displaystyle{ \frac{19!}{4!4!4!3!3!1!}}\)

[loonatic]

Kurczę, no... Nigdy tego nie zrozumiem... Ta kombinatoryka mnie rozkłada :/... Nigdy nie wiem, który z wzorów zastosować...
Teraz jak patrzę, to logicznym się wydaje, że tutaj mam wybrać 4-elementowy podzbiór 19-elementowego zbioru, nawet miałem to zapisane (przy swoim liczeniu na kartce) w ten sposób: wybrać 4 z 19, nie powt. się, a zastosowałem permutację... Jakoś tak nie wiedzieć czemu...
Mimo, że mam zapisane wzory wraz z objaśnieniami (że np.permutacja to Każdy k-wyrazowy ciąg itp. itd.), to nie mogę jakoś tego wszystkiego połączyć w całość, żeby rozw. zadanie...
Nie chcę się tego kuć na pamięć, tylko jakoś tak zrozumieć, bo przecież wykucie nic mi nie da przy zadaniach innych typów... No chyba, że ktoś ma jakiś ciekawy i przydatny sposób na zapamiętanie, jak np. wierszyk od tabelki znaków funkcji trygonometrycznych (W 1. wszystkie są dodatnie, w 2. tylko sinus, w 3. tangens i cotangens, a w 4. cosinus) ;P.
Jakieś sugestie ?

[Przemas O'Black]

To jest permutacja, tyle że z powtórzeniami.

Zauważ, że masz 5 podstawowych rodzajów ustawień w kombinatoryce:
- pemutacja bez powtórzeń (wykorzystanie wszystkich elementów, istotna kolejność, wszystkie elementy są różne od siebie)
- permutacja z powtórzeniami (wykorzystanie wszystkich elementów, istotna kolejność, niektóre elementy są identyczne)
- wariacja bez powtórzeń (nie wykorzystanie wszystkich elementów, wykorzystanie przynajmniej jednego elementu, istotna kolejność, wszystkie elementy są różne od siebie)
- wariacja z powtórzeniami (nie wykorzystanie wszystkich elementów, wykorzystanie przynajmniej jednego elementu, istotna kolejność, niektóre elementy są identyczne)
- kombinacja (nieistotna kolejność).

Wybierasz do każdej okoliczności odpowiedni rodzaj i stosujesz odpowiedni do niego wzór.

[alchemik]

loonatic, Tak szczerze powiedziawszy to i mi nigdy te wzory nie szły, dlatego próbowałem sobie je jakoś wyprowadzić, oczywiscie sam dla siebie moimi łopatologicznymi argumentami, nie wiem czy to moje rozumowanie, które przedstawię niżej coś pomożę, ale można spróbować.

Aby nie operować na tak dużych liczbach, powiedzimy że mamy zbiór 6 elementów: 3 elementy typu A., 2 elementy typu B, jeden element typu C.

Pytanie :Na ile sposobów można ustawić wszystkie te elementy (6) w ciąg (należy pamiętać, że mamy po kilka elementów każdego typu.

Oznaczmy nasze elementy następująco: \(\displaystyle{ A1, A2, A3, B1, B2, C.}\)
Czyli będziemy rozróżniać elementy danego typu między sobą.

Na ile sposobów można ustawić wszystkie te elementy (6) w ciąg, rozróżniając wszystkie elementy?
\(\displaystyle{ 6!}\)
Teraz powróćmy do naszego głównego problemu, musimy przyjąć, że ustawienie \(\displaystyle{ A1A2A3}\) jest takie samo jak \(\displaystyle{ A1A3A2}\) czy też \(\displaystyle{ A2A3A1}\) czy też dowolne inne w obrębie tych trzech elementów.

Zatem w naszych \(\displaystyle{ 6!}\) różnych ustawień musimy usunąć takie w których inne elementy \(\displaystyle{ (B1,B2,C)}\) stoją na danych miejscach, a ustawienie \(\displaystyle{ A1,A2,A3}\) się zmienia.

Przykład niech będzie takie ustawienie że, na przykład B2 stoi na drugim miejscu, C na trzecim, B1 na piątym:
_B2C_B1_, w naszych 6! były następujące ustawienia:
\(\displaystyle{ A1B2CA2B1A3 \\
A1B2CA3B1A2\\
A2B2CA1B1A3\\
A2B2CA3B1A1\\
A3B2CA1B1A2\\
A3B2CA2B1A1}\)
A nas nie obchodzi w jakiej kolejności stało \(\displaystyle{ A1,A2,A3}\), a ich ustawień między sobą było \(\displaystyle{ 3!}\)

Zatem dla każdego ustawienia \(\displaystyle{ B1B2 i C}\) na swoich miejscach mamy \(\displaystyle{ 3!}\) (ilość możliwych ciągów składających się z elementół typu A) więcej możliwości, niż byśmy chcieli.
Zatem musimy podzielić \(\displaystyle{ 6!}\) przez \(\displaystyle{ 3!}\),

Analogiczny dowód przeprowadzamy dla B. teraz mamy elementy \(\displaystyle{ AAAB1B2C}\).
Na razie wywnioskowaliśmy że wszystkich możliwych ciągów z powyższych elementów jest \(\displaystyle{ \frac{6!}{3!}}\)

Ale teraz mamy nie rozróżniać elementy typu B.
Zatem ustawienie \(\displaystyle{ AB2CAB1A}\) i \(\displaystyle{ AB1CAB2A}\) traktujemy jako takie same, a ile jest ustawień takich samych dla danego ustawienia elementów \(\displaystyle{ AAA}\) i \(\displaystyle{ C}\)? \(\displaystyle{ 2!}\)
Zatem musimy podzielić przez \(\displaystyle{ 2!}\) naszpoprzedni wynik, dlatego ostateczny wynik dla tego przypadku wynosi:

\(\displaystyle{ \frac{6!}{3!2!}}\)
Mam nadzieję, że zrozumiesz, a jeśli zrozumiałaś to teraz wiesz dlaczego napisałem wynik w takiej a nie innej formie kilka postów wyżej.

[loonatic]

Przemas O'Black i alchemik - dzięki za wyjaśnienia . Myślę, że teraz już trochę lepiej to rozumiem.