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^[a] 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 ${\displaystyle k}$ może być dowolna, np. większa od ${\displaystyle n.}$

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

${\displaystyle {\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ę ${\displaystyle \{1,\dots ,k\}\;\to \;\{1,\dots ,n\}.}$ Równoważnie oznacza to skończony niemalejący ciąg długości ${\displaystyle k,}$ którego wyrazami są elementy zbioru ${\displaystyle \{1,\dots ,n\}.}$

Przykład

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

${\displaystyle \{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ć ${\displaystyle \{c,d\},}$ jak i ${\displaystyle \{d,c\}.}$

Uzasadnienie wzoru na liczbę kombinacji

Jeżeli rozważymy zbiór ${\displaystyle \{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 ${\displaystyle a_{1},a_{2},\dots a_{k}}$ spełniały zależność:

${\displaystyle 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

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

oraz, po zamianie symboli,

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

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

Ograniczenie górne

Uwzględniając znane ograniczenie symbolu Newtona mamy

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

Zobacz też

• teoria zbiorów

Uwagi

Przypisy