Podstawy kombinatoryki
Kombinatoryka pomaga odpowiedzieć na pytanie: "Na ile sposobów mogę to zrobić?". Wszystko zależy od dwóch kluczowych pytań: czy ważna jest kolejność elementów oraz czy elementy mogą się powtarzać?
Gdy wybierasz elementy bez zwracania uwagi na ich kolejność, masz do czynienia z kombinacjami. Przykładowo, wybór 3 owoców z koszyka 10 różnych owoców to kombinacja. Nie ma znaczenia, czy najpierw weźmiesz jabłko, czy banan.
Jeśli kolejność jest istotna, mówisz o wariacjach (np. kod PIN) lub permutacjach (gdy używasz wszystkich elementów, np. ustawianie książek na półce).
Wskazówka: Żeby łatwo zapamiętać różnicę, pomyśl: kombinacje to jak zakupy (ważne co wybierasz, nieważna kolejność), wariacje to jak kod PIN (ważne co i w jakiej kolejności), a permutacje to jak ustawianie wszystkich książek na półce (używasz wszystkich elementów).
Wzory w kombinatoryce
Kombinacje bez powtórzeń to wybór k elementów z n-elementowego zbioru, bez znaczenia kolejności. Wzór to: Cnk=k!(n−k)!n!
Kombinacje z powtórzeniami pozwalają na wielokrotny wybór tego samego elementu. Wzór: Cnk=k!(n−1)!(n+k−1)!
Wariacje bez powtórzeń to uporządkowane ciągi k elementów wybranych z n-elementowego zbioru. Wzór: Vnk=(n−k)!n!
Wariacje z powtórzeniami pozwalają na wielokrotne użycie tych samych elementów. Wzór: Wnk=nk
Permutacje bez powtórzeń to wszystkie możliwe uporządkowania n elementów. Wzór: Pn=n!
Permutacje z powtórzeniami to uporządkowania, gdy niektóre elementy się powtarzają. Wzór: Pn′k=n1!n2!...nk!n!, gdzie n₁, n₂, ... to liczby powtórzeń elementów.