Wariacje z powtórzeniami
gdzie n to liczba dostępnych elementów (typów), a k to długość tworzonego ciągu (liczba pozycji do obsadzenia)
Czym są wariacje z powtórzeniami?
Wariacja z powtórzeniami to uporządkowany wybór k elementów z n-elementowego zbioru, w którym każdy element może być wybrany dowolną liczbę razy. Innymi słowy, tworzymy ciąg k-elementowy, w którym na każdej pozycji możemy umieścić dowolny z n elementów - niezależnie od tego, czy został on już użyty na innej pozycji.
Wzór jest niezwykle prosty: nk. Na każdą z k pozycji mamy n możliwości wyboru, a ponieważ wybory są niezależne, stosujemy zasadę mnożenia: n · n · ... · n (k razy) = nk. Na przykład z 10 cyfr (0-9) można utworzyć 104 = 10 000 różnych 4-cyfrowych kodów PIN, bo na każdej z 4 pozycji może stać dowolna z 10 cyfr. Wariacje z powtórzeniami to jeden z najczęściej stosowanych wzorów kombinatorycznych w zadaniach maturalnych.
Elementy wzoru
Liczba wariacji z powtórzeniami - liczba wszystkich uporządkowanych ciągów k-elementowych, które można utworzyć z n dostępnych elementów, gdy powtórzenia są dozwolone.
Liczba dostępnych elementów (typów), z których tworzymy ciąg. Musi to być liczba naturalna dodatnia (n ≥ 1). Każdy element może być użyty wielokrotnie.
Długość tworzonego ciągu, czyli liczba pozycji do obsadzenia. Musi to być liczba naturalna (k ≥ 0). W odróżnieniu od wariacji bez powtórzeń, k może być większe od n.
Potęga n do k - iloczyn k czynników równych n. Na każdej z k pozycji mamy n niezależnych wyborów, co daje łącznie nk możliwości.
Interpretacja wariacji z powtórzeniami
Na każdej pozycji ciągu dokonujemy niezależnego wyboru spośród n elementów. Wybór na jednej pozycji nie wpływa na dostępność elementów na pozostałych pozycjach. Dlatego stosujemy zasadę mnożenia: n · n · ... · n = nk.
Tak jak w wariacjach bez powtórzeń, kolejność elementów jest istotna. Ciąg (A, B, C) to inna wariacja niż (C, B, A). Dodatkowo elementy mogą się powtarzać, więc (A, A, B) i (A, B, A) to również dwie różne wariacje.
W odróżnieniu od wariacji bez powtórzeń, k może być dowolnie duże - nawet większe od n. Z 2 elementów {0, 1} można tworzyć ciągi o dowolnej długości: ciąg 8-bitowy to 28 = 256 możliwości, mimo że n = 2.
Wizualizacja
Poniższy wykres pokazuje, jak rośnie liczba wariacji z powtórzeniami nk dla różnych wartości n (bazy) w zależności od k (wykładnika). Wzrost jest wykładniczy - im większa baza n, tym szybciej rosną wartości.
Ciągi binarne: 2, 4, 8, 16, 32, 64, ...
Kody cyfrowe: 10, 100, 1000, 10000, ...
Kiedy stosować wariacje z powtórzeniami?
- Kody PIN i hasła - ile różnych k-znakowych haseł można utworzyć z n dostępnych znaków, gdy znaki mogą się powtarzać (np. 4-cyfrowy PIN z cyfr 0-9)
- Numery rejestracyjne i tablice - ile jest możliwych numerów o k pozycjach, jeśli na każdej pozycji może stać jedna z n liter lub cyfr
- Rzuty monetą lub kostką - ile jest różnych wyników k rzutów monetą (n = 2) lub kostką (n = 6), gdy kolejność rzutów ma znaczenie
- Ciągi binarne i informatyka - ile różnych ciągów k-bitowych istnieje (n = 2, wynik to 2k), np. bajt to 28 = 256 wartości
Przykłady obliczeniowe
Przykład 1: Kod PIN
Zadanie: Ile różnych 4-cyfrowych kodów PIN można utworzyć, jeśli cyfry mogą się powtarzać?
Rozwiązanie:
Mamy n = 10 cyfr (0-9) i tworzymy ciąg o długości k = 4. Cyfry mogą się powtarzać, więc stosujemy wariacje z powtórzeniami:
Odpowiedź: Można utworzyć 10 000 różnych kodów PIN (od 0000 do 9999).
Przykład 2: Rzuty kostką
Zadanie: Ile jest różnych wyników 3 rzutów sześcienną kostką do gry?
Rozwiązanie:
Kostka ma n = 6 ścian, wykonujemy k = 3 rzuty. W każdym rzucie może wypaść dowolna z 6 wartości (powtórzenia dozwolone):
Odpowiedź: Trzy rzuty kostką mogą dać 216 różnych wyników (np. (1,1,1), (1,1,2), ..., (6,6,6)).
Przykład 3: Odpowiedzi w teście
Zadanie: Test zawiera 20 pytań, a każde ma 4 odpowiedzi do wyboru (A, B, C, D). Ile jest możliwych sposobów wypełnienia testu?
Rozwiązanie:
Mamy n = 4 odpowiedzi do wyboru i k = 20 pytań. Na każde pytanie wybieramy jedną z 4 odpowiedzi niezależnie:
Odpowiedź: Istnieje ponad bilion (ok. 1,1 · 1012) sposobów wypełnienia testu. Dlatego zgadywanie odpowiedzi daje znikome szanse na zaliczenie.
Przykład 4: Porównanie z wariacjami bez powtórzeń
Zadanie: Z cyfr {1, 2, 3, 4, 5} tworzymy 3-cyfrowe liczby. Ile ich jest, gdy (a) cyfry mogą się powtarzać, (b) cyfry nie mogą się powtarzać?
Rozwiązanie:
(a) Z powtórzeniami (n = 5, k = 3):
(b) Bez powtórzeń (n = 5, k = 3):
Odpowiedź: Z powtórzeniami mamy 125 liczb, bez powtórzeń - 60. Wariacje z powtórzeniami dają więcej możliwości, bo na każdej pozycji mamy pełen zestaw n elementów do wyboru.
Częste błędy
Mylenie z wariacjami bez powtórzeń
Wariacje z powtórzeniami (nk) stosujemy, gdy elementy mogą się powtarzać (np. PIN 1123). Wariacje bez powtórzeń (n!/(n-k)!) stosujemy, gdy każdy element może wystąpić co najwyżej raz. Kluczowe pytanie: czy ten sam element może pojawić się na wielu pozycjach?
Zamiana podstawy i wykładnika
We wzorze nk podstawą jest n (liczba dostępnych elementów), a wykładnikiem k (liczba pozycji). Na przykład 3-cyfrowy kod z cyfr 0-9 to 103 = 1000, a nie 310 = 59 049. Podstawa to "z czego wybieramy", wykładnik to "ile razy wybieramy".
Stosowanie silni zamiast potęgowania
Wariacje z powtórzeniami nie korzystają z silni - wzór to po prostu nk. Silnia pojawia się w permutacjach i wariacjach bez powtórzeń. Jeśli zadanie mówi o powtarzaniu elementów, stosuj potęgowanie, nie silnię.
Zapominanie o warunku kolejności
Wzór nk zakłada, że kolejność ma znaczenie. Jeśli kolejność nie ma znaczenia i elementy mogą się powtarzać, to jest to problem kombinacji z powtórzeniami, a nie wariacji. Na przykład: wybór 3 lodów z 5 smaków (mogą się powtarzać, kolejność nieistotna) to kombinacje z powtórzeniami.
Porady i wskazówki
Zasada mnożenia: Wzór nk wynika wprost z zasady mnożenia. Na pierwszą pozycję masz n wyborów, na drugą też n (bo powtórzenia dozwolone), na trzecią też n itd. Razem: n · n · ... · n = nk. To chyba najprostszy wzór w kombinatoryce.
Typowe zadania maturalne: Najczęściej pojawiają się kody (PIN, hasło, numer), rzuty kostką lub monetą, tablice rejestracyjne i testy wielokrotnego wyboru. Gdy w zadaniu mowa o tworzeniu ciągów, w których elementy mogą się powtarzać - to wariacje z powtórzeniami.
Porównanie z innymi wzorami: Permutacja (P = n!) - ustawiamy WSZYSTKO bez powtórzeń. Wariacja bez powtórzeń (V = n!/(n-k)!) - wybieramy CZĘŚĆ bez powtórzeń, kolejność ważna. Wariacja z powtórzeniami (nk) - wybieramy CZĘŚĆ z powtórzeniami, kolejność ważna. Kombinacja (C = n!/(k!(n-k)!)) - wybieramy CZĘŚĆ bez powtórzeń, kolejność nieważna.
Informatyka i system dwójkowy: Bajt (8 bitów) to 28 = 256 wartości (0-255). Kolor RGB to 2563 = 16 777 216 kolorów. Adres IPv4 to 2564 = ok. 4,3 mld adresów. Wszystko to wariacje z powtórzeniami.
Przypadki szczególne
Ciągi binarne (n = 2)
Gdy mamy tylko 2 elementy (np. 0 i 1, prawda/fałsz, orzeł/reszka), liczba ciągów k-elementowych to 2k. Jest to podstawa informatyki i rachunku prawdopodobieństwa.
Przykład: Wyniki 5 rzutów monetą: 25 = 32 ciągi (np. OOOOO, OOOOR, ..., RRRRR).
Jednopozycyjny ciąg (k = 1)
Gdy tworzymy ciąg o długości 1, mamy po prostu n możliwości - każdy element może zostać wybrany.
Ciąg o długości 0 (k = 0)
Ciąg pusty istnieje w dokładnie jednym wariancie - nie wybieramy niczego. Zgadza się to z konwencją n0 = 1 (dla n ≥ 1).
Podzbiory zbioru n-elementowego
Każdy element zbioru jest albo wybrany, albo nie (2 opcje). Dla n elementów to daje 2n podzbiorów - to wariacja z powtórzeniami dla k = n i n = 2.
Przykład: Zbiór {A, B, C} ma 23 = 8 podzbiorów (w tym pusty i cały zbiór).