Kombinacja z powtórzeniami

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


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 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ć.

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

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,...,k}→{1,...,n}.

Przykład[edytuj]

Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego A = {abcd} jest równa . Można je wymienić: {ab}, {ac}, {ad}, {bc}, {bd}, {cd}, {aa}, {bb}, {cc}, {dd}. Kolejność nie ma tutaj znaczenia, równie dobrze można napisać {cd}, jak i {dc}.

Uzasadnienie wzoru na liczbę kombinacji[edytuj]

Jeżeli rozważymy zbiór , 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 spełniały zależność:

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

oraz, po zamianie symboli,

Liczba rozwiązań takiej nierówności dla jest równa liczbie k-elementowych kombinacji bez powtórzeń zbioru (n+k–1)-elementowego, czyli [1].

Zobacz też[edytuj]

Przypisy