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: \(\displaystyle{ \frac{n!}{ k _{1}! \cdot k _{2}! \cdot ... \cdot k_{n}! }}\) , gdzie \(\displaystyle{ k_{n}}\) - to ilość elementów w każdej grupie, zaś \(\displaystyle{ 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 {\(\displaystyle{ {A,A,B}}\)} z tego otrzymamy rozpisując to jako drzewko takie permutacje:
Kod: Zaznacz cały
http://wstaw.org/w/39iA/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 \(\displaystyle{ \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 {\(\displaystyle{ {a,a,b,b}}\)} i z tego wszystkie możliwe permutacje ( jest ich \(\displaystyle{ 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?
