kombinacje

Kombinacje to pojęcie w matematyce i teorii kombinatoryki odnoszące się do wyboru k elementów spośród n przy założeniu, że kolejność nie ma znaczenia. Przykładowo z zestawu {A, B, C, D} wybrać 2 elementy oznacza 6 możliwych kombinacji: AB, AC, AD, BC, BD, CD. W odróżnieniu od permutacji, gdzie liczy się kolejność, kombinacje liczą jedynie, które elementy tworzą podzbiór.

Liczba takich kombinacji nazywana jest n po k (n choose k) i zapisana nCk. Wyraża się wzorem nCk = n! / (k!(n−k)!). Warunki: 0 ≤ k ≤ n. W praktyce nCk jest liczbą sposobów wyboru k-elementowych podzbiorów z n-elementowego zbioru.

Jeśli akceptujemy powtórzenia, mówimy o kombinacjach z powtórzeniami; liczba takich kombinacji wynosi C(n+k−1, k). Inną interpretacją jest liczba wielomianów o stopniu k w dwumianie (1+x)^n według dwumianowej definicji.

Zastosowania obejmują szacowanie prawdopodobieństwa, projektowanie prób, analizę zestawów danych i generowanie podzbiorów w algorytmach. Pojęcie łączy się z permutacjami (gdzie kolejność ma znaczenie) oraz z trójkątem Pascala i dwumianem Newtona.

Zobacz także: permutacje, dwumian Newtona, trójkąt Pascala.