Kombinacja z powtórzeniami

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
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 | edytuj kod]

Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego jest równa Można je wymienić:

Kolejność nie ma tutaj znaczenia, równie dobrze można napisać jak i

Uzasadnienie wzoru na liczbę kombinacji[edytuj | edytuj kod]

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 | edytuj kod]

Przypisy[edytuj | edytuj kod]