Permutacje z powtórzeniami

Gdy wśród ustawianych elementów są takie same, na przykład litery w wyrazie ANANAS, zamiana dwóch jednakowych elementów nie daje nowego ustawienia. Dlatego liczbę wszystkich ustawień n!n! dzielisz przez silnie liczb powtórzeń.

P(n1,n2,…,nk)=n!n1!⋅n2!⋅…⋅nk!P(n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}

na przykład litery wyrazu MAMA

4!2!⋅2!=244=6\displaystyle \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6

dwa rodzaje elementów

n!k!⋅(n−k)!=(nk)\displaystyle \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}

n1=…=nk=1n_1 = \ldots = n_k = 1 żaden element się nie powtarza

Pn=n!\displaystyle P_n = n!
n1,n2,…,nkn_1, n_2, \ldots, n_k to liczby elementów każdego rodzaju, a n=n1+n2+…+nkn = n_1 + n_2 + \ldots + n_k to liczba wszystkich elementów.

Skąd się bierze wzór na permutacje z powtórzeniami?

Weź litery wyrazu MAMA i na chwilę je rozróżnij: M1,A1,M2,A2M_1, A_1, M_2, A_2. Cztery różne litery można ustawić na 4!=244! = 24 sposoby, jak w permutacjach bez powtórzeń.

Gdy zetrzesz numerki, ustawienia M1A1M2A2M_1 A_1 M_2 A_2 i M2A1M1A2M_2 A_1 M_1 A_2 stają się tym samym ciągiem MAMA. Każdy ciąg powstaje z tylu ustawień, na ile sposobów można zamienić miejscami litery M między sobą (2!2!) i litery A między sobą (2!2!):

  1. 4!2!⋅2!=244=6\displaystyle \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6

Przy dowolnej liczbie rodzajów rozumujesz tak samo: dzielisz n!n! przez silnię liczby elementów każdego rodzaju.

Jak policzyć permutacje z powtórzeniami krok po kroku

Ile różnych ciągów liter można ułożyć ze wszystkich liter wyrazu ANANAS? Ciąg nie musi mieć sensu. Policzymy to w czterech krokach.

Zadanie ANANAS\text{ANANAS} n=6n = 6 6!=7206! = 720 P=60P = 60
  1. Policz elementy każdego rodzaju

    Wypisz każdą literę raz i zapisz, ile razy występuje. Liczby powtórzeń muszą się sumować do liczby wszystkich liter.

    Litery wyrazu ANANAS i liczby ich powtórzeń
    A\text{A} N\text{N} S\text{S}
    33 22 11
    1. n=3+2+1=6n = 3 + 2 + 1 = 6
  2. Policz ustawienia, jakby wszystkie litery były różne

    Sześć różnych liter można ustawić na 6!6! sposobów. To licznik ułamka.

    1. 6!=7206! = 720

    ni=1n_i = 1 wszystkie elementy różne

    Pn=n!\displaystyle P_n = n!

    Nie ma przez co dzielić, bo 1!=11! = 1. Na przykład LAMPY daje 5!=1205! = 120 ciągów.

    Więcej: permutacje bez powtórzeń

    k=2k = 2 dwa rodzaje elementów

    n!n1!⋅n2!=(nn1)\displaystyle \frac{n!}{n_1! \cdot n_2!} = \binom{n}{n_1}

    Wybierasz tylko miejsca dla elementów pierwszego rodzaju, reszta zapełnia się sama.

    Więcej: przykład 2

    k≥3k \geq 3 trzy rodzaje i więcej

    Nasze litery: 3, 2, 13,\ 2,\ 1

    Dzielisz przez silnię liczby powtórzeń każdego rodzaju, jak w następnym kroku.

  3. Podziel przez silnie liczb powtórzeń

    Trzy litery A można zamienić miejscami na 3!3! sposobów, a dwie litery N na 2!2! sposoby. Tyle razy każdy ciąg wystąpił w 720 ustawieniach.

    1. 3!⋅2!⋅1!=6⋅2⋅1=123! \cdot 2! \cdot 1! = 6 \cdot 2 \cdot 1 = 12
    2. P(3,2,1)=72012\displaystyle P(3, 2, 1) = \frac{720}{12}
    3. P(3,2,1)=60P(3, 2, 1) = 60
  4. Sprawdź wynik skracaniem

    Zamiast liczyć całe silnie, skróć ułamek: 6!=6⋅5⋅4⋅3!6! = 6 \cdot 5 \cdot 4 \cdot 3!, więc 3!3! się skraca.

    1. 6!3!⋅2!=6⋅5⋅42=1202=60\displaystyle \frac{6!}{3! \cdot 2!} = \frac{6 \cdot 5 \cdot 4}{2} = \frac{120}{2} = 60

    Odpowiedź: z liter wyrazu ANANAS można ułożyć 6060 różnych ciągów.

Więcej przykładów

Najpierw rozwiąż każde zadanie sam, a dopiero potem porównaj wynik z rozwiązaniem.

Przykład 1. Litery wyrazu KOKOS

Ile różnych ciągów liter można ułożyć ze wszystkich liter wyrazu KOKOS?

Przykład 2. Ścieżki na kratce

Pionek idzie po liniach kratki z lewego dolnego rogu prostokąta 4 na 3 kratki do prawego górnego rogu. Za każdym razem przesuwa się o jedną kratkę w prawo albo w górę. Ile jest takich dróg?

Przykład 3. Flagi na maszcie

Na maszcie wiesza się jedna pod drugą 10 flag: 4 czerwone, 3 białe i 3 niebieskie. Flagi tego samego koloru są jednakowe. Na ile sposobów można je powiesić?

Przykład 4. Cyfry z zerem

Ile liczb pięciocyfrowych można zapisać za pomocą cyfr 0, 0, 1, 1, 1, używając każdej z nich dokładnie raz?

Przykład 5. Litery wyrazu MATEMATYKA

Ile różnych ciągów liter można ułożyć ze wszystkich liter wyrazu MATEMATYKA?

Najczęstsze błędy

Unikaj ich w każdym zadaniu z permutacjami z powtórzeniami.

Przypadki szczególne

W tych sytuacjach wzór upraszcza się do czegoś, co już znasz.

Żaden element się nie powtarza n!1!⋅…⋅1!=n!\displaystyle \frac{n!}{1! \cdot \ldots \cdot 1!} = n!
Mianownik jest równy 1, więc zostają zwykłe permutacje bez powtórzeń.
Wszystkie elementy takie same n!n!=1\displaystyle \frac{n!}{n!} = 1
Cztery jednakowe litery A można ustawić tylko na jeden sposób: AAAA.
Dwa rodzaje elementów n!k!⋅(n−k)!=(nk)\displaystyle \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}
Trzy białe i dwie czarne kule w rzędzie dają (52)=10\binom{5}{2} = 10 ustawień, tyle, na ile sposobów można wybrać miejsca dla kul czarnych.
Jedna para jednakowych elementów n!2!=n!2\displaystyle \frac{n!}{2!} = \frac{n!}{2}
Wśród samych różnych elementów jedna para jednakowych zmniejsza liczbę ustawień o połowę: LAMPY daje 120 ciągów, a LAMPA 60.

Powiązane wzory

Pytania i odpowiedzi

Masz pytanie do tego wzoru albo przykładu? Zadaj je tutaj. Odpowiadają inni użytkownicy i redakcja.

Twoje pytanie

Szukaj wzoru

Wpisz nazwę wzoru. Polskie znaki są opcjonalne. Strzałkami wybierzesz wynik, Enter go otworzy.