Kombinacja z powtórzeniami

Z Wikipedii

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja 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ń

Ten szablon: pokaż • dyskusja • edytuj

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 1 Przykład 2 Pochodzenie wzoru 3 Przypisy 4 Zobacz też

[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]

[edytuj] Przypisy

1. ↑ Donald Knuth, The Art of Computer Programming, tom I

[edytuj] Zobacz też

• przegląd zagadnień z zakresu matematyki
• symbol Newtona
• teoria zbiorów