Kombinacje z powtórzeniami
gdzie n to liczba typów (rodzajów) elementów, k to liczba wybieranych elementów, a elementy mogą się powtarzać
Czym są kombinacje z powtórzeniami?
Kombinacja z powtórzeniami to wybór k elementów spośród n dostępnych typów, w którym każdy typ może zostać wybrany wielokrotnie, a kolejność wyboru nie ma znaczenia. Liczy się jedynie to, ILE elementów każdego typu wybraliśmy, a nie w jakiej kolejności.
Wyobraź sobie, że stoisz przed ladą z n rodzajami ciastek i chcesz wybrać k sztuk. Możesz wziąć kilka ciastek tego samego rodzaju, a kolejność, w jakiej je wkładasz do torby, nie ma znaczenia. Dokładnie tak działają kombinacje z powtórzeniami. Wzór sprowadza się do symbolu Newtona, w którym n zastępujemy wyrażeniem n+k-1, a za k podstawiamy liczbę wybieranych elementów.
Elementy wzoru
Liczba kombinacji z powtórzeniami - ile jest sposobów wybrania k elementów z n typów, gdy elementy mogą się powtarzać i kolejność nie ma znaczenia.
Liczba dostępnych typów (rodzajów) elementów do wyboru. Musi to być liczba naturalna dodatnia (n ≥ 1). Każdy typ może być wybrany dowolną liczbę razy.
Liczba elementów, które wybieramy. Musi to być liczba naturalna (k ≥ 0). W odróżnieniu od kombinacji bez powtórzeń, k może być większe od n.
Symbol Newtona z argumentami n+k-1 i k. Wzór na kombinacje z powtórzeniami sprowadza się do zwykłych kombinacji bez powtórzeń z odpowiednio zmienionymi parametrami.
Interpretacja kombinacji z powtórzeniami
W odróżnieniu od kombinacji bez powtórzeń, tutaj k może przekraczać n. Skoro elementy mogą się powtarzać, nic nie stoi na przeszkodzie, by wybrać więcej sztuk niż jest typów. Na przykład z 3 rodzajów ciastek możemy wybrać 10 sztuk.
Kombinacje z powtórzeniami można interpretować metodą gwiazdek i kresek (stars and bars). Rozdzielamy k gwiazdek (wybranych elementów) za pomocą n-1 kresek (przegródek między typami). Liczba takich rozmieszczeń to C(n+k-1, k).
Liczba kombinacji z powtórzeniami równa się liczbie rozwiązań nieujemnych całkowitych równania x1 + x2 + ... + xn = k. Każde xi mówi, ile razy wybraliśmy i-ty typ elementu.
Wizualizacja
Poniższy wykres porównuje wartości kombinacji z powtórzeniami i kombinacji bez powtórzeń dla n = 5 typów i rosnącego k. Widać, że kombinacje z powtórzeniami rosną szybciej, bo dopuszczają wielokrotny wybór tego samego elementu, a k nie jest ograniczone przez n.
C(n+k-1, k) dla n = 5, rośnie bez ograniczeń
C(n, k) dla n = 5, zdefiniowane tylko dla k ≤ 5
Kiedy stosować kombinacje z powtórzeniami?
- Wybór produktów z wieloma sztukami - na ile sposobów można wybrać k sztuk owoców spośród n dostępnych rodzajów (np. 5 jabłek i 3 gruszki z oferty zawierającej 4 gatunki)
- Rozdzielanie identycznych przedmiotów - na ile sposobów można rozdzielić k identycznych kulek do n różnych pudełek
- Rzuty kostkami o tych samych wynikach - ile jest różnych zestawów wyników rzutu k kośćmi, gdy liczy się jedynie zestaw wartości (nie kolejność)
- Wielomiany i wyrażenia algebraiczne - ile jest jednomianów stopnia k o n zmiennych (wielomiany jednorodne)
Przykłady obliczeniowe
Przykład 1: Wybór lodów
Zadanie: W lodziarni są 4 smaki lodów. Na ile sposobów można wybrać 3 gałki, jeśli smaki mogą się powtarzać?
Rozwiązanie:
Mamy n = 4 typy (smaki) i wybieramy k = 3 elementy (gałki) z możliwością powtórzeń. Kolejność gałek nie ma znaczenia:
Obliczamy symbol Newtona:
Odpowiedź: Z 4 smaków lodów można wybrać 3 gałki na 20 różnych sposobów.
Przykład 2: Rozdzielanie piłek do pudełek
Zadanie: Na ile sposobów można rozłożyć 5 identycznych piłek do 3 różnych pudełek?
Rozwiązanie:
Piłki są identyczne, więc liczy się tylko ile piłek trafi do każdego pudełka. Mamy n = 3 typy (pudełka) i k = 5 elementów (piłek):
Korzystamy z symetrii: C(7,5) = C(7,2):
Odpowiedź: 5 identycznych piłek można rozłożyć do 3 pudełek na 21 sposobów.
Przykład 3: Zakup owoców
Zadanie: W sklepie są jabłka, gruszki i banany. Na ile sposobów można kupić 7 owoców?
Rozwiązanie:
Mamy n = 3 typy owoców i wybieramy k = 7 sztuk z powtórzeniami:
Obliczamy:
Odpowiedź: Z 3 rodzajów owoców można wybrać 7 sztuk na 36 sposobów.
Przykład 4: Rozwiązania równania
Zadanie: Ile jest rozwiązań całkowitych nieujemnych równania x + y + z = 4?
Rozwiązanie:
Szukamy liczby sposobów rozdzielenia k = 4 jednostek między n = 3 zmienne. To odpowiada kombinacji z powtórzeniami:
Obliczamy:
Odpowiedź: Równanie x + y + z = 4 ma 15 rozwiązań w liczbach całkowitych nieujemnych.
Częste błędy
Mylenie z kombinacjami bez powtórzeń
Kombinacje bez powtórzeń (C(n,k)) wymagają, by każdy element był wybrany co najwyżej raz, a k ≤ n. W kombinacjach z powtórzeniami elementy mogą się powtarzać, a k może być dowolnie duże. Użycie niewłaściwego wzoru daje zupełnie inny wynik.
Zamiana n i k we wzorze
We wzorze C(n+k-1, k) parametr n to liczba TYPÓW elementów, a k to liczba WYBIERANYCH sztuk. Zamiana tych wartości zmienia wynik. Zawsze ustal najpierw: ile jest rodzajów (n) i ile wybieramy (k).
Stosowanie wzoru, gdy kolejność ma znaczenie
Kombinacje z powtórzeniami dotyczą sytuacji, gdy kolejność NIE ma znaczenia. Jeśli kolejność jest istotna (np. kod PIN, hasło), należy użyć wariacji z powtórzeniami, a nie kombinacji.
Błąd w argumencie symbolu Newtona
Wzór to C(n+k-1, k), a nie C(n+k, k) ani C(n-1+k, k-1). Choć C(n+k-1, k) = C(n+k-1, n-1), należy poprawnie podstawić wartości. Częstym błędem jest pominięcie "-1" w argumencie.
Porady i wskazówki
Metoda gwiazdek i kresek: Przedstaw wybór jako k gwiazdek (*) rozdzielonych n-1 kreskami (|). Na przykład dla 3 typów i 4 elementów: **|*|* oznacza 2 szt. typu 1, 1 szt. typu 2 i 1 szt. typu 3. Liczba takich rozmieszeń to C(n+k-1, k).
Rozpoznawanie w zadaniach: Kombinacje z powtórzeniami stosujesz, gdy w treści pojawiają się zwroty: "smaki mogą się powtarzać", "identyczne przedmioty do różnych pojemników", "ile zestawów", "ile jest rozwiązań nieujemnych".
Symetria wzoru: C(n+k-1, k) = C(n+k-1, n-1). Gdy n-1 jest mniejsze od k, wygodniej obliczyć C(n+k-1, n-1), bo w liczniku pojawi się mniej czynników. Na przykład C(9,7) = C(9,2) = 36.
Porównanie z kombinacjami bez powtórzeń: Dla tych samych n i k (gdy k ≤ n) kombinacji z powtórzeniami jest zawsze więcej niż bez powtórzeń (lub tyle samo, gdy k = 0 lub k = 1). To logiczne - zezwalanie na powtórzenia daje więcej możliwości.
Przypadki szczególne
Wybór 0 elementów
Niezależnie od liczby typów, wybranie 0 elementów jest możliwe na dokładnie 1 sposób - nie wybierając niczego.
Jeden typ elementów (n = 1)
Gdy mamy do wyboru tylko 1 typ elementu, jest dokładnie 1 sposób wybrania k sztuk - bierzemy k identycznych elementów.
Wybór 1 elementu
Wybierając 1 element z n typów, mamy n możliwości - po jednej dla każdego typu. Wynik jest taki sam jak w kombinacjach bez powtórzeń.
Dwa typy elementów (n = 2)
Dla n = 2 typów wzór upraszcza się do k+1. Wybierając k elementów z 2 typów (np. A i B), mamy opcje: 0A+kB, 1A+(k-1)B, ..., kA+0B, czyli k+1 możliwości.
Przykład: Z 2 typów ciastek wybieramy 4 sztuki: C(2,4) = 5 sposobów (0+4, 1+3, 2+2, 3+1, 4+0).