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 może być dowolna, np. większa od

Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wyraża się wzorem[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ę 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 [2].

Zobacz też

Uwagi

  1. Liczność multizbioru określa się jako liczbę jego elementów z uwzględnieniem liczby wystąpień (repetycji) każdego z tych elementów w multizbiorze.

Przypisy

  1. Kenneth A. Ross, Charles R. B. Wright: Matematyka dyskretna. Wydawnictwo Naukowe PWN, 2001, s. 300. ISBN 83-01-12129-7.
  2. Donald Knuth, The Art of Computer Programming, tom I.