Kombinacja z powtórzeniami
Z Wikipedii
Niniejszy artykuł jest częścią cyklu kombinatoryka.
 |
|
kombinacja bez powtórzeń wariacja bez powtórzeń liczby Stirlinga zasada szufladkowa Dirichleta |
| edytuj ten szablon |
Kombinacja z powtórzeniami (pojęcie matematyczne), to każdy multizbiór którego elementami są elementy jakiegoś zbioru skończonego. k-elementową kombinacją z powtórzeniami zbioru n-elementowego A nazywa się każdy k-elementowy multizbiór składający się z elementów zbioru A. W odróżnieniu do kombinacji bez powtórzeń tu elementy mogą się powtarzać.
Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wyraża się wzorem:
Przykład:
Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego A = {a, b, c, d} jest równa 
. Można je wymienić: {a, b}, {a, c}, {d, a}, {b, c}, {d, b}, {c, d}, {a,a}, {b,b}, {c,c}, {d,d}.
[edytuj] Pochodzenie wzoru
Jeżeli rozważymy zbiór 
, to każdą jego k-elementową kombinacje 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 współczynników
Ilość rozwiązań w takiego równania dla 
jest równa ilości k-elementowych kombinacji zbioru n + k − 1-elementowego, czyli 
[1]
