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:

${\bar{C}}_n^k=(\genfrac{}{}{0ex}{}{k+n-1}{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{array}{c}\frac{5!}{2!\cdot 3!}=\frac{120}{12}=10\end{array}.$ 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⩽a_1⩽a_2⩽\dots ⩽a_{k-1}⩽a_k⩽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 $(\genfrac{}{}{0ex}{}{n+k-1}{k})$.

Ograniczenie górne

Uwzględniając znane ograniczenie symbolu Newtona mamy

• ${\bar{C}}_n^k⩾{\left(\frac{k+n-1}{k}\right)}^k$
• ${\bar{C}}_n^k⩽\frac{(k+n-1{)}^k}{k!}$
• ${\bar{C}}_n^k<{(\frac{k+n-1}{k}\cdot e)}^k,$

Zobacz też

• teoria zbiorów