Definicja (Kombinacje z powtórzeniami)
Kombinacją z powtórzeniami nazywamy każdy \(k\) - elementowy multizbiór składający się z elementów zbioru \(n\) - elementowego
KOMBINACJE Z POWTÓRZENIAMI
MULTIZBIÓR - Jest to uogólnienie pojęcia zbioru; w odróżnieniu od klasycznych zbiorów, dane elementy mogą w nim występować wielokrotnie.
W zbiorach jak i w multizbiorach kolejność występowania 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 kombinacji z powtórzeniami)
Liczba wszystkich różnych \(k\) - elementowych kombinacji z powtórzeniami zbioru \(n\)- elementowego jest równa:
\[{\displaystyle \large \bar C_n^k}=\binom{n+k-1}{k}=\binom{n+k-1}{n-1}\] gdzie \(n,k\in \mathbb{N}^+ \)\(k\) - ilość elementów w utworzonym multizbiorze
\(n\) - wielkość zbioru wyjściowego
Przykład 1
Niech dany będzie zbiór : \(A=\{a, b\}\)
Utwórzmy wszystkie multizbiory dwuelementowe zbioru \(A\)
Nasz zbiór jest dwuelementowy, czyli : \(n=2\)
Multizbióry które mamy utworzyć mają być dwuelementowe, czyli : \(k=2\)
Ilość multizbiorów jakie możemy utworzyć obliczamy ze wzoru na kombinację z powtórzeniami \(\displaystyle \bar C_n^k=\binom{n+k-1}{k}=\binom{n+k-1}{n-1}\)
Obliczmy : \(\displaystyle \bar C_2^2=\binom{2+2-1}{2}=\binom{3}{2}=\frac{3!}{2!(3-2)!}=3\)
Otrzymaliśmy trzy multizbiory :\[\{a,a\}\ \{a,b\}\ \{b,b\}\]
Przykład 2
Niech dany będzie zbiór : \(A=\{a, b\}\)
Utwórzmy wszystkie multizbiory trzyelementowe zbioru \(A\)
Nasz zbiór jest dwuelementowy, czyli : \(n=2\)
Multizbióry które mamy utworzyć mają być trzyelementowe, czyli : \(k=3\)
Ilość multizbiorów jakie możemy utworzyć obliczamy ze wzoru na kombinację z powtórzeniami \(\displaystyle \bar C_n^k=\binom{n+k-1}{k}=\binom{n+k-1}{n-1}\)
Obliczmy : \(\displaystyle \bar C_2^3=\binom{2+3-1}{3}=\binom{4}{3}=\frac{4!}{3!(4-3)!}=4\)
Otrzymaliśmy cztery multizbiory :\[\{a,a,a\}\ \{a,a,b\}\ \{a,b,b\}\ \{b,b,b\}\]
Przykład 3
Niech dany będzie zbiór : \(A=\{a, b\}\)
Utwórzmy wszystkie multizbiory czteroelementowe zbioru \(A\)
Nasz zbiór jest dwuelementowy, czyli : \(n=2\)
Multizbióry które mamy utworzyć mają być czteroelementowe, czyli : \(k=4\)
Obliczmy : \(\displaystyle \bar C_2^4=\binom{2+4-1}{4}=\binom{5}{4}=\frac{5!}{4!(5-4)!}=5\)
Otrzymaliśmy pięć multizbiory :\[\{a,a,a,a\}\ \{a,a,a,b\}\ \{a,a,b,b\}\ \{a,b,b,b\}\ \{b,b,b,b\}\]
Cechy kombinacji z powtórzeniami
- Występuje określona liczba 𝑘 spośród 𝑛 elementów, przy czym elementy mogą się powtarzać.
- Kolejność występowania elementów nie jest istotna
- k jest dowolną liczbą naturalną.
→ dalej Różne zadania - kombinatoryka →
← wstecz: Kombinacje ←