Kombinacja z powtórzeniami

Kombinacja z powtórzeniami – dowolny multizbiór złożony z elementów pewnego zbioru skończonego.

Jeśli zbiór jest n-elementowy, to każdy k-elementowy multizbiór jego elementów jest określany jako k-elementowa kombinacja z powtórzeniami zbioru n-elementowego. W odróżnieniu od kombinacji bez powtórzeń tu elementy mogą się powtarzać. Podobnie w odróżnieniu od kombinacji bez powtórzeń tu liczba $k$ może być dowolna, np. większa od $n.$

Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wyraża się wzorem:

${\overline {C}}_{n}^{k}={k+n-1 \choose k}=C(k+n-1,k)={\frac {(k+n-1)!}{k!(n-1)!}}.$

Każda k-elementowa kombinacja z powtórzeniami zbioru n-elementowego jest klasą abstrakcji wszystkich k-wyrazowych wariacji z powtórzeniami zbioru n-elementowego różniących się między sobą jedynie kolejnością elementów.

k-elementową kombinację z powtórzeniami zbioru n-elementowego można interpretować jako niemalejącą funkcję $\{1,\dots ,k\}\;\to \;\{1,\dots ,n\}.$ Równoważnie oznacza to skończony niemalejący ciąg długości $k,$ którego wyrazami są elementy zbioru $\{1,\dots ,n\}.$

Przykład

Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego $A=\{a,b,c,d\}$ jest równa ${\begin{matrix}{\frac {5!}{2!\cdot 3!}}={\frac {120}{12}}=10\end{matrix}}.$ Można je wymienić:

$\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,a\},\{b,b\},\{c,c\},\{d,d\}.$

Kolejność nie ma tutaj znaczenia, równie dobrze można napisać $\{c,d\},$ jak i $\{d,c\}.$

Uzasadnienie wzoru na liczbę kombinacji

Jeżeli rozważymy zbiór $\{1,2,\dots n\},$ to każdą jego k-elementową kombinację (obojętne czy z powtórzeniami, czy bez powtórzeń) da się uporządkować tak, by jej elementy $a_{1},a_{2},\dots a_{k}$ spełniały zależność:

$1\leqslant a_{1}\leqslant a_{2}\leqslant \dots \leqslant a_{k-1}\leqslant a_{k}\leqslant n,$

co w liczbach naturalnych (wraz z zerem) równoważne jest kolejno

$0<a_{1}<a_{2}+1<\dots <a_{k-1}+k-2<a_{k}+k-1<n+k$

oraz, po zamianie symboli,

$0<b_{1}<b_{2}<\dots <b_{k-1}<b_{k}<n+k.$

Liczba rozwiązań takiej nierówności dla $b_{1},\dots ,b_{k}\in \mathbb {N}$ jest równa liczbie k-elementowych kombinacji bez powtórzeń zbioru (n+k–1)-elementowego, czyli ${\tbinom {n+k-1}{k}}$.

Ograniczenie górne

Uwzględniając znane ograniczenie symbolu Newtona mamy

• ${\overline {C}}_{n}^{k}\geqslant \left({\frac {k+n-1}{k}}\right)^{k}$
• ${\overline {C}}_{n}^{k}\leqslant {\frac {(k+n-1)^{k}}{k!}}$
• ${\overline {C}}_{n}^{k}<\left({\frac {k+n-1}{k}}\cdot e\right)^{k},$

Zobacz też

• symbol Newtona
• teoria zbiorów