Definicja (Permutacje z powtórzeniami)
Permutacją z powtórzeniami multizbioru \(n\)-elementowego nazywamy każdy \(n\)-wyrazowy ciąg utworzony ze wszystkich elementów tego multizbioru.
PERMUTACJE Z POWTÓRZENIAMI
MULTIZBIÓR -jest to uogólnienie pojęcia zbioru, w odróżnieniu od klasycznych zbiorów dane elementy mogą występować wielokrotnie.
W zbiorach, podobnie jak w multizbiorach, kolejność elementów jest dowolna.
Przykłady
\(\{1, 2, 3\}\,\,\{1, 2, 2, 3\}\) - mamy tu dwa identyczne zbiory ale zarazem są to dwa różne multizbiory
\(\{1, 2, 3\}\,\,\{1, 1, 2, 3\}\,\,\{1, 1, 1, 2, 3\}\) - tu mamy trzy identyczne zbiory ale zarazem trzy różne multizbiory
\(\{1, 1, 2, 3\}\,\,\{1, 2, 2, 3\}\) - te multizbiory są różne
\(\{1, 2, 2, 3\}\,\,\{2, 2, 1, 3\}\) - za to te multizbiory są identyczne
Twierdzenie (Liczba permutacji z powtórzeniami)
Liczba wszystkich możliwych permutacji z powtórzeniami multizbioru \(n\) - elementowego jest równa:
\[\displaystyle \large P_{n}^{n_1,n_2,\cdots, n_k}=\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}\] gdzie \(n\) z indeksem dolnym \(n_1, n_2, ... , n_k\) oznacza krotność występowania danego elementu w multizbirze, przy czym różnych elementów jest \(k\) ponadto \(n_1+ n_2+ ... + n_k=n\) oraz \(n,k \in \mathbb{N}^{+}\)Przykład 1
Niech dany będzie multizbiór : \(A=\{a, a, b\}\)
Utwórzmy wszystkie ciągi utworzone z multizbioru \(A\)
Nasz multizbiór jest trzyelementowy czyli : \(n=3\)
Element \(a\) występuje dwa razy zatem \(n_1=2\) natomiast element \(b\) występuje raz zatem \(n_2=1\)
Powinno zachodzić : \(n_1+n_2=n\) u nas \(2+1=3\)
Permutacji z powtórzeniami obliczamy zgodnie ze wzorem : \(\displaystyle p_{n}^{n_1,n_2,\cdots, n_k}=\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}\)
\(\displaystyle p_{3}^{2,1}=\frac{3!}{2!\cdot 1!}=\frac{1\cdot 2 \cdot 3}{1 \cdot 2}=3\)
Otrzymaliśmy następujące trzy ciągi
\[(a, a, b) (a, b, a) (b, a, a)\]Przykład 2
Niech dany będzie multizbiór : \(A=\{a, a, b, b\}\)
Utwórzmy wszystkie ciągi utworzone z multizbioru \(A\)
Nasz multizbiór jest czteroelementowy czyli : \(n=4\)
Element \(a\) występuje dwa razy zatem \(n_1=2\) element \(b\) występuje też dwa raz \(n_2=2\)
Powinno zachodzić : \(n_1+n_2=n\) u nas \(2+2=4\)
Liczba permutacji z powtórzeniami wynosi: : \(\displaystyle p_{4}^{2,2}=\frac{4!}{2!\cdot 2!}=\frac{1\cdot 2 \cdot 3 \cdot 4}{1 \cdot 2 \cdot1 \cdot2}=6\)
Otrzymaliśmy sześć ciągów :
\[(a, a, b, b) (b, b, a, a) (a, b, b, a)\] \[(b, a, a, b)(a, b, a, b)(b, a, b, a)\]Przykład 3
Niech dany będzie multizbiór : \(A=\{a, a, b, c\}\)
Utwórzmy wszystkie ciągi utworzone z multizbioru \(A\)
Nasz multizbiór jest czteroelementowy czyli : \(n=4\)
Elementy występują \(a\) - dwa razy \(n_1=2\) , \(b\) - jeden raz \(n_2=1\) , \(c\) - jeden raz \(n_3=1\)
\(n_1+n_2+n_3=n\) u nas \(2+1+1=4\)
Liczba permutacji z powtórzeniami wynosi:: \(\displaystyle p_{4}^{2,1,1}=\frac{4!}{2!\cdot 1!\cdot1!}=\frac{1\cdot 2 \cdot 3 \cdot 4}{1 \cdot 2 \cdot1 \cdot1}=12\)
Otrzymaliśmy dwanaście ciągów :
\[(a, a, b, c) (a, a, c, b) (a, b, c, a)\] \[(a, c, b, a)(b, c, a, a)(c, b, a, a)\] \[(a, b, a, c) (a, c, a, b) (b, a, c, a)\] \[(c, a, b, a)(b, a, a, c)(c, a, a, b)\]Przykład 4
Niech dany będzie multizbiór : \(A=\{a, a, a, b, b\}\)
Utwórzmy wszystkie ciągi utworzone z multizbioru \(A\)
Nasz multizbiór jest pięcioelementowy czyli : \(n=5\)
Elementy występują \(a\) - trzy razy \(n_1=3\) , \(b\) - dwa razy \(n_2=2\)
\(n_1+n_2=n\) u nas \(3+2=5\)
Liczba permutacji z powtórzeniami wynosi:: \(\displaystyle p_{5}^{3,2}=\frac{5!}{3!\cdot 2!}=10\)
Otrzymaliśmy dziesięć ciągów :
\[(a, a, a, b, b) (a, a, b, a, b) (a, a, b, b, a)\] \[(a, b, a, a, b)(a, b, a, b, a)(a, b, b, a, a)\] \[(b, a, a, a, b) (b, a, a, b, a) (b, a, b, a, a)\] \[(b, b, a, a, a)\]Cechy permutacji z powtórzeniami
- w permutacji z powtórzeniami występują wszystkie elementy danego multizbioru.
- istotna jest kolejność występowania elementów.
PERMUTACJE Z POWTÓRZENIAMI - ZADANIA
Zadanie 2
Ile różnych liczb 7 cyfrowych można ułożyć z multizbioru \(\{2, 2, 2, 4, 4, 6, 6 \}\) Zadanie 3
Ile różnych liczb 5 cyfrowych można utworzyć jeśli iloczyn jej składników równa się 8 Zadanie 4
Ile 6-cyfrowych liczb parzystych można ułożyć, korzystając z multizbioru \(\{1, 1, 2, 2, 4, 4\}\)?