Permutacje i silnia - ile jest ustawień? Permutacje z powtórzeniami

Klasa 3 liceum i technikum

Permutacja zbioru $n$-elementowego to każdy $n$-wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru, czyli każde ustawienie tych elementów w kolejności. Liczba permutacji zbioru $n$-elementowego wynosi $P_n = n!$ (czytamy: „en silnia”). Na przykład trzy litery $A, B, C$ można ustawić na $3! = 6$ sposobów: $ABC$, $ACB$, $BAC$, $BCA$, $CAB$, $CBA$.

Permutacja to szczególny przypadek wariacji bez powtórzeń: wybieramy po kolei wszystkie $n$ elementów, więc $k = n$.

Skąd się bierze n!

Przykład 1. Na ile sposobów można ustawić $5$ różnych książek na półce?

Pierwsze miejsce na półce możemy zająć dowolną z $5$ książek, drugie - jedną z $4$ pozostałych, trzecie - jedną z $3$, czwarte - jedną z $2$, a na ostatnie miejsce zostaje jedna książka. Z reguły mnożenia:

$5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.$

Taki iloczyn wszystkich liczb naturalnych od $1$ do $n$ nazywamy silnią i oznaczamy $n!$. Silnia rośnie bardzo szybko - już dla $10$ elementów ustawień jest ponad trzy miliony:

Dlaczego 0! = 1

Każda kolejna silnia powstaje z poprzedniej przez pomnożenie: $n! = n \cdot (n-1)!$, np. $5! = 5 \cdot 4! = 5 \cdot 24 = 120$. Jeśli ta zależność ma działać także dla $n = 1$, musi być

$1! = 1 \cdot 0!, \qquad \text{czyli} \qquad 0! = 1.$

Jest też uzasadnienie kombinatoryczne: zbiór pusty da się ustawić na dokładnie jeden sposób („nic nie robimy”). Dzięki umowie $0! = 1$ wzory $V_n^k = \tfrac{n!}{(n-k)!}$ i późniejszy symbol Newtona działają bez wyjątków także dla $k = n$.

Rachunki z silnią prawie zawsze polegają na skracaniu - większą silnię rozpisujemy do mniejszej:

$\frac{9!}{7!} = \frac{9 \cdot 8 \cdot 7!}{7!} = 72, \qquad \frac{(n+1)!}{(n-1)!} = \frac{(n+1) \cdot n \cdot (n-1)!}{(n-1)!} = n(n+1).$

Permutacje z warunkiem: sklejanie w blok

Przykład 2. Na półce stawiamy $7$ różnych książek, wśród nich $3$ tomy encyklopedii. Na ile sposobów można to zrobić, jeśli tomy encyklopedii mają stać obok siebie (w dowolnej kolejności)?

Krok 1. Sklejamy tomy w jeden blok. Blok encyklopedii traktujemy jak jedną dużą książkę. Ustawiamy więc $4$ zwykłe książki i $1$ blok, czyli $5$ obiektów: $5! = 120$ sposobów.

Krok 2. Ustawiamy tomy wewnątrz bloku. Trzy tomy mogą stać w bloku w dowolnej kolejności: $3! = 6$ sposobów.

Krok 3. Reguła mnożenia:

$5! \cdot 3! = 120 \cdot 6 = 720.$

Odpowiedź: $720$ sposobów. Bez warunku byłoby ich $7! = 5040$, więc ustawienia z tomami obok siebie stanowią $\tfrac{720}{5040} = \tfrac{1}{7}$ wszystkich.

Warunek „nie obok siebie” najprościej liczyć przez zdarzenie przeciwne: wszystkie ustawienia minus te, w których elementy stoją obok siebie. Więcej o takich strategiach w lekcji kombinatoryka - zadania różne.

Okrągły stół

Przykład 3. Na ile sposobów $5$ osób może usiąść przy okrągłym stole, jeśli liczy się tylko to, kto siedzi obok kogo (ustawienia różniące się obrotem uważamy za takie same)?

Gdyby krzesła były ponumerowane, ustawień byłoby $5! = 120$. Ale każde „okrągłe” ustawienie można obrócić na $5$ sposobów (każda osoba może siedzieć na krześle nr 1) i wszystkie te obroty dają to samo ustawienie przy stole. Każde ustawienie policzyliśmy więc $5$ razy:

$\frac{5!}{5} = 4! = 24.$

Inaczej: jedną osobę sadzamy gdziekolwiek - to ustala „punkt odniesienia” - a pozostałe $4$ osoby ustawiamy względem niej na $4!$ sposobów. Ogólnie przy okrągłym stole jest $(n-1)!$ ustawień.

Permutacje z powtórzeniami

