Kombinacja z powtórzeniami
Z Wikipedii
Niniejszy artykuł jest częścią cyklu kombinatoryka.
 |
|
kombinacja bez powtórzeń wariacja bez powtórzeń liczby Bella zasada szufladkowa Dirichleta |
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:
Spis treści |
[edytuj] 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}, {a, d}, {b, c}, {b, d}, {c, d}, {a,a}, {b,b}, {c,c}, {d,d}. Kolejność nie ma tutaj znaczenia, równie dobrze można napisać {c,d}, jak {d,c}.
[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 bez powtórzeń zbioru n + k − 1-elementowego, czyli 
[1]
