Kombinacje bez powtórzeń
gdzie n to liczba wszystkich elementów zbioru, k to liczba wybieranych elementów, a n! oznacza silnię liczby n
Czym są kombinacje bez powtórzeń?
Kombinacja bez powtórzeń to wybór k elementów z n-elementowego zbioru, w którym kolejność wybranych elementów nie ma znaczenia. Liczy się jedynie to, KTÓRE elementy zostały wybrane, a nie w jakiej kolejności. Na przykład wybór osób {Anna, Bartek, Celina} to ta sama kombinacja co {Celina, Anna, Bartek} - w obu przypadkach wybrano te same trzy osoby.
Wzór na kombinacje korzysta z symbolu Newtona (czytamy "n po k" lub "n nad k"), oznaczanego jako (n k). Jest to jedno z najważniejszych pojęć kombinatoryki, które znajduje zastosowanie w rachunku prawdopodobieństwa, statystyce, dwumianie Newtona, a także w codziennych sytuacjach - od losowań po tworzenie zespołów.
Elementy wzoru
Symbol Newtona - liczba kombinacji k-elementowych ze zbioru n-elementowego. Czytamy "n po k" lub "n nad k". Wynik jest zawsze liczbą naturalną.
Liczba wszystkich dostępnych elementów zbioru, z którego dokonujemy wyboru. Musi to być liczba naturalna (n ≥ 0) i zachodzić warunek n ≥ k.
Liczba elementów, które wybieramy ze zbioru. Musi to być liczba naturalna spełniająca warunek 0 ≤ k ≤ n.
Silnia liczby n, czyli iloczyn wszystkich liczb naturalnych od 1 do n. Na przykład 5! = 120. Z definicji 0! = 1.
Interpretacja kombinacji
W kombinacjach liczy się tylko to, KTÓRE elementy wybrano, nie w jakiej kolejności. Dlatego {A, B, C} i {C, A, B} to ta sama kombinacja. To odróżnia kombinacje od wariacji, gdzie kolejność ma znaczenie.
Kombinacja to wariacja podzielona przez liczbę permutacji wybranych elementów. Skoro k elementów można ustawić na k! sposobów, to C(n,k) = V(n,k) / k! = n! / (k!(n-k)!). Dzielimy, bo wariacje liczą każdą kolejność osobno.
Zachodzi równość C(n,k) = C(n, n-k). Wybór k elementów ze zbioru jest równoważny z pozostawieniem n-k elementów. Na przykład C(10,3) = C(10,7) = 120. Ta właściwość pozwala skracać obliczenia.
Wizualizacja
Poniższy wykres przedstawia wartości symbolu Newtona C(n,k) dla ustalonego n = 10 i kolejnych wartości k od 0 do 10. Widoczna jest charakterystyczna symetria - wartości rosną do maksimum w środku, a następnie maleją symetrycznie.
Wartości symbolu Newtona dla n = 10 i k od 0 do 10
C(10,k) = C(10, 10-k), np. C(10,3) = C(10,7) = 120
Kiedy stosować kombinacje bez powtórzeń?
- Wybór zespołu lub komisji - na ile sposobów można wybrać k osób z grupy n kandydatów, gdy nie przydzielamy im funkcji (kolejność nie ma znaczenia)
- Losowanie kul, kart, numerów - ile jest różnych wyników losowania k obiektów z n dostępnych, np. losowanie 6 z 49 w Lotto
- Tworzenie podzbiorów - ile jest k-elementowych podzbiorów danego zbioru n-elementowego
- Rachunek prawdopodobieństwa - obliczanie liczby zdarzeń sprzyjających w zadaniach typu "ile jest sposobów wybrania..."
Przykłady obliczeniowe
Przykład 1: Wybór drużyny
Zadanie: Na ile sposobów można wybrać 3 osoby z grupy 8 kandydatów do drużyny?
Rozwiązanie:
Kolejność wyboru nie ma znaczenia - liczy się tylko skład zespołu. Stosujemy wzór na kombinacje:
Rozwijamy 8! do momentu pojawienia się 5! i skracamy:
Odpowiedź: Z 8 kandydatów można wybrać 3-osobową drużynę na 56 różnych sposobów.
Przykład 2: Losowanie w Lotto
Zadanie: W grze Lotto losujemy 6 liczb z 49. Ile jest możliwych wyników losowania?
Rozwiązanie:
Kolejność wylosowanych liczb nie ma znaczenia, więc stosujemy kombinacje:
Obliczamy licznik i mianownik:
Odpowiedź: W Lotto jest 13 983 816 możliwych wyników, co oznacza, że szansa trafienia szóstki to mniej niż 1 na 14 milionów.
Przykład 3: Przekątne wielokąta
Zadanie: Ile przekątnych ma sześciokąt wypukły?
Rozwiązanie:
Każdy odcinek łączący dwa wierzchołki to albo bok, albo przekątna. Liczba wszystkich takich odcinków to C(6,2), a boków jest 6:
Odejmujemy liczbę boków:
Odpowiedź: Sześciokąt wypukły ma 9 przekątnych.
Przykład 4: Wykorzystanie symetrii
Zadanie: Oblicz wartość C(12, 10).
Rozwiązanie:
Korzystamy z właściwości symetrii: C(n, k) = C(n, n-k). Łatwiej obliczyć C(12, 2) niż C(12, 10):
Odpowiedź: C(12, 10) = 66. Dzięki symetrii wystarczyło obliczyć prosty ułamek zamiast operować dużymi silniami.
Częste błędy
Mylenie kombinacji z wariacjami
W kombinacjach kolejność NIE ma znaczenia, a w wariacjach MA znaczenie. Jeśli wybierasz 3 osoby do drużyny - to kombinacja. Jeśli wybierasz prezesa, wiceprezesa i sekretarza - to wariacja, bo ta sama trójka osób na różnych stanowiskach to inny wynik.
Zamiana n i k we wzorze
We wzorze C(n,k) parametr n oznacza liczbę WSZYSTKICH elementów (z czego wybieramy), a k to liczba WYBIERANYCH elementów. Zamiana tych wartości daje zupełnie inny (i zwykle bezsensowny) wynik. Zawsze sprawdzaj: n ≥ k.
Nieprawidłowe skracanie silni
Częstym błędem jest próba skracania n!/(k! · (n-k)!) w sposób n/(k · (n-k)). Silnia w liczniku i mianowniku to NIE zwykłe mnożenie. Należy rozwinąć n! i skrócić z większą silnią w mianowniku.
Zapominanie o warunku k ≤ n
Nie można wybrać więcej elementów, niż jest dostępnych. Wyrażenie C(5, 8) nie ma sensu - nie da się wybrać 8 elementów z 5. Zawsze sprawdzaj, czy k ≤ n, zanim zaczniesz obliczenia.
Porady i wskazówki
Wykorzystuj symetrię: Gdy k jest bliskie n, zamień C(n,k) na C(n, n-k). Na przykład C(20,17) = C(20,3) = (20 · 19 · 18) / (3 · 2 · 1) = 1 140. Znacznie prostsze niż rozwijanie C(20,17) wprost.
Szybkie obliczanie: C(n,k) to iloczyn k kolejnych liczb od n w dół, podzielony przez k!. Na przykład C(8,3) = (8 · 7 · 6) / (3 · 2 · 1) = 336/6 = 56. Nie musisz obliczać pełnych silni.
Słowa kluczowe w zadaniach: Kombinacje rozpoznasz po zwrotach: "na ile sposobów można wybrać", "ile jest podzbiorów", "ile jest zestawów", "wylosować k z n". Kluczowy jest brak przypisania ról lub kolejności wybranym elementom.
Trójkąt Pascala: Wartości C(n,k) tworzą trójkąt Pascala, w którym każda liczba jest sumą dwóch liczb nad nią: C(n,k) = C(n-1,k-1) + C(n-1,k). Dla małych n i k możesz szybko odczytać wynik z trójkąta zamiast liczyć.
Przypadki szczególne
Wybór zbioru pustego: C(n, 0) = 1
Ze zbioru n-elementowego można wybrać 0 elementów na dokładnie 1 sposób - nie wybierając niczego. Jest to zbiór pusty.
Wybór całego zbioru: C(n, n) = 1
Ze zbioru n-elementowego można wybrać wszystkie n elementów na dokładnie 1 sposób - biorąc cały zbiór.
Wybór jednego elementu: C(n, 1) = n
Ze zbioru n-elementowego można wybrać 1 element na n sposobów - po prostu każdy z elementów osobno.
Suma wszystkich kombinacji: 2n
Suma wszystkich symboli Newtona dla ustalonego n daje liczbę wszystkich podzbiorów zbioru n-elementowego, czyli 2n.
Przykład: Dla n = 4: C(4,0) + C(4,1) + C(4,2) + C(4,3) + C(4,4) = 1 + 4 + 6 + 4 + 1 = 16 = 24.