Permutacje z powtórzeniami
gdzie n = n1 + n2 + ... + nk to łączna liczba elementów, a ni to liczba powtórzeń i-tego rodzaju elementu
Czym są permutacje z powtórzeniami?
Permutacja z powtórzeniami to uporządkowanie n elementów, wśród których niektóre są identyczne. Gdyby wszystkie elementy były różne, mielibyśmy n! permutacji, ale ponieważ zamiana miejscami identycznych elementów nie tworzy nowego ustawienia, dzielimy przez silnie liczb powtórzeń poszczególnych rodzajów elementów.
Klasycznym przykładem jest liczenie anagramów wyrazu z powtarzającymi się literami. W wyrazie "MAMA" mamy 4 litery, ale M powtarza się 2 razy i A powtarza się 2 razy. Gdybyśmy rozróżniali kopie tych liter (M1A1M2A2), mielibyśmy 4! = 24 ustawień. Jednak ponieważ obie litery M są identyczne i obie litery A są identyczne, dzielimy przez 2! · 2! = 4, co daje 24/4 = 6 różnych anagramów.
Elementy wzoru
Łączna liczba wszystkich elementów do uporządkowania. Równa sumie n1 + n2 + ... + nk. Na przykład w wyrazie "KOKOS" n = 5.
Liczba różnych rodzajów (typów) elementów w zbiorze. Na przykład w wyrazie "KOKOS" mamy 3 rodzaje liter: K, O, S.
Liczba powtórzeń i-tego rodzaju elementu. W wyrazie "KOKOS": n1 = 2 (litera K), n2 = 2 (litera O), n3 = 1 (litera S).
Silnia łącznej liczby elementów - tyle byłoby permutacji, gdyby wszystkie elementy były różne. To licznik ułamka.
Interpretacja wzoru
Gdy każdy element występuje dokładnie raz (wszystkie ni = 1), mianownik wynosi 1! · 1! · ... · 1! = 1, więc wzór upraszcza się do n!. To zwykłe permutacje bez powtórzeń.
Im mniej powtórzeń, tym więcej permutacji. Pojedyncze powtórzenie jednego elementu (np. 2 takie same litery wśród 10 różnych) niewiele zmniejsza liczbę ustawień - dzielimy tylko przez 2.
Im więcej powtórzeń, tym mniej różnych permutacji. Skrajny przypadek: gdy wszystkie elementy są identyczne (n1 = n), istnieje tylko jedna permutacja, bo n!/n! = 1.
Wizualizacja
Poniższy wykres porównuje liczbę permutacji bez powtórzeń (n!) z liczbą permutacji z powtórzeniami dla różnych konfiguracji powtarzających się elementów. Widać, jak powtórzenia drastycznie zmniejszają liczbę możliwych ustawień.
Maksymalna liczba ustawień, gdy wszystkie elementy są różne
Mniejsza liczba ustawień z powodu identycznych elementów
Kiedy stosować permutacje z powtórzeniami?
- Anagramy wyrazów z powtarzającymi się literami - np. ile różnych ciągów liter można ułożyć z liter wyrazu "MATEMATYKA", "KOKOS" czy "ABRAKADABRA"
- Rozdział obiektów tego samego rodzaju - np. rozdzielenie identycznych piłek do ponumerowanych pudełek, rozmieszczenie kolorowych kulek w rzędzie
- Ścieżki na siatce - liczba najkrótszych dróg z jednego rogu siatki do drugiego, gdy poruszamy się tylko w prawo (P) i w górę (G)
- Kodowanie i ciągi znaków - ile różnych ciągów można utworzyć z określonej puli znaków, gdy niektóre znaki się powtarzają
Przykłady obliczeniowe
Przykład 1: Anagramy wyrazu "MAMA"
Zadanie: Ile różnych ciągów liter można utworzyć ze wszystkich liter wyrazu "MAMA"?
Rozwiązanie:
Wyraz "MAMA" ma 4 litery: M pojawia się 2 razy, A pojawia się 2 razy.
Podstawiamy do wzoru:
Odpowiedź: Z liter wyrazu "MAMA" można utworzyć 6 różnych ciągów: MAMA, MAAM, AMMA, AMAM, MMAA, AAMM.
Przykład 2: Anagramy wyrazu "KOKOS"
Zadanie: Ile różnych ciągów liter można utworzyć ze wszystkich liter wyrazu "KOKOS"?
Rozwiązanie:
Wyraz "KOKOS" ma 5 liter: K × 2, O × 2, S × 1.
Podstawiamy do wzoru:
Odpowiedź: Z liter wyrazu "KOKOS" można utworzyć 30 różnych ciągów liter.
Przykład 3: Ścieżki na siatce
Zadanie: Na ile sposobów można przejść z lewego dolnego rogu siatki 4×3 do prawego górnego rogu, poruszając się wyłącznie w prawo (P) lub w górę (G)?
Rozwiązanie:
Trzeba wykonać 4 kroki w prawo i 3 kroki w górę, łącznie 7 kroków. Szukamy liczby różnych ciągów złożonych z 4 liter P i 3 liter G:
Odpowiedź: Istnieje 35 najkrótszych ścieżek z lewego dolnego do prawego górnego rogu siatki 4×3.
Przykład 4: Rozstawienie flag
Zadanie: Na maszcie trzeba powiesić 10 flag: 4 czerwone, 3 białe i 3 niebieskie. Na ile sposobów można je uporządkować?
Rozwiązanie:
Mamy 10 flag, z czego: czerwone × 4, białe × 3, niebieskie × 3.
Obliczamy krok po kroku:
Odpowiedź: 10 flag (4 czerwone, 3 białe, 3 niebieskie) można rozwiesić na maszcie na 4 200 różnych sposobów.
Częste błędy
Zapominanie o dzieleniu przez silnie powtórzeń
Najczęstszy błąd to obliczenie samego n! bez dzielenia przez iloczyn silni powtarzających się elementów. Na przykład dla wyrazu "MAMA" błędna odpowiedź to 4! = 24 zamiast poprawnych 4!/(2!·2!) = 6.
Nieprawidłowe zliczanie powtórzeń
Trzeba dokładnie policzyć, ile razy każdy element się powtarza. W wyrazie "MATEMATYKA" (10 liter): M×2, A×3, T×2, E×1, Y×1, K×1. Pominięcie jednego powtórzenia daje zupełnie inny wynik.
Pominięcie elementów występujących raz
Elementy występujące jednokrotnie też powinny być uwzględnione (ni = 1), ale 1! = 1, więc nie wpływają na wynik. Nie trzeba ich umieszczać w mianowniku, ale trzeba je zliczyć w łącznej liczbie n.
Mylenie z kombinacjami
Wzór na permutacje z powtórzeniami n!/(n1!·n2!) wygląda podobnie do symbolu Newtona n!/(k!·(n-k)!). To nie przypadek - kombinacja to szczególny przypadek permutacji z powtórzeniami dla dwóch grup. Jednak zastosowanie jest inne.
Porady i wskazówki
Sprawdź sumę: Zawsze upewnij się, że n1 + n2 + ... + nk = n. Jeśli suma powtórzeń nie zgadza się z łączną liczbą elementów, gdzieś jest błąd w zliczaniu.
Skracanie ułamka: Zamiast liczyć pełne silnie, skracaj od razu. Na przykład 7!/(4!·3!) = (7·6·5)/(3·2·1) = 210/6 = 35. Wystarczy rozpisać te czynniki z n!, których nie ma w największej silni w mianowniku.
Rozpoznawanie w zadaniach: Permutacje z powtórzeniami pojawiają się, gdy w treści zadania mowa o uporządkowaniu elementów, z których niektóre są identyczne. Kluczowe słowa: "identyczne", "tego samego rodzaju", "nierozróżnialne", "jednokolorowe".
Związek z symbolem Newtona: Dla dwóch grup elementów (np. P razy "prawo" i G razy "góra") permutacja z powtórzeniami daje ten sam wynik co symbol Newtona: n!/(n1!·n2!) = C(n, n1).
Przypadki szczególne
Brak powtórzeń (wszystkie ni = 1)
Gdy żaden element się nie powtarza, mianownik wynosi 1, a wzór redukuje się do zwykłych permutacji.
Wszystkie elementy identyczne
Gdy mamy tylko jeden rodzaj elementu (n1 = n), istnieje tylko jedno uporządkowanie.
Przykład: Ciąg "AAAA" (4 identyczne litery) ma tylko 1 permutację.
Dwie grupy elementów
Dla dwóch rodzajów elementów (n1 + n2 = n) wzór upraszcza się do symbolu Newtona.
Przykład: 3 białe i 2 czarne kule w rzędzie: 5!/(3!·2!) = C(5,2) = 10.
Wielomian Newtona
Permutacje z powtórzeniami pojawiają się jako współczynniki wielomianowe w rozwinięciu potęgi sumy wielu składników.