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-elementowyLiczność multizbioru określa się jako liczbę jego elementów z uwzględnieniem liczby wystąpień (repetycji) każdego z tych elementów w multizbiorze. 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 może być dowolna, np. większa od
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ę Równoważnie oznacza to skończony niemalejący ciąg długości którego wyrazami są elementy zbioru
Przykład 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 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 Donald Knuth, The Art of Computer Programming, tom I..
Ograniczenie górne Uwzględniając znane ograniczenie symbolu Newtona mamy
Zobacz też teoria zbiorów
Uwagi
Przypisy
Kategoria:Kombinatoryka