Przykład 4. Ile różnych „słów” (niekoniecznie mających sens) można ułożyć, przestawiając litery słowa ANANAS?

Krok 1. Udajemy, że litery są różne. Ponumerujmy powtarzające się litery: $A_1 N_1 A_2 N_2 A_3 S$. Sześć różnych znaków można ustawić na $6! = 720$ sposobów.

Krok 2. Usuwamy numerki. Słowo $ANANAS$ odpowiada wielu ustawieniom z numerkami: trzy litery $A$ można między sobą przestawić na $3! = 6$ sposobów, dwie litery $N$ - na $2! = 2$ sposoby, a słowo się nie zmienia. Każde słowo policzyliśmy więc $3! \cdot 2! = 12$ razy:

$\overline{P}_6 = \frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{12} = 60.$

Odpowiedź: można ułożyć $60$ słów.

To samo rozumowanie działa dla liczb z powtarzającymi się cyframi: z cyfr $1, 1, 2, 2, 2$ ułożymy $\tfrac{5!}{2! \cdot 3!} = 10$ liczb pięciocyfrowych.

Typowe błędy

• Dzielenie tylko przez jedną grupę powtórzeń. W permutacjach z powtórzeniami dzielimy przez silnię każdej grupy powtórzeń. Dla ANANAS: przez $3!$ i $2!$, nie tylko przez $3!$.
• Zapomniane ustawienia wewnątrz bloku. Po sklejeniu elementów w blok trzeba jeszcze pomnożyć przez liczbę ustawień wewnątrz bloku ($3!$ w przykładzie 2).
• Okrągły stół liczony jak rząd. Przy stole $n$ osób to $(n-1)!$, a nie $n!$ ustawień - chyba że krzesła są ponumerowane albo rozróżnialne.
• Mylenie $0!$ z zerem. $0! = 1$, więc $\tfrac{5!}{0!} = 120$, a nie „dzielenie przez zero”.

Najczęstsze pytania

Co to jest permutacja? Permutacja zbioru $n$-elementowego to ustawienie wszystkich jego elementów w ciąg (w kolejności). Liczba permutacji wynosi $n!$, np. $4$ osoby można ustawić w kolejce na $4! = 24$ sposoby.

Ile wynosi 0 silnia?$0! = 1$. Wynika to z zależności $n! = n \cdot (n-1)!$ zastosowanej dla $n = 1$: $1! = 1 \cdot 0!$, a skoro $1! = 1$, to $0! = 1$.

Czym permutacja różni się od wariacji? W permutacji ustawiamy wszystkie $n$ elementów ($n!$ możliwości), a w wariacji bez powtórzeń tylko $k$ z nich ($\tfrac{n!}{(n-k)!}$). Permutacja to wariacja bez powtórzeń z $k = n$.

Jak obliczyć permutacje z powtórzeniami? Dzielimy $n!$ przez iloczyn silni liczebności powtarzających się grup: $\tfrac{n!}{k_1! \cdot k_2! \cdot \ldots}$. Np. słowo MAMA ma $\tfrac{4!}{2! \cdot 2!} = 6$ przestawień.

Ile wynosi 10 silnia?$10! = 3\,628\,800$. Kolejne wartości: $5! = 120$, $6! = 720$, $7! = 5040$, $8! = 40\,320$, $9! = 362\,880$.

Na ile sposobów można posadzić n osób przy okrągłym stole? Na $(n-1)!$ sposobów, jeśli ustawienia różniące się tylko obrotem uważamy za takie same. Dla $5$ osób jest to $4! = 24$.

Przećwicz

• Permutacje - zadania → - kolejka, osoby obok siebie i nie obok siebie, na przemian, okrągły stół, książki w blokach, liczby z przestawionych cyfr i anagramy (zadania z pełnym rozwiązaniem krok po kroku).
• Cały zestaw: kombinatoryka - zadania z rozwiązaniami →

Podsumowanie

• Permutacja to ustawienie wszystkich elementów w kolejności; jest ich $n!$.
• $n! = 1 \cdot 2 \cdot \ldots \cdot n$, $0! = 1$, a rachunki z silnią upraszczamy skracaniem ($n! = n \cdot (n-1)!$).
• Elementy, które mają stać obok siebie, sklejamy w blok i mnożymy przez ustawienia wewnątrz bloku.
• Przy okrągłym stole jest $(n-1)!$ ustawień.
• Permutacje z powtórzeniami: $\tfrac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_s!}$.

Zobacz też

• Kombinacje - następna lekcja: wybór bez kolejności i symbol Newtona.
• Wariacje - gdy ustawiamy tylko część elementów.
• Kombinatoryka - permutacje, wariacje, kombinacje - zestawienie wzorów.