szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 sty 2015, o 22:30 
Użytkownik

Posty: 33
Dzień dobry.

Próbuję zrozumieć jak powstał wzór na permutacje z powtórzeniami, lecz jakoś nie za bardzo mi to idzie.
No wzór jest taki: \frac{n!}{ k _{1}!  \cdot  k _{2}! \cdot ... \cdot k_{n}!  } , gdzie k_{n} - to ilość elementów w każdej grupie, zaś n to łączna ilość wszystkich elementów (suma elementów wszystkich grup). Ale jak to powstało.

Weźmy jako przykład zbiór 3 elementów {{A,A,B}} z tego otrzymamy rozpisując to jako drzewko takie permutacje:
Obrazek
I jak widać wśród permutacji (czyli przestawień) liter A mamy dwie powstałe grupy zbiory, które się powtarzają (ABA, ABA oraz AAB, AAB). Dlatego po jednym z tych powtórzeń należy skreślić.
Liczba permutacji z powtórzeniami wynosi tutaj \frac{3!}{ 2!  \cdot 1!  }= \frac{3\cdot2!}{2!\cdot1} = \frac{3}{1}=3. Elementy A tworzą 2-elementową grupę (z tego mamy 2!) oraz B tworzy 1-elementową grupę (i z tego mamy 1!).

Tak samo, gdy mamy zbiór 4 elementów {{a,a,b,b}} i z tego wszystkie możliwe permutacje ( jest ich 4!=24 ) to:
AABB, AABB, ABAB, ABBA, ABAB, ABBA, AABB,
AABB, ABAB, ABBA, ABAB, ABBA, BAAB, BABA, BAAB,
BABA, BBAA, BBAA, BAAB, BABA, BAAB, BABA, BBAA, BBAA

Widać, że tu także mamy powtórzenia. Mamy tutaj dwie grupy 2 elementowe (pierwsza składa się z dwóch elementów a, druga zaś z dwóch elementów b).

Ale jak wyjaśnić obliczanie wszystkich możliwych permutacji z powtórzeniami (czyli wzoru podanego na początku), bo jakoś nie wychodzi mi? Jak dojść do tego wzoru?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 sty 2015, o 22:55 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
jest to tak zwany Problem Mississipi
weźmy to właśnie słowo:
MISSISSIPPI
permutacji liter będzie \frac{11!}{1!4!4!2!}
chodzi o to, że wszystko mieszamy na 11! sposobów, wszystkie i możemy między sobą zamieszać na 4! sposobów i to nie robi nam różnicy, do tego wszystkie s na 4! sposobów itd.
Góra
Mężczyzna Offline
PostNapisane: 13 sty 2015, o 23:18 
Użytkownik

Posty: 33
No dobrze, ale jakie jest wyprowadzenie wzoru?
Jak do niego dojść?
Góra
Mężczyzna Offline
PostNapisane: 13 sty 2015, o 23:30 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
właśnie takie
wszystkiego jest n! ale jeśli w tym jest grupa k takich samych elementów to k elementów można permutować na k! sposobów. To znaczy, że wśród wszystkich n! permutacji k! jest identycznych
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Pytanie trochę algorytmiczne - suma elementów  Morfeo  4
 Pytanie co do drogi i cyklu eulera  bartek483  6
 Pytanie dotyczące stanów w Łańcuchu Markowa  Vince221  0
 permutacje, wariacje, kombinacje...  mat1989  23
 Permutacje, kombinacje?  kzn1990  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl